Google Interview Question for Software Engineer / Developers






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

typedef struct
{
    Mutex m;
    int reader_cnt; // initialize to 0, 0 means available for reader or writer
                    // -1 means taken by a writer
                    // >0 means taken by readers
} RWLock;

int read_lock(RWLock *lock) 
{
    int res = 0;
    MutexLock(lock->m);

    if (reader_cnt == -1 ) // taken by writer
    {
         MutexUnlock(lock->m);
         return -1;
    }

    reader_cnt++;
    MutexUnlock(lock->m);

    return res;
}

int read_unlock(RWLock *lock)
{
    int res = 0;
    MutexLock(lock->m);
     
    if (reader_cnt < 1) {
        MutexUnlock(lock->m);
        return -1;
    }

    reader_cnt--;
    MutexUnlock(lock->m);
    return res;
}

int write_lock(RWLock *lock)
{
    MutexLock(lock->m);

    if (reader_cnt != 0) // taken by other readers or writer
    {
         MutexUnlock(lock->m);
         return -1;
    }    

    reader_cnt--;
    MutexUnlock(lock->m);

    return 0;
}

int write_unlock(RWLock *lock)
{
    MutexLock(lock->m);

    if (reader_cnt != -1)
    {
         MutexUnlock(lock->m);
         return -1;
    }

    reader_cnt = 0;
    MutexUnlock(lock->m);

    return 0;
}

- mytestaccount2 August 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

/**
 * 
 * <p>Title: ReadWriteLock</p>
 * <p>Description: ReadWriteLock using Mutex</p>
 * @author    shaohui.liu
 * @date      Apr 13, 2011
 */
public class ReadWriteLock
{
	interface Mutex
	{
		void lock();

		void unlock();
	}

	private int readerCounter = 0;

	private Mutex counterMutex;

	private Mutex readerWriteMutex;

	public void read_lock()
	{
		counterMutex.lock();

		if (readerCounter == 0)
		{
			readerCounter++;
			readerWriteMutex.lock();
		}
		else
		{
			readerCounter++;
		}

		counterMutex.unlock();
	}

	public void read_unlock()
	{
		counterMutex.lock();
		readerCounter--;
		if (readerCounter == 0)
		{
			readerWriteMutex.unlock();
		}
		counterMutex.unlock();
	}

	public void write_lock()
	{
		readerWriteMutex.lock();
	}

	public void write_unlock()
	{
		readerWriteMutex.unlock();
	}
}

- lshmouse April 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice solution!

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

hi can u explain why u have used two mutex obj..e.g

private Mutex counterMutex;


private Mutex readerWriteMutex;


also plz explain the algo..??

- Algoseekar April 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There are enough flaws in this.
Please google reader-writer implementation online

- gavinashg September 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agree with the comment that the code won't work. The problem is only the thread that locks the mutex can unlock it.

- Anonymous April 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No need to have 2 mutex.

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

ding!

- Anonymous April 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The code has one problem
First reader executes read_lock(). He locks readerWriter. readerCounter = 1
Second reader executes read_lock(). readerCounter = 2
First reader executes read_unlock(). Here it does no release readerWriterLock, since readerCount = 1.
Second reader executes read_unlock. Will try to release readerWriter lock since readerCount=0, but will not be able to release lock , since it did not lock it.

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

I think readerCounter , counterMutex, readerWriteMutex all have to be static, i.e., they're associated with the class instead of any instance of the class.

- kgbounce June 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this the readers writers problem in OS?

- nmc July 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this the readers writers problem in OS?

- nmc July 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

think of the algorithm with some considerations in mind:
1. if you read, you want to prevent some process writing to it as you do
2. multiple process may read
3. when you write, same thing as 1 and 2

so the counter is to count how many processes are read/writing. Before changing the counter we lock the counter so other processes cannot change it.

the counter keeps track of how many read/write are currently in progress and the lock needs to wait for before totally unlocking

that should help you understand this code. gj btw.

- charles April 20, 2011 | 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