## Hackerrank: Waiter

You are a waiter at a party. There are  stacked plates on pile A0. Each plate has a number written on it. Then there will be Q iterations. In i-th iteration, you start picking up the plates in  Ai-1 from the top one by one and check whether the number written on the plate is divisible by the i-th prime. If the number is divisible, you stack that plate on pile Bi . Otherwise, you stack that plate on pile Ai. After Q iterations, plates can only be on pile B1,B2,..,Bq,Aq. Output numbers on these plates from top to bottom of each piles in order of B1,B2,…,Bq,Aq.

Input Format

The first line contains two space separated integers, N and Q.
The next line contains N space separated integers representing the initial pile of plates, i.e., A0. The leftmost value represents the bottom plate of the pile.

Constraints

• 1 <= N <=5 * 10^4
• 2 <= number_ith <= 10^4
• 1 <= Q <= 1200

Output Format

Output N lines. Each line contains a number written on the plate. Printing should be done in the order defined above.

Sample Input 0

5 1
3 4 7 6 5


Sample Output 0

4
6
3
7
5


Explanation 0

Initially:

A0 = [3, 4, 7, 6, 5]<-TOP

After 1 iteration:

A0 = []<-TOP

B1 = [6, 4]<-TOP

A1 = [5, 7, 3]<-TOP

We should output numbers in B1  first from top to bottom, and then output numbers in A1 from top to bottom.

Sample Input 1

5 2
3 3 4 4 9


Sample Output 1

4
4
9
3
3


Explanation 1

Initially:

A0 = [3, 3, 4, 4, 9]<-TOP

After  iteration:

A0 = []<-TOP

B1 = [4, 4]<-TOP

B2 = [9, 3, 3]<-TOP

After  iteration:

A1 = []<-TOP

B1 = [4, 4]<- TOP

B2 = [3, 3, 9]<-TOP

We should output numbers in B1  first from top to bottom, and then output numbers in B2 from top to bottom.

You can tell that the Explanation 1 is wrong but it doesn’t matter. The problem description is quite confusing, but it’s really simple.

You’re given a set and you have to split that set into two separate parts, one that is divisible by some prime numbers, and the other isn’t. The visible part are constructed by multiple stacks. Each iteration i-th, you go through the stack A, if any element in stack A is divisible by i-th prime, put it into a stack B i-th, otherwise put it back in a new stack of A, which will reverse the original stack.

Later on, either when new stack A is empty or we run out of the iteration loop, we go through the stacks B, pop out each element in each stack and print it out. Then go through the final stack A, which might or might not be empty.

This my the solution in Java.

https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/Waiter.java

## Hackerrank : Maximum Element

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.


Input Format

The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

Constraints
1 <= N <= 10^5
1 <= x <= 10^9
1 <= type <= 3

Output Format

For each type  query, print the maximum element in the stack on a new line.

Sample Input

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3


Sample Output

26
91

First thing you should notice is the constraint:
1 <= N <= 10^5
Most of the time, if you see the constraint is 10^5 (ten to the power of 5), it means your solution must be at most O(n log n) or better.

Okey, since it’s marked as “Easy” so there will be no hidden things that you need to figure out. Basically you need to build a stack and get the biggest elements in the stack and quick / fast as possible, so this is all about data structure.

Obviously we need a stack, to push and pop items as required. But how can we tell which item in the stack is biggest.

The easiest solution is go through the stack and get the max item. It works but it’s too slow. The time complexity will be O(n^2), roughly.

Method1:
We can use an additional collection, like a Heap, more specifically, a MaxHeap to store the elements in order. To insert an item to a Heap, it is O(n log n), to remove an item in a heap, it’s aso O(n log n). Finally, this is what we want, to get the biggest element as fast as possible. Specifically for MaxHeap, the top will be the biggest element. Overall this will work and the time complexity will be roughly O(n log n). The hardest thing is to implement the MaxHeap yourself.

Method2:
This is more “language-oriented”. It removes the “re-invent the wheel” part, no need to implement MaxHeap yourself.
In Java we have a SortedSet, it’s really fast for adding item as well as lookup smallest/largest item. The only problem though, is duplicated items. We need to watch out for duplicated items. Obviously, because set only stores non duplicated items. We can use a Map to store the item and its frequency. When the frequency goes down to 1, we know that we can remove the item from the set, as well as the frequency map. This is relatively fast, but it consumes a lot of spaces. It’s O(n) in space complexity.

