Flipkart Interview Question
Senior Software Development EngineersTeam: digital
Country: India
Interview Type: Phone Interview
We will do this by doing a pre order traversal by the tree and maintaining of stack of conditions at each node. i.e. if we are traversing the left tree then we add a condition (< value of node) and if right then condition (>= value of node). These are the conditions that a BST satisfies. For each node check which conditions is doesn't satisfy in the stack and print the pair for which it doesn't satisfy the condition. Running time n nodes and logn comparisons for each node no n*log(n)
Its complexity will be O(n^2), not O(n*log(n)).
Suppose, you start from root node, then to check that it follows BST property, we have to make sure all of the nodes in its left sub-tree are smaller than root. And all nodes in right sub-tree are greater or equal to it. So effectively we are comparing root's values with n-1 nodes. Therefore, its complexity would be O(n^2).
You can solve in O(n*logn*logn), which is even better than O(n^2):
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace PrintWrongPairsInBST
{
class Program
{
static void Main(string[] args)
{
//Tree:
// 7
// 2 19
// 8 5 12 17
// 13 21
// 46
//Which isnt sorted
Tree t = new Tree(7);
t.left = new Tree(2);
t.right = new Tree(19);
t.left.left = new Tree(8);
t.left.right = new Tree(5);
t.right.left = new Tree(12);
t.right.right = new Tree(17);
t.left.right.left = new Tree(13);
t.right.right.left = new Tree(21);
t.right.right.left.left = new Tree(46);
Process(t,
new LinkedList<int>(),
new LinkedList<char>());
}
static void Process(Tree t,
LinkedList<int> value,
LinkedList<char> direction)
{
if (t == null) //Very base case
{
return;
}
if (t.left == null && t.right == null) //Leaf
{
if (value.Count > 0)
{
int[] pathValue = new int[value.Count + 1];
int index = 0;
foreach (int v in value)
{
pathValue[index++] = v;
}
pathValue[index++] = t.info;
char[] pathDirection = new char[direction.Count + 1];
index = 0;
foreach (char d in direction)
{
pathDirection[index++] = d;
}
pathDirection[index++] = 'U';
ProcessPath(pathValue,
pathDirection);
}
return;
}
//Induction
value.AddLast(t.info);
direction.AddLast('L');
Process(t.left,
value,
direction);
value.RemoveLast();
direction.RemoveLast();
value.AddLast(t.info);
direction.AddLast('R');
Process(t.right,
value,
direction);
value.RemoveLast();
direction.RemoveLast();
}
static void ProcessPath(int[] value,
char[] direction)
{
for (int i = value.Length - 1; i >= 0; i--)
{
for (int j = i - 1; j >= 0; j--)
{
if (direction[j] == 'L')
{
if (value[i] > value[j])
{
Console.WriteLine("({0}, {1})", value[i], value[j]);
}
}
else if (direction[j] == 'R')
{
if (value[i] < value[j])
{
Console.WriteLine("({0}, {1})", value[i], value[j]);
}
}
}
}
}
}
class Tree
{
public int info = 0;
public Tree left = null;
public Tree right = null;
public Tree(int info)
{
this.info = info;
this.left = null;
this.right = null;
}
}
}
Solution:
(8, 2)
(8, 7)
(13, 5)
(13, 7)
(46, 21)
(46, 17)
(21, 17)
(17, 19)
One way is to do in order traversal of the tree and look for count inversions, means whether the next number is smaller than the other. O(nlogn)
- nascent February 12, 2014