微软西雅图挂经

This was my first onsite interview with Microsoft and I must say I had an awesome experience. For most part it went very good for me, I guess the reason for my rejection was somebody else performed better than me (and the team for which I was interviewed for mentioned that they have budget to select only 1 Engineer). Questions were relatively easier except for one, which made it to the title of this post.

店面
Implement a Queue without using STL, in the most Object Oriented way.

Onsite
第一轮:
1.1: Open ended question
Given a function, what this function is trying to do, can you find some problem with this function, and how can you improve the performance of this function with whatever it is doing?

void copy(int n, unit8_t *input, unit8_t *output)
{
	while(n--)
	{
		*output++ = *input++;
	}
}

1.2: 53. Maximum Subarray

第二轮:
2.1: Lunch Interview: What keeps you motivated, Why you want to join Microsoft, How you like working in your current company, Explain an interesting problem that you solved recently.

2.2: Most beautiful Interview Question I have ever come across:

You are given an abstract machine that has a timer, which can be visualized as a 1 dimensional timeline gradually increasing. This machine has an abstract OS running on it, which can perform only 3 operations:

  1. CreateTask(time, task()) - Schedules a task() by setting a timer for a given time from current time (i.e relative to current time), and when the expected time is reached it triggers the task() . OS is constrained in a way that it can schedule only 1 task() by using CreateTask . Until the scheduled task() is executed or expilictly cancelled using EndTask , no other CreateTask will execute.

More explaination:
Analogy of CreateTask function can be explained with an Alarm clock. Suppose you have a hypothetical Victorian Alarm Clock that can schedule only one alarm (by spinning a spring). You set the alarm time based on the input relative to current time, which means if now time is 10:00pm and you are asked to set alarm 8hrs from now, then your alarm should ring at 6:00am.

  1. ElapseTask() - this function returns the time elapsed since the last CreateTask was called. If the task which was scheduled by the CreateTask has already been executed, then ElapseTask will only return 0.

More Explaination:
Taking the alarm clock analogy here, if an alam clock was set at 10:00pm for 8hrs from that time, then calling ElapseTask at 12:00am will return 2, calling ElapseTask at 5:00am will return 7, but calling ElapseTask anytime after 6:00am will return 0.

  1. EndTask() - Cancels any scheduled task previously set by a CreateTask .

Problem statement: You have to use these 3 OS calls and design a API or a set of APIs that can schedule multiple task.

第三轮:
Given a NxM 2D grid. In some cells there are blockers (which no one can access), there are some cells which contains guard(G), and rest of the cells are just empty. Now you need to find out what is the minimum Manhattan distance of each empty cells from the guard cells. In case of conflict, choose the distance which is minimum.

第四轮: Non-technical
Just a casual interview with manager. I felt like I was drivng the conversation for the most part, I was asking lot of questions and very less questions were asked to me. As I retrospect now, I guess this was the part that I should have really convinced my interviewer that I’m the right person for this role. Overall, the interview went cold. Nothing was coming out of him.

这题是 https://leetcode.com/problems/01-matrix