Method3:
This is when “algorithm” comes to handy. Let’s say we need to insert an item, and also we need to know what is the maximum value after we insert the new item. If this still isn’t enough for you then please continue reading. So instead of just saving an item, you can also save the max value so far given the new item, also we need a global max variable to know the max value so far. The item on the top of the stack is guaranteed to be paired with the biggest element. When the stack is empty we need to reset the maximum value and when popping item out of stack, we need to update the global max value (if needed).

There may be more solutions for this problem but these are what I’ve come up with.

Here’s the sample code if you get trouble implementing the mentioned solutions.

## Segment Tree: min/max range queries problem.

Given an array arr[0…n-1] and multiple queries. With each query, we need to find the minimum (or maximum) value from index qs (query start) to qe (query end) where 0 <= qs <= qe < n.

Examples:

Input : arr[] = {1, 8, 5, 9, 6, 14, 2, 4, 3, 7}
queries = 5
qs = 0 qe = 4
qs = 3 qe = 7
qs = 1 qe = 6
qs = 2 qe = 5
qs = 0 qe = 8
Output: Minimum = 1 and Maximum = 9
Minimum = 2 and Maximum = 14
Minimum = 2 and Maximum = 14
Minimum = 5 and Maximum = 14
Minimum = 1 and Maximum = 14


There are multiple ways for solving this problem.

1. Simple solution:
Each query, we run through arr[qs…qe], find and print out the min/maximum value. This approach is useful on a small scale problem, but when array involves thousands of elements and we have thousands of queries, it is impractical, since its time complexity is O(q * n), with q is number of queries and n is number of elements in array.

2. Segment Tree
Utilize the properties of segment tree can help us solve this problem efficiently.
A segment tree is a binary tree, the way it is built can be compared to merge sort algorithm. The root node contains the min value in range [0…n-1], left and right child of root node contains range of half left and half right: [0…mid] and [mid+1…0], respectively. This can be applied on left and right child of any node.
Except leaf nodes, leaf nodes contain elements in the original array.

Segment tree of array: [2, 5, 1, 4, 9, 3]

Number of elements in segment tree is 2*n – 1, with n is the number of elements in the array. But since we gonna use array for the implementation, we need 2*next_power_of_two(n) – 1, next_power_of_two is a function return the smallest possible power of two that is bigger than n. Example next_power_of_two(5) will yield 8.

Time complexity will be O(q * logn) with q is the number of queries and n is number of elements in array, which is significantly faster than the simple approach.

class SegmentTree:

########################### Private Interface ############################

def __init__(self, arr):
self._seg_tree = [float('Inf')]*(2*self._next_power_of_two(len(arr))-1)
# input array
self._arr = arr
self._construct_tree(self._arr, self._seg_tree, 0, len(self._arr)-1, 0)

def _construct_tree(self, arr, seg_tree, low, high, pos):
if low >= high:
# build two child first
# (value, (range)) -> help query easier
seg_tree[pos] = (arr[low], (low, low))
return
mid = (low+high) // 2

# build left subtree
self._construct_tree(arr, seg_tree, low, mid, 2*pos+1)
# build right subtree
self._construct_tree(arr, seg_tree, mid+1, high, 2*pos+2)

# build the parent of two children above
# get min of two children, and range is [low, high]
seg_tree[pos] = (min(seg_tree[self._left(pos)][0], seg_tree[self._right(pos)][0]), (low, high))

def _is_power_of_two(self, n):
return n > 0 and (n & (n-1)) == 0

def _next_power_of_two(self, n):
# if n is already a power of two, return it
if self._is_power_of_two(n):
return n
count = 0
while n > 0:
count += 1
# right shift bit = divide by 2
n = n >> 1
# 1 << count = 2**count
return 1 << count

def _left(self, p):
# return left child of p
return p*2 + 1

def _right(self, p):
# return right child of p
return p*2 + 2

def _has_child(self, p):
# check if p has children
return self._left(p) < len(self._seg_tree) and self._right(p) < len(self._seg_tree)               ########################### Public Interface ############################          def query_min(self, qs, qe, pos):         # since there are some INF element         # we need to check instance type         if isinstance(self._seg_tree[pos], float):             return float('Inf')         # get range of the current 'pos'         # and min of current range         start, end = self._seg_tree[pos][1]         min_val = self._seg_tree[pos][0]                  # case 1: range of node is within qs and qe          #       => return min of range
if qs <= start and qe >= end:
return min_val

# case 2: range of node is outside qs and qe
#       => return INF (indicate redundant value)
if end < qs or start > qe:
return float('Inf')

# case 3: range of node is partition overlapped with qs and qe
#       return min([left_child, qs, qe], [right_child, qs, qe])
# first we need to check if it has child
# if no, return its value, otherwise call query_min for left and right child
if self._has_child(pos):
return min(self.query_min(qs, qe, self._left(pos)), self.query_min(qs, qe, self._right(pos)))
else:
return self._seg_tree[pos][0]


