## Microsoft Interview Questions

- 0of 0 votes
Given an array: 1,2,3 ,5,8,7,6,9,5,7,3,0,5

subarry:5,7

Find the subarray in the large array and return the minimum length and index where you can find the subarray. Note: that the subarray may be present in the large array non-contiguous.

In the above case : the answer is length = 2 and

index = 8

- 0of 0 votes
Suppose you have a matrix in the form of a 2 dimensional array. Write a method to read the rows of the matrix alternatively from right to left, left to right so on and return them as a 1 dimensional array.

for eg:

1 2 3

4 5 6

7 8 9

should return 1 2 3 6 5 4 7 8 9

- -1of 1 vote
Anyone appeared for microsoft hacker rank test lately

- 0of 0 votes
how to restrict creation of object inside the function fun

although destructor and constructor is private??

#include <iostream>

class ABC

{

private :

~ABC()

{

}

ABC()

{

std::cout <<"ABC";

}

public:

static void fun()

{

ABC t;

}

};

int main()

{

ABC::fun();

}

- -1of 1 vote
Given a matrix which is spirally sorted. Remove an element and insert another element maintaining the sorted order.

- 0of 0 votes
Given two sets of strings A and B. Find the

(A-B) U (B-A) ( U = union ). The answer should be in lexicographical order and A’s elements should appear before B’s.

- 0of 0 votes
Given a few points in first quadrant – (x1,y1) …..(xn,yn) and given another set of points (a1,b1…..an,bn), determine whether all the points (a1,b1…an,bn) have already occured in (x1,y1)…..xn,yn)

- 0of 0 votes
Given a graph where every two nodes are either friends or enemies with each other. Find a way to go from one node to the other.

Restrictions:

1) You can also travel from one node to next if they are friends with each other

2) You have some “magic potions”. You can convert an enemy path to a friend path with a magic potion.

Find the path with min number of magic potions required.

- 0of 0 votes
You are given a structure msg

struct msg

{

long timestamp;

double price;

string label;

};

The msg represents price of a stock on a given timestamp.

Create a class with two functions -

addStockPrice(msg m) -> Used to add Stock Price in Data structure

getAvgPriceForAStockLast10Minutes(String stockName) -> Get average price of a stock for last 10 minutes.

The program should be time and space optimized.

- 0of 0 votes
Design and Implement: Producers and Consumer Problem. Producers produce different kind of messages and Consumers register themselves for different kind of messages. Need to design and implement Producer, Consumer and a Delegator which is responsible for storing and delivering the messages to appropriate listeners.

Changed the question to handle millions of messages.

Changed the question to handle different priority messages.

Threading model for Producer, Listener and Delegator.

In the end he asked me to code 2 methods of Delegator.

1: which adds the message from Producer to its internal queue.

2: Delegate, which delivers the message to appropriate listener.

- 1of 1 vote
This is a question I received in an online challenge.

A list of numbers are given. We need to find the total number of groups in which the digits of each number have same frequency.

For example if numbers are:

1

10

3

33

There are 4 groups:

G1={1}has one 1.

G2={3} has one 3.

G3={10}has one 1 and one 0.

G4={33}as two 3s.

- 0of 0 votes
Find out if there is cycle in Directed graph

- -1of 1 vote
Given billions of Rectangle, find rectangle with minimum area overlapping to a given point P(x,y)

There is a simple way to achieve answer in O(n) by processing each rectangle sequentially, but optimize it further provided large number of Rectangle array.

- 0of 0 votes
Given a circular array of images, in LandScape and Portrait mode. Bidirectional movement in array is allowed.

e.g.

LPPPLPPP

L-> Landscape

P-> Portrait

Cost of Viewing a Portrait image is Vp

Cost of Viewing a Landscape is (Rp(rotate) + Vp).

Cost of movement is -> m

once you visited the image viewing cost is zero if you revisit the image. Only movement cost is considered.

Jumps in array is not allowed.

Calculate the maximum number of images you can see with cost X.

- 2of 2 votes
Given a string e.g. ABCDAABCD. Shuffle he string so that no two smilar letters together.

E.g. AABC can be shuffled as ABAC.

- 0of 0 votes
Given a DNA sequence e.g. AAAGTAAGTAAGTGGG.....

Find all the duplicates with length 10.

- 1of 1 vote
what is the best sorting algorithm in terms of complexity and why?

- 0of 0 votes
Circular Queue - what it is ? and write a program for this

- 0of 0 votes
Circular Queue - what it is ? and write a program for this

- -2of 2 votes
I have an array of integer. That provides data to one of the UI screen. That UI screen can show at a time only one data. For each iteration on the array 3 elements get picked up however only the highest number out of those usually shows up on the UI.

{1,4,5,2,3,4,5,6} means if 1,4,5 picked up only 5 will be shown up on the UI

in next iteration 4,5,2, should be picked up.

next iteration 5,2,3

write a solution for this.

- -2of 2 votes
I have an array of integer. That provides data to one of the UI screen. That UI screen can show at a time only one data. For each iteration on the array 3 elements get picked up however only the highest number out of those usually shows up on the UI.

{1,4,5,2,3,4,5,6} means if 1,4,5 picked up only 5 will be shown up on the UI

in next iteration 4,5,2, should be picked up.

next iteration 5,2,3

write a solution for this.

- 1of 1 vote
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

- 3of 3 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.