CareerCup

convert a number m to n with minimum operations. The operations allowed were -1 and *2.
For Eg : 4 and 6. Answer is 2.
1st operation : -1 -> 4-1 = 3.
2nd operation : * -> 3 * 2 =6.

How many Fibonacci numbers exists less than a given number n.Can you find a function in terms of n , to get the number of fibonacci number less than n.
Example : n = 6
Answer: 6 as (0, 1, 1, 2, 3, 5)

You are given two arrays of length M and N having elements in range 0-9.Your task is to create maximum number of length K from elements of these two arrays such that relative order of elements is same in the final number as in the array, they are taken from i.e. If two elements a,b are taken from array1 and and a comes before b in array1 so in the final number a should come before b (Relative order kept same) .
Example: N=4 and M =6
Array1 = { 3 , 4 , 6,5}
Array2 ={9,1,2,5,8,3}
Suppose K = 5, then number will be {9,8,6,5,3}
You can see {9,8,3} are taken from array2 in the same order as they are in Array2. Similarly {6,5} are taken from Array1 in the same order and number 98653 is maximum possible number.

Given three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.

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.

Find minimum number of swaps to convert one binary array to another.
Note: It is always possible.
You are given two integer array having only 0's and 1's. Find minimum number of swaps to convert array1 to array2.
NOTE: You can only swap adjacent elements.

Sparse number is an integer if there are no adjacent 1 in it's binary representation.
Like: 5 -> 101 (no adjacent 1)
9 -> 1001 (no adjacent 1)
while 6-> 110 is not sparse number.
Now you are given an integer find the NEXT BIGGER sparse number.Please mind 'it is next bigger'.

You are given heights of n candles .
First day you lit one candle
second day you need to lit two candles
Third day you need to lit three candles
..........
........
till possible.
After lighting candles the height of candles deduced by 1 each day.You can also extinguish any candle you want but only at the end of day.
So you need to tell the maximum number number of days , you can carry on lighting the candles.
Example : there are three candles of heights {2 , 2 ,2 }
Answer : 3
1.You light first candle on day one. heights -> {1,2,2}
2.You light second and third and extinguish first one . heights ->{1, 1,1}
3.You light all the candles. heights -{0,0,0}

Given an array A[1...N] of positive integers, you have to sort it in ascending order in the following manner : In every operation, select any 2 non-overlapping sub-arrays of equal length and swap them. i.e, select two sub-arrays A[i...(i+k-1)] and A[j...(j+k-1)] such that i+k-1< j and swap A[i] with A[j], A[i+1] with A[j+1] ... and A[i+k-1] with A[j+k-1].

**Example:**
For n=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.
How can we figure out minimum number of swaps in most effective way ?

(Variant of Children-Sum Problem better than O(n^2))
Given a tree, implement a function which replaces a node’s value with the sum of all its childrens’ value, considering only those children whose value is less than than the main node’s value.
Eg: input = 60->50->80->40 , output = 90->40->40->0

Given a function rev(int i) which reverses the segment of array ar[] from 0-i, Implement a function sort() using rev().

Find the top k frequent items in a stream of numbers .

Suppose you receive 10 million mails in 10 seconds. How will you process them and find what might be the reasons to receive these many mails. Discuss different approaches to find the reasons.

you have experience with a 3x3 Sudoku.Think about 2*2 sudoku:

The array has 4 rows and 4 columns.
The numbers 1, 2, 3 and 4, each appears exactly once in each row.
The numbers 1, 2, 3 and 4, each appears exactly once in each column.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 1, 2.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 1, 2 and columns 3, 4.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 1, 2.
The numbers 1, 2, 3 and 4, each appears exactly once in the 2x2 square formed by the intersection of rows 3, 4 and columns 3, 4.
Your task is:
1. Count all possible different solutions of the 2*2 sudoku.
2.Print all solutions.
3.Store all solutions.

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]

given a pre and post order kindof a traversal (2 arrays) create an n-ary treee out of it with struct of the form :


struct node {
int data;
struct node *child[MAX];
int child_num;
}

given matrix like :

a b e d
b c f e
a b d d
….

find the longest path of consecutive alphabets given a starting alphabet. You can move in all 8 directions. for eg. a->b(right)->c(down)->d(diagnal down)… len = 4 , find max such len

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

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.

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

Find the unique number that is present only once in array while all the others are present three times.
Example: 2,3,5,1,2,2,5,3,5,3
Answer : 1 as 2,3,5 are repeated three times
Complexity should be better than O(nlogn)

