HackerRank: Cavity Map

Problem

You are given a square map of size n×nn×n. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side (edge).

You need to find all the cavities on the map and depict them with the uppercase character X.

Input Format

The first line contains an integer, nn, denoting the size of the map. Each of the following nn lines contains nnpositive digits without spaces. Each digit (1-9) denotes the depth of the appropriate area.

Constraints
1n1001≤n≤100

Output Format

Output nn lines, denoting the resulting map. Each cavity should be replaced with character X.

Sample Input

4
1112
1912
1892
1234

Sample Output

1112
1X12
18X2
1234

Explanation

The two cells with the depth of 9 fulfill all the conditions of the Cavity definition and have been replaced by X.

Solution

HackerRank: The Grid Search

Problem

Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits. For example, consider the following 2D matrix:

1234567890  
0987654321  
1111111111  
1111111111  
2222222222  

Assume we need to look for the following 2D pattern:

876543  
111111  
111111

If we scan through the original array, we observe that the 2D pattern begins at the second row and the third column of the larger grid (the 8 in the second row and third column of the larger grid is the top-left corner of the pattern we are searching for).

So, a 2D pattern of P digits is said to be present in a larger grid G, if the latter contains a contiguous, rectangular 2D grid of digits matching with the pattern P, similar to the example shown above.

Input Format
The first line contains an integer, T, which is the number of test cases. T test cases follow, each having a structure as described below:
The first line contains two space-separated integers, R and C, indicating the number of rows and columns in the grid G, respectively.
This is followed by R lines, each with a string of C digits, which represent the grid G.
The following line contains two space-separated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits, which represent the pattern P.

Constraints
1T5
1R,r,C,c1000
1rR
1cC

Test Case Generation
Each individual test case has been generated by first specifying the size (R and C) of the large 2D matrix, and then randomly generating the digits in it. A limited number of digits in the larger matrix may be changed by the problem setter (no more than 5% of the total number of digits in the matrix). So the larger 2D matrix is almost-random. The pattern matrix has been manually-curated by the problem setter.

Output Format
Display ‘YES’ or ‘NO’, depending on whether (or not) you find that the larger grid GG contains the rectangular pattern PP. The evaluation will be case sensitive.

Sample Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

Sample Output

YES
NO

Explanation

The first test in the input file is:

10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530

As one may see, the given 2D grid is indeed present in the larger grid, as marked in bold below.

7283455864  
6731158619  
8988242643  
3830589324  
2229505813  
5633845374  
6473530293  
7053106601  
0834282956  
4607924137  

The second test in the input file is:

15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

The search pattern is:

99
99

This cannot be found in the larger grid.

Solution

HackerRank: Chocolate Feast

Problem

Little Bob loves chocolate, and he goes to a store with $N$N in his pocket. The price of each chocolate is $C$C. The store offers a discount: for every MM wrappers he gives to the store, he gets one chocolate for free. How many chocolates does Bob get to eat?

Input Format:
The first line contains the number of test cases, TT.
TT lines follow, each of which contains three integers, NN, CC, and MM.

Output Format:
Print the total number of chocolates Bob eats.

Constraints:
1T10001≤T≤1000
2N1052≤N≤105
1CN1≤C≤N
2MN2≤M≤N

Sample input

3
10 2 5
12 4 4
6 2 2

Sample Output

6
3
5

Explanation
In the first case, he can buy 5 chocolates with $10 and exchange the 5 wrappers to get one more chocolate. Thus, the total number of chocolates is 6.

In the second case, he can buy 3 chocolates for $12. However, it takes 4 wrappers to get one more chocolate. He can’t avail the offer and hence the total number of chocolates remains 3.

In the third case, he can buy 3 chocolates for $6. Now he can exchange 2 of the 3 wrappers and get 1 additional piece of chocolate. Now he can use his 1 unused wrapper and the 1 wrapper of the new piece of chocolate to get one more piece of chocolate. So the total is 5.

Solution

HackerRank: Encryption

Problem

An English text needs to be encrypted using the following encryption scheme.
First, the spaces are removed from the text. Let LL be the length of this text.
Then, characters are written into a grid, whose rows and columns have the following constraints:

  • LrowscolumnL⌊L⌋≤rows≤column≤⌈L⌉, where x⌊x⌋ is floor function and x⌈x⌉ is ceil function

