Ibibo Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

a simple nlogn solution will be do a inorder traversal of the tree...at every node calculate val = node.value - k(given number) and do a binary search for val from the root node if node.value < val or from the current node if node.value > val

we can initially find out the max and min values in the tree to increase the efficiency further by using the max or min value to identify whether its worth going to the left or right child of a given node

- The Artist December 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Artist,
Good approach.I have a question though:
Worst case scenario (lets say the right most leaf and its parent form the sum), you will traverse the whole tree and search the whole tree for val correct? which would make it O(n^2) ?

My implementation of your algorithm ...

struct Node
{
  int data;
  Node* left;
  Node* right;
}

Driver Function

bool FindSum(Node* root, int sum, Node* node1, Node* node2)
{
  node1 = NULL;
  node2 = NULL;

  if(!root)
    return false;
    
  Node* current = root;
  
  while(current && current->data > sum)
    current = current->left;
    
  if(!current)
    return false;
    
  FindSum(current, current, sum, node1, node2);
  
  if(!node1)
    return false;
    
  return true;
}

Recursive Function to do a In-Order traversal

void FindSum(Node* root, Node* current, int sum, Node* node1, Node* node2)
{
  int value = sum - current->data;
  if(FindNode(root, value, node2))
  {
    node1 = current;
    return;
  }
  
  if(current->left)
    FindSum(root, current->left, sum, node1, node2);
    
  if(current->right)
    FindSum(root, current->right, sum, node1, node2);
}

Helper Function to find a node with given data

bool FindNode(Node* root, int data, Node* node)
{
  if(!root)
    return false;
    
  while(root)
  {
    if(root->data == data)
    {
      node = root;
      return true;
    }
    else if(root->data < data)
      root = root->right;
    else
      root = root->left;
  }
  
  return false;
}

- JSDUDE April 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

To come up with (one of) the best possible solution to this problem, we need to be aware of the limitations and inherent advantages of using a BST. The problem can then be solved efficiently. Let us take a look at (some of) the properties of BST and the nature of the problem that’ll help us in finding a solution that is very close to the best possible solution.
1. In a BST, the numbers are sorted in a particular order during insertion. For any given node at any level, the value of the nodes in its left sub tree are always lesser than the value of the parent node and the value of the nodes in the right sub tree are always greater than the value of the parent node.
2. There are no nodes with duplicate values in a BST.
3. We have to eliminate (or don’t have to find) duplicate pairs.
Step 1. We first find (zero-in on) the node whose value is less than the given number n. We call this node newRoot (the logic behind this move is if we hope to find all pairs of numbers that add up to n in a BST, we should ignore the nodes that are greater or equal to n. Refer to point 1 above and this reasoning will seem obvious).
Step 2. Start with the node that was identified in step 1.
a. If the value of this node is less than n/2 then search for the node starting from newRoot with the value n – value (the logic is to limit the value for ki, our first number in the pair. If we find ki, kj must be out there).
b. If a node was found that satisfied the search condition in step 2a, print the pair [value, n – value] (we found kj using ki).
Step 3. Repeat step 2 for the current node’s left child.
Step 4. If the value of the current node is less than n/2, repeat step 2 for current node’s right child (there is no point looking for a number on the right side of the current node if the node’s value is greater than n/2 since we know we won’t find it).

- ansariinjnu December 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if node value is negative? then there could be no node value less than the given number n!

- visitor December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent question visitor...i wish comments to comment can be +1'd

- The Artist December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n) solution without using any extra or auxiliary space-
1. Find the left most node of tree means the
smallest one. Worst case complexity O(n).
2 . similarly find the right most node, say both to be a and b respectively.
3. Now traverse the tree recursively from left node to right as well right to left simultaneously in inorder form. Terminating condition would be when a->val>b->val or either we get the required sum.

- Karan Gupta August 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach would be:
1. traverse the tree in Inorder traversal - while scanning, store the elements in a array.
2. Scan the array using two forloops and find the elements that sum to required sum.

Tried not using an array for this, but havent come up to a soln yet.

Thanks

- Poonam December 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

not a good solution...has O(n^2 complexity)...you need to take advantage of the fact that its a BST or that the array you created after inorder traversal is sorted.

- The Artist December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

instead of two for loops we can use BST property to reduce the complexity to nlogn...

Something like this,
i = 1; j = n;
mid = (i + j)/2;
while( i < j){
value = sum - a[i];
search the array for "value" using the BST property and if found set j to this particular location(print these values) / if not found set it to the location that just greater then value.
increment i;
}

This will run O(nlogn) & space O(n).

- havefun December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

efficcient method

- niranjan January 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Inorder gives sorted array, use two pointer approach to find the sum, becomes linear (2n).

- aaman.singh85 February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

smaller= bst.getMin();
while (smaller<larger){
    larger=bst.floor(k-smaller);
    if (larger+smaller==k){
             print(larger, smaller);
            return;
     }
    smaller=bst.ceiling(k-larger);
    if (larger+smaller==k){
              print(larger,smaller);
              return;
    }
print("no answer");
}

- FT December 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain your answer...and also I don't recall floor and ceiling being normal functions of a bst...

- code4ghana December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is easy to modify a Binary search to get a FLOOR or CEILING. if we you are at a leaf and have not found the key, return predecessor or successor, respectively.

