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

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

How to apply Lean - Kanban for your business

This is the topic of Scrum Breakfast meetup this time, speaker: Ms. Phuong Bui - Technical Project Manager of YOOSE Pte. Ltd. http://www.meetup.com/Scrum-Breakfast-Vietnam-Agile-and-Scrum-Meetup/events/230313727/ Lean comes from Lean manufacturing is a method that focuses on elimination of wastes. In other words, this is a set of principles for archiving the quality, speed and customer alignment. The first time I knew about the term "Lean" is  from the book Software Craftsmanship . Sandro recommends if we want to transform our pet projects into a real business, we should get familiar with Lean Startup concepts. In this talk, Ms. Phuong pointed out some major wastes includes information (ex: unclear requirements), processes (ex: waiting), physical environment and people. Knowing what the problems should be the best way to eliminate them. The difference between  Single item flow and Batch processing is the second main point; and it is the Lean's idea. Batch pr...
Post a Comment
Read more

The HelloWorld example of JSF 2.2 with Myfaces

I just did by myself create a very simple app "HelloWorld" of JSF 2.2 with a concrete implementation Myfaces that we can use it later on for our further JSF trying out. I attached the source code link at the end part. Just follow these steps below: 1. Create a Maven project in Eclipse (Kepler) with a simple Java web application archetype "maven-archetype-webapp". Maven should be the best choice for managing the dependencies , so far. JSF is a web framework that is the reason why I chose the mentioned archetype for my example. 2. Import dependencies for JSF implementation - Myfaces (v2.2.10) into file pom.xml . The following code that is easy to find from  http://mvnrepository.com/  with key words "myfaces". <dependency> <groupId>org.apache.myfaces.core</groupId> <artifactId>myfaces-api</artifactId> <version>2.2.10</version> </dependency> <dependency> <groupId>org.apache.myfaces.core<...
Post a Comment
Read more

Applying pipeline “tensorflow_embedding” of Rasa NLU

According to this nice article , there was a new pipeline released using a different approach from the standard one ( spacy_sklearn ). I wanted to give it a try to see whether it can help with improving bot’s accuracy. After applying done, I gave an evaluation of “tensorflow_embedding”. It seemed to work better a bit. For example, I defined intents “greet” and “goodbye” with some following messages in my training data. ## intent:greet - Hey! How are you? - Hi! How can I help you? - Good to see you! - Nice to see you! - Hi - Hello - Hi there ## intent:goodbye - Bye - Bye Bye - See you later - Take care - Peace In order to play around with Rasa NLU, I created a project here . You can have a look at this change from this pull request . Yay! When I entered message “hi bot”, then bot with “tensorflow_embedding” could detect intent “greet” with better confidence scores rather than bot with “spacy_sklearn”. The following are responses after executing curl -X POST loc...
Post a Comment
Read more

Sharing a virtualenv across several Python projects using Pipenv

There is a standard library for all projects in Python. However, several projects don’t always have the same dependencies all the time. That is where virtual environments come to play. You can follow this official document to use two separated tools  virtualenv and pip to  fulfill that need. My preferred alternative is to use pipenv . Pipenv is easy to use and convenient. The following are my steps to make a shared virtualenv for my all projects which requires the same dependencies. Step 1. Create an isolated virtualenv. python -m venv my-shared-env Step 2. Create a symbolic link to the created virtualenv. cd project_1 ln -s ~/.local/share/virtualenvs/my-shared-env .venv I have encountered the following issue at step 1. FileNotFoundError: [Errno 2] No such file or directory: '{my_project_path}/.venv/bin/pip': '{my_project_path}/.venv/bin/pip' The root cause was I tried to create virtualenv by running pipenv install and renaming the generated virtualenv to ...
Post a Comment
Read more