Rahul Sharma
BAN USER
- 0of 2 votes
AnswersHow 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.
- Rahul Sharma in United States
Example : n = 6
Answer: 6 as (0, 1, 1, 2, 3, 5)| Report Duplicate | Flag | PURGE
Google Software Developer Algorithm - 4of 4 votes
AnswersYou 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) .
- Rahul Sharma in United States
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.| Report Duplicate | Flag | PURGE
Google Research Scientist Algorithm - 0of 0 votes
AnswersYou 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.
- Rahul Sharma in India
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.| Report Duplicate | Flag | PURGE
Directi SDE-2 Coding - 0of 0 votes
AnswersFind minimum number of swaps to convert one binary array to another.
- Rahul Sharma in United States
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.| Report Duplicate | Flag | PURGE
Adobe Software Engineer Algorithm - 4of 4 votes
AnswersSparse number is an integer if there are no adjacent 1 in it's binary representation.
- Rahul Sharma in United States
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'.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Coding - 0of 0 votes
AnswersYou are given heights of n candles .
- Rahul Sharma in India
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}| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 0of 2 votes
AnswersGiven 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].
- Rahul Sharma in India
**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 ?| Report Duplicate | Flag | PURGE
Google SDE-2 - 0of 0 votes
Answers(Variant of Children-Sum Problem better than O(n^2))
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Amazon SDE1 Coding - 0of 0 votes
AnswersFind the top k frequent items in a stream of numbers .
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer - -1of 1 vote
AnswersSuppose 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.
- Rahul Sharma in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answersyou have experience with a 3x3 Sudoku.Think about 2*2 sudoku:
- Rahul Sharma in India
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.| Report Duplicate | Flag | PURGE
Google SDE-2 - 0of 0 votes
Answersgiven matrix like :
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Amazon SDET Coding - 2of 2 votes
AnswersYou 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.
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Directi Intern Algorithm - 0of 0 votes
AnswersYou 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.
- Rahul Sharma in India
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.| Report Duplicate | Flag | PURGE
Directi Intern Coding - 1of 1 vote
AnswersThere 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:
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFind the unique number that is present only once in array while all the others are present three times.
- Rahul Sharma in India
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)| Report Duplicate | Flag | PURGE
Adobe Member Technical Staff Algorithm - 3of 3 votes
AnswersYou 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.
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 7of 7 votes
AnswersGiven a number M (N-digit integer) and K-swap operations(a swap
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Google SDE-2 Coding - 1of 1 vote
AnswersThey conducted a hiring round and this was asked there ?
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Manhattan associates SDE-2 Algorithm - 2of 2 votes
AnswersThere 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”.
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Directi SDE1 Algorithm - 0of 0 votes
AnswersConsider 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.
- Rahul Sharma in India
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.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersQuestion was very similar to this one
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Directi SDE-2 Algorithm - -1of 1 vote
Answersan 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.
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Directi SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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.
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Directi SDE1 - 0of 0 votes
Answerswe have website having several web-pages. And also there are lot many user who are accessing the web-site.
- Rahul Sharma in India
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.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersTraverse 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).
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Oracle SDE-2 Algorithm - 5of 5 votes
AnswersGiven 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
- Rahul Sharma in India
E.g i/p = {2,4,6,9,5,1}
o/p= { -1,1,2,3,2,-1}| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven 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
- Rahul Sharma in India
o f a s
l l q w
z o w k
and the string is follow, then the function should return true.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven 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
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Coding - 0of 0 votes
AnswersYou 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
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersSuppose 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 ?
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Adobe SDE-2 Compiler - 0of 0 votes
AnswersStarting 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.
- Rahul Sharma in India| Report Duplicate | Flag | PURGE
Adobe Intern Algorithm - 0of 0 votes
AnswersDNA 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).
- Rahul Sharma in United States| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 0of 0 votes
AnswersGiven an array consisting of both positive and negative numbers,
- Rahul Sharma in India
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.| Report Duplicate | Flag | PURGE
Testing / Quality Assurance - -2of 8 votes
AnswersAs we know facebook always asks questions from graph theory he asked me this problem to code-
- Rahul Sharma in India
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).| Report Duplicate | Flag | PURGE
Facebook SDE-2 Algorithm - 9of 9 votes
Answersyou 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
- Rahul Sharma in India
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| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - -1of 1 vote
AnswersGiven a weighted directed graph with n vertices where edge weights are integers (positive, zero, or
- Rahul Sharma in India
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)| Report Duplicate | Flag | PURGE
Google Software Analyst
1 Answer codechef puzzle problem
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.
- Rahul Sharma September 18, 2013
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| Flag | PURGE 1 Answer CURRENCY SETTER ALGORITHM
The Government of Byteland has decide to issue new currency notes with special protection features to so as to commemorate a great mathematician.
- Rahul Sharma May 26, 2013
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| Flag | PURGE
This is obvious. Something better ?
- Rahul Sharma December 26, 2014@naren .. sorry for that . Yes you are right .
- Rahul Sharma December 19, 2014@Victor cant it help us that there are only 'a' and 'b' . Your algorithm is a general.
- Rahul Sharma November 22, 2014but this is a very inefficient process for both time and space ?? what will be complexity of your program, can you please confirm ?
- Rahul Sharma November 21, 2014Ok but what about redundant calculations ?
- Rahul Sharma November 14, 2014It is not better than brute force but we can make it efficient by removing unwanted branches as early as possible .
- Rahul Sharma October 20, 2014Read about disjoint set data structure
- Rahul Sharma October 13, 2014before posting your solution always look at previous solutions .
- Rahul Sharma October 13, 2014I think a general solution will b of the complexity O(n^3).
1. Make a structure like
struct ds
{
int value;
int index;
};
2. Sort according to values. // This process is nlogn
3. Iterate trough all pair (A,B) // This process is O(n^2)
a).compute sum = A+B
b).search two indexes(i,j) in sorted array such that :
Array[i]+array[j]=sum // ths process is O(n) in sorted array
So complexity is O(n^3).
This can be improved using hashing.
ok
- Rahul Sharma October 10, 2014Wrong as i specified in the very first comment .
- Rahul Sharma October 10, 2014Those who are thinking for the solution based on the suffix array like :
After finding the first b at position i;
Reverse the whole string from i to last index.
Then find the first string in the suffix array.
NOTE : make sure this is not passing the following case
baababaa
According to this algo :
Suffix array will be like :
aab
aababaab
-------------
---------------
------------------
so if you chose first :
Resultant string will be :
aabbabaa
While if you chose 2nd
Resultant string will be :
aababaab (THE CORRECT ONE)
SO DEVISE AN ALGORITHM THAT PASSES THIS TEST CASE ,IF YOU ARE TRYING IT BY SUFFIX ARRAY
The very first solution comes to mind , but unfortunately it is wrong :
Example:
baabaabbaa
According to your algorithm :
1).
baa||baabbaa
aab||baabbaa
2).
baabaa||bbaa
aabaab||bbaa (ONLY THIS IS CORRECT )
3).
baabaabbaa||
aabbaabaab
HOW CAN YOU RESOLVE THESE CONFLICTS ?
HINT : DON'T TRY TO COUNT NUMBER OF 'b' AFTER 'a'.CONFLICT MAY AGAIN ARISE AND VERY INEFFICIENT.
have a look :
yougeeks.blogspot.in/2014/08/directi-interview-question-given.html
have a look and please report if u find anything incorrect :
yougeeks.blogspot.in/2014/08/directi-interview-question-given.html
It is giving wrong output for first input ......
- Rahul Sharma August 23, 2014can we do it in a better way than O(n^2) if we are goint to calculate answer for all ...
- Rahul Sharma July 26, 2014right
- Rahul Sharma May 01, 2014Sorry frnds ... BUT it was a SQL question :)
- Rahul Sharma April 30, 2014The questions are genuine .So i dont think that there should be any problem to you .
- Rahul Sharma November 26, 2013have a look it as simple at all ... if any error plz report :)
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<sstream>
#include<iostream>
#include<iomanip>
using namespace std;
inline void swapp(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
int main()
{
int n,array[400];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>array[i];
}
for(int i=0;i<n-2;i++)
{
if(array[i]>array[i+1])
{
swapp(&array[i],&array[i+1]);
}
if(array[i+1]<array[i+2])
{
swapp(&array[i+1],&array[i+2]);
}
i=i+1;
}
for(int i=0;i<n;i++)
{
cout<<array[i]<<" ";
}
}
2D
- Rahul Sharma November 22, 2013no extra space .
- Rahul Sharma October 15, 2013Order is not maintained by your solution .... look closely ..
- Rahul Sharma October 15, 2013MISSING COSTRAINTS ARE O(N) AND NO EXTRA SPACE.
- Rahul Sharma October 14, 2013Sorry i need o(n) solution... how to edit this question .. m unable to see the edit option.?
- Rahul Sharma October 14, 2013You can code assuming that n can be at most 20 and number of special islands are not more than 10.
- Rahul Sharma October 13, 2013You can code assuming that n can be at most 20 and number of special islands are not more than 10.
- Rahul Sharma October 13, 2013no you cant repeat the node in the path.
- Rahul Sharma October 09, 2013@ piyush kapoor u are right answer is d ... but what does it mean "determining whether there are paths of arbitrarily large weight " please explain..
- Rahul Sharma September 05, 2013// Addition may also be so complex :) but google can make it in interview, i think !!
/* AUTHOR @ AVANEESH KUMAR2013 ,BIET JHANSI, prmrs111@live.com */
#include<stdio.h>
#include<cstring>
#include<iostream.h>
#include<string.h>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<vector>
#include<set>
#include<complex>
#include<list>
// TOO lazy :)
using namespace std;
#define input(t) scanf("%d",&t)
#define input_ll(t) scanf("%lld",&t)
#define LL long long
#define myfor(i,a,b) for(i=a;i<=b;i++)
#define vi vector <int>
#define pb push_back
//<<<<<<<<<<<<<<<<<<<<<<<<<STARTED>>>>>>>>>>>>>>>>>>>>
vi array1;
vi array2;
int ans[79];
int n,spcarry=0,l;
int carry(int start)
{
if(start==n-1)
{
ans[start]=(array1[start]+array2[start])%10;
return (array1[start]+array2[start])/10;
}
else if(start>n-1)
{
return 0;
}
else
{
ans[start]=(array1[start]+array2[start]+carry(start+1));
if(start==0)
spcarry=ans[0]/10;
ans[start]=(array1[start]+array2[start]+carry(start+1))%10;
return (array1[start]+array2[start]+carry(start+1))/10;
}
}
int main()
{
int i,temp;
cout<<"what is the length of arrays?"<<endl;
cin>>n;
myfor(i,0,n-1)
{
cin>>temp;
array1.pb(temp);
}
myfor(i,0,n-1)
{
cin>>temp;
array2.pb(temp);
}
carry(0);
cout<<spcarry;
myfor(i,0,n-1)
cout<<ans[i];
}
use trie data structure
- Rahul Sharma April 05, 2013
RepCallaRita, techsupport at Knowledge Systems
Hi, I am an Administrative person . It is to develop and sustain an early childhood organisation. I was a teacher ...
RepShaneMMullen, SEO at IIT-D
Are you facing love life and married life problem. Contact vashikaran specialist right now. He will guide your solution with ...
RepDo you Need Voodoo Spell For love, revenge or voodoo spells for cheaters? Consult Free right away to get custom ...
RepA real dynamo when it comes to buying and selling carnival rides in Fort Lauderdale, FL. Spend several years working ...
RepAre you looking a solution for marry your love? Islamic dua to marry someone you love is the effective solution ...
RepDiscover the best online vaporizer store to buy quality vaping accessories at affordable price. Visit NY Vape Shop, specialized in ...
RepHad moderate success buying and selling weebles in Ohio. Had some great experience buying and selling wooden trains on Wall ...
RepPandit Ji is the best vashikaran expert for vashikaran mantra for girlfriend in Mumbai.It is the strongest method to ...
Repstanjachrissi, Integration Software Engineer at xyz
Hi,my name is Stanja Chrissi. I was conceived and FL. I moved on from CA and went ahead to ...
RepAre you looking for strong dua for husband love?Astrology is the perfect way to get your lost love back ...
RepHire high professional child development center in Charlotte. Pal-A-Roo’s Child Development Center is a family-owned child care facility offering ...
Rep
RepEdwin Adcox, Dev Lead at Advisory Board Company
Welcome to the best and certified exotic car rental company of USA. Here, at Prestige luxury Rentals, we offer the ...
RepSandyBMartinez, iOS Developer
Searching for a simple and delicious homemade treats for dogs?Visit Healthy Dog treats online store and shop the best ...
Repnormadyen, Blockchain Developer at 247quickbookshelp
I am working as a Pharmacy technician in Sunny Sypus company. I can maintain employee records for a company or ...
RepHazelMiller, Site Reliability Engineer at Delve Networks
Hazel Miller has been a stalwart advocate for sound public policy that advances the jobs creating potential of America’s ...
RepRocioNavarro189, None at Student
Hello Everyone,My name is Rocio Navarro Form Auckland,NZ,and 31 years old.I am searching for a servant ...
RepLarry Alvarez, Analyst at ASU
Prestige Luxury Rentals is one of the most renowned car rental companies in USA. We are locally owned and operated ...
Reppamelacochran447, Intern at design
I am Pamela Cochran, and I am working as a Manager in Compact Disc Center. Last Month, I searched for ...
RepHad a brief career donating velcro in Africa. Spent several years training sock monkeys in Pensacola, FL. Gifted in working ...
RepNY Vape Shop is the most popular Vaporizer Store for new trend vaporizer pen and all related accessories. We are ...
RepGerard Swearingen, Consultant at ADP
Want to book exotic and luxury car rental in Atlanta, GA ? We, Prestige Luxury Rentals are the best car rentals ...
RepAre you searching the strong and the most powerful Mantra for your husband? Consult our vashikaran specialist now. He provides ...
RepBonnieToney, abc at A9
I am a highly dedicated and accomplished asset manager with an exceptional work ethic and customer service record. I adapt ...
RepHandyman Homes is the one-stop destination for all your home improvement and handyman needs.We take care of residential & commercial ...
RepRuizLeslie, Management accountant at Omni Superstore
Ruiz , a Management accountant with 4 years in the field of administrative functions, managing the office of the Leadership team ...
RepDo you want to use Kamdev Vashikaran Mantra to subdue someone?Or If you are willing to attract your love ...
Repsuganpdhchejara921, Problem Setter at TP
Are you facing love life and married life problem. Contact vashikaran specialist right now. He will guide your solution with ...
Make a duplicate array , sort duplicate array and compare with original array element by elements , if there are only two mismatch , then it is possible otherwise not.
- Rahul Sharma April 22, 2015