I summarized the microsoft interview questions on geeksforgeeks website
(http://www.geeksforgeeks.org/tag/microsoft/) and I solved these questions(https://docs.google.com/file/d/0B3x3UPn47ZkKWnV2LU1EZHItcXM/edit) but these was korean.
I rellay hope that these will be helpful to prepare your interview.
Thanks!
Q1. Given a sorted array having duplicate elements,how would you find first index of a given element in O(logn).
Write code for it. Change the condition to find out last index of that elements.
[ Hint Binary search]
Q2. You have a dictionary of words. Given a word, print all anagram are in dictionary . State the data structure to be used to solve this problem.
Q2. Reverse a 32-bit integers. write code for it.
Q4. You have a file with million words in it. Find most frequent 10 word in that file. Node that you can store all word in memory.
(Note : Min-Heap + List )
Q2. Given a BST, find out the minimum length form root to leaf with sum S. Note that:
a) Path from root to leaf node.
b) Sum of node of the path is S.
c) if multiple such path exist, print minimum length path.
d) What is advantage of BST rather than BT used for this algorithm, how it improve the performance. in BST, is it required to explore both side ?
e) Write working codes for it.
Given two integers represented in Linked list format and now add these two lists and put it in the third list, at any point of time a node can have only one digit in it.
1. Compress a string in-place.
2. Define BST. Check a tree is BST or not.
Problem – 1: Given a singly linked list,in which the last node points to the middle node,delete the middle node and remove the loop.
Problem – 2: Given an array of size n, find the majority element.Majority element is one which gets repeated for more than n/2 times.
1) Copy a linked list with next and arbit pointer.
(http://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/).
I told him that I knew this question, then he asked me for the approach and test cases and moved to the next question.
2) Given two sorted arrays. Second array has enough extra space to accommodate elements in first array. Give the resulting sorted array obtained by merging two arrays without using extra space.
3) Consider a binary tree for which root node and a target node are given to you. Give the next sibling of the target.(let the target be in level k, then you need to give the immediate node which is in level k)
Q2. He asked me to write the code to clone a singly linked list with next and random pointer and told me not to worry about any space complexity. A fairly easy one. Solved it using a hash.
Q3. In continuum to the previous question, he asked me to rewrite the above code without using any hash. Did it very quickly :P.
Q1. He asked me to write a function which will connect all the nodes in a binary tree at the same level.
I told him, I knew it and explained it in brief. He was cool and asked me whether I wanted to have a new question or just write this one. I said, “As you wish”. So he moved on.(아는 문제가 나왔을 때 대처 법)
Q3. He quickly moved to the last question. A file with numbers from 0-9999999 (each number in a line) is given. How to sort the content. I gave him a solution with radix sort (as maximum 7 digits are possible for each number). Then he posed a constraint of very less RAM available. I discussed a modified external merge sort like algorithm with him. But then he told me to minimize the huge time taken by external merge sort. Then he gave a hint as “Use bits”. So I told him, to use a 10^7 size vector (which actually uses one bit for one boolean).
Finally I was HIRED !!! 
Q2. A matrix m*n is given. If a cell contains 0 (zero) make that row and column zero.
Q3. Given a pointer to a circular linked list, delete that node
Problem – 1: Given a word and a text, return the count of the occurences of anagrams of the word in the text.
For eg. word is “for” and the text is “forxxorfxdofr”, anagrams of “for” will be “ofr”, “orf”,”fro”, etc. So the answer would be 3 for this particular example.
Problem – 2: Given a binary tree with parent pointers, find the right sibling of a given node(pointer to the node will be given), if it doesn’t exist return null. Do it in O(1) space and O(n) time.
1. Implement a stack having findMiddle operation as well, which returns middle element of stack on O(1) time.
1. Given an array of size n, having numbers from 1..n , with one number missing and one occurring twice. Find the 2 numbers
2. Given a number having only one ’1′ and all other ’0′s in its binary representation, find position of bit which is ’1′.
3. Code for Iterative in-order Traversal of a tree.
Q1 – Rotate an array by K.
Q2 – Reverse a link list. If you are able to reverse a link list than reverse the K node’s of link list.
Q1 – Given an array which contains a number in majority (i.e. A number occurs more than 50% times in the array) need to find it.
a) Write code for merge two sorted LinkedList Inplace.
a) You are given an array containing only 3 type of characters let say a,b,c write a program to sort the array having these. Eg abcaacbbaaaaccc sort it. I gave standard 3 flag solution then he asked you are complicating it you can use other method then I gave counting method.He asked me to compare the complexity of both methods.then discuss leads to while calculating complexity we compare number of iteration only or total calculation in the program.
Ques1. Write code for run -length encoding of a given string in-place (without using any extra memory).
Sample Input: aaaaaaaaaabcccccc
Output: a10bc6
Ques1. How can we do a Tree Traversal without using a stack (not even the stack for recursion). Write code for an in-order traversal without using stack. What would be the changes in the function if we want to do a pre-order or post-order traversal?
Ques3. Given a linked list with two pointers, one is next pointer and another is a random pointer which can point to any node in the list (forward, backward or itself), you have to make a copy of this list without tempering the original list. Write the code for the same in O(n) time complexity.
Ques1. Give different possible approaches for Checking whether two strings are anagrams (with and without using hash tables). What are the possible advantages and drawbacks of each approach? Write code for the approach which involves first sorting the two strings and then matching character by character (O(nlogn) approach). Which sorting you will use and why? Write test cases also.
Ques1. Write code for finding the least common ancestor of two given nodes in a binary tree. ( both recursive and iterative approach).
5. Convert Singly and Doubly sorted linked list to BST and optimize it.
[Can be solved in O(nlog(n)) and O(n)]
1) Find the output:
void print(){ char str[20] = “hello world”; int i=0; while (str[i]!=’’) { printf("%c", str[i]); i++; str[i] = str[i-1]; }} |
There was a very detailed discussion on this question for nearly twenty minutes. I think I kind of screwed this one. Basically, I had to explain how and why does a segmentation fault occurs.
2) Suppose a linked list contains list of documents containing a particular word. You are given two such linked lists and you have to print names of all documents that contain both these words. [I gave an algorithm based on the assumption that the list contains document names in sorted order]. I was also asked to write the code regarding this. This operation can be classified as (A and B), where A and B are the words and they have lists associated with them. He then moved on to more complicated cases such as (A and B or C and (not D)). Brackets may or may not be presented. I was only asked to give an algorithm corresponding to this.
Inorder Tree Traversal without recursion and without stack!
3. If you have huge log file, you need to print last ‘n’ lines from the log file. Write a code for it assuming regular file read operations.
He was also expecting that the page hit is minimum.
I had provided a solution which would read the file one by one and then will store it in a ‘n’ size circular linked list.
4. If you have a m*n floor, find out a ‘k’ size square tile which will take care of filling the complete floor without breaking of tile.
Use GCD logic.
1. Given a no. in in form of base 4, you have to convert into base 2. The no. is given as a String. Do it in place.
3. Two BST’s are given. You have to print common nodes that are present in both of them.
2. Given a binary tree, check if it is balanced or not.
3. Given an array, find a sub-array in which all pairs have their sum greater than k.
3. Traverse a binary tree in a Zig-Zag order.
asking questions is a good gesture.
1. Given a sorted array and it has been rotated unknown times. You have to find minimum element of the array. I did in O(log n).
4. Given an unsorted array, how to divide them into two equal arrays whose difference of sum is minimum
-> First I proposed sorting and then distributing them to two buckets. She’s fine with that. However she doesn’t want to sort the array and asked if i can solve in O(n) time
1. Given an array, rotate the elements of an array within O(n) time and with 0(1) space
1. Given a sorted array, find the pair of elements whose sum can be equal or close to given sum
2. Given an array [a1b2c3d4] convert to [abcd1234] with 0(1) space and O(n) time
1. Given Linked list, write heapify and delete methods.
2. Given two sorted arrays of any length, find out the median of them if they are sorted into single array.
1) Write a program for beautificaion (proper indentation) of a program file in an IDE.
ex:
int main(){
if(i<10){if(i>10)
prinf("Hi");else{};
}else{}
return 0;
}You are provided with getToken() which returns a token
ex: if(i>10) is a token
int main() is a token
{,} are tokens
so output should be
int main()
{
if(i<10)
{
if(i>10)
printf("hi");
else
{
}
}
else
{
}
return 0;
}
void beautify(char* inputfile,char* outputfile)
Give some testcases for the above program
2) Write a program to find the diameter of a binary tree and then he wanted to extend it for m-ary tree.
1) You are provided with a string which contains single byte as well as two byte characters. If a character is single byte char, it’s MSB is 0, if it’s a 2 byte char, it’s MSB is 1. Write a program to check whether the given string is palindrome or not.
Test cases for above program.
1) Write a program to Validate an IPv4 Address.
Write test cases for above program.
Write a code for printing last n lines in a file (refer man page of tail command in linux). The file size may vary, it may be 1MB or it may be 100 GB.
Give top 10 test cases for the above program
1. Swap every consecutive odd and even positioned bit in a number.
Ex:- 10101011010101 = 01010111101010
2. Given a binary search tree . Convert it into a doubly linked list in place (no extra space) such that prev points to left child and next points to right child.
3. Given a linked list that contains 0,1 and 2 . Sort this linked such that it contains 0s first, then 1s and then 2s in O(n) time. Ex:- 2->2->1->0->0->2->1->1->0 = 0->0->0->1->1->1-2->2->2
3. Reverse alternate k nodes in an linked list.
Ex:- 1->2->3->4->5->6->7->8 if k=2; then return 2->1->3->4->6->5->7->8
2. Given a func :: int typeOfTriangle(int side1,int side2,int side3); (func gives a number for the type of triangle)
Write test cases to check functionality and security issues and even automate the generation of test cases.
2) Binary search tree to Doubly linked list conversion( prefer in-place conversion )
1) You have given a number N, print all balanced parenthesis expression which can be generate using N pairs of open and close braces. For ex. for N=3, ((())),()()(),()(()),(())()
First i gave him a brute force solution(generate all possible combination and check for valid expression),then he ask me for optimized code and I was able to do it after little mess-up.also ask for complexity of my code.
2) You have given a adjacency matrix of a graph, find the number of connected component set of the graph.
1) A string str and two character a and b are given to a function, find out the minimum distance between these two given characters in the str. first I gave him a bruce force solution( O(n^2) ) then he ask to optimize it ( O(n) ) and finally somehow i was able to do it.
4) iterative inorder traversal.
4) You have given a range in Integer(a to b), find all the prime number between a and b.
…..i) first i gave him the simple solution(check every no. whether it is prime or not).
…..ii) then he asked about Sieve and to implement it, and which on is better( first approach or seive)
1) Check whether a linked list is a palindrome or not
Q2) Output of following C program.
#include < stdlib.h >
#include < stdio.h >
int main()
{
unsigned int a, b, c;
a = rand();
b = rand();
c = a + b;
if( c < a || c < b)
{
printf("correct");
}
else
{
printf("error");
}
}
Q1) Write code to implement a command called 'tail -5 filename' in unix file using file pointers and also write test cases (HINT using fread and fseek command)
Q1) Write code to convert given number into words (eg 1234 as input should output one thousand two hundred and thirty four)
Q5) Write code to count number of nodes of a tree, find depth of a tree, find width of the tree.
1. Given the head pointer of a linked list, each node having data value only 0/1/2, properly sort the linked list and return the head pointer.
2. Given a picture with pixels arranged in an N*N matrix, right rotate the picture by 90 degree.
3. Two of the nodes of a BST are swapped. Correct the BST.
1. Given two sorted linked list, create a third list which contains only those elements of first list, which are not common with second list. Do this with O(n) time. Discuss all possible test cases for this function and whether your function can handle all those test cases.
2. Given two linked lists, how do you check whether the two lists intersect at some node with O(n) time? Discuss all possible test cases for this function and whether your function can handle all those test cases.
2. Given three points a, b and c, write a function to find what type of triangle they construct or whether a triangle can be made at all. Discuss all possible test cases for this function and whether your function can handle all those test cases.
Question 1: You have to rotate an n*n array right by 90 degree.
Question 2: Given a linked list containing 0s,1s or 2s. Sort it.
Question 3: Two elements of BST are swapped by mistake. You have to restore the tree without changing its structure.
Note that you don’t have to write a function only, as happens in Amazon. Instead you are expected to write it from scratch along with main function and all the helping functions.
My advice: Screw the instruction, write the function you are expected to write for all the three questions, then go for helping functions and main function.
Question 3: Given a linked list a random ptr also exists. Clone the original linked list. Also give the test cases.
http://www.geeksforgeeks.org/microsoft-interview-set-1/
Question 1: A file consists of numerous words in it. You have to print the 10 most frequent words. Data structures to be used were asked and was asked to finally code it.
Question 2: Write a function which checks whether the tree is height balanced or not. Give test cases also.
위 내용을 정리한 PDF는 여기 있습니다.
https://docs.google.com/file/d/0B3x3UPn47ZkKWnV2LU1EZHItcXM/edit