Google Interview Question
Software Engineer / DevelopersCountry: Israel
Interview Type: In-Person
Here is the recursive solution:
#include <iostream>
using namespace std;
class FoundInfo {
public:
bool found;
int value;
FoundInfo(bool fnd, int val) {
this->found = fnd;
this->value = val;
}
};
class Node {
public:
int value;
Node* left;
Node* right;
Node(int val) {
this->value = val;
left = NULL;
right = NULL;
}
FoundInfo findKth(int &k) {
FoundInfo Found(false, 0);
if (this->left) {
Found = this->left->findKth(k);
if (Found.found) {
return Found;
}
}
--k;
if ( k == 0 ) {
Found.value = this->value;
Found.found = true;
return Found;
}
if (this->right) {
Found = this->right->findKth(k);
}
return Found;
}
};
int main() {
Node* root = new Node(4);
Node* child1 = new Node(2);
Node* child2 = new Node(6);
Node* gchild11 = new Node(1);
Node* gchild12 = new Node(3);
Node* gchild21 = new Node(5);
Node* gchild22 = new Node(7);
root->left = child1;
root->right = child2;
child1->left = gchild11;
child1->right = gchild12;
child2->left = gchild21;
child2->right = gchild22;
int k=4;
printf("value(%d)\n", root->findKth(k).value);
return 0;
}
Below is java program-cum-algo that uses pass by reference or pointer
FindKth(Node Root, k)
{
List<Node> list = new List<Node>();
Inorder(root, k, list);
return (list.size>0)? list.get(0) :null;
}
This function will return -1 if we have already reached the kth element.
Once this function returns "list" (which is supposed to be pass by reference) should have the required element.
Inorder(Node N, int k, List<>list)
{
if(N==null) return 0;
int l = Inorder(N.Left, k ,list);
if(l==-1) return -1;
if(l==k-1) { list.add(N); return -1; } // we found the element
int r = Inorder(N.Right, k-l-1);
if(r==-1) return -1;
return r+l+1;
}
public static int getKthElement(TreeNode root, int k){
if (k < 0 || root == null){
return Integer.MIN_VALUE;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
fillStack(stack, root);
TreeNode current;
while(!stack.isEmpty()){
current = stack.pop();
if (k == 0){
return current.val;
}
k -= 1;
fillStack(stack, current.rightChild);
}
return Integer.MIN_VALUE;
}
private static void fillStack(Stack<TreeNode> stack, TreeNode node){
while (node != null){
stack.push(node);
node = node.leftChild;
}
}
Solution in Python in linear O(k):
def find_kth_node(tree, k):
return _kth_node_recursive(tree.root_node, k)[1]
def _kth_node_recursive(node, k):
kth_node = None
if node.left_child:
k, kth_node = _kth_node_recursive(node.left_child, k)
if kth_node:
return k, kth_node
k -= 1
if k == 0:
return k, node
if node.right_child:
k, kth_node = _kth_node_recursive(node.right_child, k)
return k, kth_node
InOrder traversal solution without recursion.
public class problem_7{
public static class Node{
public Node left;
public Node right;
public Integer value;
public Node(Integer v){
value = v;
}
}
public static int find(Node head, int k){
Stack<Node> stack = new Stack<Node>();
HashMap<Node, Boolean> used = new HashMap<Node, Boolean>();
stack.push(head);
int count = 0;
while(!stack.empty()){
Node currentNode = stack.pop();
if(currentNode == null) continue;
if(currentNode.left == null || used.containsKey(currentNode.left) == true){
used.put(currentNode, true);
count++;
if(count == k)
return currentNode.value;
continue;
}
stack.push(currentNode.right);
stack.push(currentNode);
stack.push(currentNode.left);
}
return -Integer.MAX_VALUE;
}
public static void main(String [] args){
Node head = new Node(4);
Node l_1 = new Node(5);
Node r_1 = new Node(0);
Node l_21 = new Node(3);
Node l_22 = new Node(7);
l_1.left = l_21;
l_1.right = l_22;
head.left = l_1;
head.right = r_1;
System.out.println(problem_7.find(head, 5));
}
}
The following algorithm calculates the "rank" of each node and stops when the desired rank (i.e. "k" ) is found
int k = 4;
int FindRank( CNode * node_p, int rank, bool &is_done )
{
if ( !is_done )
{
if ( node_p->m_left )
{
rank = FindRank( node_p->m_left, rank, is_done ) + 1;
}
if ( rank == k )
{
printf("Number : %d, rank: %d\n", node_p->m_number, rank );
is_done = true;
}
else
{
if ( node_p->m_right )
{
FindRank( node_p->m_right, rank + 1, is_done);
}
}
}
return rank;
}
Here is the complete code so you can run and test it
#include "stdafx.h"
class CNode
{
public:
CNode( int number )
{
m_number = number;
m_right = NULL;
m_left = NULL;
}
int m_number;
CNode * m_right;
CNode * m_left;
};
CNode * root = NULL;
void InsertNumber( CNode * node_p, int number )
{
if ( number > node_p->m_number )
{
if ( node_p->m_right )
{
InsertNumber( node_p->m_right, number );
}
else
{
node_p->m_right = new CNode( number );
}
}
else
{
if ( node_p->m_left )
{
InsertNumber( node_p->m_left, number );
}
else
{
node_p->m_left = new CNode( number );
}
}
}
void PrintTree( CNode * node_p )
{
if ( node_p )
{
PrintTree( node_p->m_left );
printf("%d,", node_p->m_number );
PrintTree( node_p->m_right );
}
}
int k = 4;
int FindRank( CNode * node_p, int rank, bool &is_done )
{
if ( !is_done )
{
if ( node_p->m_left )
{
rank = FindRank( node_p->m_left, rank, is_done ) + 1;
}
if ( rank == k )
{
printf("Number : %d, rank: %d\n", node_p->m_number, rank );
is_done = true;
}
else
{
if ( node_p->m_right )
{
FindRank( node_p->m_right, rank + 1, is_done);
}
}
}
return rank;
}
int _tmain(int argc, _TCHAR* argv[])
{
int A[8]={4,3,6,9,8,2,1,7};
int i;
root = new CNode( A[0] );
for ( i = 1 ; i < 8 ; i++ )
{
InsertNumber( root, A[i] );
}
PrintTree( root );
printf("\n");
bool is_done = false;
FindRank( root, 0, is_done );
printf("\n");
return 0;
}
I think the first question to ask is what the k-th mean?
Does it mean the k-th largest ? or the k-th smallest?
or just mean the k-th node you encounter whether by DFS or BFS ?
to be honest, I don't quite understand this question .
/*
* Find Kth largest element in given BST
* time: average case is O(logN), worst case is O(n) if it's not balanced BST
* space: O(1)
*
* idea:
n == num_elements(left subtree of tree), value=root.val;
n > num_elements(left subtree of T), ignore the left subtree, then find the k - num_elements(left subtree of T) smallest element of the right subtree.
n < num_elements(left subtree of T), find kth smallest element in left subtree.
*/
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class findNLargestBST {
// assume it is balanced BST
public static int depth (TreeNode root) {
int depth =0;
if (root == null) return depth;
TreeNode tmp = root;
while (tmp !=null) {
tmp=tmp.left;
depth++;
}
return depth;
}
public static int NthElement (TreeNode root, int depth, int n) {
int count = (int) (Math.pow((double)2, depth) -1);
int e =0;
int index = count/2+1;
if (n == index) return e=root.val;
else if ( n< index) e = NthElement(root.left, depth-1, n);
else e= NthElement (root.right, depth-1, n-index);
return e;
}
public static int NthLargest (TreeNode root, int n) {
int depth = depth (root);
int count = (int) (Math.pow((double)2, depth) -1);
int e =0;
if (n > count) {
System.out.println("none");
e =0;
} else {
e = NthElement (root, depth, count-n+1);
}
return e;
}
public static void main (String[] args) {
/* find second largest:
* 20
* 10 30
* 40
*
*/
TreeNode n1 = new TreeNode(20);
TreeNode n2 = new TreeNode(10);
TreeNode n3 = new TreeNode(30);
TreeNode n4 = new TreeNode(40);
n1.left =n2; n2.right = n3;
n3.right = n4;
int n=2;
System.out.println(NthLargest(n1,n));
}
}
convert the tree to a Stack by going from right to left and then pop k elements.
public TreeNode findK(TreeNode node, int k) {
Stack<TreeNode> stk = new Stack<TreeNode>();
fillStack(mode, stk);
TreeNode ret = null;
for(int index=0; index<k; index++)
ret = stack.pop();
return ret;
}
private void fillStack(TreeNode node, Stack<TreeNode> stk) {
if(null == node)
return;
fillStack(node.right, stk);
stk.push(node);
fillStack(node.left, stk);
}
My solution is as follows:
public int getKthElem(TreeNode root, int k) {
if (root == null)
return -1;
int lc = getCount(root.left);
if (lc == k-1)
return root.value;
if (lc >= k)
return getKthElem(root.left, k);
else
return getKthElem(root.right, k-1-lc);
}
public int getCount(TreeNode root) {
if (root == null)
return 0;
return getCount(root.left)+getCount(root.right)+1;
}
-1 indicates if not found, you should check with interviewers.
The time efficiency is O(n);
public static Node find(Node root, int k) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node temp = queue.remove();
k--;
if (k == 0) return temp;
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
return root;
}
// Time O(n), Space O(1)
class Solution {
int counter;
TreeNode node;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return node.val;
}
void inorder(TreeNode root, int k) {
if (root != null) {
inorder(root.left, k);
counter++;
if (counter == k) {
node=root;
}
inorder(root.right, k);
}
}
}
Do an inorder traversal and stop at k'th element. Use recursion.
- anan January 27, 2015