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

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

Installing NGINX on macOS

I have heard of a lot of NGINX recently. One of them was it can help for security issues; for sure, it much be more. It so happens that our team has got a ton of user stories from a security audit. It's time to delve into it. What is NGINX? In order to get a basic idea and have some fun , I've just picked some available posts from my favorite Vietnamese blogger communities as below: https://kipalog.com/posts/Cau-hinh-nginx-co-ban---Phan-1 https://viblo.asia/hoang.thi.tuan.dung/posts/ZabG912QGzY6 NGINX (pronounce: Engine-X) is a web server (comparing to IIS, Apache). It can be used as a reverse proxy ( this is what I need for security issues with configuration ), load balancer and more. How to get started? I found the below path for learning NGINX by googling "learn nginx": https://www.quora.com/What-are-some-good-online-resources-to-learn-Nginx In this post, I only went first step. This is installing NGINX on macOS and taking a first look at the confi...
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

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

DevOps for Dummies

Everyone talks about it, but not everyone knows what it is. Why DevOps? In general, whenever an organization adopts any new technology, methodology, or approach, that adoption has to be driven by a business need. Any kind of system that need rapid delivery of innovation requires DevOps (development and operations). Why? DevOps requires mechanisms to get fast feedback from all the stakeholders in the software application that's being delivered. DevOps approaches to reduce waste and rework and to shift resources to higher-value activities. DevOps aims to deliver value (of organization or project) faster and more efficiently. DevOps Capabilities The capabilities that make up DevOps are a broad set that span the software delivery life cycle. The following picture is a reference architecture which provides a template of a proven solution by using a set of preferred methods and capabilities. My Remarks Okay, that sounds cool. What does it simply mean, again? The f...
Post a Comment
Read more