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

Building Axon.ivy Projects on Bitbucket Pipelines

Read me  if you don't know what Axon.ivy (Ivy) is. Motivation -  Ivy projects are designed to be built on a continuous integration (CI) server like Jenkins - Today, Bitbucket supports for CI with Bitbucket Pipelines - We're using Bitbucket. Then, why not? It must be very cool and convenient for us if we can centralize our CI and VCS (version control system) tools in one place. Here is an approach We have to use a maven plugin called project-build-plugin  to build ivy projects. This plugin requires an instance of Ivy engine during building time. Bitbucket Pipelines allows us to specify our own docker image as a build environment. What we need to do  is to prepare our docker image with needed stuffs such as JDK, Maven, Ivy engine, etc. Step 1. Prepare Docker images For testing purpose, I already created two docker images: Maven and Axon.ivy engine. They are now available on Docker Hub This image for Maven using Oracle JDK 8 This image for Axon.iv...
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