Vin
BAN USER- 0of 0 votes
AnswerDifference between Trie and N-array tree.
- Vin in India| Report Duplicate | Flag | PURGE
Ebay Software Engineer / Developer Algorithm - 0of 0 votes
AnswersList of parent and child of a binary tree are given in the format (parent, child) –> (p1,c1) (p2,c2) etc [ie, binary tree represented by adjacency list]
- Vin in India
How to check "loop" exists in this binary tree or not efficiently.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswersList of parent and child of a binary tree are given in the format (parent, child) –> (p1,c1) (p2,c2) etc [ie, binary tree represented by adjacency list]
- Vin in India
How to check "loop" exists in this binary tree or not in efficiently.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
AnswersThere is a sentence that your friend knows, but while giving it to you, he lost all the spaces. You have a dictionary with you, that will tell you given word exist or not. How would you reconstruct the original sentence using it.
- Vin in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 0of 0 votes
AnswersGiven a chess board of finite length (NxN), start position of a knight(x, y) and an end position (p, q). 1) Find number of minimum hops required to reach end position.
- Vin in India
2) Check your solution extendable to infinite length chess board ??| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersDesign a DS to perform
- Vin in India
1. Insert
2. Search
3. Delete
4. Get Random
All in O(1).| Report Duplicate | Flag | PURGE
Amazon SDE1 - -4of 4 votes
AnswersA student needs to implement a BST structure to solve a problem, but instead he used a linked list. New value will always be added at beginning of a linked list. So basically at each step after insertion , root of BST and head of link list should point to same node. Then give an example of input sequence, in which his implementation works…
- Vin in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 2 votes
AnswersGiven an array consisting of both positive and negative numbers, 0 is considered as positive, 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.
- Vin in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 4of 6 votes
AnswersFind the nearest leaf node from given node in binary tree.
- Vin in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - -1of 7 votes
AnswersFind maximum product of subarray in given array of integers
- Vin in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 1of 1 vote
AnswersDesign T9 dictionary
- Vin in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 11of 13 votes
AnswersThere are some glasses with equal volume 1 litre. The glasses kept as follows
1 2 3 4 5 6 7 8 9 10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflow and fill equally both 2nd and 3rd glass. Glass 5 will get water from both 2nd glass and 3rd glass and so on..
- Vin in India
If you have X litre of water and you put that water in top glass, so tell me how much water contained by jth glass in ith row.
Example. If you will put 2 litre on top.
1st – 1 litre
2nd – 1/2 litre
3rd - 1/| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersAn array of size N is given. The array contains digits from 0 to 9. Generate the maximum number using the digits in the array such that it is divisible by 2, 3 and 5
- Vin in India
input: {1,8,7,6,0}, output: 8160
input: {7,7,7,6,}, output : none(-1)| Report Duplicate | Flag | PURGE
General Questions and Comments - 0of 0 votes
AnswersThere is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).
- Vin in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Matrix
need more clarification, as per the question, out put should contain 2 as well.
if that is the case, below will work.
take 2 pointers which points to the first elements of A and B respectively.
while both pointers are in list range compare the values pointer by the pointers
if both values are equal, increment both pointers till the next value not equal to current value.
if one less than the other, print the smaller value and increment the pointer which points to smaller one.
print the remaining values in the non completed list.
time O(n) and constant space.
here the logic is simple:
scan the array from right to left.
find the biggest number in the array and remember it.
find second largest number to the left of first and remember it.
find third largest number to the left of second and remember it.
update maximum product when found a bigger product.
let the inputs are in an array A of size n
1. init result[3] with 0 /* for final result */
2. init maximum_product with 0
3. init temp[3] with 0 /* for temporary results. */
4. for i <- n to 1
5. if (A[i] > temp[3]) /* this is the highest number found so far. */
6. temp[3] <- A[i]
7. temp[2] <- 0
8. temp[1] <- 0
9. else
10. if (A[i] > temp[2])
11. temp[1] <- 0
12. temp[2] <- A[i]
13. else if (A[i] > temp[1])
14. temp[1] <- A[i]
15. if (temp[1] * temp[2] * temp[3] > maximum_product)
14. maximum_product <- temp[1] * temp[2] * temp[3]
15. result[1] <- temp[1]
16. result[2] <- temp[2]
17. result[3] <- temp[3]
18. /* end of for loop*/
19. if (result[1] && result[2] && result[3])
20. print result[1] && result[2] && result[3]
21. else print "no solution found"
@xint - time will be O(n) only.
I had taken an example of 3 lists above. we can generalize it.
Instead of 3 pointers, take an array of K pointers which initially points to the first elements of K lists.
Now find the minValue and maxValue among this K pointers.
Find the range and update smallest_range, if needed.
Increment the pointer points to minValue and compare the value now pointed with minValue and maxValue and update it, if needed. so this will take only constant time.(no need to find the minValue and maxValue among K pointers each time since we are already tracking min and max among the K pointers )
repeat till end of list
time - O(n), space - O(k)
This can be solved easily as below.
1. initialize smallest_range as MAX_INT
2. keep 3 pointers/index p1, p2 and p3 which points to the first elements of lists L1, L2 and L3 respectively.
3. find the max value and min value pointed/indexed by p1, p2 and p3
4. difference of max value and min value discovered in step 3 is the current range. compare it with smallest_range and update it, if found smaller.
5. increment the pointer/index of min value found in step 3.
6. repeat step 3 to 5 until the pointer/index of min value is in range.
constant space and O(n) time.
we can improve as below:
int isPrime(int num){
int i = 1;
if(num <= 1) return 0;
if(num == 2 || num == 3) return 1;
/* primes will be of 6k + or - 1 form */
if((num - 1)%6 != 0 && (num + 1)%6 != 0) return 0;
for(; i*i <= num; i += 2){
if( num%i == 0) return 0;
}
return 1;
}
@USTChucat - no need to count the max line using a function like lineCounts(). Since we need to find the max line, we can keep a variable for keep track of max line. whenever we are inserted to the hash table check for max line also eg:
@ line_count - Hash Table
@ bestLine - keeps track of the max line
Line line = new Line(points[i], points[j]);
if (!line_count.containsKey(line)) {
line_count.put(line, 1);
} else {
line_count.put(line, line_count.get(line) + 1);
}
if (bestLine == null ||
line_count.get(line) > line_count.get(bestLine)) {
bestLine = line;
}
@ sonesh - the line is in slope y intersect form, so we can calculate the hash value using this two. may you need to take care about the infinite slop also. one Eg:
@slope and intercept are float values:
int hashCode() {
int sl = (int)(slope * 1000);
int in = (int)(intercept * 1000);
return ((sl & 0X0000FFFF)| (in << 16));
}
This can be solved in O(n^2) time and O(m) space. where m is the distinct number of lines among all given points.
1. use a hash table - key is line and number of appearance of line as value.
2. for each pair of points find the line in slope y intercept form
3. if the line is not there in hash table, add it to the hash table with appearance value 1
4. if the line is already in hash table, increment the appearance value
5. line with the max number of appearance in the hash table is the result.
This will fails if one node is the child of other.
so this need a small correction to the last step: "now traverse both upwards and they reach at LCA"
compare both the nodes, if not same, traverse up one step using parent node.
repeat the above step till both are same or till the root.
There can be 3 states for each character
0- Not present in the stream at all
1-Present once in the stream (this we are interested)
2-Present more than once in the stream
to represent the above 3 valus, 2 bits are enough.
so allocate an array of size (256*2) bits, if character represented by ASCII value.
for any character 'x' in the stream, bits 2* asciivalueof('x') and 2* asciivalueof('x')+1 represents the appearance state in the array
1. scan the full stream one by one, set this 3 values properly in the array
2. then scan the array to find the value 1 and return the index.
space needed : constant O(1)
time needed : O(n)
@Anonymous - good point that i missed, updated the solution now.
- Vin April 08, 2013