catlover
BAN USER 0of 0 votes
AnswersLink all the level order nodes to makes a linked list with the first node of each level acting as the root of that linklist.
 catlover in India
10
/ \
6 17
/ / \
4 14 19
So the Linklist will be
10>null
6>17>null
4>14>19>null Report Duplicate  Flag  PURGE
Amazon SDE1  0of 0 votes
AnswersYou have three containers, small, medium and large. Passenger comes in, checkin the luggage. You have to store the baggage in the appropriate container and generate a unique token number. Then passenger should get back the bag using the same token number. Trick was if small container is full store in medium if available or large. Now if the large bag comes in and there is now a empty space in small, than move the small bag back to small & store the large bag. How to generate the unique token number and move the baagage internally without changing the token number?
 catlover in India
Lookup should be in constant time complexity and insertion in minimum complexity. Report Duplicate  Flag  PURGE
Amazon SDE1 Algorithm
As already told here, we can keep track of each level while doing a BFS. At each level, we can see which is the max element.
int height2(TreeNode *root) {
if (!root) return 0;
queue<TreeNode*> nodesQueue;
int nodesInCurrentLevel = 1;
int nodesInNextLevel = 0;
int nodes = 1;
int maxAtCurrLevel = INT_MIN;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
TreeNode *currNode = nodesQueue.front();
nodesQueue.pop();
if (currNode>data > maxAtCurrLevel)
maxAtCurrLevel = currNode>data; // If value of current node greater than current maximum of this level
nodesInCurrentLevel;
if (currNode) {
cout << currNode>data << " ";
nodesQueue.push(currNode>left);
nodesQueue.push(currNode>right);
nodesInNextLevel += 2;
}
if (nodesInCurrentLevel == 0) {
nodes++;
cout<<"\n";
nodesInCurrentLevel = nodesInNextLevel;
nodesInNextLevel = 0;
cout<<"Maximum element at this level: "<<maxAtCurrLevel <<endl;
maxAtCurrLevel = INT_MIN: //level finished
}
}
return nodes;
}

catlover
September 28, 2012 Mathematical formula for this type of problem could be the number of ways of reaching from bottom right to the top left. Allowed directions are two, that is up and right.
For M rows, N columns, number of ways:
(M + N)! /( M! * N!)
It of course, doesn't consider the constraint of picking maximum gold coins. It is just the number of ways possible.
The question asks about finding second maximum in minimum number of comparisons. It doesn't asks about minimum complexity, which is ofcourse O(n). Minimum number of comparisons for second max. element are N  2 + logN .
See this link for detail:
stackoverflow.com/questions/9889679/findsecondlargestnumberinarrayatmostnlog2n2comparisons
See this : cse(dot)ust(dot)hk/~dekai/271/notes/L05/L05(dot)pdf . It explains kth smallest/largest elem in O(n) and is not a randomized algo
And this link also for other methods with non linear complexity : geeksforgeeks(dot)org/archives/2392
Also, someone above posted that selection algo (as used in selection sort)is O(n). But I guess it will be O(kn). Please clarify, if someone has idea.
Level order traversal could be used also
Method 1:
int Height(Tree t) {
int height = 1;
if(t != NULL) {
std::list<Tree> q; //Queue to store tree nodes
q.push_back(t);
q.push_back(NULL); //null is the delimeter to show end of the level
while(!q.empty()) {
TreeNode *node = q.front();
q.pop_front();
if(node == NULL) {//delimeter encountered, increase height and push NULL if q not empty
height++;
if(!q.empty())
q.push_back(NULL);
}
else {
if(node>left)
q.push_back(node>left);
if(node>right)
q.push_back(node>right);
}
}
}
return height;
}
Method 2:
int height2(TreeNode *root) {
if (!root) return 0;
queue<TreeNode*> nodesQueue;
int nodesInCurrentLevel = 1;
int nodesInNextLevel = 0;
int nodes = 1;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
TreeNode *currNode = nodesQueue.front();
nodesQueue.pop();
nodesInCurrentLevel;
if (currNode) {
cout << currNode>data << " ";
nodesQueue.push(currNode>left);
nodesQueue.push(currNode>right);
nodesInNextLevel += 2;
}
if (nodesInCurrentLevel == 0) {
nodes++;
cout<<"\n";
nodesInCurrentLevel = nodesInNextLevel;
nodesInNextLevel = 0;
}
}
return nodes;
}

catlover
May 17, 2012
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
Rep
Rep
RepGoogle+ ozslatersd
Rep.·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º>, Software Engineer / Developer at Tepito Soft
I can accept failure, everyone fails at something. But I can't accept not trying
¡Viva Mexico Cabrones !
Open Chat in New Window
This code is giving correct outputs for all the inputs I tried: ideone(.)com(/)EjnCSV
 catlover November 24, 2013But I still don't get the logic :)