## Microsoft Interview Question for Software Engineer in Tests

• 0

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

f(t,0);
int f(tree *t,int cnt)
{
if(!t) return cnt;
else if(t->data)
{
cnt++;
cl = f(t->left);
cr = f(t->right);
return max(cl,cr);
}
else
return cnt;
}

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

int f(node * t) {
if(!t) return 0;
if(t->data==0) return 0;
else {
int leftdepth =f(t->left);
int rightdepth = f(t->right);
if(leftdepth>rightdepth)
return leftdepth +1;
else
return rightdepth+1;
}
}

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

public static int checkDeepestOne(BinaryTreeNode node){
if(node == null){
return 0;
}

if(node.element.compareTo(1) == 0){
return 1 + Math.max(checkDeepestOne(node.left),checkDeepestOne(node.right));
}
else{
return 0;
}
}

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

@All above,
Please follow the question correctly.. Question is related to finding "PATH" and you all people are just trying to find position(depth) of deepest 1.

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

The question is to find the deepest path of all 1's. If 0, return, if 1, recurse counting depth.

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

a position can also mean a path, as for a tree, there is only one path to reach a position

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

Do the BFS and find the required deepest Node Pointer.

If Once you found the deepest node then find the path between root to deepest Node.

void findPath(Node root, Node node){
Stack->push(root);
if(node == root){
print stack data;

return;
}
if(root->left != null){
findPath(root->left, node);
}
if(root->right!=null){
findPath(root.right, node);
}
Stack->pop();
}

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

int path_depth(node *cur)
{
if(cur == NULL)
{
return 0;
}
if(cur->data ==0)
{
return 0;
}
if(cur->data == 1)
{
return max(path_depth(cur->left), path_depth(cur->right)) + 1;
}
}

void print_path(node *cur)
{
if(cur == root && root->data == 1)
{
print(root->data);
}
if(cur->data == 0)
{
return;
}
if(cur->left && cur->right)
{
if(path_depth(cur->left) > path_depth(cur->right))
{
print_path(cur->left);
}
if(path_depth(cur->left) < path_depth(cur->right))
{
print_path(cur->right);
}
if(path_depth(cur->left) == path_depth(cur->right) && path_depth(cur->left) == 0)
{
return;
}
else
{
print_path(cur->right);
}
}
else if(cur->left)
{
print_path(cur->left);
}
else if(cur->right)
{
print_path(cur->right);
}
else
{
return;
}
}

Please correct me if you think I was wrong or this is too complicated. Thanks.

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

@aammgg didn't check you approach, but the idea might work. As a matter of fact using dynamic programing approach we could do less calculations, but as usual memory vs. loops... Bellow code could be optimized e.g. by removing new Stack for cases where allocation doesn't make sense etc. Please let me know your thoughts. here's my solution:

{{
static Stack FindPath(TreeNode root)
{
Stack stack = new Stack();
if (root != null && root.Value == 1)
{
Stack left = FindPath(root.Left);
Stack right = FindPath(root.Right);

if (left.Count > right.Count)
{
stack = left;
}
else
{
stack = right;
}

stack.Push(root);
}

return stack;
}

-- print
Stack st = FindPath(node);

while (st.Count > 0)
{
// print some name, printing 1s doesn't make sense...
Console.WriteLine(((TreeNode)st.Pop()).Name);
}
}}

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

It is easy to solve this if the path is not required. But if path is required it becomes little more complex.

``````public List<BinaryNode> FindPathToDeepest1Node(BinaryNode startNode)
{
if (null == startNode)
{
return null;
}

List<BinaryNode> deepest1Path = new List<BinaryNode>();
int pathLen = FindPathToDeepest1NodeRecur(startNode, ref deepest1Path);
Console.WriteLine("Path length of the longest path with 1's is {0}", pathLen);
return deepest1Path;
}

private int FindPathToDeepest1NodeRecur(BinaryNode startNode, ref List<BinaryNode> deepest1Path)
{
int pathLen = 0;
if (null == startNode || startNode.Value == BinValue.Zero)
{
return pathLen;
}

pathLen++;

List<BinaryNode> deepest1PathLeft = new List<BinaryNode>();
int deepestLenInLeftSubTree = FindPathToDeepest1NodeRecur(startNode.Left, ref deepest1PathLeft);

List<BinaryNode> deepest1PathRight = new List<BinaryNode>();
int deepestLenInRightSubTree = FindPathToDeepest1NodeRecur(startNode.Right, ref deepest1PathRight);

if (deepestLenInLeftSubTree >= deepestLenInRightSubTree)
{
pathLen += deepestLenInLeftSubTree;
}
else
{
pathLen += deepestLenInRightSubTree;
}

return pathLen;
}``````

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

