words&lyrics
BAN USER- 0of 0 votes
AnswersGiven a dictionary of words, two APIs
- words&lyrics in India
Is_word(string)
Is_prefix(string)
And a NxN matrix with each postion consisting of a character. If from any position (i,j) you can move
in any of the four directions, find out the all the valid words that can be formed in the matrix.
(looping is not allowed, i.e. for forming a word position if you start from (i,j) and move to (i-1,j) then
from this position you cannot go back to (i,j))| Report Duplicate | Flag | PURGE
Amazon Applications Developer - 0of 0 votes
AnswersQ1) Given that there are n players and each one of them has played exactly one game with every
- words&lyrics in India
other player. Also given is an API that tells whether player ‘a’ won or lost to player ‘b’, where ‘a’ and
‘b’ could be any of the players. Arrange the n players in a length n array such that player at position
‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’
Interested in linear time solution
PS: Its not a sorting problem. Please notice that problem is not asking for ranking in decreasing order..| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm
The tree is not necessarily heap.!
A heap has additional property that it is almost a complete binary tree, No such constraint is imposed here.
Consider the case
3
2
1
This is not a heap still satisfies the above criteria.
See mu comment below for the approach to solve this
This can be done in O(n) time and constant space.
See my comment below!!
O(n) time O(1) Space
1. Find max and min
2. Traverse the array and for each a[i] change sign of a[[a[i]- min]]
Each time a element is found sign of location corresponding to that
(mapped to a[i]-min) changes sign. So same sign after this traversal means
even number of occurrences, different sign means odd no. of occurrences
3.Finally traverse the array from i =0 to i = max-min
and look for -ve element at location 'j'.
4. Return j+min
This algorithm will work only if all elements are of same sign initially
And again klogk is not possible. It should be nlogk. One clear reason , you can't take n out as it is not possible to say about which are k smallest if you have not seen all the element!
- words&lyrics July 15, 2012Min heap won't work!
It should be max heap!
This is wrong!!
You said:
"
If A[k/2] < B[k/2], it means these A[1] to A[k/2] elements are part of first k elements.
"
Well, not necessarily
consider the case
A[] = {2,3,4,5,6,7}
B[] = {1,6,9,10,11,12}
Consider k = 4
now comparing 4 & 10 , 10 is greater
So by your algo algo {2,3,4} should be three smallest
but answer should be {1,2,3}
Answer must be either in of the array and within first k elements in each so total data to be looked at is 2k
Correct solution will eliminate half of it after each iteration. Its easy to see how it can be done!
Think more!
For two arrays to generate same BST:
1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))
Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4
(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)
For two arrays to generate same BST:
1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))
Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4
(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)
For two arrays to generate same BST:
1. Root should be same
2. Relative order of all elements greater than root should be same
3. Relative order of all elements less than root should be same.
(and of course the elements should be same as well:))
Example:
Same BST :
6,2,7,8,5,1,3,9,10,4
6,7,8,2,5,9,1,10,3,4
(root same and relative order of elements less and greater than root same
7,8,9,10 & 2,5,1,3,4
)
The tree is not necessarily heap.!
A heap has additional property that it is almost a complete binary tree, No such constraint is imposed here.
Consider the case
3
2
1
This is not a heap still satisfies the above criteria.
Now here is recursive approach to solve:
1.In the given in order traversal the maximum will be the root of the tree. and the the sub array to the left is left sub tree and to the right is right sub tree.
2. Recursively repeat the above step for left and right sub tree
Sorry! I got it! Good solution!
- words&lyrics July 14, 2012I am not sure why Max heap!!
If we use min heap
1. inserting will be O(1) (just need to replace the root when some thing smaller arrives). In case of max heap insertion will be O(lgn)
2. Traversal (to get k smallest ) will be same for both
Sorry for the last comment! Its working Thanks!
- words&lyrics July 14, 2012For N=10, k=3 this is giving output as 0 . It should be 4. Please check1
- words&lyrics July 14, 2012Can you give the pseudo code!
I still can't understand the expression!
I can't understand this!
Can you just explain this or give a code in c!
Can you give some pseudo code!
- words&lyrics July 13, 2012Match b/w Winner
a vs b a
a vs c c
b vs c b
Possible solutions cab , bca or abc
(nlgn) is pretty straight forward.
Clearly this can have more than one solution set.
We need just one so there should be better than O(nlogn)
approach
By a won b , I guess you mean a defeated b
Possible solutions in this case are:
cab , abc , bca
cba is not the solution as c lost to b so cannot be before
Can you explain a bit!
- words&lyrics July 13, 2012Sorting on the basis of number of wins will give a solution. But this problem can have multiple solutions i.e , not unique. So we just need to build one such solution out of the given input. And I was told linear time is possible.
- words&lyrics July 13, 2012Its not a sorting problem. What you are suggesting is ranking player in order of number of wins. This is not ranking constraint is
with the element only next to it(before and after ). Infact it can have more than one solution , to say that , the result is not unique. You have to just build one solution out of the given order.
PS : To be done in linear time
Yes i guess so! Can you please suggest the solution!
- words&lyrics July 13, 2012
No need to sort!
- words&lyrics July 18, 2012Maintain a minheap of 3 elements based on absolute values. height of this will always be 1
Complexity O(n)