## Microsoft Interview Questions

- 0of 0 votes
If you have 1TB of unsorted long integers but 1GB of memory, devise an algorithm to efficiently sort the integers. What is the time complexity? What is the space complexity?

- 0of 0 votes
Generic Question: You have a list of items that's nearly sorted. What algorithm would you use to completely sort it? Even though it's already sorted, the least element could be at the other end ...eg: 4,5,6,7,8,9,10,11,1

She then said that what would be the approach if the data was not like that, as in , not so extreme.

- 0of 0 votes
Given a string that represents an integer with no upper bound (billions, trillions, etc..), write a function "convert" that returns the integer value of the string. For example: "1000322" returns 1000322.Try to do this in O(1) space, and O(n) time. Better if possible.

- 0of 0 votes
Given a binary tree, write a function LCA that returns the least common ancestor of two nodes. This is not a BST. Try not to use parent pointers in the custom Node class.

Iterative solution takes O(1) space, recursive solution takes O(n) space.

- 0of 0 votes
Given a list of IP address correspondences, such as

IP1 = IP2

IP3 = IP4

IP3 = IP2

IP5 = IP6

IP7 = IP8

etc.

Return a list of unique IP addresses. In this case

IP1, IP5, IP7

Consider IPs as Strings or any other data type.

- 0of 0 votes
Given a list of integers (array or list), write a function that returns true if the list can be split into two lists that have an equal sum.

Example: {4,2,2,0,-1, 1} returns true

{4}, {2,2,0,-1,1}

and {3,3,1} returns false.

Hints by interviewer:

- Complexity is 2^n

- 2of 2 votes
Given 4 teams and 3 gamedays, create an algorithm such that each team plays another team every gameday and by the end of the 3 game days each team should have played one game with every other team.

- 0of 0 votes
Given an array of ints (positive numbers) find out the index that balances the array. If no such index exists, return the index that minimizes the difference.

How can you do it by touching each element only once.

- 0of 0 votes
Insert an int into a circular single linked list.

Discuss corner cases: what if the element to be inserted is the smallest, how can we speed things up (e.g. if the method is called multiple times you can keep track of the "last"/greatest element).

Thorough testing discussions.

- 0of 0 votes
How to sort a very large array (>50GB int array) stored on disk given that you have a 200MB RAM memory.

Discussions on this: test it, corner cases, etc.

- 2of 2 votes
Given a number (integer) as a string turn in into a number:

E.g. "One million two hundreds thousands fifty seven" => shoud return 1200057.

How to model it and how to test it? What data structures would you use. Deep testing (corner cases)

- 0of 0 votes
Given a number N, write all possible sums of consecutive numbers that add up to N.

That is:

return all pairs (a, k) such that a+(a+1)+...+(a+k)=n

After that:

1. what if N is negative or a is negative;

2. what if N is real and the possible implications of this