For example, the sentence if man was meant to stay on the ground god would have given us roots after removing spaces is 5454 characters long, so it is written in the form of a grid with 7 rows and 8 columns.

ifmanwas  
meanttos          
tayonthe  
groundgo  
dwouldha  
vegivenu  
sroots
  • Ensure that rows×columnsLrows×columns≥L
  • If multiple grids satisfy the above conditions, choose the one with the minimum area, i.e. rows×columnsrows×columns.

The encoded message is obtained by displaying the characters in a column, inserting a space, and then displaying the next column and inserting a space, and so on. For example, the encoded message for the above rectangle is:

imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau

You will be given a message in English with no spaces between the words. The maximum message length can be8181 characters. Print the encoded message.

Here are some more examples:

Sample Input:

haveaniceday

Sample Output:

hae and via ecy

Sample Input:

feedthedog    

Sample Output:

fto ehg ee dd

Sample Input:

chillout

Sample Output:

clu hlt io

Solution

 

HackerRank: Caesar Cipher

Problem

Julius Caesar protected his confidential information by encrypting it in a cipher. Caesar’s cipher rotated every letter in a string by a fixed number, K, making it unreadable by his enemies. Given a string, S, and a number, K, encrypt S and print the resulting string.

Note: The cipher only encrypts letters; symbols, such as -, remain non-encrypted.

Input Format

The first line contains an integer, N, which is the length of the non-encrypted string.
The second line contains the non-encrypted string, S.
The third line contains the integer encryption key, K, which is the number of letters to rotate.

Constraints
1N100
0K100
S is a valid ASCII string and doesn’t contain any spaces.

Output Format

For each test case, print the encoded string.

Sample Input

11
middle-Outz
2

Sample Output

okffng-Qwvb

Explanation

Each non-encrypted letter is replaced with the letter occurring K spaces after it when listed alphabetically. Think of the alphabet as being both case-sensitive and circular; if K rotates past the end of the alphabet, it loops back to the beginning (i.e.: the letter after z is a, and the letter after is A).

Selected Examples:
m (ASCII 109) becomes o (ASCII 111).
i (ASCII 105) becomes k (ASCII 107).
remains the same, as symbols are not encoded.
O (ASCII 79) becomes Q (ASCII 81).
z (ASCII 122) becomes b (ASCII 98); because z is the last letter of the alphabet,
a (ASCII 97) is the next letter after it in lower-case rotation.

Solution

HackerRank: [Algo] Matrix Rotation

Problem

You are given a 2-D matrix, a, of dimension M x N and a positive integer R. You have to rotate the matrix R times and print the resultant matrix. Rotation should be in anti-clockwise direction.

Rotation of a 4 x 5 matrix is represented by the following figure. Note that in one rotation, you have to shift elements by one step only (refer sample tests for more clarity).

matrix-rotation

It is guaranteed that the minimum of M and N will be even.

Input Format
First line contains three space separated integers, M, N and R, where M is the number of rows, N is number of columns in matrix, and R is the number of times the matrix has to be rotated.
Then M lines follow, where each line contains N space separated positive integers. These M lines represent the matrix.

Output Format
Print the rotated matrix.

Constraints
2 <= M, N <= 300
1 <= R <= 109
min(M, N) % 2 == 0
1 <= aij <= 108, where i[1..M] & j[1..N]

Sample Input #00

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #00

2 3 4 8
1 7 11 12
5 6 10 16
9 13 14 15

Sample Input #01

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #01

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

Sample Input #02

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

Sample Output #02

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

Sample Input #03

2 2 3
1 1
1 1

Sample Output #03

1 1
1 1

Explanation
Sample Case #00: Here is an illustration of what happens when the matrix is rotated once.

 1  2  3  4      2  3  4  8
 5  6  7  8      1  7 11 12
 9 10 11 12  ->  5  6 10 16
13 14 15 16      9 13 14 15

Sample Case #01: Here is what happens when to the matrix after two rotations.

 1  2  3  4      2  3  4  8      3  4  8 12
 5  6  7  8      1  7 11 12      2 11 10 16
 9 10 11 12  ->  5  6 10 16  ->  1  7  6 15
