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

JSF 2 - Dynamically manipulating the component tree with system events

Let's suppose we want to modify the metadata (attributes)  of elements such as render , requried , maxlength but we do not define in JSF tags. The manipulating components can be conducted in Drools  files, for example. How could we do? I think that is what we need to change something of component tree during JSF life-cycle. JSF supports event handling throughout the JSF life-cycle. In this post, I use two events: postAddToView for scanning components tree and preRenderView for manipulating the meta of components before rendering to GUI. I modified my own project from previous post for this example. This is my first further JSF trying out with the project as I said before. :) We define the tags f:event below the form - a container component of the components which we want to work on. The valid values for the attribute type for f:event can be found from tag library document  of JSF 2. <!DOCTYPE html> <html xmlns="http://www.w3.org/1999/xhtml" x...
Post a Comment
Read more

Make simple music program with beep(freq, duration) with Pascal

Pascal is my first programing language when I have studied in high school. It was really exciting for me. :) The Pascal programming language was created by Niklaus Wirth in 1970. It was named after Blaise Pascal, a famous French Mathematician. It was made as a language to teach programming and to be reliable and efficient. Pascal has since become more than just an academic language and is now used commercially . I tried to make a simple music program by using Lazarus IDE on MS Window 7, 64-bit. It frustrated me a few times how difficulty to use Sound command to make a sound. Sound did not work on my compiler and my platform anymore. So far, I just could use beep(freq, duration) from window unit to implement my work. Here is my code. ;) program mysong; uses Windows, crt; const C: Integer = 512; { x = A * EXP(LN(2)/12)} C_: Integer = 542; D: Integer = 574; D_: Integer = 608; E: Integer = 644; F: Integer = 682; F_: Integer = 723; G: Integer = ...
Post a Comment
Read more

AngularJS - Build a custom validation directive for using multiple emails in textarea

AngularJS already supports the built-in validation with text input with type email. Something simple likes the following: <input name="input" ng-model="email.text" required="" type="email" /> <span class="error" ng-show="myForm.input.$error.email"> Not valid email!</span> However, I used a text area and I wanted to enter some email addresses that's saparated by a comma (,). I had a short research and it looked like AngualarJS has not supported this functionality so far. Therefore, I needed to build a custom directive that I could add my own validation functions. My validation was done only on client side, so I used the $validators object. Note that, there is the $asyncValidators object which handles asynchronous validation, such as making an $http request to the backend. This is just my implementation on my project. In order to understand that, I supposed you already had experiences with ...
Post a Comment
Read more

Books Read in 2022

My bookshelf Technical - Operating System: Three Easy Pieces. Andrea Arpaci-Dusseau, Remzi Arpaci-Dusseau. - The Effective Engineer. Edmond Lau. - English Grammar in Use. Raymond Murphy - Mythical Man-Month, The: Essays on Software Engineering. Brooks Jr., Frederick P.  - Peopleware: Productive Projects and Teams (3rd edition). Tom DeMarco, Timothy Lister. - A Philosophy of Software Design. John Ousterhout. - Modern Computer Architecture and Organization: Learn x86, ARM, and RISC-V architectures and the design of smartphones, PCs, and cloud servers. Jim Ledin. Thought Provoking - Đúng Việc. Giản Tư Trung. - A Brief History of Time. Stephen Hawking. - Một đời như kẻ tìm đường. Phan Văn Trường. - Một đời thương thuyết. Phan Văn Trường. - Tinh hoa xử thế - Dám bị ghét. Kishimi Ichiro, Koga Fumitake. - Phép màu để vượt lên chính mình. Nhan Húc Quân. - Scouting for Boys: A Handbook for Instruction in Good Citizenship Through Woodcraft. Robert Baden-Powell. - Thay Đổi Cuộc Sống Với Nhân ...
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