- 0of 0 votes
How would you convert a row number on Excel to a label? Rows are labeled alphabetically with letters added on once the alphabet has been fully used. (Ex. row # 5 is labeled E, row # 27 is labeled AA, row # 28 is AB, row # 53 is BA and so forth) What would the row label be for a large number, such as 1500?

- 0of 0 votes
Given an array of five integers that represents a poker hand e.g. [2,2,2,3,3] return the value of the hand, valid values are only "pair","two pairs","three of a kind","full house","four of a kind" we don't have to worry about straight, flush or straight flush.

My approach was to have a fixed array of 13 elements (each element represents one possible value of the hand) this array will keep the occurrence of each value of our hand and after we have all the values we just iterate this array and multiply all the values by itself and adding them to get a unique result.

For example if we have [2,2,3,4,5] our fixed array will have a "2" and three "1" so our result will be "2*2+1*1+1*1+1*1",the result will be 7, so all the possible hands will have unique values, if we find a 7 as a result we will know it is a pair, a 9 will be two pairs, a 11 will be three of a kind, 13 will be a full house and 17 will be a four of a kind.

This algorithm is O(1) both in complexity and space but the interviewer didn't like it too much.

- 0of 0 votes
Given a 2d array (say n*m), visit all elements faster than linear time (i.e. faster than m*n). (Assume not too big array. i.e. fits in memory etc.etc)

I gave a solution: 4 pointers that start from 4 ends ((0,0), (0,n), (m,0), (m,n)) and walk the edges. Once done next inner rows and columns (i.e. (1,1), (1,n-1), (m-1,1), (m-1,n-1)). Easier to implement with just the indices and we can say 4 times faster. Another solution I gave was to use multithreading. He said no multithreading. But the interviewer was not convinced and he gave me a hint to use recursion (?). Couldn't get the solution that he wanted.

- -1of 3 votes
A frog has to cross the river from one end to another end. river has stones in between randomly where frog can jump. frog can't jump into the river. problem is that will frog ever reach other end with following conditions?

1. frog allow to do same jump as previous jump. or

2. frog allow to jump 1 more as previous jump. or

3. frog allow to jump 1 less as previous jump.

consider river as Boolean Array. Stone is a element in array where value is true .

- 3of 3 votes
Given a singly connected linked list, find the largest palindrome in the list in O(1) space.

- 3of 3 votes
Given a linked list consisting of String in each Node . Given just a pointer to the head Node find whether the resultant String formed by combining all the Nodes of the linked list is a palindrome or not in O(1) space and O(n) time.

eg – Consider this linked List structure

“aba” -> “cd” -> “efe” -> “d” -> “caba”

Hence this structure is palindrome .

- 0of 0 votes
2 process runs the following code. What will be the output

`// Assume this address is legal address for both the process int *sharedmemoryaddress = 0x1232; void SomeRunningFunction() { for(int i = 1; i < 1000; ++i) { *sharedmemoryaddress = i; sleep(2000); } }`

What does the 2 process print. Consider unicore and multicore processors. What is the significance of sleep here. What are we achieving from sleep.

- 0of 0 votes
Given an N-ary tree with thousands of nodes in it. Pair (Join) the Leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have Intersecting path.

For example,

A

/ | \

B C D

/ / | \

E F G H

Leaf nodes: E, F, G, H & D

Possible Pairs in O/Ps:

a) (E-F), (G-H) or

b) (E-G), (F-H) or

c) (E-H), (F-G) or

d) (E-D), (F-G) or

e) (E-D), (G-H) or

f) (E-D), (F-H) or

g) (D-H), (F-G) or

h) (D-G), (F-H) or

i) (D-F), (G-H)

Note: If we pair(join) say, (E-F) then we can NOT pair any of the (D-G) or (D-H) as they SHARE the COMMON path from A to C.

i.e. E-B-A-C-F —> (E-F) pair

D-A-C-G —> (D-G) pair

D-A-C-H —> (D-H) pair

- 0of 0 votes
Given a tree, and a pointer to some node in the tree, print the left most element in the same level as that node

- 0of 0 votes
Given an input of the calendar objects of 10,000 employees, input is a time interval T and an employee[] array, find the first interval where all the employees in the employee[] array are free for a minimum time interval T (i.e schedule the meeting)

- 0of 2 votes
Given a binary tree, connect all node in the same level in toggle manner.

Toggle the linking every K level. For first K level, you should link to next right node. Next K you should link to next left and so on.

Node structure is :

struct node

{

int data;

struct node *left, *right, *next;

};

Each level next should point to the next right or left node in the level. For last node in each level, next should be NULL

For ex - if K=2 then for first 2 level of tree connect next pointer from left to right and for next 2 levels connect next pointer from right to left and so on.

- 0of 0 votes
This question is windows based subsystem design to test the design skills. We are working in a complex system which involves multiple process, DLLs, windows services which will be gets installed on our system with the project. We have to design a logger system for this project where in all the multiple subsystem can use this logger system for their logging activities .

Design pattern used

Statically linked or Dynamically linked?

How the logger functions are designed (sample signatures)

How we can improve performance while logging (Think of ETL tracing)

