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

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

Styling Sort Icons Using Font Awesome for Primefaces' Data Table

So far, Primefaces has used image sprites for displaying the sort icons. This leads to a problem if we want to make a different style for these icons; for example, I would make the icon "arrow up" more blurry at the first time the table loading because I want to highlight the icon "arrow down". I found a way that I can replace these icons with Font Awesome icons. We will use "CSS Pseudo-classes" to achieve it. The hardest thing here is that we should handle displaying icons in different cases. There is a case both "arrow up" and "arrow down" showing and other case is only one of these icons is shown. .ui-sortable-column-icon.ui-icon.ui-icon-carat-2-n-s { background-image: none; margin-left: 5px; font-size: 1.1666em; position: relative; } .ui-sortable-column-icon.ui-icon.ui-icon-carat-2-n-s:not(.ui-icon-triangle-1-s)::before { content: "\f106"; font-family: "FontAwesome"; position: ...
Post a Comment
Read more

How to convert time between timezone in Java, Primefaces?

I use the calendar Primefaces component with timeOnly and timeZone attributes for using only hour format (HH:mm). Like this: <p:calendar id="xabsOvertimeTimeFrom" pattern="HH:mm" timeOnly="true" value="#{data.dateFrom}" timeZone="#{data.timeZone}"/> We can convert the value of #{data.dateFrom} from GMT/UTC time zone to local, conversely, from local time zone to GMT/UTC time zone. Here is my functions: package vn.nvanhuong.timezoneconverter; import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.Calendar; import java.util.Date; import java.util.TimeZone; public class TimeZoneConverter { /** * convert a date with hour format (HH:mm) from local time zone to UTC time zone */ public static Date convertHourToUTCTimeZone(Date inputDate) throws ParseException { if(inputDate == null){ return null; } Calendar calendar = Calendar.getInstance(); calendar.setTime(inputDate); int ...
Post a Comment
Read more

Sharing a virtualenv across several Python projects using Pipenv

There is a standard library for all projects in Python. However, several projects don’t always have the same dependencies all the time. That is where virtual environments come to play. You can follow this official document to use two separated tools  virtualenv and pip to  fulfill that need. My preferred alternative is to use pipenv . Pipenv is easy to use and convenient. The following are my steps to make a shared virtualenv for my all projects which requires the same dependencies. Step 1. Create an isolated virtualenv. python -m venv my-shared-env Step 2. Create a symbolic link to the created virtualenv. cd project_1 ln -s ~/.local/share/virtualenvs/my-shared-env .venv I have encountered the following issue at step 1. FileNotFoundError: [Errno 2] No such file or directory: '{my_project_path}/.venv/bin/pip': '{my_project_path}/.venv/bin/pip' The root cause was I tried to create virtualenv by running pipenv install and renaming the generated virtualenv to ...
Post a Comment
Read more

Functional programming in Java 8

In my previous post , we discussed about why we should consider to use functional programming. Now, let's delve into what functional programming in Java is. What is pure functional programming? Shortly,  f unctional programming is programming using functions. A function corresponds to a mathematical function such as log, sin. Basically, it takes zero or more arguments, give one or more result, and has no side effects. We can't completely program in pure functional style in Java Why?  For example, calling Scanner.nextLine twice typically gives different result. So, it's just called "functional-style programming". How is that? - There is no mutating structures visible to callers. That means your side effect may not be visible to a program, but it's visible to the programmer in terms of slower execution. - A function or method shouldn't throw any exceptions (follows the concept "pass arguments, return result"). We can use types like Opti...
Post a Comment
Read more