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

How I did customize "rasa-nlu-trainer" as my own tool

Check out my implementation here Background I wanted to have a tool for human beings to classify intents and extract entities of texts which were obtained from a raw dataset such as Rocket.chat's conversation, Maluuba Frames or  here . Then, the output (labeled texts) could be consumed by an NLU tool such as Rasa NLU. rasa-nlu-trainer was a potential one which I didn't need to build an app from scratch. However, I needed to add more of my own features to fulfill my needs. They were: 1. Loading/displaying raw texts stored by a database such as MongoDB 2. Manually labeling intents and entities for the loaded texts 3. Persisting labeled texts into the database I firstly did look up what rasa-nlu-trainer 's technologies were used in order to see how to implement my mentioned features. At first glance rasa-nlu-trainer was bootstrapped with Create React App. Create React App is a tool to create a React app with no build configuration, as it said. This too...
Post a Comment
Read more

Junit - Test fails on French or German string assertion

In my previous post about building a regex to check a text without special characters but allow German and French . I met a problem that the unit test works fine on my machine using Eclipse, but it was fail when running on Jenkins' build job. Here is my test: @Test public void shouldAllowFrenchAndGermanCharacters(){ String source = "ÄäÖöÜüß áÁàÀâÂéÉèÈêÊîÎçÇ"; assertFalse(SpecialCharactersUtils.isExistSpecialCharater(source)); } Production code: public static boolean isExistNotAllowedCharacters(String source){ Pattern regex = Pattern.compile("^[a-zA-Z_0-9_ÄäÖöÜüß áÁàÀâÂéÉèÈêÊîÎçÇ]*$"); Matcher matcher = regex.matcher(source); return !matcher.matches(); } The result likes the following: Failed tests: SpecialCharactersUtilsTest.shouldAllowFrenchAndGermanCharacters:32 null A guy from stackoverflow.com says: "This is probably due to the default encoding used for your Java source files. The ö in the string literal in the J...
5 comments
Read more

Fulfilling Your Contribution Needs

Human resource management motivation Managing human today is quite different from the industrial age which treats people as just "chickens". Rather than people now are very important to the success of an organization. People are an organization's special resource. They should be encouraged to grow to contribute their effort and creativeness to their beloved working environment because the contribution is one of their most needs in life. Training people: getting rid of the ineffective model and adopting the new one The ineffective model of training people: Hiring new people --> giving them a crash course once --> expecting them working effectively.  That somehow makes sense but you're about to expect a luck because you do not really spend your effort for mentoring them. If they can work effectively, well...lucky you! Otherwise, you will blame that these people are ineffective and you let them go and hire the new ones. What a waste of time! The new effe...
Post a Comment
Read more

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

Strategy Design Pattern

For example, I have a program with an Animal abstract class and two sub-classes Dog and Bird. I want to add new behavior for the class Animal, this is "fly".  Now, I face two approaches to solve this issue: 1. Adding an abstract method "fly" into the class Animal. Then, I force the sub-classes should be implemented this method, something like: public abstract class Animal{ //bla bla public abstract void fly(); } public class Bird extends Animal{ //bla bla public void fly(){ System.out.println("Fly high"); } } public class Dog extends Animal{ //bla bla public void fly(){ System.out.println("Cant fly"); } } 2. Creating an interface with method "fly" inside. The same issue to an abstract class, I force the classes these implement this interface should have a method "fly" inside: public interface Flyable{ public void fly(); } public class Bird implements Flyable{ //bla bla public void fly(){ System.out.pr...
Post a Comment
Read more