As you can see in the query_min() method, there are three cases can happen.
1. The range of current node is completely inside the range of query.
2. The range of current node is completely outside the range of query.
3. The range of current node is partition overlapped with the range of query.

More understanding can be gained after watching this video. In my opinion, it is by far the most understandable video describing how a min/max query works on segment tree.
Segment Tree Query Demo

Some problem for practising:
https://www.hackerrank.com/challenges/service-lane/problem
http://www.spoj.com/problems/RMQSQ/

## Problem: Manasa and Stones

Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

Note: The numbers on the stones are in increasing order.

Input Format

The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains n (the number of stones). The second line contains a, and the third line contains b.

Constraints

1 <= T <= 10
1 <= n, a, b <= 10^3

Output Format

Space-separated list of numbers which are the possible values of the last stone in increasing order.

Sample Input

2
3
1
2
4
10
100


Sample Output

2 3 4
30 120 210 300


Explanation

All possible series for the first test case are given below:

1. 0,1,2
2. 0,1,3
3. 0,2,3
4. 0,2,4

Hence the answer 2 3 4.

Series with different number of final steps for second test case are the following:

1. 0, 10, 20, 30
2. 0, 10, 20, 120
3. 0, 10, 110, 120
4. 0, 10, 110, 210
5. 0, 100, 110, 120
6. 0, 100, 110, 210
7. 0, 100, 200, 210
8. 0, 100, 200, 300

Hence the answer 30 120 210 300.

Approach:

1. Using backtracking. Generate all possible sequences, get all last values, and put them into a set. This is acceptable with n small (less than 15), since the complexity is O(2^n). Here is the code for backtracking
2. Analyze. Let’s take 2 examples above and find out the pattern. In the first example, n = 3 and there are 3 different ending values, max value is 4 and the difference from the largest to the smallest is 1 (4 -> 3 -> 2) . In the second example, n = 4 and there are 4 different ending values, max value is 300 and difference between pairs is 90. Have you seen the pattern yet? With n, there are n different values, the largest value is max(a,b)*(n-1), the difference is max(a,b) – min(a,b), or a – b, if a is bigger, otherwise b-a. How can we know that this pattern is the one that we’re looking for. First, since there are only two values a,b, assume a is bigger than b (it works the same way if b is bigger than a). Then the biggest possible value you can get is b*(n-1). since the first one is 0. The second biggest is b*(n-1) – (a-b), since this is the second biggest, the last value is b, instead of a. We c0ntinue this as long as the value return after calculate the difference is positive. And this is actually n-1 times, since we already manually calculate the largest.

Source code. The chain function is how you print out all possible stones chain, with complexity O(2^n). Inside main is the code to solve this problem.

def chain(n, arr, options):
for i in options:
arr[n] = arr[n-1] + i
if n == len(arr) - 1:
print(arr)
else:
chain(n+1, arr, options)

def test():
chain(1, [0]*4, (10, 100))

if __name__ == '__main__':
t = int(input().strip())
for _ in range(t):
n = int(input().strip())
a = int(input().strip())
b = int(input().strip())
if b > a:
a, b = b, a
pos_values = [0]*n
pos_values[0] = a*(n-1)
for i in range(1, len(pos_values)):
pos_values[i] = pos_values[i-1] - (a-b)
pos_values = list(set(pos_values))
print(*sorted(pos_values))


## Problem: Check Mirror in N-ary tree

*Difficulty: Medium

Given two n-ary tree’s the task is to check if they are mirror of each other or not.

Example

1                      1
/    \                 /   \
2      3             3     2

Output: 1

1                        1
/  \                    /  \
2    3                2     3

Output: 0

Note: you may assume that root of both the given tree as 1.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space separated values n and e denoting the no of nodes and edges respectively. Then in the next line two lines are 2*e space separated values u,v denoting an edge from u to v for the both trees .

Output:
For each test case in a new line print 1 if both the trees are mirrors of each other else print 0.

Constraints:
1<=T<=20
1<=n<=15
1<=e<=20

Example:
Input:

2
3 2
1 2 1 3
1 3 1 2
3 2
1 2 1 3
1 2 1 3
Output:
1
0

Approach: Since this is a N-arr tree, that means one node can have multiple child. So the easiest way is to consider it as a graph. Each graph has a list of adjacent nodes. The way to to check  if two threes (or graphs if you will) are mirror of each other or not is:

1. They have the same number of nodes
2. All node have the same number of adjacent nodes
3. The child list of each node in the first tree when reversed will be exactly like the one in the node of second tree and vice versa.