You are given a string S. Each character of S is either ‘a’, or ‘b’. You wish to reverse exactly one sub-string of S such that the new string is lexicographically smaller than all the other strings that you can get by reversing exactly one sub-string.
For example, given ‘abab’, you may choose to reverse the substring ‘ab’ that starts from index 2 (0-based). This gives you the string ‘abba’. But, if you choose the reverse the substring ‘ba’ starting from index 1, you will get ‘aabb’. There is no way of getting a smaller string, hence reversing the substring in the range [1, 2] is optimal.

Input:
First line contains a number T, the number of test cases.
Each test case contains a single string S. The characters of the string will be from the set { a, b }.

Output:
For each test case, print two numbers separated by comma; for example “x,y” (without the quotes and without any additional whitespace). “x,y” describe the starting index (0-based) and ending index respectively of the substring that must be reversed in order to acheive the smallest lexicographical string. If there are multiple possible answers, print the one with the smallest ‘x’. If there are still multiple answers possible, print the one with the smallest ‘y’.

Constraints:
1 ? T ? 100
1 ? length of S ? 1000

Sample Input:
5
abab
abba
bbaa
aaaa
babaabba

Sample Output:
1,2
1,3
0,3
0,0
0,4

Given a number M (N-digit integer) and K-swap operations(a swap
operation can swap 2 digits), devise an algorithm to get the maximum possible integer?
Examples:
M = 132 K = 1 output = 312
M = 132 K = 2 output = 321
M = 7899 k = 2 output = 9987
M = 8799 and K = 2 output = 9987

Write a recursive method to get the multiplication of two numbers such that there are minimum number of addition operations.

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]

They conducted a hiring round and this was asked there ?

Hi friends This question was asked in recent hiring challenge at hackerearth , that is over now,Please discuss your strategies.I am not able to devise algorithm please provide some hints to solve it.

Pulkit is really good at maths. Recently, he came to know about a problem on matrices. Amazed by the problem he got, he asked Ashish the same problem. Ashish also being good at maths solved the problem within 5 minutes. Now, its your time to solve the problem.

You will be given n*m binary matrix. You need to tell if it is possible to delete a column such that after deleting that column, rows of the matrix will be unique. If yes than print "Yes" else print "No".

[Input]

First line contains an integer t denoting no.of test cases.

Next line contains 2 integers n and m denoting no.of rows and columns.

Next n line contains binary string of length m each.

[Output]

For each test case output "Yes" or "No".

[Constraints]

1<=t<=100

1<=n<=1000

2<=m<=1000

Sample Input (Plaintext Link)

2

3 3

101

000

100

2 2

11

11

Sample Output (Plaintext Link)

Yes

No

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

Consider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.



Input:

The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.



Output:

Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.



Constraints:

1 <= T <= 10000

4 <= N <= 10^9

1 <= K <= N



Sample Input:

3

4 1

5 2

5 3



Sample Output:

2

5

0



Explanation:

For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order).

For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.

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

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.

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.

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

we have website having several web-pages. And also there are lot many user who are accessing the web-site.
say user 1 has access pattern : x->y->z->a->b->c->d->e->f
user 2 has access pattern : z->a->b->c->d
user 3 has access pattern : y->z->a->b->c->d
user 4 has access pattern : a->b->c->d
and list goes on for lot many users which are finite and numbered.
Now the question is we have to determine the top 3 most occurring k-Page-sequence.
for the above example result will be : (k=3) a->b->c , b->c->d , z->a->b.

Given an array of heights of poles. Find the no of poles which are visible if you are standing at the ith pole

Traverse a given 2D matrix from given source to destination in such way that every cell should be visited exactly one time (we have to cover all cells of matrix exactly once and have to reach at destination).

Given N sets of integers, remove some sets so that the remaining all sets are disjoint with one another. Find the optimal solution so that the number of sets remaining at the end is maximum

If in a relation there are multiple duplicate rows . Your task is to delete one duplicate row.

a1 a2
1 3
1 3
2 4
3 5
3 5
3 5
after deletion
a1 a2
1 3
2 4
3 5
3 5

3

Given stock price of Amazon for some consecutive days. Need to find the maximum span of each day’s stock price. Span is the amount of days before the given day where the stock price is less than that of given day

E.g i/p = {2,4,6,9,5,1}
o/p= { -1,1,2,3,2,-1}

Given a matrix of characters and a string, find whether the string can be obtained from the matrix. From each character in the matrix, we can move up/down/right/left. for example, if the matrix[3][4] is

o f a s
l l q w
z o w k

and the string is follow, then the function should return true.

Given 2 strings str1 and str2. What is the efficient way to navigate from str1 to str2? The constraints are i) a string can be changed to another string by changing only one character. ii) all the intermediate strings must be present in dictionary. If not possible, return “not possible to navigate from str1 to str2″. (pre-processing is allowed and enough memory is available). for example: str1 = feel and str2 = pelt, then the navigation is feel -> fell -> felt -> pelt