1- choose the min as for the smaller.
2- find the larger number in a way that smaller+larger is equal to k or is closet smaller number to k. return if equal to k.
3- if you are here it means that smaller + larger < k. therefore, let's find another number for smaller so that smaller + larger = k or is the closest smaller number to k. if equal to k return. else go to 2.

basically, larger variable gets smaller in each step. and smaller variable gets larger in each step, until either the result is found or smaller get bigger than larger.

- FT December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

did not have energy to go through your logic but hope you considered that the tree may have negative numbers...

- The Artist December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You could store the nodes into a hastable with extra O(n) space.
Traverse the BST.
If node.value>k, visit only the left child of the node.
Else if n-k<n: check to see if n-k is in the hastable if not, put n into the hastable, visit the left child first, the the right.
Else: check to see if n-k is in the hashtable if not put n into visit right child first, then visit left child.
//of course in both else scenarios, if n-k is in the hashtable, you have found a pair and you can exit.

Runtime: this will be at most O(n) but it should be in practice ~O(lgn).

- code4ghana December 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Text;

namespace bst
{
public class Node
{
private int value;
private Node left;
private Node right;
public Node(int value, Node left, Node right)
{
this.value = value;
this.left = left;
this.right = right;
}

public int Value
{
get { return this.value; }
}
public Node Left
{
get { return this.left; }
}

public Node Right
{
get { return this.right; }
}

public override string ToString()
{
return value.ToString();
}
}

public class TwoNumbers
{
public int No1 { get; set; }
public int No2 { get; set; }
}

public class Tree
{


public TwoNumbers SumOfTwo(Node root, int value)
{
Node temp = null;
TwoNumbers ret = new TwoNumbers();

temp = root;

while (temp != null)
{
Console.WriteLine(temp);

if (value > temp.Value)
{
if (ret.No1 == 0)
{
if (temp.Right == null || temp.Right.Value >= value)
{
Console.WriteLine("No1 set to " + temp);
ret.No1 = temp.Value;
temp = root;
continue;
}
else
{
temp = temp.Right;
continue;
}
}
else
{
if (value - ret.No1 == temp.Value && ret.No1 != temp.Value)
{
Console.WriteLine("No2 set to " + temp);
ret.No2 = temp.Value;
return ret;
}

if (value - ret.No1 < temp.Value)
{
temp = temp.Left;
}
else
{
temp = temp.Right;
}
}
}
else
{
temp = temp.Left;
}
}

return ret;
}
}

class Program
{
static Node PrepareBinaryTree()
{
Node n1 = new Node(1, null, null);
Node n4 = new Node(4, null, null);
Node n7 = new Node(7, null, null);
Node n13 = new Node(13, null, null);

Node n2 = new Node(2, n1, null);
Node n6 = new Node(6, n4, n7);
Node n14 = new Node(14, n13, null);

Node n3 = new Node(3, n2, n6);
Node n10 = new Node(10, null, n14);

Node n8 = new Node(8, n3, n10);

return n8;
}

static void Main(string[] args)
{
Tree tree = new Tree();
Node root = PrepareBinaryTree();

TwoNumbers found = tree.SumOfTwo(root, 2);

Console.ReadLine();
}
}
}

- Dogu December 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can modify TwoNumbers found = tree.SumOfTwo(root, 2);

It will find first higest smaller number than th target, then tries to find its complement, if fails, returns No2=null

- Dogu December 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void Find(struct Node *node,int sum,map<int ,struct Node *> &mymap)
{
if(!node)
return;
map<int ,struct Node *> :: iterator it;
Find(node->left,sum,mymap);
it=mymap.find(node->data);
if(it!=mymap.end())
printf("%d %d \n",node->data,it->second->data);
else
mymap.insert(pair<int,struct Node *>(sum-node->data,node));
Find(node->right,sum,mymap);
}

- Anonymous December 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Two stacks S1,S2 both have inorder traversal in LrtR and RRtL manner, keep popping out from stack and check sum.

- Ashar December 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think if you used an array instead of a stack, you won't have to store the data twice.

- Yang December 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Yang, I believe the maximum stack depth would be log n in average case, hence total memory used would be 2 * log n , and in case of array it has to be n. Hence on an average case 2 stacks has to be a preferred option.

- m3th0d.itbhu April 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is my approach
1. store inorder traversal of the tree to a list
2. given the numbers are sorted increasing order after the inorder traversal, you can then do a linear scan.

// Given a BST, Find if two nodes add up to a sum K

public static bool SumExists(Node node, int k)
{
	List<int> nodeValues = InOrder(node);
	int left = 0, right = nodeValues.Count() - 1;

	while(left < right)
	{
		int val = nodeValues[left] + nodeValues[right];
		if (val == k)
			return true;
		else if (val < k)
			left ++;
		else
			right --;
	}

	return false;
}

List<int> InOrder(Node root)
{
	List<int> output = new List<int>();
	InOrder(root, output);
	return output;
}

void InOrder(Node root, List<int> output)
{
	if(root == null)
		return;

	InOrder(root.left, output);
	output.add(root.val);
	InOrder(root.right, output);
}

- Yang December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use Queue and traverse the queue in a loop and compare the addition of prev and current node with given sum. If sum is equal then exit and print those two nodes.

- Raja January 23, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More