## Directi Interview Questions

- 0of 0 votes
You are given a rooted tree. The tree is not necessarily binary. The tree contains N nodes, labeled 1 to N. You are given the tree in the form of an array P[1..N] of size N. P[i] denotes label of the parent of node labeled i. For clarity, you may assume that the tree satisfies the following conditions.

The root of the tree is labeled 1. Hence P[1] is set to 0.

The parent of node T will always have a label less than T. Hence P[i] < i will always be true.

All nodes contain a mutable value (or, more simply, a variable), which is initially set to 0.

You are asked to perform several operations of the following type

ADD X Y: add Y to the value at node X.

ADDUP X Y: add Y to the value at node X. Then, add Y to the value at P[X] (i.e. the parent of X). The, add Y to the value at P[P[X]] (i.e. the parent of P[X]).. and so on, till you add Y to the value at root.

After you have performed all the given operations, you are asked to answer several queries of the following type

VAL X: print the value at node X.

VALTREE X: print the sum of values at all nodes in the subtree rooted at X (including X).

Input

The first line of input contains the number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains the numbers N, M and Q respectively (separated by single space character). N depicts the number of nodes. M depicts the number of operations you must perform. Q depicts the number of queries you must answer.

The next N lines contain a number each, depicting the array P[1..N]. Of course the number on the first such line is always 0.

The next M lines contain description of the respective operation. An operation will be either "ADD X Y" or "ADDUP X Y" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the operations.

After the operations, the next Q lines contain description of the queries. A query will be either "VAL X" or "VALTREE X" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the queries.

Output

Print the result of each query on a line by itself. Since the answer for some queries may be too large, please print the result modulo 1,000,000,007. Do not print any blank lines between test cases.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 50000

1 ≤ M ≤ 50000

1 ≤ Q ≤ 50000

1 ≤ X ≤ N

1 ≤ Y ≤ 50000

The input file will be smaller than 2 MB.

Sample Input

2

5 5 3

0

1

1

1

3

ADD 1 10

ADD 2 20

ADD 3 30

ADD 4 40

ADDUP 5 50

VAL 3

VALTREE 3

VALTREE 1

7 4 5

0

1

2

2

2

1

2

ADD 6 76

ADDUP 1 49

ADD 4 48

ADDUP 2 59

VALTREE 1

VALTREE 5

VAL 5

VALTREE 2

VAL 2

Sample Output

80

130

250

291

0

0

107

59

Explanation

In the first sample case, at the end of app the operations, the values at each of the nodes is as follows

1: 60

2: 20

3: 80

4: 40

5: 50

Also, the sum of the values of all the nodes in the subtree rooted at each of the nodes is as follows

1: 250

2: 20

3: 130

4: 40

5: 50

- 0of 0 votes
You are given a grid with 3 rows and N columns. Each cell in the grid contains the value 0 initially. You perform several operations of the following type on the grid

Pick a row, say r. Pick a start column and end column, say s and e. Of course 1 ≤ s ≤ e ≤ N. Now, set all values in the grid in row r, from column s to column e to 1.

After you perform all the operations, you wish to find subgrids in this grid (or rectangles, if you please) which contain only 1s. Most importantly, you wish to find the rectangle that has the largest area. Print the area of this rectangle.

Input

The first line of input contains a number T, the number of test cases. The first line of each test case contains the number N and M respectively, separated by a single space. N is the number of columns in the grid. M is the number of operations you perform on the grid. Each of the next M lines contain three integers R, C1 and C2 respectively to describe the operation. R is the row in which the operation is performed. C1 and C2 are the start and end columns respectively. You may assume that 1 ≤ C1 ≤ C2 ≤ N.

- 1of 1 vote
You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum.

You can only choose consecutive toffee packets to put in a box.

Input

The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains two space separated integers N, M denoting the number of toffee packets and the number of boxes respectively. The second line of each test case contains N space separated integers c1, c2, ..., cN where ci denotes the number of the toffees in the ith toffee packet.

Output

For each test case, output a single line containing the maximum number of toffees in a box. Also, output -1 if such an assignment of toffee packets to boxes is not possible.

Constraints

1 ≤ T ≤ 20

1 ≤ N,K ≤ 100000

1 ≤ ci ≤ 1000

Example

Input:

1

4 2

10 3 5 7

Output:

13

Explanation

