## Microsoft Interview Questions

- 0of 0 votes
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 :) )

- 0of 0 votes
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

- 2of 2 votes
Write a function to detect the number of cycles in a directed graph. The graph is passed as an adjacency matrix.

- 1of 1 vote
Given a sentence in a form of a string, reverse the words in the string and return a string. Handle a case where there might be period at the end of the sentence. If there is a period, the period has to come to the end of the reversed sentence. Discuss the time complexity of your algorithm.

INPUT: "This is a sentence"

OUTPUT: "sentence a is This"

INPUT2: "This one has period."

OUTPUT2: "period has one This."

- 1of 1 vote
Sort an array of 0s, 1s and 2s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example

Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};

Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

But they have added 1 trick into the question, You cannot use high = n;

It means don't calculate the length of array.

Can anyone help me in writing the code for this problem ?

- 2of 2 votes
there are N cities (numbered from 1 to N) in the game and connect them by N-1 highways. It is guaranteed that each pair of cities are connected by the highways directly or indirectly.The game has a very important value called Total Highway Distance (THD) which is the total distances of all pairs of cities. Suppose there are 3 cities and 2 highways. The highway between City 1 and City 2 is 200 miles and the highway between City 2 and City 3 is 300 miles. So the THD is 1000(200 + 500 + 300) miles because the distances between City 1 and City 2, City 1 and City 3, City 2 and City 3 are 200 miles, 500 miles and 300 miles respectively.

During the game the length of some highways may change. you want to know the latest THD.

sample input

3 5

1 2 2

2 3 3

QUERY

EDIT 1 2 4

QUERY

EDIT 2 3 2

QUERY

sample output

10

14

12

- 2of 4 votes
Given two arrays were digits of one array represent a number,maxmise the number by replacing it with elements of second array.

eg:

arr={3,1,4,5,6}

rep={1,9,5,2,3}

after replacement

arr={9,5,4,5,6}

one digit of rep can be used to replace only once.

- 4of 4 votes
Write a program to process the matrix. If an element is 0 at ith row and jth column, then make the whole ith row and jth column to 0.

Constraints:

Space complexity should be O(1)

Time complexity - Only single pass is allowed. Note that single pass is not O(n). This is single pass : An element will read and written only ones.

Edit:

Recursion is not allowed since it is O(n) space on stack

- 0of 0 votes
Given N tasks, find the maximal points that can be achieved by finishing them

Problem Constraints

There are T minutes for completing N tasks

Solutions can be submitted at any time, including exactly T minutes after the start

i-th task submitted t minutes after the start, will get maxPoints[i] - t * pointsPerMinute[i] points

i-th task takes requiredTime[i] minutes to solve

Input Format

Line 1: T, total minutes available to finish

Line 2: Comma separated list of maxPoints

Line 3: Comma separated list of pointsPerMinute

Line 4: Comma separated list of requiredTime

Sample Input

75

250,500,1000

2,4,8

25,25,25

Sample Output

1200

Explanation

First, solve the third task 25 minutes after the start of the contest. Get 1000 - 8 * 25 = 800 points

Second, solve the second task 50 minutes after the start of the contest. Get 500 - 4 * 50 = 300 points

Third, solve the first task 75 minutes after the start of the contest. Get 250 - 2 * 75 = 100 points

In total, get 800 + 300 + 100 = 1200 points

Any optimized solution for this ?

- 0of 0 votes
Give four points, determine is it is a square, rectangle or none of the above.

- 0of 0 votes
Given list of nodes of a tree, find the root of the tree. Nodes in the list are not in any particular order.

If all nodes in the tree are not given, return null

A

B C

D E F

F E A << input

A << output

