## Google Interview Question for Software Engineer / Developers

• 2

Country: Israel
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Do an inorder traversal and stop at k'th element. Use recursion.

Comment hidden because of low score. Click to expand.
0

Why use recursion ?. I think it is better to do inorder traversal without recursion.

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();
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 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;
}
}``````

Comment hidden because of low score. Click to expand.
0

This example is not BST.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

Comment hidden because of low score. Click to expand.
0

I believe it's asking for kth element when items are sorted ascending

Comment hidden because of low score. Click to expand.
0
of 0 vote

YOu need to ask, do we know the size ! :D then you can optimize it !

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do an inorder traversal and DO NOT USE recursion, use iterative solution. The question is all about it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
* 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));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

The time efficiency is O(n);

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static TreeNode kth(TreeNode n, int k) {
int i=0;
Stack<TreeNode> s = new Stack<TreeNode>();
while(true) {
while(n!=null){
s.push(n);
n = n.left;
}
if(s.empty())
break;
n=s.pop();
i++;
if(i == k) {
System.out.println(n.value);
return n;
}
n = n.right;
}
return null;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static TreeNode kth(TreeNode n, int k) {
int i=0;
Stack<TreeNode> s = new Stack<TreeNode>();
while(true) {
while(n!=null){
s.push(n);
n = n.left;
}
if(s.empty())
break;
n=s.pop();
i++;
if(i == k) {
System.out.println(n.value);
return n;
}
n = n.right;
}
return null;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static Node find(Node root, int k) {

while (!queue.isEmpty()) {
Node temp = queue.remove();
k--;
if (k == 0) return temp;

if (temp.left != null) {
}
if (temp.right != null) {
}
}
return root;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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);

}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

EDIT: Perform in order traversal of the tree via DFS and stop at k-th node.

Comment hidden because of low score. Click to expand.
0

this is preorder traversal, hence wrong.

Comment hidden because of low score. Click to expand.
0

You were absolutely right, my mistake. Code was removed.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.