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

Multiple Inheritance of State and Implementation

Today, I was just curious about why an enum can not extend anything else. I took a look on the Oracle document here , and I found the answer is below: "All enums implicitly extend java.lang.Enum. Because a class can only extend one parent (see Declaring Classes), the Java language does not support multiple inheritance of state (see Multiple Inheritance of State, Implementation, and Type), and therefore an enum cannot extend anything else." I have been learned of it before. But, wait a sec...! Why Java does not support multiple inheritance of state? Since I have worked with other programming languages like C++, I was able to make a class extend some other classes. The short answer is to avoid the issues of multiple inheritance of state .  I wonder if other programming languages have these below terms but Java does. Multiple inheritance of state It is the ability to inherit fields from multiple classes. There is a problem and Java avoids it. "For exa...
Post a Comment
Read more

4 Remarkable Notes for JSF Apps Using HTML5

In the previous post , I've already shared with you how my team consults clients by using a HTML prototype. This post is about the used technologies for reusing the provided HTML template and communicating with backend. What is the issue when using HTML elements with Primefaces components? Primefaces is a great extension for developing JSF web apps. However, it is really frustrating in case we have to make it work with an existing HTML template. Why? - Primefaces has its own theme for styling. - Primefaces changes the HTML structure. Therefore, that would be a huge effort to use the Primefaces' components to replicate the elements of the HTML template; especially it is impossible for images drawing by " canvas " tag. That requires us to find a better approach. Since Java EE 7 (introducing JSF 2.2 included), it supports to use HTML5 elements . The idea is that JSF components don't effect the style and HTML structure, so we can easily reuse the provided HTM...
2 comments
Read more

Using Drools to Dynamically Manipulate Metadata of JSF Components

The post is just an approach to change metadata (e.g maxlength, required, etc) of JSF components (e.g. inputText, selectOneMenue, etc) by Drools. Project structure Tools being used Java version 1.8.0_131 Apache Maven 3.5.0 Apache Tomcat 8.0.16 Don't forget to configure your confidential information on  these following files: pom.xml, settings.xml (Maven) and tomcat-users.xml (Tomcat). For example: Source code https://github.com/vnnvanhuong/java_lab/tree/master/jsfdrools
Post a Comment
Read more

Monday vhandit #2

  Introduction to OpenLDAP directory service "A directory is a specialized database specially designed for searching and browsing, in addition to supporting basic lookup and update functions" A directory service can be local, providing a restricted context; or global, providing service to a much broader context. Curlie is a good example of a directory service. LDAP (Lightweight Directory Access Protocol) is a protocol for accessing directory services , specifically X.500-based directory services. OpenLDAP is an open-source implementation of LDAP. Writing system software: code comments I have read Clean Code (by Uncle Bob) and I thought that I should void comments since the code it explains its implementation itself. That is right but not always true. In this post, the author categorized the comments into 9 types. Only "trivial comments" and "backup comments" are the ones that should be avoided. I myself agree with "writing good comments is harder tha...
Post a Comment
Read more

Regex - Check a text without special characters but German, French

Special characters such as square brackets ([ ]) can cause an exception " java.util.regex.PatternSyntaxException " or something like this if we don't handle them correctly. I had met this issue. In my case, my customers want our application should allow some characters in German and French even not allow some special characters. The solution is that we limit the allowed characters by showing the validation message on GUI. For an instance, the message looks like the following: "This field can't contain any special characters; only letters, numbers, underscores (_), spaces and single quotes (') are allowed." I used Regular Expression to check it. For entering Germany and French, I actually don't have this type of keyboard, so I referred these sites: * German characters: http://german.typeit.org/ * French characters: http://french.typeit.org/ Here is my code: package vn.nvanhuong.practice; import java.util.regex.Matcher; import java.util...
Post a Comment
Read more