Implementation: Python 3

def is_mirror(tree_1, tree_2):
if len(tree_1) != len(tree_2):
return False
for node in tree_1:
if len(tree_1[node]) != len(tree_2[node]):
return False
if tree_1[node] != list(reversed(tree_2[node])):
return False
return True

def create_tree():
tree = {}
arr = list(map(int, input().strip().split()))
for i in range(0,len(arr),2):
if arr[i] in tree:
tree[arr[i]].append(arr[i+1])
else:
tree[arr[i]] = [arr[i+1]]
return tree

if __name__ == '__main__':
t = int(input().strip())
for _ in range(t):
n, e = list(map(int, input().strip().split()))
tree_1 = create_tree()
tree_2 = create_tree()
# print(tree_1)
# print(tree_2)
print(1 if is_mirror(tree_1, tree_2) else 0)


## Problem:

*Difficulty: Easy

Problem:

ctci-find-the-running-median-english

Approach:
Since the constraints is so high, we need a way to insert and sort the array (or list) that has the complexity equal or lower than O(logn). With n loop and each loop costs O(logn) we have the complexity O(nlogn), which is acceptable. Using linked list and binary search is one of the possible ways. But If you know Python, this problem can be solved in 10 lines of code, using insort method from bisect module.

Implementation: Python 3

import bisect

