Search for a range challenge

Problem statement
Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of \mathcal{O}(log n). If the target is not found in the array, return [-1, -1]. For example, given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Solution

 

Minimum window substring challenge

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity \mathcal{O}(n).

Sample Input 0

Sample Output 0

Solution
The first step we are going to take is, count the occurrences of each letter in string T. We will use a Map for that.

We then iterate over each character of string S using an iterator i and keep a count of characters encountered so far. Again, for that we will use a Map<Character, Integer> count. We will track the start and ending of the smallest substring using start and end. At first both, start and end are initialised to -1. As soon, as we hit a character that is contained in T we set start = i, as this is the soonest possible way that a substring may contain all characters in T.

While we are iterating over the letters in S, we check if we have collected all the required characters. As soon as that is the case, we set end = i. Now we have a substring that contains all the characters of T. But we are not done yet. Maybe there exists a smaller substring that also contains all the characters of T.

We continue iterating over the remaining characters in S while incrementing our end to i and adding them to count. If we hit a character that is equal to S[start] (the tail of the current substring) we remove it from the current substring. We also keep removing characters from the tail that are not contained in T or characters that are in T but we have in excess.

When we are done removing characters, we check if the new resulting substring is shorter than the previous one. If such is the case we update our answer.

The algorithm terminates when we have iterated over all characters in S.

The full implementations (two variations) are listed below.

Full code (Implementation 1)

Full code (Implementation 2)

 

Append and delete challenge

Problem statement
You have a string, s, of lowercase English alphabetic letters. You can perform two types of operations on s:

  1. Append a lowercase English alphabetic letter to the end of the string.
  2. Delete the last character in the string. Performing this operation on an empty string results in an empty string.

Given an integer, k, and two strings, s and t, determine whether or not you can convert s to t by performing exactly k of the above operations on s. If it’s possible, print Yes; otherwise, print No.

Input Format
The first line contains a string, s, denoting the initial string.
The second line contains a string, t, denoting the desired final string. The third line contains an integer, k, denoting the desired number of operations.

Constraints
1 \le |s| \le 100
1 \le |t| \le 100
1 \le k \le 100
s and t consist of lowercase English alphabetic letters.

Output Format
Print Yes if you can obtain string t by performing exactly k operations on s; otherwise, print No.

Sample Input 0

Sample Output 0

Explanation 0
We perform 5 delete operations to reduce string s to hacker. Next, we perform 4 append operations (i.e., r, a, n, and k), to get hackerrank. Because we were able to convert s to t by performing exactly k=9 operations, we print Yes.

Sample Input 1

Sample Output 1

Explanation 1
We perform 4 delete operations to reduce string s to the empty string (recall that, though the string will be empty after 3 deletions, we can still perform a delete operation on an empty string to get the empty string). Next, we perform 3 append operations (i.e., a, b, and a). Because we were able to convert s to t by performing exactly k=7 operations, we print Yes.

Solution

 

Mini-max sum challenge

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Then print the respective minimum and maximum values as a single line of two space-separated long integers.

Input Format
A single line of five space-separated integers.

Constraints
Each integer is in the inclusive range [1, 10^9].

Output Format
Print two space-separated long integers denoting the respective minimum and maximum values that can be calculated by summing exactly four of the five integers. (The output can be greater than 32 bit integer.)

Sample Input

Sample Output

Solution

 

Kangaroo challenge

There are two kangaroos on an x-axis ready to jump in the positive direction (i.e, toward positive infinity). The first kangaroo starts at location x_1 and moves at a rate of v_1 meters per jump. The second kangaroo starts at location x_2 and moves at a rate of v_2 meters per jump. Given the starting locations and movement rates for each kangaroo, can you determine if they’ll ever land at the same location at the same time?

Input Format
A single line of four space-separated integers denoting the respective values of x_1, v_1, x_2, and v_2.

Constraints
0 \le x_1 \textless x_2 \le 10000
1 \le v_1 \le 10000
1 \le v_2 \le 10000

Output Format
Print YES if they can land on the same location at the same time; otherwise, print NO.

Note: The two kangaroos must land at the same location after making the same number of jumps.

Sample Input 0

Sample Output 0

Explanation 0
The two kangaroos jump through the following sequence of locations:
0 \rightarrow 3 \rightarrow 6 \rightarrow 9 \rightarrow  12
4 \rightarrow  6 \rightarrow 8 \rightarrow 10 \rightarrow 12
Thus, the kangaroos meet after 4 jumps and we print YES.

Sample Input 1

Sample Output 1

Explanation 1
The second kangaroo has a starting location that is ahead (further to the right) of the first kangaroo’s starting location (i.e., x_2 \textgreater x_1). Because the second kangaroo moves at a faster rate (meaning v_2 \textgreater v_1) and is already ahead of the first kangaroo, the first kangaroo will never be able to catch up. Thus, we print NO.

Solution
In order for the two kangaroos to land at the same location after i amount of time, the following must be true: x_1 + i \times v_1 == x_2 + i \times v_2. In other words, x_2 - x_1 == (v_1 - v_2)\times i. Thus, if (x_2 - x_1) % (v_1 - v_2) == 0 we return YES otherwise we return NO.

The full code is listed below.

Full code

 

Beautiful quadruples challenge

Problem statement
We call an quadruple of positive integers, (W, X, Y, Z), beautiful if the following condition is true:

W \oplus X \oplus Y \oplus Z \ne 0

Note: \oplus is the bitwise XOR operator.

Given A, B, C and D, count the number of beautiful quadruples of the form (W, X, Y, Z) where the following constraints hold:

