Microsoft Interview Question for Interns


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 6 vote

Guys why just don't use priority queue to store callbacks for this task? Each element of the queue contains callback address, pointer to callback paramenters and timestamp when it should be fired. The timestamp is a priority. Timer could be implemented using condition variable or another analogue, the main idea is to have possibility to wake it up from another thread. When callback is added to the queue, the timer thread is waken up, it gets the top element of priority queue, calculates the different between current time and elements timestamp and sleeps until calculated timeout exceeds. When the thread is awaken by timeout it starts new thread which invokes callback or put this callback to the queue of execution which can be served by threads pool.

- Gosham October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

Hi Gosham. This is exactly what I have come to when implementing a timer queue in Linux (it's missing the " CreateTimerQueue" functionality analog of Windows). But I have a small (but very important) correction - do not use periodic polling per ce since it is very-very resource consuming. Instead use the "pthread_cond_timedwait" function, that can be released by either explicitly signalling it (signal the wait condition) or when the timeout period expires. It works like a charm even with nanosecond precision - the timer thread wakes up and invokes the callback function of the object stored in the priority queue.
So, voting up your suggestion.

- ashot madatyan October 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

use the approach that i have given no message will loss ..
it is very similay to interrupt handling ( isr and bottom halves )
put all critical job in one function and put all the deffered job in another and
schedule deffered function to run later ...
most of the RTOS uses very much similay technique ...

- istiyak916 October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Need to reread this after a coffee... woah

- S O U N D W A V E October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to use a FIFO for buffering the incoming requests?

- carterpeng October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is a bit blurry, but from what I understand -
Here's a way to implement a N to 0 (zero) timer, handling multipule request (by signaling).
Assume the timer refreshes every second and could check if should serve a request.

Whenever the timer is Invoked with time t do:
if first time - create array a of size n+1 (0-n), the array holds a linked list in each cell.
add to list a[n] the request identifier and return. Also store t in N.

else (not first time) -
let i be the number of past seconds. (global to timer class)
if t <= n-i - add request id. to list at a[n-i-t] and return.
else -
a. create new array a' like a of size t+1
b. copy a to a' by placing each list at location k (in a) to location k-i
(in a'). *k-i is the time left for handling.
c. let a be a' (discarding former a).

on each refresh entrance:
increase i by one
if list at a[i] isn't empty serve (or signal) all requests on the list and remove them.

- Dawn October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is an easy approach

1. first take a dynamic buffer .
2. and my timer is capable for handling one request at a time .
3. if suppose multiple request is generated so , what we all need to do is this
4. we take the request put it inside the buffer and make a linked list of it
5. so , we have all the request in my list . now go through the list and clear all the pending job .
6. one thing make sure that whenever a request is genereted immediatly save the status of your current job and handle the request so no request get lost ....
thank u

- istiyak916 October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Hi folks, I would recommend using a "async and await" function calls which can handle all requests asynchronously.
Imagine this timer to be a Phone app which is created in the server. If the requests comes in and we queue each requests, the user might have to wait long to get a response back from the server as the resources is blocked by the previous users. Instead using await and async the user can keep getting response with out potentially a long wait period.

Implementing a queue in the server is a very long process and given that it is a placement drive, I think they are looking for these types of special keywords.

- Swatkats October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can use round robin algorithm...

- BarathVutukuri October 12, 2013 | 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