Mohit
BAN USER- -2of 4 votes
AnswersAsked to explain how to check Binary tree is BST?
- Mohit in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -3of 3 votes
AnswersFind Nodes which are at "K" distance from given node.
- Mohit in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -3of 3 votes
AnswersFind In order predecessor in BST.
- Mohit in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -4of 4 votes
Answersasked me about assembly line problem.
- Mohit in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - -4of 4 votes
Answersasked me to solve Knapsack Problem
- Mohit in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - -3of 3 votes
AnswersAsked to explain how to check Binary tree is BST?
- Mohit in India
then asked me to write whole code of it.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -3of 3 votes
AnswersFind In order predecessor in BST.
- Mohit in India
explain logic and write full code with all boundary conditions.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
I think we have to do post order traversal
and set node value as
private int PostOrderTrav(Node node)
{
if(node == null)
return 0;
int LeftVal = PostOrderTrav(node.Left);
int rightVal = PostOrderTrav(node.Right);
node.Value = Math.Max(node.Value , LeftVal+rightVal)
return node.Value
}
We have to use augmented data structure.
We have to create a balanced binary search tree.
Node structure will be like
Node
{
Node Left;
Node Right;
int value;
int NoOfChildNodes;
}
While adding each node we keep on updating "NoOfChildNodes" for all nodes who all will
be parent of new node.
After creating that tree we can find any ith Min/Max Node.
Now we have to find 1000th min node
we will start from root node and start traversing downwards.
If (node.NoOfChildNodes > 1000)
// traverse on right child
else
// traverse on right child. We have to update the i value also.
Let node.NoOfChildNodes = 1200 and i = 1000
if node.Left.NoOfChildNodes = 700 and Node.right.NoOfChildNodes = 500
then we have to find 300th Min element in right sub tree. (1000-700).
Keep on traversing downward till we get desired node.
Complexity computation
Making Balanced Binary search tree(ex AVL tree) for n nodes is: O(nlog(n))
For searching element in BST : O(log n)
For very large n vale , log(n) is negligible
that is nlog(n)+log(n) ~= nlog(n)
cristian.botau is correct
Solution with start and end is not giving correct solution with
Further improvement in Mukseh's first code can be done by adding check for
if (i > n - result)
break;
Complete code will be as
int result = 0;
for (int i = 0; i < (n - 1); i++)
{
if (i > n - result)
break;
int[] count = new int[2] { 0, 0 };
for (int j = i; j < n; j++)
{
count[a[j]]++;
if ((count[0] == count[1]) && (count[0] > result / 2))
result = 2 * count[0];
}
}
class SpiralMove2DArray
{
int[,] array;
int[,] traversed;
const int ArrayBound = 4;
enum direction
{
east, south, west, north
}
direction MoveDir;
int xIndex, yIndex;
public SpiralMove2DArray()
{
array = new int[ArrayBound, ArrayBound];
traversed = new int[ArrayBound, ArrayBound];
MoveDir = direction.east;
xIndex = 0;
yIndex = 0;
int k = 0;
for (int i = 0; i < ArrayBound; i++)
{
for (int j = 0; j < ArrayBound; j++)
{
array[i, j] = k;
k++;
}
}
PrintValue();
while (CanTraverse())
{
switch (MoveDir)
{
case direction.south:
if (CanMoveSouth())
{
xIndex += 1;
PrintValue();
}
else
{
MoveDir = direction.west;
}
break;
case direction.east:
if (CanMoveEast())
{
yIndex += 1;
PrintValue();
}
else
{
MoveDir = direction.south;
}
break;
case direction.north:
if (CanMoveNorth())
{
xIndex -= 1;
PrintValue();
}
else
{
MoveDir = direction.east;
}
break;
case direction.west:
if (CanMoveWest())
{
yIndex -= 1;
PrintValue();
}
else
{
MoveDir = direction.north;
}
break;
default:
break;
}
}
}
private void PrintValue()
{
Debug.WriteLine(array[xIndex, yIndex]);
traversed[xIndex, yIndex] = 1;
}
private bool CanTraverse()
{
if (CanMoveEast() || CanMoveNorth() || CanMoveSouth() || CanMoveWest())
{
return true;
}
return false;
}
private bool CanMoveSouth()
{
if ((xIndex == ArrayBound - 1) || (traversed[xIndex + 1, yIndex] == 1))
return false;
return true;
}
private bool CanMoveEast()
{
if ((yIndex == ArrayBound - 1) || (traversed[xIndex, yIndex + 1] == 1))
return false;
return true;
}
private bool CanMoveNorth()
{
if ((xIndex == 0) || (traversed[xIndex - 1, yIndex] == 1))
return false;
return true;
}
private bool CanMoveWest()
{
if ((yIndex == 0) || (traversed[xIndex, yIndex - 1] == 1))
return false;
return true;
}
}
We have to make 2 for loops
1. for placing red cards
2. find position for red card
We are maintaining an array.
I am placing value "1" where we will place red card.
In 2nd inner loop we have to check for 2 conditions:
1. if Index > array bound .. set it as 0.
2. If we get "1" at any location discard it while counting "K"
Here is the code for it.
SetCards(7, 8, 5)
internal void SetCards(int blackCards, int redcards, int K)
{
int[] array = new int[blackCards + redcards];
int index = -1;
for (int i = 0; i < redcards; i++)
{
for (int j = 0; j < K;)
{
index++;
if(index == array.GetLength(0))
{
index = 0;
}
if (array[index] != 1)
{
j++;
}
}
array[index] = 1;
}
}
How about following these steps
1.
if(a <= 0 || b <= 0 || c <= 0)
return error;
if(a == b && a == c)
return equilateral;
else if (a==b || b==c || a==c)
return isosceles;
else
{
if( //sort these three numbers and if smallest+middle > largest)
return scalene;
else
return error;
}
We have to use dynamic programming approach
int[] coinsArray = new int[5] { 1, 2, 5, 10, 20 };
private int GetMinNo(int iAmount)
{
array = new int[coinsArray.GetLength(0) + 1, iAmount + 1];
for (int i = 0; i < array.GetLength(0); i++)
{
for (int j = 0; j < array.GetLength(1); j++)
{
array[i, j] = 0;
if(i == 1)
{
array[i, j] = j;
}
}
}
for (int iCoin = 2; iCoin < array.GetLength(0); iCoin++)
{
for (int amount = 0; amount < iAmount + 1; amount++)
{
array[iCoin, amount] = Math.Min(array[iCoin-1, amount], amount / coinsArray[iCoin - 1] + array[iCoin-1, amount % coinsArray[iCoin - 1]]);
}
}
return array[array.GetLength(0)-1, array.GetLength(1)-1];
}
we have to print all nodes which are child of desired nodes and are child of parent nodes.
public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance)
{
if ((root == null) || (iDistance < 0))
return -1;
int lPath = -1, rPath = -1;
if(root.value == requiredNode)
{
PrintChildNodes(root, iDistance);
return iDistance - 1;
}
lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance);
rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance);
if (lPath > 0)
{
PrintChildNodes(root.right, lPath - 1);
return lPath - 1;
}
else if(lPath == 0)
{
Debug.WriteLine(root.value);
}
if(rPath > 0)
{
PrintChildNodes(root.left, rPath - 1);
return rPath - 1;
}
else if (rPath == 0)
{
Debug.WriteLine(root.value);
}
return -1;
}
public void PrintChildNodes(Node aNode, int iDistance)
{
if (aNode == null)
return;
if(iDistance == 0)
{
Debug.WriteLine(aNode.value);
}
PrintChildNodes(aNode.left, iDistance - 1);
PrintChildNodes(aNode.right, iDistance - 1);
}
All these test cases are working
//string str = "960961962964";
//string str = "123457891011";
//string str = "12345789";
//string str = "123412351237";
//string str = "123112321234";
//string str = "293031323335";
//string str = "99101";
//string str = "99100101103104";
//string str = "99101";
string str = "911";
class FindMissing
{
private string astr;
public int missingNo = -1;
public FindMissing(string astr)
{
this.astr = astr;
Perform();
}
private void Perform()
{
int i = 0;
for (; i < astr.Length/2 ; i++)
{
int abc = Convert.ToInt16(astr.Substring(0, i+1));
bool a = DoCheck(abc.ToString().Length, abc + 1, true);
if (true == a)
break;
}
}
private bool DoCheck(int startIndex, int expectedNo, bool isLastok)
{
int abc = Convert.ToInt16(astr.Substring(startIndex, expectedNo.ToString().Length));
bool isCont = (expectedNo == abc) ? true : false;
if (false == isCont)
missingNo = expectedNo;
if (isCont == false && isLastok == false)
{
return false;
}
else
{
if (startIndex + expectedNo.ToString().Length < astr.Length)
{
if (true == DoCheck(startIndex + expectedNo.ToString().Length, abc+1, isCont))
return true;
}
else
return true;
}
return false;
}
}
public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance)
{
if ((root == null) || (iDistance < 0))
return -1;
int lPath = -1, rPath = -1;
if(root.value == requiredNode)
{
PrintChildNodes(root, iDistance);
return iDistance - 1;
}
lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance);
rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance);
if (lPath > 0)
{
PrintChildNodes(root.right, lPath - 1);
return lPath - 1;
}
else if(lPath == 0)
{
Debug.WriteLine(root.value);
}
if(rPath > 0)
{
PrintChildNodes(root.left, rPath - 1);
return rPath - 1;
}
else if (rPath == 0)
{
Debug.WriteLine(root.value);
}
return -1;
}
public void PrintChildNodes(Node aNode, int iDistance)
{
if (aNode == null)
return;
if(iDistance == 0)
{
Debug.WriteLine(aNode.value);
}
PrintChildNodes(aNode.left, iDistance - 1);
PrintChildNodes(aNode.right, iDistance - 1);
}
Many of the solution here used 3 for loops .. using them here is ok, because we know we have 3 options 20,9,6
What if we have large set of options then making that no of for loops will not be a good solution.
Better use recursion or backtracking algo:
Hint of backtracking ....
we should make logic which runs like:
20, 9, 6
20, 9, 6, 6 ... till this sum <= desired value
when all combination with one 20 and one 9 are over
then work for
20, 9 , 9 , 6
20, 9 , 9 , 6, 6 ...
and so on ... till we get valid sum or all over options get exhausted.
This solution works great if there are no duplicate values in the array.
example:
if we have missing element 5 and 4 occur twice then result has to be 5 (as expected)
but it will be 4(from array) XOR 4 (from array) XOR 4 (from Index) XOR 5 (from Index)
Now result will be from = 4 (from Index) XOR 5 (from Index) .. as both 4 from array will cancel mutual effect.
to solve this situation we can take one more array of bool(Occupancy Array). What ever value we get from array we go to that
index of occupancy array and mark it as occupied (true). After traversal of all value ... we traverse this occupancy array ...
the index which has false value will be our result.
I tried to make the equation where
- Mohit March 27, 2016n => No of total images which can be viewed which we want to maximize
X = m*(n-1) + (n-a)Vp + a(Rp + Vp)
X => Total cost given in problem
a => No of landscape images that can be viewed
n-a => No of portrait images
But now I am not getting how to proceed further.