Generate all numbers in ascending order which are having factors as 2,3 and 5. Discuss various approaches.

Given a Binary tree and a arbirary node of that tree , find all the nodes at a Distance of K from that Node .Nodes DON’T have parent pointers

You are given pairs of numbers. In a pair the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b<c.So you can form a long chain in the similar fashion. Find the longest chain which can be formed

Suppose we have two functions void g() and void h(). The function h() has been called somewhere in the body of g(). Now using a debugger, we find that that the program crashes as soon as the return statement in h() ( at the end of function h() ) is executed. There is nothing syntactically wrong with the program. How will you debug the code ?

Starting and ending co-ordinates of one-dimensional line segments are given. Find the co-ordinates of longest line segment that can be formed from these segments. Write two functions addSegment() and findMaxSegment(). He asked to write a perfect C code.

Suppose there were n numbers in an array S1, S2, S3, S4.......SN rearrange them in a such a way that they satisfy bellow property.
S1<S2>S3<S4>......

DNA sequence(a string) is given (let say strDNA) and another string to search for(let say strPat). You have to find the minimum length window in strDNA where strPat is subsequence(Write code).

You are given 2 convex hulls. Develop an algorithm to find all the common points; that is the points that lie in the intersection of these 2 convex hulls. Write code.

You are given two string named str1 and str2. Your task is to find the minimum window in str1 which contains all characters from string str2.

Given an array consisting of both positive and negative numbers,
rearrange the elements such that positive and negative numbers are
placed alternatively, constraints are that it should be in-place and
order of elements should not change.

As we know facebook always asks questions from graph theory he asked me this problem to code-

there is a grid of n*n where each cell represent an Island or and some of these are very dangerous so u have to avoid these during path selections.You can move up,down,left ,right.You are given your starting position ,positions of dangerous Islands and position some specific Islands.Your task is to deliver a message to all the specific Islands in minimum number of moves to all specific Islands(NOTE- there are also chances that no moves are possible to cover all specific Island ,in such case you have to tell "NOT POSSIBLE TO DELIVER ALL ",otherwise output minimum moves).

Write code to print all different paths in an undirected graph from a given source to destination with no loop(any node can be at most once in a path ).

Given a undirected graph, source and destination, write the code to find the total number of distinct nodes visited, considering all possible paths.

you are given n-strings 1you have to find whether a chain can be termed with all the strings given number n? A chain can be formed b/w strings if last char of the 1st string matches with 1st char of second string. For example you are given

number of strings = 3

first string=sdfg

second string=dfgs

third string=ghjhk

they can be concatenated as ->

second first third

dfgs sdfg ghjhk (characters at concatenation points are same)

so concatenated string is-dfgsdfghjhk

Given a weighted directed graph with n vertices where edge weights are integers (positive, zero, or
negative), determining whether there are paths of arbitrarily large weight can be performed in time
(a) O(n)
(b) O(n · log(n)) but not O(n)
(c) O(n1.5) but not O(n log n)
(d) O(n3) but not O(n1.5)
(e) O(2n) but not O(n3)

Johnny has some difficulty memorizing the small prime numbers. So, his computer science teacher has asked him to play with the following puzzle game frequently.
The puzzle is a 3x3 board consisting of numbers from 1 to 9. The objective of the puzzle is to swap the tiles until the following final state is reached:
1 2 3
4 5 6
7 8 9
At each step, Johnny may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.
Help Johnny to find the shortest number of steps needed to reach the goal state.
Input

The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case consists of a 3x3 table describing a puzzle which Johnny would like to solve.
The input data for successive test cases is separated by a blank line.
Output

For each test case print a single line containing the shortest number of steps needed to solve the corresponding puzzle. If there is no way to reach the final state, print the number -1.
Example

Input:
2

7 3 2
4 1 5
6 8 9

9 8 5
2 4 1
3 7 6

Output:
6
-1

The Government of Byteland has decide to issue new currency notes with special protection features to so as to commemorate a great mathematician.

It has decided to issue notes summing up to N and all the sums from 1 to N should only made by selecting some of the notes in only one unique way.

With n = 5 the sets {1,1,1,1,1}, {1,2,2}, {1,1,3} are valid. Invalid sets are

-{1,1,1,2} because 2 can be made by {1,1} and {2}and also 3 by {1,1,1} and {1,2}

-{1,2,4} because all from 1 to 5 can be uniquely made but the sum is not 5.

Input

First line contains T(1<=T<=1000) the number of test cases. Each test case contains a integer N (<=10^9) in one line.
Output

Output the solution of each test case on a line.
Example

Input:
2
10
1000


Output:
1
13