Skip to main content

Coding Exercise, Episode 1


I have received the following exercise from an interviewer, he didn't give the name of the problem. Honestly, I have no idea how to solve this problem even I have tried to read it three times before. Since I used to be a person who always tells myself "I am not the one good at algorithms", but giving up something too soon which I feel that I didn't spend enough effort to overcome is not my way. Then, I have sticked on it for 24 hours.

According to the given image on the problem, I tried to get more clues by searching. Thanks to Google, I found a similar problem on Hackerrank (attached link below). My target here was trying my best to just understand the problem and was trying to solve it accordingly by the Editorial on Hackerrank. Due to this circumstance, it turns me to love solving algorithms from now on (laugh). Check it out!

Problem

You are given a very organized square of size N (1-based index) and a list of S commands

The ith command will follow the format (a[i], b[i], d[i]) and will be executed as:

For every elements inside the inner-square whose top-left corner located at (a[i], b[i]) and bottom-right corner located at (a[i] + d[i], b[i] + d[i]) will rotate 90 degree clockwise. And the ith inner-square always contains (i + 1)th inner-square

E.g. If the input square with size N = 7 and command (2, 3, 3), the execution will be (image):

After executed S commands, you will then be asked to do L queries to determine the final location given the initial value w[i].
E.g. With the above example, the final position of 25 will be (4, 4) - its initial location was (4, 5)

Input format and constraints

- Line 1: integer N - size of the square (N <= 10^7)
- Line 2: integer S - number of commands (S <= 10^5)
- S subsequent lines: S commands with format (a[i], b[i], d[i]) with constraints
1 <= a[i], b[i] and 0 <= d[i] < N
a[i-1] <= a[i] and a[i] + d[i] <= a[i - 1] + d[i - 1]
b[i-1] <= b[i] and b[i] + b[i] <= b[i - 1] + b[i - 1]
The next line will contains integer L - number of queries (L <= 10^5)
Each subsequent line ask for the final position of a number w[i] (0 <= w[i] < N^2)

Here is one input example

7
2
1 2 4
2 3 3
2
11
24

Here is the output

4 4
2 5

Solution 

(with my commenting on the code)


Reference
[1]. https://www.hackerrank.com/challenges/king-richards-knights
Labels:

Comments

  1. UnknownJanuary 21, 2018 at 4:40 AM

    Holy shit, this is exactly the task that LenderRate has offered me back then xD.

    ReplyDelete

Post a Comment

Popular posts from this blog

Selenium - Override javascript functions to ignore downloading process

I have got an issue with downloading process on IE 8. This browser blocks my automatic-download functionality on my app so that I could not work with my test case any more after that. In my case, I didn't care about the file is downloaded or not, I just focus on the result after downloading process finished successfully. Therefore, I found a solution to ignore this process so that I can work normally. I use Primefaces, here is the remote command to trigger the download process <p:remoteCommand name="cmdGenerateDocument" actionListener="#{logic.onGenerateDocument}" update="xrflDocumentCreationPanel" oncomplete="clickDownloadButton();"/> The following is my test case: @Test public void shouldUpdateStep6ToWarningIfStep1IsValidAfterFinished(){ MainPage mainPage = new MainPage(); waitForLoading(mainPage.getDriver()); EmployeeDetailPage empDetailPage = new EmployeeDetailPage(); waitForLoading(empDetailPage.getDriver()); e...
Post a Comment
Read more

What the heck is Meteor DDP?

I was using Meteor for my messenger project. I was so curious about the real time connection. I wanted to know how exactly this mechanism works. In this post, I will go through the DDP Specification, an overview of WebSocket, and a simple demo about how to subscribe a publication of Rocket.Chat (containing a DDP server) from an external webpage. At a glance, I knew that Meteor invented a protocol called DDP which uses for handling real time connection. So then, what is DDP? "DDP (Distributed Data Protocol) is the stateful WebSocket protocol that Meteor uses to communicate between the client and the server." [1] All right! Why does DDP matter? "DDP is a standard way to solve the biggest problem facing client-side JavaScript developers: querying a server-side database, sending the results down to the client, and then pushing changes to the client whenever anything changes in the database" . [2] In order to understand deeply the protocol, I decided ...
Post a Comment
Read more

Only allow input number value with autoNumeric.js

autoNumeric is a jQuery plugin that automatically formats currency and numbers as you type on form inputs. I used autoNumeric 1.9.21 for demo code. 1. Dowload autoNumeric.js file from  https://github.com/BobKnothe/autoNumeric 2. Import to project <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script> <script type="text/javascript" src="js/autoNumeric.js"></script> 3. Define a function to use it <script type="text/javascript"> /* only number is accepted */ function txtNumberOnly_Mask() { var inputOrgNumber = $("#numberTxt"); inputOrgNumber.each(function() { $(this).autoNumeric({ aSep : '', aDec: '.', vMin : '0.00' }); }); } </script> 4. Call the function by event <form> <input type="text" value="" id="numberTxt"/>(only number) </form> <script ty...
Post a Comment
Read more

A Template for Software Engineering Standards

Software engineering standard template A well-structured standard acts as a blueprint that guides engineers in their daily tasks and long-term goals. Below, I will outline a template for creating a comprehensive software engineering standard. Header The header serves as the document's identifier. It contains the following: Authors : The people who have contributed to the creation of the standard. Created Date : The date when the document was initially created. Version : The version of the standard. It is typically updated with significant changes. Status : The current status of the document, whether it's in draft, in-review, or official. Next Review Date : The date when the standard will be reviewed for relevancy and accuracy. Table of Contents A table of contents provides an overview of what the document contains, making it easier for readers to navigate through the document. Body The body of the standard comprises: Values : The core beliefs that guide the decision-maki...
Post a Comment
Read more

Installing NGINX on macOS

I have heard of a lot of NGINX recently. One of them was it can help for security issues; for sure, it much be more. It so happens that our team has got a ton of user stories from a security audit. It's time to delve into it. What is NGINX? In order to get a basic idea and have some fun , I've just picked some available posts from my favorite Vietnamese blogger communities as below: https://kipalog.com/posts/Cau-hinh-nginx-co-ban---Phan-1 https://viblo.asia/hoang.thi.tuan.dung/posts/ZabG912QGzY6 NGINX (pronounce: Engine-X) is a web server (comparing to IIS, Apache). It can be used as a reverse proxy ( this is what I need for security issues with configuration ), load balancer and more. How to get started? I found the below path for learning NGINX by googling "learn nginx": https://www.quora.com/What-are-some-good-online-resources-to-learn-Nginx In this post, I only went first step. This is installing NGINX on macOS and taking a first look at the confi...
Post a Comment
Read more