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

[Snippet] CSS - Child element overlap parent

I searched from somewhere and found that a lot of people says a basic concept for implementing this feature looks like below: HTML code: <div id="parent">  <div id="child">  </div> </div> And, CSS: #parent{   position: relative;   overflow:hidden; } #child{   position: absolute;   top: -1;   right: -1px; } However, I had a lot of grand-parents in my case and the above code didn't work. Therefore, I needed an alternative. I presumed that my app uses Boostrap and AngularJs, maybe some CSS from them affects mine. I didn't know exactly the problem, but I believed when all CSS is loaded into my browser, I could completely handle it. www.tom-collinson.com I tried to create an example to investigated this problem by Fiddle . Accidentally, I just changed: position: parent; to position: static; for one of parents -> the problem is solved. Look at my code: <div class="modal-body dn-placeholder-parent-positi...
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

MS SQL Server Views

"Creates a virtual table whose contents (columns and rows) are defined by a query. Use this statement to create a view of the data in one or more tables in the database. For example, a view can be used for the following purposes: - To focus, simplify, and customize the perception each user has of the database. - As a security mechanism by allowing users to access data through the view, without granting the users permissions to directly access the underlying base tables. - To provide a backward compatible interface to emulate a table whose schema has changed." [1] Beside that, our team used view in order to improve the performance of our web apps when a database has a very complicated relationship between its tables by using ORM Frameworks such as Hibernate. Example code: --create CREATE VIEW placeholders AS SELECT EMPKEY AS empkey, CONNUMB AS connumb, EMPNBR AS empNbr, ACEEMPN AS empFirstName, ACEEMPFN AS empLastName, EMPNAM AS empFullName, ...
Post a Comment
Read more

Why Business Rules Engine Matter

"A good DSL minimizes the 'communication gap' between a domain concept and the code that implements it" - Robert C. Martin A Use Case It looks like adopting a new technology is always driven by a business need. The organizations, such as banks, have their own business processes (such as data gathering and document management). These processes are different from others but usually the differences are not big. How do we build a product which can be reused the similar features but still be adaptable with the specific requirements of each bank? Then, the answer is we should have a library/framework. There is an idea that we can implement this library/framework by using a business rules engine. Which has the following benefits: Be able to modify implementation of business domain at runtime (such as XML, CSV) S ource code is more readable for both developers and domain experts. Therefore, source code can be consider it as a document Since Business Rules Engine...
Post a Comment
Read more

Why Functional Programming Matter

What issues do we concern when implementing and maintaining systems? One of the most concern is debugging during maintenance: "this code crashed because it observed some unexpected value." Then, it turns out that the ideas of  no side effects  and  immutability , which functional programming promotes, can help. Shared mutable data is the root cause Shared mutable data are read and updated by more than one of the methods. Share mutable data structures make it harder to track changes in different parts of your program. An immutable object is an object that can't change its state after it's instantiated so it can't be affected by the actions of a function. It would be a dream to maintain because we wouldn't have any bad surprises about some object somewhere that unexpectedly modifies a data structure. A new thinking: Declarative programming There are two ways thinking about implementing a system by writing a program. - Imperative programming: has...
Post a Comment
Read more