- 0of 0 votes
Sort a set of ip address given either in ascending or descending order

char** SortIPAsc(char** pIPAddress);

char** SortIPDesc(char** pIPAddress);

- 1of 1 vote
for given array

`s[] = {5,1,0,4,2,3}`

1) length of array is not given.

2) If length of array is 5 content is guaranteed to be between 0 to 5. There is no repetition of numbers. Sample example for length(s, 3)

- a[3] = 4 , a[4] = 2, a[2] = 0, a[0] = 5, a[5] =3

returns length of 4 .

For given condition write subroutine

int length (s, 3)

- to find the number of steps it takes to find given value - It's a function api - that I was asked to write with the conditions - I cannot change parameters of the function - I have to make sure return value is correct

Additional Condition:

You cannot use any loop statements like for, while and so on -

You cannot use any global or static variables.

You cannot call other routines inside this routine

You cannot modify given function parameters - it stays length (s, n) only

You cannot change original array too

- 0of 0 votes
Given three arrays(arr1, arr2, arr3) each containing distinct positive numbers find three numbers a,b,c each from arr1, arr2, arr3 respectively such that (abs(a-b) + abs(b-c) + abs(c-a)) is minimum.

- 1of 1 vote
design question:

I will request you to first read only upto Solution-2 only and try to think about your solution and then read other lines. If we read whole post(without thinking about your solution) then your brain will get polluted with my idea and you may not be able to think naturally.

----------------------------------------------------------------------------

One machine daily taking backup of its datatstore on some server machine, MINIMIZE network data transferred.

Solution -1 : Compress storage and then send over network

Solution - 2 : Take diff and send only diff(and not whole data daily)

Interviewer asked for better ideas as above two are well known ideas but I was stuck.

---------------------------------------------------------------------------------

So he gave me hint(no 1) and depending upon hint I devise following solution

Solution - 3: Divide storage into sequence of 1K bits so total number of possible patters are 2^1000. Now Using hashTable just store existing 1000bits-length pattern and all their sequence numbers. And, then transfer this hashTable to server. So for example datastore consists of "file1, file2, file3=file1+file2" then we can reduce network data by 50%

So interviewer asked why 1000bits and why not 100bits or 10000bits. Also, as we increase length of bit-pattern, probability of getting duplicate patterns reduces and if we decrease length of pattern we may not be able to effectively reduce network data transferred

Solution-4: Don't divided storage bits into equal length pattern but in variable length pattern so client tells server "Pattern-X(bit string) of length L exists at offsets 5, 10003, 363738, 42311, 43433.

Interviewer said how can check for variable length patterns on client machine as this will be computaionally inefficient. I suggested Trie, Huffman coding, file-by-file comparison but he straightway discarded those ideas :)

He gave final important hint that

somehow client should give indication to server that next bytes are going to be like this without tranferring those bytes and

then server should tell client that "OK don't send next 1000bits as I already have them from previously send/stored data at different section(like different file) in storage"

and asked me how to do it and how will be the handshake/protocol between server-client

Since, throughout interview I was stuck to my hashTable solution and not able to think beyond hashTable, as per HR I got negative feedback in this interview :(

Overall interviewer was helping lot and was really helpful. He gave lot of hints and time(never said "Ok thats enough let us move on"...Finally I myself gave up :) )

- 1of 1 vote
Given the two objects below, implement the methods defined in the Phonebook class. This is a simulated phonebook. You should expect LookupByName and LookupByPhoneNumber to be called much more often than AddPerson. Also, this is a multi-threaded simulation so your implementations of the functions other than the constructor should be threadsafe. Feel free to rewrite this in any language of your

choice.`public struct Person { string name; string phoneNumber; } public class Phonebook { public Phonebook (List<Person> people) { } public Person LookupByName(string name) { } public person LookupByphoneNumber(string phoneNumber) { } public void Addperson(person person) { } }`

- 1of 1 vote
Check given Number is same after 180 degree rotation?

i/p: 69

o/p: True

i/p: 916

o/p: True

i/p: 123

o/p: False