Below are the possible assignments of toffee packets to boxes.

10 [3 5 7]

10 3 [5 7]

10 3 5 [7]

For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13

- 0of 0 votes
Amr bought a new video game "Guess Your Way Out!". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.

Let's index all the leaf nodes from the left to the right from 1 to 2^h. The exit is located at some node n where 1 ≤ n ≤ 2^h, the player doesn't know where the exit is so he has to guess his way out!

Amr follows simple algorithm to choose the path. Let's consider infinite command string "LRLRLRLRL..." (consisting of alternating characters 'L' and 'R'). Amr sequentially executes the characters of the string using following rules:

Character 'L' means "go to the left child of the current node";

Character 'R' means "go to the right child of the current node";

If the destination node is already visited, Amr skips current command, otherwise he moves to the destination node;

If Amr skipped two consecutive commands, he goes back to the parent of the current node

before executing next command;

If he reached a leaf node that is not the exit, he returns to the parent of the current

node;

If he reaches an exit, the game is finished.

Now Amr wonders, if he follows this algorithm, how many nodes he is going to visit before reaching the exit?

Input

First Line contains T the number of test cases

The next T lines contains 2 integers h, n

Output

Output T lines each containing an integer representing the number of nodes (excluding the exit node) Amr is going to visit before reaching the exit by following this algorithm.

Constraints

1 ≤ T ≤ 10

1 ≤ h ≤ 50

1 ≤ n ≤ 2^h

Example

Input:

1

2 2

Output:

2

Explanation

Example case 1. Amr would visit first root node then root->left node and then go to the root->left->right node which is the exit. hence 2 nodes visited before reaching the exit

- 0of 0 votes
You are walking down the escalator to catch a subway train. The escalator itself moves at a speed of Ve meters per minute. You can walk down the escalator at a relative speed of Vy meters per minute. The length of the escalator is L meters. Trains arrive T minutes apart. Let t be the time between your arrival to the station if you stand still on the escalator and the arrival of the last train before your arrival. Assume that t is a random variable uniformly distributed between 0 and T. Return the probability of catching an earlier train if you choose to walk down the escalator instead of standing still on it.

Input :

The first line of the input contains an integer Tc denoting the number of test cases. Each test case contains the following 4 lines

Ve - velocity of escalator

Vy - your relative velocity with the escalator

L - length of escalator

T - Time Period of Trains

Output

For each test case, output a single line containing the expected probability having an absolute or relative error less than 10^-6.

Constraints

0 ≤ Tc ≤ 5 * 10 ^ 7

1 ≤ Ve ≤ 1000

1 ≤ Vy ≤ 1000

1 ≤ L ≤ 10 ^ 5

1 ≤ T ≤ 10 ^ 6

Example

Input:

2

10

10

20

2

10

10

100

4

Output:

0.5

1.0

Explanation

Example case 1. If you stand still, it'll take you 20/10 = 2 minutes to reach the bottom of the escalator. If you choose to walk, it'll make you 20/(10+10) = 1 minute. In the second case you save 1 minute and in 50% of the cases it'll allow you to catch an earlier train.

Example Case 2. Here, if you choose to walk instead of stand still, you will save 5 minutes and you will certainly be guaranteed to catch an earlier train.

- 4of 4 votes
Given an integer array which represents the heights of adjacent vertical bars standing on the ground.

The width of each bar is 1. Now you have to pick two bars and remove all the remaining such that when

rain falls the water collected between two bars is maximum. Note that the distance between bars

remains the same after removing the remaining bars.

eg:

1. [10,5,6,12,14] ans: 30 (10*3)

2. [3 16 10 5 6 12 20 18] ans: 80 (16*(number of integers between 16 and 18)).

- 0of 0 votes
Design a data structure to support following operation:

Insert, delete, search and min difference

Time complexity of finding min Difference should be less than O(log n).

- 1of 1 vote
You are given an array A[] with n elements. You are given S[], E[] and H[] array with each M elements.

Apply an operation such that all the elements from A[ S[i] ] and A[ E[i] ] will be less than H[i].

Example :

given array A[] = [2,4,8,6,7]

S[0] = 1

E[0] = 4

H[0] = 5

So, after doing an operation, the resulting array is A[] = [ 2,4,5,5,5]

Thus, u need to do the same thing for all i.

After doing this, find out the maximum element in the array.

