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

Avoiding Time-Wasting Pitfalls in Agile Estimation

If you do Scrum at work, you might be very familiar to the estimation in Planning 1 . My PO has once complained to my team that why it took too long for estimating just a story. Wasting time results in the planning timebox is violated. I give you some advice from my experience: Estimation is estimation, not measure. When you read some requirements, you see some risks but you actually don't know how complicated it will be.  Don't try to influence the others by explaining how to do it in too detail. Just keep in mind that you know the business domain pertaining to customer needs and estimate how much effort you will spend for it. The effort should be compared to your baseline one that you use for a simple requirement. The bottom line is we do "relative estimation", not absolute estimation. For example, you are asked to estimate the height of a building. Basically, you just need to answer "how many times higher is the build than your height"; you do...
Post a Comment
Read more

Math fundamentals and Katex

It was really tough for me to understand many articles about data science due to the requirements of understanding mathematics (especially linear algebra). I’ve started to gain some basic knowledges about Math by reading a book first. The great tool Typora and stackedit with supporting Katex syntax simply helps me to display Math-related symbols. Let’s start! The fundamental ideas of mathematics: “doing math” with numbers and functions. Linear algebra: “doing math” with vectors and linear transformations. 1. Solving equations Solving equations means finding the value of the unknown in the equation. To find the solution, we must break the problem down into simpler steps. E.g: x 2 − 4 = 4 5 x 2 − 4 + 4 = 4 5 + 4 x 2 = 4 9 x = 4 9 ∣ x ∣ = 7 x = 7  or  x = − 7 \begin{aligned} x^2 - 4 &= 45\\ x^2 - 4 + 4 &= 45 + 4\\ x^2 &= 49\\ \sqrt{x}&=\sqrt{49}\\ |x| &= 7\\ x=7 &\text{ or } x=-7 \end{aligned} x 2 − 4 x 2 − 4 + 4 x 2 x ​ ∣ x ∣ x = 7 ​ = 4 5 = 4 ...
Post a Comment
Read more

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

Creating a Chatbot with RiveScript in Java

Motivation "Artificial Intelligence (AI) is considered a major innovation that could disrupt many things. Some people even compare it to the Internet. A large investor firm predicted that some AI startups could become the next Apple, Google or Amazon within five years"   - Prof. John Vu, Carnegie Mellon University. Using chatbots to support our daily tasks is super useful and interesting. In fact, "Jenkins CI, Jira Cloud, and Bitbucket" have been becoming must-have apps in Slack of my team these days. There are some existing approaches for chatbots including pattern matching, algorithms, and neutral networks. RiveScript is a scripting language using "pattern matching" as a simple and powerful approach for building up a Chabot. Architecture Actually, it was flexible to choose a programming language for the used Rivescript interpreter like Java, Go, Javascript, Python, and Perl. I went with Java. Used Technologies and Tools Oracle JDK 1.8...
Post a Comment
Read more

Java Core - Top 10 Questions Every Developer Should Know

#RandomlyPickedByMe What is the difference between Javascript and Java? Difference between StringBuilder and StringBuffer? Why do I get "SomeType@a3fde" when I print my code? Why is String immutable? Why "equals" method when we have "==" operator? Is List<Dog> a subclass of List<Animal>? Why shouldn't we use raw type? Is Java “pass-by-reference” or “pass-by-value”? What's the advantage of a Java enum versus a class with public static final fields? Why "double x = 0.1 + 0.2" and result of print(x) is 0.30000000000000004? 1. What is the difference between Javascript and Java? Holy crap! (Vietnamese: Thế quái nào lại có câu hỏi ngớ ngẩn vậy chứ?) "Java and Javascript are similar like Car and Carpet are similar." - Greg Hewgill (on StackOverflow) 2. Difference between StringBuilder and StringBuffer String is immutable. StringBuilder and StringBuffer are mutable. StringBuffer is thread-safe. String...
Post a Comment
Read more