catlover
BAN USER- 2of 2 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;
}
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/find-second-largest-number-in-array-at-most-nlog2n2-comparisons
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;
}
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 !
Repdawnmhodges111, abc at 247quickbookshelp
Hello I am a Web writer. All my studies complete from california.my hobby is write different type article.Right ...
Repliliylinda619, Area Sales Manager at Alliance Global Servies
My name is Sarah Torres and I am a Fitness director in the Independent Planners. I am a very kind ...
Repjoshuacmurphy36, Animator at ABC TECH SUPPORT
Hey,I am an agricultural engineer. And I love this job. We Agricultural Engineers do engineering design and planning in ...
Repopalphelan234, Associate at 247quickbookshelp
I am a specialized Cardiac and vascular nurse at the Circus World . Here I meet different people and observe their ...
RepAlvaPolly, Animator at ADP
I am Alva , working as a Brand Specialist with two years experience in Keeney's. I’ve excellent communication and ...
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 :)