13 14 15 16      9 13 14 15      5  9 13 14

Sample Case #02: Following are the intermediate states.

1  2  3  4      2  3  4 10    3  4 10 16    4 10 16 22
7  8  9 10      1  9 15 16    2 15 21 22    3 21 20 28
13 14 15 16 ->  7  8 21 22 -> 1  9 20 28 -> 2 15 14 27 ->
19 20 21 22    13 14 20 28    7  8 14 27    1  9  8 26
25 26 27 28    19 25 26 27    13 19 25 26   7 13 19 25



10 16 22 28    16 22 28 27    22 28 27 26    28 27 26 25
 4 20 14 27    10 14  8 26    16  8  9 25    22  9 15 19
 3 21  8 26 ->  4 20  9 25 -> 10 14 15 19 -> 16  8 21 13
 2 15  9 25     3 21 15 19     4 20 21 13    10 14 20  7
 1  7 13 19     2  1  7 13     3  2  1  7     4  3  2  1

Sample Case #03: As all elements are same, any rotation will reflect the same matrix.

Solution

HackerRank: Cut the sticks

Problem

You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:
5 4 4 2 2 8

Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:
3 2 2 6

The above step is repeated until no sticks are left.

Given the length of N sticks, print the number of sticks that are left before each subsequent cut operations.

Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

Input Format
The first line contains a single integer N.
The next line contains N integers: a0, a1,…aN-1 separated by space, where ai represents the length of ith stick.

Output Format
For each operation, print the number of sticks that are cut, on separate lines.

Constraints
1 ≤ N ≤ 1000
1 ≤ ai ≤ 1000

Sample Input #00

6
5 4 4 2 2 8

Sample Output #00

6
4
2
1

Sample Input #01

8
1 2 3 4 3 3 2 1

Sample Output #01

8
6
4
1

Explanation

Sample Case #00 :

sticks-length        length-of-cut   sticks-cut
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE

Sample Case #01

sticks-length         length-of-cut   sticks-cut
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

Solution

 

HackerRank: Service Lane

Problem

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the service lane is N units. The service lane consists of N segments of equal length and different width.

Calvin can enter to and exit from any segment. Let’s call the entry segment as index i and the exit segment as index j. Assume that the exit segment lies after the entry segment (ij) and 0i0≤i. Calvin has to pass through all segments from index i to index j (both inclusive).

Paradise Highway

Calvin has three types of vehicles – bike, car, and truck – represented by 1, 2 and 3, respectively. These numbers also denote the width of the vehicle.

