Microsoft Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

- First read 1 number from each of K streams, and build a PriorityQueue
- After that keep removing top from PQ, and add next number from the same stream(from which top came)
----- if this stream is over, just move on
- Now repeat this while PQ is not empty

public static void sortKStreams(File f[], int K) 
			throws IOException{
		
		PriorityQueue<NumNode> PQ = new PriorityQueue<NumNode>(3);
		
		Scanner scanners[] = new Scanner[f.length];
		
		//insert 1 number each from one stream
		for(int i=0; i<K; i++){
			scanners[i] = new Scanner(f[i]);
			if(scanners[i].hasNextInt()){
				int inp = scanners[i].nextInt();
				PQ.add(new NumNode(inp, i));
				System.out.println("INITIAL BUILD Adding:" + inp + " from stream=" + i);
			}
		}
		
		//While PQ is not empty
		while(PQ.isEmpty() == false){
			//read next min from PQ
			NumNode nextMin = PQ.remove();
			System.out.println("Final result " + nextMin.getNumber());
			
			//read one element from the stream that provided min last time, and add to PQ
			//Note: as streams get exhausted, PQ size decreases linearly
			int nextReadVal = -1;
			
			Scanner sc = scanners[nextMin.getStreamNumber()];
			if(sc.hasNextInt()){
				nextReadVal = sc.nextInt();
				System.out.println("Adding to PQ: Value:" + nextReadVal + ", From stream=" + nextMin.getStreamNumber());
				PQ.add(new NumNode(nextReadVal, nextMin.getStreamNumber()));
			}
			
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		
		for(int i=0; i<K; ++i){
			scanners[i].close();
		}
	}

- X July 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use simple merge since both streams are sorted.

- Noobie July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

First number of one stream could be higher than (or equal to) the last number of other stream
S1 S2 S3 S4
10 12 15 7
9 11 14 4
5 8 13 3
1 7 6 0

We create a Min-Heap which takes O(nlogn) for creation and
ReadNextNumber - O(1) - findmin operation on min-heap
WriteToStream - O(log n) - insert operation on min-heap

- codealtecdown July 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

each stream has its worker in a thread. for each read number from any stream we create a process that sleeps (100 + said number). for example for 2 streams: a: 7, 2, 1, 100,... and b: 0, 42, 80928, 124,.... you will have worker_i(n) -> spawn fun(n) -> sleep(100+n), print(n) end, end.

enjoy

- ionel munteanu July 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1) Peek the first number from each queue.
Step 2) Read out and write the smallest of the numbers to the output stream.
Step 3) Go to Step 1 until all numbers read.

- Nishan July 31, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More