Microsoft Software Development Engineer-II interview questions

I had phone interview with hiring manager. He was really nice and supportive. he asked question about my background and what i do at my current company. explained it well. then coding question - write a program to add a node to the list. I asked if i should consider it as sorted linked list. They always expect the better code, so when you write down "working" code, they'll ask to modify it. At end, I asked few questions about the team & company & product. overall experience was good.

Interview 1 1) You have a c style string containing some spaces. Move the spaces to the starting of the string. Do it in place in one iteration. 2) You have a bit pattern and an infinite stream of bits coming in. You need to raise an alarm whenever the given pattern comes. Storing the stream is not allowed. Interview 2 1) You have an array of size N. Implement a queue using this. 2) A sorted array has been rotated. You need to find out the point of inflexion, i.e the position at which the smallest element of the array is present.(I did this in log n time) For example if the array is [6,7,8,9,1,2,3,4,5], the output should be 4 Interview 3 1) You have a BST and int value(take it to be variable val). You need to print our all possible paths in the BST which sum to val, they may or may not start at the root. 2) You are given a dictionary and two strings a and b. You need to convert the string a to b such that only one alphabet is changed at a time and after each change the transformed string is in the dictionary. You need to do this in the minimum number of transformations. For example the transformation from cat-->boy can be done as follows cat-->bat-->bot-->boy (if dictionary has bat and bot) Interview 4 1) You gave been given a tree(not binary, it can have any number of children) in an array. The ith entry of the array is the parent of the ith node. For the root node this entry is -1. You need to find the height of this tree(O(n) soln was asked for). For example the array [2,6,3,6,3,6,-1] represents the tree below. The height of the tree is 4(the path from 6 to 0) 6 / | \ 1 3 5 / \ 2 4 / 0