1 \le W \le A
1 \le X \le B
1 \le Y \le C
1 \le Z \le D

When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:
– They contain same integers.
– Number of times each integers occur in the quadruple is same.

For example (1, 1, 1, 2) and (1, 1, 2, 1) should be considered as same.

Input Format
A single line with four space-separated integers describing the respective values of A, B, C and D.

Constraints
1 \le A, B, C, D \le 3000

Output Format
Print the number of beautiful quadruples.

Sample Input

Sample Output

Explanation
There are 11 beautiful quadruples for this input:
(1,1,1,2)
(1,1,1,3)
(1,1,1,4)
(1,1,2,3)
(1,1,2,4)
(1,1,3,4)
(1,2,2,2)
(1,2,2,3)
(1,2,2,4)
(1,2,3,3)
(1,2,3,4)

Thus, we print 11 as our output.
Note that (1, 1, 1, 2) is same as (1, 1, 2, 1) .

Solution
Since the order of the integers in a quadruple does not matter we can sort our input values such that A \le B \le C \le D:

We will then solve it for the first half of the quadruple (a,b,c,d). For that we define the following arrays:
total = new int[3001]: total[B] holds the number of pairs \{ a,b\} such that a \le b with 1 \le a \le A and 1 \le b \le B:

count = new int[3000 + 1][4096 + 1]: count[B][x] holds the number of pairs \{a,b\} such that a \le b and a \oplus b = x with 1 \le a \le A and 1 \le b \le B:

Note here that the maximum XOR value achievable is 4096 since 1 \le A, B, C, D \le 3000 (12 bits).

We can now go ahead and use total and count to find our solution. Remember we sorted our A \le B \le C \le D so that we count our quadruples (a,b,c,d) such that a \le b \le c \le d.

For the second half of (a,b,c,d) we have \{c,d\} with 1 \le c \le C and 1 \le d \le D. Let c \oplus d = y. We know that a \oplus b \oplus c \oplus d = 0 if a \oplus b = y. We know that we have a total of total[c] pairs \{a,b\} with a \le b and 1 \le b \le c. We want to exclude the pairs that have a \oplus b = y. There are count[c][y] pairs \{a,b\} that combined with \{c,d\} result to 0. So from total[c] we have to exclude count[c][y] and do this for all possible c and d:
\sum_{c=1}^{C}\sum_{d=1}^{D}total[c]-count[c][c \oplus d]

The full code is listed below.

Full code

 

Sort hotel list challenge

Problem statement
Given a set of hotels and its guests reviews, sort the hotels based on a list of words specified by a user. The criteria to sort the hotels should be how many times the words specified by the user is mentioned in the hotel reviews.

Input
The first line contains a space-separated set of words which we want to find mentions in the hotel reviews.

The second line contains one integer M, which is the number of reviews.

This is followed by M+M lines, which alternates an hotel ID and a review belonging to that hotel.

Output
A list of hotel IDs sorted, in descending order, by how many mentions they have of the words specified in the input.

Notes
– The words to be find will always be singe words line ‘breakfast’ or ‘noise’. Never double words like ‘swimming pool’.
– Hotel ud is a 4-byte integer.
– Words match should be case-insensitive.
– Dots and commas should be ignored.
– If a word appears in a review twice, it should count twice.
– If two hotels have the same number of mentions, they should be sorted in the output based on their ID, smallest ID first.
– In case one or more test cases time out, consider revisiting the runtime complexity of your algorithms.

Sample input

Sample output

Explanation
Hotel 2 has 7 mentions of the words: ‘location’ and ‘citycenter’ are mentioned twice while ‘breakfast’, ‘price’ and ‘staff’ are mentioned once. Hotel 1 in the other hand has 6 mentions in total ‘location’ and ‘citycenter’ also twice and then ‘view’ and ‘metro’ once.

Solution/Full code

 

Delta encoding challenge

Problem statement
Given a list of numbers, e.g.:

Output a delta encoding for the sequence. In a delta encoding, the first element is reproduced as is. Each subsequent element is represented as the numeric difference from the element before it. E.g. for the sequence above, the delta encoding would be:

However, if a difference value does not fit in a single signed byte, i.e. -127 \le x \le 127, then, instead of the difference, we would like to use an escape token, printing it.

This will denote that the value following the escape token is a full four-byte difference value, rather than a one-byte different value.

For this exercise, we’ll declare -128 as the escape token.

Following the same example above, the final result would be:

Solution

 

Sum of 2 numbers in an array

Problem statement
Identify whether there exists a pair of numbers in an array such that their sum is equal to N.

Input
The first line contains one integer N, which is the sum we are trying to find. The second line contains one integer M, which is the length of the array. This is followed by M lines each containing one element of the array.

Output
Output 1 if there exists a pair of numbers in the array such that their sum equals N. If such a pair does not exist, output 0.

Sample Input

Sample Output

Solution

 

Polygons challenge

Problem statement
Identify whether four sides (given by four integers) can form a square, a rectangle, or neither.

Input
You will receive an list of strings, each containing four space-separated integers, which represent the length of the sides of a polygon. The input lines will follow the ‘A B C D’ order as in the following representation:

Output
A single line which contains 3 space-separated integers; representing the number of squares, number of rectangles, and number of other polygons with 4 sides. Note that squares shouldn’t be counted as rectangles. Invalid polygons should also be counted as ‘other polygons’.

Constraints
The four integers representing the sides will be such that: -2000 \le x \le 2000 (Where x represents the integer)

Sample Input

Sample Output

Solution