yolo
BAN USER- 0of 4 votes
AnswersConstruct a BST from inorder and preorder traversal string. Write code for it.
- yolo in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - -11of 11 votes
AnswersGiven a tree, verify if it contains a subtree.
- yolo in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 0of 2 votes
AnswersGiven a maze that contains floor plan with rooms.
- yolo in India
For example, consider a n*m matrix where each block represent a room.
You can move up-down and left-right from one room to another. But there are some rooms where there no door to one or more side of the wall.
some rooms are bathrooms.
Given a room location, return the nearest bathroom.
Start by writing method signature. Interviewer said that :)
It was bar raiser round.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 5of 7 votes
AnswersDelete last node from the linked list. First node pointer is not given.
- yolo in India
I told him its not possible in conventional linked list.
He asked me what if we can add some more data in node.
Data should not be a pointer to previous node i.e., it should still be singly linked list.| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists
Modify the quick sort algorithm.
Since all the elements less than pivot will be on the left and more will be on right, keep calling partition() method until it partition the array at kth index.
Here is the algo-
If k = pivot
return pivot //all values before pivot is your ans
if k < pivot.
partition(begin, k-1, array) //answer lies in left partition
if k > pivot.
partition(k+1, end, array) //answer lies in right partition
Worst case complexity will be same as Quick sort.
But average case when each time array is divided into two parts, number of comparisons will be
n + n/2 + n/4 + n/8 +...... = 2n
Hence O(n).
Use dynamic programming approach.
Maintain a 2D array.
ith row will store the longest increasing sequence for ith number in the original array.
For optimization purpose, you can use another array to maintain the length of each row. Call it lengthArray.
Use DP approach to find longest increasing sequence for all the numbers from 0 to nth elements. Each time update the lengthArray.
at the end, iterate through lengthArray and find the largest element.
Lets say its jth.
Now print jth row from 2D array.
I think ConnectionPool should be singleton class.
- yolo July 12, 2013