n = int(input())
l = []
for _ in range(n):
ai = int(input())
bisect.insort(l, ai)
if len(l) % 2 == 0:
print('%.1f' % ((l[len(l)//2-1]+l[len(l)//2])/2))
else:
print('%.1f' % (l[len(l)//2]))


## Problem: Separate the Numbers

*Difficulty: Easy

Problem:
separate-the-numbers-english

Approach:
Here’s how I did it, and I think example is the best way to explain it:
Example:
s = 1011121314
Start with first number = 10, next is 11, next is 12, …..
Eventually, return True
The maximum length of first number will be equal len(s) // 2 (if length s is even), or len(s) // 2 + 1 (length s is odd)
Let’s take another example:
10000001000001
First number: 1, next 0 => False
First number: 10, next 00=> False
First number: 100, next 000=>False
First number: 1000. next 000=>False
….
First number:1000000 next 1000001 => True
Hope you get the idea :>

Implementation: Python 3

def is_beautiful(number):
if number == '' or number[0] == '0' or len(number) <= 2:
return [False]
bound = len(number) // 2
start_length = 1
while start_length <= bound:
first_str = number[:start_length]
first_int = int(first_str)
i = start_length
try:
while i < len(number):
next = next_str(i, first_str, first_int, number)
if next is None:
break
else:
changed = False
next_1, next_2 = next
if int(next_1) == first_int+1:
first_str = next_1
first_int = int(next_1)
i += len(next_1)
changed = True
else:
if next_2:
if int(next_2) == first_int+1:
first_str = next_2
first_int = int(next_2)
i += len(next_2)
changed = True
# cant found next number
if not changed:
break
# check out of bound
if i > len(number):
break
# all numbers statisfy the condition
if i == len(number):
return True, number[:start_length]
except Exception:
pass
start_length += 1
return [False]

def next_str(i, first_str, first_int , number):
# get the next number
# check if it has equal or longer length
# return two next, but only one of them is usable
next_1 = ""
next_2 = ""
if i < len(number):
if number[i] == '0':
return None
else:
if i + len(first_str) <= len(number):
next_1 = number[i:i+len(first_str)]
if i + len(first_str) + 1 <= len(number):
next_2 = number[i:i+len(first_str)+1]
return next_1, next_2
return None

def main():
t = int(input())
for _ in range(t):
number = str(input().strip())
result = is_beautiful(number)
if result[0]:
print('YES', result[1])
else:
print('NO')

if __name__ == '__main__':
main()


## Problem: Making Anagrams

*Difficulty: Easy

Problem:

ctci-making-anagrams-english

Approach: To be able to make anagrams from two string, we have to find their common characters first. For example, if we have abccd and cdcc, then their common characters is c and d. Then we build two string contains only character that is in both string a and string b. In the previous example, string a = ccd and string b = cdcc. The last thing we need to do is make them anagrams. We do that by iterating through either string a or string b, with each character d, if there are more d in string a than string b, we remove d from a to make the number of d equal in both a and b. In our example, string b will remove 1 ‘c’, then a = ccd and b = dcc. Notice that we don’t have to do this on string, we rather do this on dictionary of string. Since the input only contains lower English alphabet, the maximum size of the dictionary will contain only 26 keys and 26 corresponding values. If key ‘c’ in a has higher value than key ‘c’ in b, then set its value to ‘c’ in b.

Implementation: Python 2.7

from collections import Counter

def make_anagrams(a, b):
a_set = set(list(a))
b_set = set(list(b))
a_counter = Counter()
b_counter = Counter()
# get char in common
for c in a:
if c in b_set:
a_counter[c] += 1
for c in b:
if c in a_set:
b_counter[c] += 1
# make anagrams
for key in a_counter.keys():
a_val = a_counter.get(key)
b_val = b_counter.get(key)
if a_val > b_val:
a_counter[key] = b_val
else:
b_counter[key] = a_val
# calculate removed char
a_lost = len(a) - sum([a_counter.get(x) for x in a_counter.keys()])
b_lost = len(b) - sum([b_counter.get(x) for x in b_counter.keys()])
return a_lost + b_lost

if __name__ == '__main__':
a = input().strip()
b = input().strip()
print(make_anagrams(a, b))


## Problem: Arrays Left Rotation

• Difficulty: Easy

Problem description:
Array Left Rotation pdf

All approaching ideas is inspired by Python.
Approach: The first thing come in my mind is using a for loop, using Python list slice notation. But it’s too expensive both in computing muscle and memory usage. With the constraints, it will get TLE. Another approach is using modular arithmetic. Basically, rotate array d times means that we start iterating at index d. We have to use modular arithmetic to wrap around the array in case of reaching the end of array but still haven’t iterated through all elements yet.

Implementation: Python 3

def rotate(arr, d):
count = 0
start = d % len(arr)
while count < len(arr):
print(arr[start], end=' ')
count += 1
start = (start + 1) % len(arr)
print()

if __name__ == '__main__':
n, d = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
rotate(arr, d)


## Problem: Word Boggle

*Difficulty: Medium

Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
boggle[][]   = {{'G','I','Z'},
{'U','E','K'},
{'Q','S','E'}};

Output:  Following words of dictionary are present
GEEKS, QUIZ



Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains an integer x denoting the no of words in the dictionary. Then in the next line are x space separated strings denoting the contents of the dictinory. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.

Output:
For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.

Constraints:
1<=T<=10
1<=x<=10
1<=n,m<=7

Example:
Input:

1
4
GEEKS FOR QUIZ GO
3 3
G I Z U E K Q S E

Output:
GEEKS QUIZ

*Approach: This problem is almost the same with this.
The mechanism gonna be used here is back tracking. There are only two main parts in the algorithm:

• With each cell in boggle matrix (two for loops)
• Check all possible words that can be generated with that cell
• While generating, if a generated word can be found in dictionary, add to result
• if the length of generated word equal the length of longest word in dictionary, return (base case)
• After getting all words, put them into a set to eliminate duplicate words, then sorted them alphabetically before output

Suppose max_level is the length of longest word in dictionary, as soon as the length of a generated word exceeds max_level, we return. Why? Because if we still continue generating, there is no word will match anything in dictionary.

Implementation: Python 2.7

from __future__ import print_function

def generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word):
visited_cells.append((x, y))
word += boggle[x][y]
#print word
if word in dictionary:
result.append(word)
eight_directions = ((x+1, y), (x-1, y), (x, y+1), (x, y-1),
(x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1))
eight_directions = [(new_x,new_y) for new_x,new_y in eight_directions
if in_bound(new_x, new_y, boggle) and (new_x, new_y) not in visited_cells]
if level > max_level:
return
for new_x, new_y in eight_directions:
generate_words(new_x, new_y, dictionary, boggle,
visited_cells, level+1, max_level, result, word)
visited_cells.pop()

def find_all_possible_words(dictionary, boggle):
max_level = get_max_level(dictionary)
overall_result = []
for x in xrange(len(boggle)):
for y in xrange(len(boggle[x])):
result = []
visited_cells = []
level = 0
word = ""
generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word)
if result:
overall_result.extend(result)
overall_result = set(overall_result)
overall_result = list(sorted(overall_result))
if overall_result:
print(*overall_result, sep=" ")
else:
print(-1)

def get_max_level(dictionary):
return max(len(x) for x in dictionary)

def in_bound(x, y, boggle):
return (x >= 0 and x < len(boggle)) and (y >= 0 and y < (len(boggle[0])))

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
dictionary = raw_input().strip().split()
n, m = map(int, raw_input().strip().split())
boggle = []
temp = raw_input().strip().split()
for i in range(0, len(temp), m):
boggle.append(temp[i:i+m])
#print(dictionary)
#print(boggle)
find_all_possible_words(dictionary, boggle)


c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r