- 1of 1 vote
There is a 2D grid and there are two players P1 and P2. Their x,y positions are given. Then there are N gems on the grid and their positions are also given. The two players together are supposed to collect the gems in the given sequence making minimum moves (movement in all 8 directions is considered as 1 move). Note: the gems should be collected in the given order by either one of the players and then their position then becomes the position of the gem.

- 0of 0 votes
You are given a large array of 10,000,000 bits. Each bit is initially 0. You perform several operations of the type "Flip all the bits between start_index and end_index, inclusive". Given a sequence of several such operations, perform all the operations on the array. Finally, split the array into sets of 4 bits - first four, next four, then next four and so on. Each set can represent a hexadecimal integer. There will be exactly 2,500,000 hexadecimal integers. Calculate the frequency of each of the hexadecimal integers from '0' to 'f' among the 2,500,000 integers, and print it. See Input / Output and explanation of Sample Input / Output for clarity.

Input

The first line of input contains an integer T (1 ≤ T ≤ 10), the number of test cases. Then follows the description of T test cases. You should assume that the array has exactly 10,000,000 bits and that the bits are all unset at the start of each test case. The first line of each test case contains an integer N (1 ≤ N ≤ 10,000), the number of operations performed. The next N lines contain two integers separated by a space, the start_index and end_index for the respective operation. Note that the flip operation is performed from start_index to end_index, inclusive. Also, the array is 1-indexed - meaning, the smallest index is 1 and the largest index is 10,000,000.

Output

For each test case, output 16 integers on a single line, separated by single space characters. The first integer should represent the number of times 0 occurs among the 2,500,000 hexadecimal integers created according to the problem statement. The second integer should represent the number of times 1 occurs among the 2,500,000 hexadecimal integers created according to the problem statement, and so on.

Constraints

1 ≤ start_index ≤ end_index

start_index ≤ end_index ≤ 10,000,000

Sample Input

2

2

1 4

9999997 10000000

2

3 6

5 8

Sample Output

2499998 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2

2499998 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0

Explanation

In the first test case, after we perform the two operations and split the array into 2,500,000 groups of 4 bits, the first and the last group will have all 4 bits set - representing 'f' hexadecimal digit. All the other groups will have all 4 bits unset - representing '0' hexadecimal digit.

In the second test case, after we perform the two operations and split the array into 2,500,000 groups of 4 bits, the first two groups will have the state 0011. This represents the hexadecimal digit '3'. All the other groups will have all the 4 bits unset - representing '0' hexadecimal digit.

- 0of 0 votes
write a shell script to append the contents of one file to another file. If any word is common in both files that need not be appended.

- 0of 0 votes
There is a log file with writes processes details in the below mentioned format .

---

Process_Name - RID(MB) - Time

---

It is updated every second. write bash script to report processes which is having RID greater than 30.

NB: Avoid reading the file line by line as it is very huge and updated every second

- 5of 5 votes
`A tree is given in which each edge is having some weight associated with it and you are given a number K. So starting from root in K-steps how much maximum weight you can collect. You can traverse in any direction either from parent to child or child to parent. You can visit a node multiple times. Eg: O 5/ \ 6 O O 24/ 1 \ \11 For K=1, ans=6 For K=2, ans=29 etc..`

- 1of 1 vote
Given row on N house, each is marked either R or B. And each house having some gems. You have to collect gems from these house with some constraint:

You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses)

each time you take gem from one house, you will multiply gems received with gems currently, you have.

You have to choose continuous houses.

You have to return start point and end point of house (remember this should be continuous )

- 5of 5 votes
you have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.

You have to return sum of max M subarray of size K (non-overlapping)

N = 7, M = 3 , K = 1

A={2 10 7 18 5 33 0} = 61 — subsets are: 33, 18, 10 (top M of size K)

M=2,K=2