``````// Call following method with currCount = 0 ; maxCount = 0;
// After method returns print 1  maxCount times.

public void DeepestOnePath(treeNode curr, int currCount, ref int maxCount) //Method
{
if (curr == null || curr.value == 0)
return;

currCount++;

// if a leaf Node
if (curr.rightChild == null && curr.leftChild == null)
{
if (maxCount < currCount)
maxCount = currCount;

return;
}

DeepestOnePath(curr.leftChild, currCount, ref maxCount);
DeepestOnePath(curr.rightChild, currCount, ref maxCount);
}``````

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

``````template <typename T>
string deepest1(struct BTNode<T>* t) {
if (t != NULL) {
if (isLeaf(t)) return "";
if (t->data == 1) {
string l = deepest1(t->left);
string r = deepest1(t->right);
if (l.length() > r.length()) {
if (t->left != NULL && t->left->data == 1) return "l"+l;
return l;
}
else {
if (t->right != NULL && t->right->data == 1) return "r"+r;
return r;
}
}
}
return "";
}``````

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

public static Stack<Node> FindMaximumDepthOfNode(Node inputNode)
{
Stack<Node> retPath = new Stack<Node>();

if(inputNode != null && inputNode.data != 0)
{
Stack<Node> leftPath, rightPath;

leftPath = FindMaximumDepthOfNode(inputNode.leftNode);
rightPath = FindMaximumDepthOfNode(inputNode.rightNode);

if (leftPath.Count >= rightPath.Count)
{
retPath = leftPath;
}
else
{
retPath = rightPath;
}

Node currentNode = inputNode;
currentNode.leftNode = null;
currentNode.rightNode = null;
retPath.Push(inputNode);
}

return retPath;
}

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

public static Stack<Node> FindMaximumDepthOfNode(Node inputNode)
{
Stack<Node> retPath = new Stack<Node>();

if(inputNode != null && inputNode.data != 0)
{
Stack<Node> leftPath, rightPath;

leftPath = FindMaximumDepthOfNode(inputNode.leftNode);
rightPath = FindMaximumDepthOfNode(inputNode.rightNode);

if (leftPath.Count >= rightPath.Count)
{
retPath = leftPath;
}
else
{
retPath = rightPath;
}

Node currentNode = inputNode;
currentNode.leftNode = null;
currentNode.rightNode = null;
retPath.Push(inputNode);
}

return retPath;
}

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

Here is a solution from my side. Please let me know your views,

static int count = 0;
Stack S = new Stack();

void deepestNode(Node * root)
{
if(root == null)
return;
if(root.data == 1)
root.data = count;
s.Push(root);
count++;
deepestNode(root->left);
deepestNode(root->right);
}

The stack can then be checked for the deepest level node in the tree. The path of which can be determined from the tree again. Traversal log(n)

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

Is everyone over thinking, or am I missing something here ?

``````List<Node> depth(Node p, List<Node> nodePath)
{
if(p==NULL || p.left().value != 1)return nodePath ;

List<Node> left = depth(p.left());
List<Node> right = depth(p.right());

if (left.size() > right.size())
return left;
else
return right;
}``````

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

Sorry I Copy pasted something out of order

``````List<Node> depth(Node p, List<Node> nodePath)
{
if(p==NULL || p.left().value != 1)return nodePath ;

List<Node> left = depth(p.left(), nodePath);
List<Node> right = depth(p.right(), nodePath);

if (left.size() > right.size())
return left;
else
return right;
}``````

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

Simple and neat solution...

``````void printLongestPathWithOnes(node* root, int cpath[], int clen, int mpath[], int &mlen)
{
if(!root || !root->data)
return;

cpath[clen++] = root->data;

if(clen > mlen)
{
mlen = clen;
for(int i = 0; i < mlen; i++)
mpath[i] = cpath[i];
}

printLongestPathWithOnes(root->left, cpath, clen, mpath, mlen);
printLongestPathWithOnes(root->right, cpath, clen, mpath, mlen);
}``````

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

'

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

and 1=

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

' and 1=

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

\'

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

'''

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

ookjk85h74

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

1 OR 1=1

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

1' OR '1'='1

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

1'1

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

' 1 AND 1=1

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

1 AND 1=1

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

1\'1

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

) or ('1'='1--

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

' or 1=1/*

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

' or 1=1--

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

order by 1000/*

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

order by 1000;--

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

' order by 1000/*

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

' order by 1000;--

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

' or 1=1--

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

" or 1=1--

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

') or ('a'='a

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

'

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

and 1=

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

' and 1=

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

\'

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

'''

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

ookjk85h74

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

1 OR 1=1

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

1' OR '1'='1

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

1'1

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

' 1 AND 1=1

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

1 AND 1=1

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