- 1of 1 vote
`John observers the following while driving to work. • 4 were driving a red car. • 3 were driving a blue car. • 3 were driving a black car. He also notices that • 3 of them were listining to Hip Hop • 4 of them were listining to pop music. • 3 of them were listining to Rock. Additionally he notices that, • 3 of them reached office before time on Friday. • 3 of them reached office before time on Tuesday. • 2 of them reached office before time on Wednesday. • 2 of them reached office before time on Thursday. Which of the following practice maximises his chance of getting to office before time. a) He should drive a red car to work listining to pop music on a friday? b) He should drive a blue car to work listining to rock music on a Tuesday. State how did you calculate the probabiltiy for both in your answer.`

- 0of 0 votes
Minimum number of jumps required to climb stairs

Its basically like, you have 2 parallel staircases and both the staircases have n steps. You start from the bottom and you may move upwards on either of the staircases. Each step on the staircase has a penalty attached to it. You can also move across both the staircases with some other penalty.

I had to find the minimum penalty that will be imposed for reaching the top.

I tried writing a recurrence relation but I couldn't write anything because of so many variables.

I recently read about dynamic programming and I think this question is related to that.

With some googling, I found that this question is the same as

https://www.hackerrank.com/contests/frost-byte-final/challenges/stairway

Can you please give a solution or an approach for this problem ?

- 0of 0 votes
Input: two linked lists that have some duplicate nodes

the list node contains a student's info: name, telephone, address. duplication exist if the same name and phone number appears in two different lists or repeat more than ones in the same list.

Output: one lists that contains unique elements, duplications should be removed.

- 0of 0 votes
Input: two strings, one is short then the other

Output: indices of where a permutation of the short string start at the long string.

- 1of 3 votes
Generate all possible sorted arrays from alternate elements of two given sorted arrays.

Given two sorted arrays A and B, generate all possible arrays such that once first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. Then first element is taken from B then From A, and do same as above.

- -1of 3 votes
Design a game like angry birds

- -1of 1 vote
Check if the given cordinates on a map correspond to the correct address (where address or cordinates are provided in a tab separated file)

- 1of 1 vote
Reverse string except spaces. A string has mix of alphabets and spaces. Your task is to reverse the string, but preserve the positions of spaces. For example, reverse of " a if" is " f ia".

- 0of 2 votes
Write a function which takes a BST and then "flattens" it (converts in-place into new BST), so all the nodes have only right child and no left.

Example:`10 / \ 5 15`

Output:

`5 \ 10 \ 15`

- 2of 2 votes
Round 6

Question 3 : You are given a word document, you have to print the words with frequencies. Now print the kth rank word in terms of frequency. Print top k words as well by frequencies

- 0of 0 votes
Round 6

Question 2 : VRBO(Vacation Rentals by Owner), is a portal for real state where owners can rent their properties, renters can occupy them for sort duration by giving rent to the owner via VRBO. Lets start by thinking how you can design such system. ?, What are the complexities you have address here ?, both business and technical ?, what will be your main focus ?, tell me about the architecture of the system ?

Note that he wasn't concern about finer implementation details, but looking for broader things and thoughts.

- 0of 0 votes
Round 6 (taken by PRINCIPAL SOFTWARE ENGINEER)

Question 1 : Since when you started searching for a new job ?, any project you are proud of ?, If you are given the same project now, how differently you will do now ?, why do you think whatever you have applied at that time was optimal ?.

- 0of 0 votes
Round 5

Question 5 : Now lets say you are given k number of input streams, each stream have two method implemented, one is ReadNextNumber() and another is WriteToStream(), lets say each of the streams are sorted. How will you return a single sorted stream which contains all the streams data.

- -1of 1 vote
Round 5

Question 4 : Now lets say you have 1 PB(1000 TB) of numbers, what kind of system you would prefer, not that you can't store this data in one box. How will you sort these many numbers, what is the time complexity in seconds ?. does increasing core per machine help here ?

- -1of 1 vote
Round 5

Question 3 : Now lets say you have 1 TB(1000 GB) of numbers, how do you sort it, tell me the complexity in seconds ?, any optimization you would like to do here, ?, lets say your machine is having two core, now ?

- -1of 1 vote
Round 5

Question 2 : You are given a 1 GB of numbers, you have to sort them. Tell me the time required in seconds ?