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

Git Feature Branch Workflow

Motivator It's important for a team to have an agreement on how the changes of source code should be applied. According to projects and teams size, we will define a workflow or select one from recommended workflows ; the "Feature Branch Workflow" is a candidate. What is it? - One branch "master" for main codebase - Several separated branches for features development Why should we care? - Be super simple and allow each developer works on a particular feature. - A stable codebase (master) benefits for continuous integration (CI) environment - Leverage "Pull request" for Code review How it works? A lifecyle of a feature branch (usually created by a story) 1. Creator creates a new branch from a story.  For example: "ABC-1-setup-projects" 2. Creator checkouts the created branch and works on the branch (commits, pushes) 3. Creator has done the feature, he uses "pull request" to merge his branch into branch "master...
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

Managing JAR files with Apache Maven

Apache Maven (Maven) is a software project management and comprehension tool. Based on the concept of a project object model (POM), Maven can manage a project's build, reporting and documentation from a central piece of information. Why Maven? Let’s learn about the Maven’s history here https://maven.apache.org/background/history-of-maven.html to understand why Maven is created. There are a lot of useful things that we should use Maven. In my opinion, the most important thing is that Maven solves the problems with managing jar files. It centralizes these files in one place and it is easy to use by declaring dependencies in a xml file (pom.xml).  Using Maven to manage JAR files Firstly, I would like to give you an example about using some JAR files without Maven.  In my project, I need some JAR files such as SNMP4J.jar, jta26.jar, jgraphx.jar, etc… so I had to search them on the Internet with visiting a lot of websites, download and add these files into my proje...
Post a Comment
Read more

My must-have apps for daily work

There is no doubt that cool apps can help us be more productive and enjoyable at work. For the time being, I really love the following apps which are used by me almost every day. 1. A personal Kanban In fact, a personal kanban is the most useful app for me. Why does it matter? It is not just a to-do list, but it keeps me motivated every day because it helps me be able to know what my "big picture" is. I usually set up my plans together with a path to reach them.  KanbanFlow  is my preferred tool. KanbanFlow 2. A terminal Needless to say, a terminal is a must-have app for every developer, especially the ones use macOS/Linux. Due to its importance, I love to decorate and enhance it to be super exciting with various tools such as  iTerm ,  oh-my- zsh , and  thefuck . ;) iTerm + oh-my-zsh 3. A documentation "ecosystem" As a developer, I can not remember all things that I have experimented a day. Moreover, a document is really useful for sharing an...
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