1\'1

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

) or ('1'='1--

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

' or 1=1/*

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

' or 1=1--

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

order by 1000/*

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

order by 1000;--

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

' order by 1000/*

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

' order by 1000;--

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

' or 1=1--

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

" or 1=1--

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

') or ('a'='a

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

'

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

and 1=

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

' and 1=

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

\'

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

'''

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

ookjk85h74

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

1 OR 1=1

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

1' OR '1'='1

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

1'1

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

' 1 AND 1=1

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

1 AND 1=1

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

1\'1

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

) or ('1'='1--

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

' or 1=1/*

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

' or 1=1--

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

order by 1000/*

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

order by 1000;--

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

' order by 1000/*

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

' order by 1000;--

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

' or 1=1--

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

" or 1=1--

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

') or ('a'='a

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

``````public class DeepestOneInBinaryTree {

class Node{
int value;
Node leftChild, rightChild;
boolean isLeftChildOfRoot;
}

static int deepestOneInTree(Node root){
if(root == null){
return 0;
}
Stack<Node> pathFromRoot = new Stack<Node>();
Node longestPathEndPoint;
int maxLengthOfValidPath=0;
int currentLengthOfValidPath=0;
while(!pathFromRoot.empty()){
Node currNode = pathFromRoot.peek();
boolean doneProcessingNode = false;
if(currNode.value == 1){
currentLengthOfValidPath = pathFromRoot.size();
if(currentLengthOfValidPath > maxLengthOfValidPath){
maxLengthOfValidPath = currentLengthOfValidPath;
longestPathEndPoint = currNode;
}
if(currNode.leftChild != null){
pathFromRoot.push(currNode.leftChild);
currNode.leftChild.isLeftChildOfRoot = true;
} else if(currNode.rightChild != null){
pathFromRoot.push(currNode.rightChild);
currNode.rightChild.isLeftChildOfRoot = false;
} else {
doneProcessingNode = true;
}
} else {
doneProcessingNode = true;
}

if(doneProcessingNode){
pathFromRoot.pop();
boolean stackInValidState = false;
while(!stackInValidState){
if(pathFromRoot.empty()){
break;
}
Node parentOfCurrNode =  pathFromRoot.peek();
if(currNode.isLeftChildOfRoot){
if(parentOfCurrNode.rightChild != null){
pathFromRoot.push(parentOfCurrNode.rightChild);
stackInValidState = true;
} else {
currNode = pathFromRoot.pop();
}
}
}
}
}
return maxLengthOfValidPath;
}
}``````

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

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

'

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

and 1=

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

' and 1=

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

\'

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

'''

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

ookjk85h74

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

1 OR 1=1

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

1' OR '1'='1

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

1'1

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

' 1 AND 1=1

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

1 AND 1=1

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

1\'1

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

) or ('1'='1--

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

' or 1=1/*

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

' or 1=1--

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

order by 1000/*

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

order by 1000;--

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

' order by 1000/*

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

' order by 1000;--

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

' or 1=1--

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

" or 1=1--

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

') or ('a'='a

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

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

'

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

and 1=

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

' and 1=

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

\'

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

'''

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

ookjk85h74

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

1 OR 1=1

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

1' OR '1'='1

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

1'1

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

' 1 AND 1=1

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

1 AND 1=1

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

1\'1

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

) or ('1'='1--

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

' or 1=1/*

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

' or 1=1--

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

order by 1000/*

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

order by 1000;--

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

' order by 1000/*

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

' order by 1000;--

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

' or 1=1--

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

" or 1=1--

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

') or ('a'='a

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

Simple Python solution:

a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count

``````def max_path(root, count):

if not root:
return count

if root.val == 0:
return 0
else:
count += 1

count = max(max_path(root.left, count), max_path(root.right, count))

return count``````

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

Simple Python solution:

a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count

``````def max_path(root, count):

if not root:
return count

if root.val == 0:
return 0
else:
count += 1

count = max(max_path(root.left, count), max_path(root.right, count))

return count``````

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

Simple Python solution:

a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count

``````def max_path(root, count):

if not root:
return count

if root.val == 0:
return 0
else:
count += 1

count = max(max_path(root.left, count), max_path(root.right, count))

return count``````

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

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

'

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

and 1=

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

' and 1=

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

\'

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

'''

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

ookjk85h74

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

1 OR 1=1

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

1' OR '1'='1

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

1'1

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

' 1 AND 1=1

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

1 AND 1=1

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

1\'1

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

) or ('1'='1--

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

' or 1=1/*

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

' or 1=1--

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

order by 1000/*

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

order by 1000;--

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

' order by 1000/*

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

' order by 1000;--

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

' or 1=1--

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

" or 1=1--

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

') or ('a'='a

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.