Microsoft Interview Questions

1)Given a Parent -Child binary tree ,build the child -sibling version of it?
Minimize the space requirements wherever possible.

2)Given a binary tree build a linked list of all its nodes such that the nodes of a level appear before the nodes of the next level?

3)Given an infinite stream of bits with the bits being appended at the highest significant position. give an algorithm to to say whether the number formed by using the sequence of bits that had been processed till then, is divisible by 3 or not?

4)Given a string S of words and no of character per line m ,with m being greater than the longest word in S,print S in a set of lines so that each line contains no more than m characters and no word split between 2 lines.

5)Given an expression remove the unnecessary brackets in it with out creating an ambiguity in its execution.
input output
ex1: (a+(b)+c) a+b+c


ex2: (a*b)+c a*b+c


6)Propose a tree based data structure to identify a node with nth rank with maximum efficiency .

7)Given a string S of alphabets and 2 characters a,b find the minimum distance between instances of them such that position of a <= position of b.

8)Given an array of size n with first l positions filled with characters and a string s ,replace all the instances of ’%’ with this string s,given that the lengh of the array is sufficient to handle these substitutions.
input output
eg: abcdef%ghi%—— and “ppp” abcdefpppghippp

9)Given a binary tree verify whether it is a binary search tree or not?
10)Write a C code to merge 2 binary search trees and do the same 2 merge linked lists.How is the former different when compared to the later.(Discuss the issues)