Microsoft Interview Question for Software Engineer / Developers






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

int reader_count = 0;  //Keeps track of reader count
Mutex csMutex;         //Mutex for the critical section.
Mutex readerMutex;     //Mutex for the reader_count access. If you don't have this the reader_count will get corrupted.
void reader_func()
{
    readerMutex.acquire();
    if(reader_count == 0)
           csMutex.acquire();
     reader_count++;
  readerMutex.release();

 //critical section

    readerMutex.acquire();
   reader_count--;
   if(reader_count == 0)
        csMutex.release();
   readerMutex.release();
}

void writer_func()
{
   csMutex.acquire();
   //critical section
   csMutex.release();
}

- spookymulder83 December 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

and what a man from a microsoft said about your code?

- Anonymous December 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

he said "you've been served with bluescreen"

- gekko gordan December 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

post your solution if u have one

- Anonymous December 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

/* Algorithm: //assuming writer thread has the highest priority i.e. readers wont enter CS if writer is waiting for access to CS
 * reader_func():
 * 	if writer thread not waiting then proceed
 *		if less than max_readers atomically increment semaphoreVar
 *			enter CS
 *			acquire semaphoremutex.
 *				decrement, check if writer is waiting and semaphoreVar==0. 
 *				if yes then notify writer
 *			release semaphoremutex
 *		else
 *			max_readers already in CS so try later
 *	else
 *		writer thread waiting so try after it is done
 *
 * writer_func():
 *	acquire semaphoremutex
 *		if semaphoreVar!=0 then requestFlag; [release semaphoremutex and wait on condition variable]
 *			when notified acquire semaphoremutex
 *		process CS
 *	release semaphoremutex
*/

int MAX_READERS = 10 /*max readers 10*/ , cSem = 0 /*counting semaphore*/;
volatile bool requestCS = false;  //this flag is used by writer to request CS.
WaitCondition waitForReadersExit; //condition variable which is invoked when readers==0.
Mutex semMtx;	//mutex for atomically operating on cSem variable

void reader_func()
{
   if(!requestCS){ //if writer thread not waiting then proceed
	if(testAndIncrement(cSem,MAX_READERS)){ //if cSem less than MAX_READERS then increment it atomically proceed
		//Critical Section processing
		semMtx.acquire();
			--cSem;
			if(requestCS && cSem==0)		 //if writer requested CS and no readers are in CS then
				waitForReadersExit.notify(semMtx);//unlock semMtx and notify writer
			else
				semMtx.release();
        }else{
		//max readers in CS.  Try later
	}
  }else{
       //writer has placed request, wait till writer is done.
  }
}
void writer_func()
{
   semMtx.acquire();
	   if(cSem!=0){
		requestCS = true; 
		waitForReadersExit.wait(semMtx)	//unlocks 'semMtx' and waits on the condition variable
	   }
	   //critical section
	   requestCS = false;
   semMtx.release();
}
//atomically test and increment semaphore variable
bool testAndIncrement(semVar,MAX_READERS){
	semMtx.acquire();
	if(MAX_READERS>semVar){
		++semVar; semMtx.release(); return true;
	}semMtx.release();
	return false;
}

- GekkoGordan December 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
- GekkoGordan December 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. The interviewer wanted me to discuss the pros and cons of my solution. Given a scenario where there will be lots of readers and few writers, the writers might not acquire a lock on csMutex at all give the way the code is written. There will always be bunch of readers accessing the critical section and all writers will have to most likely wait forever. So the above code favors the readers.

2. How would you change the above code to favor the writers? Whenever a writer is waiting, come up with a mechanism that won't allow any more readers into the critical section or acquire the lock. The existing readers will be allowed to finish and the last reader will release the lock. Once this is done the waiting writer will acquire the lock and do its task.

3. You can also put a limit on the number of readers that can access the critical section. Once in a while or when a writer is waiting, change the limit to 0 so that no new reader can acquire the lock thereby allowing a writer to acquire the lock on the mutex.

4. GekkoGordan's code handles this case. Good.

- spookymulder83 December 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

gekko's code is good. But it won't handle multiple writers because if multiple writers are waiting on a single variable and all are notified and only one proceeds into Critical section. after that the other writers would have equal priority as readers because requestCS is set to false by first writer. So changing the requestCS variable to a counting variable will assure all writers are done before readers proceed.

- blueskin.neo December 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

woow..I saw other comments from gekko to be sarcastic, funny and criticizing but he does know how to answer problems. hmmm...
nice solution

- Anonymous December 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm not sure tht u can use conditional variables. Otherwise the answer of gekko is correct

- kykydyk March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class ReaderWriterLock
{
	Mutex noReader;
	Mutex noWriter;
	Mutex countMutex;
	unsigned int readers;

public:
	void AcquireReader()
	{
		noWriter.Acquire();
		countMutex.Acquire();
		if (++readers == 1)
			noReader.Acquire();
		countMutex.Release();
		noWriter.Release();
	}
	void ReleaseReader()
	{
		countMutex.Acquire();
		if (--readers == 0)
			noReader.Release();
		countMutex.Release();
	}
	void AcquireWriter()
	{
		noReader.Acquire();
		noWriter.Acquire();
	}
	void ReleaseWriter()
	{
		noWriter.Release();
		noReader.Release();
	}
};

- Anonymous December 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mutex writerRequestMutex;
bool writerRequest=false;
int readerCount=0;
const int Max_Readers = 10;

void read_func()
{
	writerRequestMutex.lock();
	while(writerRequest!=false && readerCount>=Max_Readers)
	{
		writerRequestMutex.unlock();
		doSleep();
		writerRequestMutex.lock();
	}	
	
	readerCount++;
	writerRequestMutex.unlock();

	//critical section

	writerRequestMutex.lock();
	readerCount--;
	writerRequestMutex.unlock();
	
	if(readerCount==0)
		writerRequestMutex.wake();
	
}


void write_func()
{
	writerRequestMutex.lock();
	while(readerCount!=0)
	{
		writerRequest=true;
		writerRequestMutex.wait();
	}

	//critical section

	writerRequest=false;
	writerRequestMutex.unlock();
}

- Anonymous February 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

best solution man!

- Anonymous February 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Slight mistake: in the write_func you should set writerRequest=true before the lock and then wait on the lock. No need for while loop:

void write_func()
{
writerRequest=true; // This should let readers relinquish the lock and goto sleep

writerRequestMutex.lock();

// critical section

writerRequest = false;

writerRequestMutex.unlock();
}

Also there is no wake function on a mutex (as you indicated in your code)

- Ashish Kaila March 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Reader-writer lock */
int reader_ctr=0;
void reader_func() {
    mutex_acquire(&reader);
    reader_ctr++;
    if(reader_ctr==1) mutex_acquire(&writer);
    mutex_release(&reader);
   //critical section
    mutex_acquire(&reader);
    reader_ctr--;
    if(reader_ctr==0) mutex_release(&writer);
    mutex_release(&reader);
}

void writer_func() {
    mutex_acquire(&writer);
   //critical section
    mutex_release(&writer);
}

- jzhu May 20, 2012 | 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