{3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2

- 1of 1 vote
There are different buildings standing close to each other. These are of same width but different height.

Suppose if rainfall happens, what will be the volume of water that get trapped on top of all these buildings together. ?

INPUT (Example)

No: of buildings : 4

heights of the buildings(in any units): 3 4 3 4

- 2of 2 votes
You have a set of N objects. Each of these objects have certain properties associated with them. A property is represented by a (key, value) pair. For example, assume you have the following two objects.

Tower:

{

(height, 100), (weight, 50),

(xposition, 25), (yposition, 36)

}

Tree:

{

(area, 100), (noofleaves, 500),

(height, 25), (yposition, 36)

}

Each object you have, will have at most 4 properties. An object will have at least 1 property. Note, from the two objects above, that it is not necessary for key in the properties to be same for all the objects. Also, it is not necessary for the key to be different.

Now, given N such objects, you wish to answer M queries. Each query is represented by a set of properties (again, at most 4 properties, and at least 1 property). The answer for the query is the number of objects in the set, that have all the given properties. Two properties are considered equal iff both the key and the value match.

For example, if you have the above two objects, then the answer for the following queries is

Query:

{ (height, 100), (yposition, 36) }

Answer:

1 // matches Tower, but not Tree

Query:

{ (yposition, 36) }

Answer:

2 // matches both Tower and Tree

Query:

{ (height, 100), (noofleaves, 500) }

Answer:

0 // neither Tower, not Tree satisfy both properties

Input

The first line of input contains N and M. This is followed by the description of the N objects. The description of the i-th object will start by a number k, which is the number of properties associated with the object. The next k lines contain two space separated strings - the property key and the property value. Note that the property value is not necessarily an integer (although this is so for the example above).

This is followed by the description of M queries. The format of a query will be exactly same to that of the objects. Check the Sample Input for clarification.

One test file will contain only one test case. A single test case may contain several queries.

Output

Print M lines. Each line must be the answer of the respective query.

Constraints

1 ≤ N ≤ 10000

1 ≤ M ≤ 100000

1 ≤ k ≤ 4

Sample Input

2 3

4

height 100a

weight 50b

xposition 25a

yposition 36b

4

area 100a

noofleaves 500

height 25

yposition 36b

3

weight 80

xposition 25a

yposition 36b

1

yposition 36b

2

xposition 25a

yposition 36b

Sample Output

0

2

1

- 0of 0 votes
You are given a rectangular grid with 2 rows and N columns. The top row is labeled 1 and the bottom row is labeled 2. The columns are labeled from 1 to N in increasing order. Each cell in the grid contains a single character.

Consider a hamiltonian walk in this grid. Meaning, pick a starting cell, say (i,j), and consider a path that starts from (i,j) and goes through every cell in the grid exactly once. Note that you can only walk to adjacent cells, or cells that you share a common edge with. There may be several such paths. Let us concatenate the characters in the order in which the cells are visited during a walk. The string formed can be called the string for the walk.

Among all the possible walks, and their respective strings, find out the lexicographically smallest string. We know that the length of the strings are all the same - to be precise, 2N. Thus, the lexicographically smallest string is simply the alphabetically smallest string if you compare the characters from left to right.

Input

The first line of input contains a number T, the number of test cases. Then follow T test cases. Each test case contains 3 lines. The first line contains the number N, the number of columns in the grid. It is well known of course that the grid contains 2 rows. The next two lines contain the description of the grid in the form of two strings; the string of N characters in row 1 from left to right and the string of N characters in row 2 from left to right, respectively. Each character will be a lowercase engish letter.

Output

Output a single line for each test case. The line must contain a string with 2N characters. This string should be the lexicographically smallest string for some hamiltonian walk in the grid.

Constraints

1 = T = 100

1 = N = 10

Sample Input

2

3

abc

def

10

ababaaabab

bababababa

Sample Output

abcfed

aaababababababababab

Explanation

In the first test the possible strings are { abcfed, adebcf, adefcb, badefc, bcfeda, cbadef, cfedab, cfebad, dabcfe, dabefc, defcba, edabcf, efcbad, fedabc, fcbade, fcbeda }. The smallest string is abcfed.

- 1of 1 vote
There is a string whose characters can only be either ‘a’, ‘b’ or ‘_’ (there can be only one ‘_’ in the string). At each step, we can modify the string as follows:

1. ‘_’ can be swapped with its adjacent character, example “a_ba” can be changed to either “_aba” or “ab_a”.

2. Two characters adjacent to ‘_’ (both on the same side of ‘_’) can be reversed along with the ‘_’ if both characters are different, example, “aa_ba” can be changed to “aaab_” but not to “_aaba” because both characters are ‘a’.

You are given two strings, the initial state and the final state (lengths will be same), you have to output the minimum number of steps required to change the string in initial state to the string in the final state.

example:

input: a_b ab_

output: 1

input: abaa_a b_aaaa

output: 4

reason for example 2:- abaa_a -> aba_aa -> ab_aaa -> _baaaa -> b_aaaa

- 1of 1 vote
Given a stream of characters (stream is increasing char by char), check if newly

formed 10character word is present in already parsed/scanned stream. Print such

repeating streams lexicographically at the end.

- 1of 1 vote
There is a rectangle with left bottom as (0, 0) and right up as (x, y). There are n circles such that their centers are inside the rectangle. Radius of each circle is r. Now we need to find out if it is possible that we can move from (0, 0) to (x, y) without touching the circle. We can move freely anywhere.

- 1of 1 vote
We need to make a string of size n. Each character of the string is either ‘R’, ‘B’ or ‘G’. In the final string there needs to be at least r number of ‘R’, at least b number of ‘B’ and at least g number of ‘G’ (such that r + g + b <= n). We need to find number of such strings possible.

For example,

n = 4, r = 1, b = 1, g = 1.

Output:

36

- 0of 0 votes
You are given two integer arrays A and B .

1<=i<=len(A) so i is iterator of array A

1<=j<=len(B) so j is iterator of array B

find all the pairs(i,j) such that : i < j and A[i]>B[j]

- 2of 2 votes
There is a compressed string eg. ”ab2c3”, the string has lowercase characters and numbers. We can uncompress the given string as follows: whenever we get a number “n” in the string, the portion of the string before the number will repeat “n” times. So in the above example, we get a 2, so string will become “ababc3”, now we get a 3, so final string will be “ababcababcababc”.

Given a compressed string and a number k, you have to output the k’th character in the uncompressed string.

1 <= length of string <= 1500

1 <= n <= 1000

1 <= k < 2^31

example:

input: ab2c3 10

output: c

- 0of 0 votes
Question was very similar to this one

http://www.hackerearth.com/thoughtworks-hiring-challenge/algorithm/swap-it-2/

Bob loves sorting very much. He is always thinking of new ways to sort an array.His friend Ram gives him a challenging task.He gives Bob an array and an integer K .The challenge is to produce the lexicographical minimal array after at most K-swaps.Only consecutive pairs of elements can be swapped.Help Bob in returning the lexicographical minimal array possible after at most K-swaps.

Input: The first line contains an integer T i.e. the number of Test cases. T test cases follow. Each test case has 2 lines. The first line contains N(number of elements in array) and K(number of swaps).The second line contains n integers of the array.

Output: Print the lexicographical minimal array.

Constraints:

1<=T<=10

1<=N,K<=1000

1<=A[i]<=1000000

Sample Input (Plaintext Link)

2

3 2

5 3 1

5 3

8 9 11 2 1

Sample Output (Plaintext Link)

1 5 3

2 8 9 11 1

Explanation

After swap 1:

5 1 3

After swap 2:

1 5 3

{1,5,3} is lexicographically minimal than {5,1,3}

Example 2:

Swap 1: 8 9 2 11 1

Swap 2: 8 2 9 11 1

Swap 3: 2 8 9 11 1

- -1of 1 vote
an array is given.for each number at index i,find a number at index j such that aj 3.N number of books is given.each books is having some pages pi.How books should be alloted to m students so that maximum number of pages alloted to a student is minimum.Each student will read atleast one book.and one book can be read by only one person.find minimum value.

- 0of 0 votes
Given a set of restaurants (the number being quite large) and its geographical location(x,y) , you are allowed to do an significant amount of pre-processing on it. Now suppose there are x customers located at position (s,t), design an efficient algorithm to find the k nearest restaurants to these customers.

- 1of 1 vote
A ternary string consists of only a, b, c following the given 3 rules

1. a's cannot be consecutive.

2.b can appear only once.

Find the nuber of possible ternary string of length n.

- 2of 2 votes
how to do this round1 question 1:

http://www.geeksforgeeks.org/directi-interview-set-5-campus/

A string can contain only a, b or c. There cannot be 2 consecutive same character. First and last character cannot be same. Now given a string with ‘a’, ‘b’, ‘c’ or ‘?’. We need to find the string replacing ‘?’ that satisfy the above conditions. For multiple answer display lexicographically smallest string. For no answer possible display “Not Possible”.

- 2of 2 votes
There is a binary tree. We are given 3 nodes a, b and c. We need to find a node in the tree such that we remove all edge from that node we get a, b and c in three different trees