Microsoft Interview Report
- 0of 0 votes
AnswersFor SDE Interns...On-site Interview #4
Assume that you have 2^32 bytes of memory. When a program asks to allocate memory, a 4kb chunk of memory gets allocated. It can be allocated at any position (e.g. 0, 57, 8192). Now assume we have a function called lookup(), which, when fed an arbitrary address, (1) returns the value of the starting address of the chunk encompassing the requested address if it was allocated, or (2) returns a value indicating false if no block was allocated. Lookup must work IN CONSTANT TIME. To help clarify the functionality, here is some example expected behavior:Allocate(1) /* allocates bytes 1-4096 */ Allocate(4099) /* allocates bytes 4099-8194 */ Lookup(123) /* returns 1 */ Lookup(4096) /* returns 1 */ Lookup(4098) /* returns -1 or false */ Lookup(6042) /* returns 4099 */ Lookup(8198) /* returns -1 or false */
To the readers, my solution had 2 checks maximum (and thus was O(1)). I have provided the solution as pseudocode, java code, and given links to images depicting the reasoning behind my solution as responses below.
- woohoo March 28, 2011| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDesign an alarm clock for a blind person.
- woohoo March 28, 2011| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswersWhy do you want to work at Microsoft?
- woohoo March 28, 2011| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Experience - 0of 0 votes
AnswersFor SDE Interns...On-site Interview #1
- woohoo March 28, 2011
Please note I have posted all four of my on-site interview questions. I was completely grilled on my resume during all four interviews but didn't feel it necessary to add those questions.
Write a function to validate a BST. (I used a queue, so next he said) now, do it without a queue. What is the complexity of your solution?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFor SDE Interns...On-site Interview #3
- woohoo March 28, 2011
Pretend you work for a phone company. At your company, you have a satellite that routes phone calls. We want to bill customers by the maximum number of simultaneous phone calls they make in a single day. (After asking clarifying questions I received the following information: assume no calls last more than 24 hours and that at midnight each night all the calls are automatically dropped. In the event that one call ends as soon as another starts, answer part 2 of this question in such a way as to maximize revenue).
What information should the satellite store for each phone call? Define a data structure for this (e.g. write a struct).
Write a function that finds the maximum number of simultaneous phone calls from a given customer. (Hint: typical solution is O(nlogn), but if you use an absurd amount of memory like I did, it can be done in O(n)).
Edit: Your solution should not be real-time. The data has already been collected and you need to work with it.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFor SDE Interns...On-site Interview #2
- woohoo March 28, 2011
In Microsoft Word, words that are misspelled are underlined in red. Which data structure would you use to identify misspelled words, and why? Be prepared to defend any design decisions that you make. Write a function that uses your data structure to check if a word has been spelled correctly.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswerWhat project are you most proud of doing, and why?
- woohoo March 28, 2011| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Experience