You are given an array width of length N, where width[krepresents the width of the kth segment of the service lane. It is guaranteed that while servicing he can pass through at most 1000 segments, including the entry and exit segments.

  • If width[k]=1, only the bike can pass through the kth segment.
  • If width[k]=2, the bike and the car can pass through the kth segment.
  • If width[k]=3, all three vehicles can pass through the kth segment.

Given the entry and exit point of Calvin’s vehicle in the service lane, output the type of the largest vehicle which can pass through the service lane (including the entry and exit segments).

Input Format

The first line of input contains two integers, N and T, where N denotes the length of the freeway and T the number of test cases. The next line has N space-separated integers which represent the width array.

T test cases follow. Each test case contains two integers, i and j, where i is the index of the segment through which Calvin enters the service lane and j is the index of the lane segment through which he exits.

Constraints
2N100000
1T1000
0i<j<N
2ji+1min(N,1000)
1width[k]3,where 0k<N

Output Format

For each test case, print the number that represents the largest vehicle type that can pass through the service lane.

Note: Calvin has to pass through all segments from index i to index j (both inclusive).

Sample Input

8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7

Sample Output

1
2
3
2
1

Explanation

Below is the representation of the lane:

   |HIGHWAY|Lane|    ->    Width

0: |       |--|            2
1: |       |---|           3
2: |       |-|             1
3: |       |--|            2
4: |       |---|           3
5: |       |--|            2
6: |       |---|           3
7: |       |---|           3
  1. (0, 3): Because width[2] = 1, only the bike can pass through it.
  2. (4, 6): Here the largest allowed vehicle which can pass through the 5th segment is the car and for the 4th and 6th segment it’s the truck. Hence the largest vehicle allowed in these segments is a car.
  3. (6, 7): In this example, the vehicle enters at the 6th segment and exits at the 7th segment. Both segments allow even trucks to pass through them. Hence the answer is 3.
  4. (3, 5): width[3] = width[5] = 2. While the 4th segment allows the truck, the 3rd and 5thallow up to a car. So 2 will be the answer here.
  5. (0, 7): The bike is the only vehicle which can pass through the 2nd segment, which limits the strength of the whole lane to 1.

Solution

 

Unirest: Lightweight HTTP Request Client Libraries

UniRest

Unirest is a set of lightweight HTTP libraries available in multiple languages, built and maintained by the Mashape team.

Unirest.post("http://httpbin.org/post")
  .queryString("name", "Mark")
  .field("last", "Polo")
  .asJson()

Features

  • Make GET, POST, PUT, PATCH, DELETE, HEAD, OPTIONS requests
  • Both syncronous and asynchronous (non-blocking) requests
  • It supports form parameters, file uploads and custom body entities
  • Easily add route parameters without ugly string concatenations
  • Supports gzip
  • Supports Basic Authentication natively
  • Customizable timeout, concurrency levels and proxy settings
  • Customizable default headers for every request (DRY)
  • Customizable HttpClient and HttpAsyncClient implementation
  • Automatic JSON parsing into a native object for JSON responses
  • Customizable binding, with mapping from response body to java Object

Installing

Is easy as pie. Kidding. It’s about as easy as doing these little steps:

With Maven

You can use Maven by including the library:

<dependency>
    <groupId>com.mashape.unirest</groupId>
    <artifactId>unirest-java</artifactId>
    <version>1.4.7</version>
</dependency>

There are dependencies for Unirest-Java, these should be already installed, and they are as follows:

<dependency>
  <groupId>org.apache.httpcomponents</groupId>
  <artifactId>httpclient</artifactId>
  <version>4.3.6</version>
</dependency>
<dependency>
  <groupId>org.apache.httpcomponents</groupId>
  <artifactId>httpasyncclient</artifactId>
  <version>4.0.2</version>
</dependency>
<dependency>
  <groupId>org.apache.httpcomponents</groupId>
  <artifactId>httpmime</artifactId>
  <version>4.3.6</version>
</dependency>
<dependency>
  <groupId>org.json</groupId>
  <artifactId>json</artifactId>
  <version>20140107</version>
</dependency>

If you would like to run tests, also add the following dependency along with the others:

<dependency>
  <groupId>junit</groupId>
  <artifactId>junit</artifactId>
  <version>4.11</version>
  <scope>test</scope>
</dependency>
<dependency>
  <groupId>commons-io</groupId>
  <artifactId>commons-io</artifactId>
  <version>2.4</version>
  <scope>test</scope>
</dependency>

Without Maven

Alternatively if you don’t use Maven, you can directly include the JAR file in the classpath:http://oss.sonatype.org/content/repositories/releases/com/mashape/unirest/unirest-java/1.4.7/unirest-java-1.4.7.jar

Don’t forget to also install the dependencies (org.json, httpclient 4.3.6, httpmime 4.3.6,httpasyncclient 4.0.2) in the classpath too.

There is also a way to generate a Unirest-Java JAR file that already includes the required dependencies, but you will need Maven to generate it. Follow the instructions at http://blog.mashape.com/post/69117323931/installing-unirest-java-with-the-maven-assembly-plugin

Creating Request

So you’re probably wondering how using Unirest makes creating requests in Java easier, here is a basic POST request that will explain everything:

HttpResponse<JsonNode> jsonResponse = Unirest.post("http://httpbin.org/post")
  .header("accept", "application/json")
  .queryString("apiKey", "123")
  .field("parameter", "value")
  .field("foo", "bar")
  .asJson();

Requests are made when as[Type]() is invoked, possible types include Json, Binary, String, Object.

If the request supports and it is of type HttpRequestWithBody, a body it can be passed along with.body(String|JsonNode|Object). For using .body(Object) some pre-configuration is needed (see below).

If you already have a map of parameters or do not wish to use seperate field methods for each one there is a.fields(Map<String, Object> fields) method that will serialize each key – value to form parameters on your request.

.headers(Map<String, String> headers) is also supported in replacement of multiple header methods.

Full Documentation @ unirest.io