Rajat
BAN USER- -2of 2 votes
AnswersThree coke machines. Each one has two values min & max, which means if you get coke from this machine it will load you a random volume in the range [min, max]. Given a cup size n and minimum soda volume m, show if it's possible to make it from these machines.
- Rajat in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersWrite an algorithm to evaluate the Postfix Expression
- Rajat in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm - 0of 0 votes
AnswersImplement the integral part logn base 2 with bit manipulations
- Rajat in United States| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm
int kthLargest(int matrix[][], int k ){
int m = matrix.length; // Number of rows
int n = matrix[0].length; // Number of Cols
if( k > m*n) {
return -1;
} // Not found
else {
int rowNumber = (int)Math.ceiling(k/n) - 1;
int colNumber = k - n * rowNumber -1;
return matrix[rowNumber][colNumber];
}
}
Example
1 2 3 4
9 10 11 12
K = 5
rowNumber = Ceiling(5 / 4) -1 = 2 - 1 = 1
colNumber = 5 - 1 * 4 - 1 = 0
Answer :
matrix[1][0] = 9
I did it by doing the inorder traversal of the node and keeping track of the last visited node. The last visited node connected to the next pointer. Not sure if this is correct.
Class Node {
Node left;
Node right;
Node nextRight;
}
void updateNextRight(Node root) {
Node lastVisited = null;
updateNextRightPointers( root, lastVisited );
}
void updateNextRightPointers( Node node, Node lastVisited) {
if( node == null ) return;
updateNextRightPointers(node.left,lastVisited);
if(lastVisited != null) {
lastVisited.nextRight = root;
}
lastVisited = root;
updateNextRightPointers( node.right, lastVisited);
}
Generate all permutations in lexicographical order. That is going to take care of the duplicate characters in the string as well. Complexity of generating the next permutation is going to be high as compared to normal permutation as u involve sorting as well here.
- Rajat February 04, 2013In normal algorithm complexity for generating the next permutation is going to be O(n) in worst case. In the case of lexicographical sorting it is going to be o(n + logk)