Google Interview Question for Software Engineers


Country: United States




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

Use the following mechanism.

There is a lock manager node and bunch of other nodes

1. Each node, if it wants to acquire a lock, sends a lock request to the lock manager and wait for async callback from the lock manager
2. Lock manager has lock request queue checks if the queue is empty, it sends a lockAcquired notification to the caller node, then it puts the lock request in a queue. If the queue is not empty, it just pushes the lock request to the queue.
3. When a node receives the lockAcquired notification, it can process data. (Meaning lock is acquired)
4. When a node finishes processing, it will call unlock to the node manager.
5. When unlock call is received from the node manager, it pops the data from the queue and if the queue is not empty, sends a lockAcquired notification to the next node in the queue.

- wminghao November 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice.

But how to resolve the dependency and deadlock situation? Suppose, machine m1 acquires lock for file1 and keeps the lock for very long file due to processing. So, all the requests to access file1 will be stalled. Now, if machine m2 wants to do something sequential (i.e. read file1, file2, file3 one by one), it will be blocked for that time (Asynchronous works will be done easily. But sequential tasks will be stalled).

- Psycho February 18, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

there are so many ways to do this .
Centralized mechanism

1.Master keeps a token and slaves nodes request for the token when they enter a critical section and wait for it.

2.If the master has token it reply back otherwise queue the request .

3.When the master receives the token back from the slave it send the token to the first enqued request.

There are other ways to do this as well like Ring mechanism ,where token is circulated in a ring,RA algorithm ,DHT based solution

- nishant304 December 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be achieved with lamport distributed mutual exclusion algorithm

- Nitish December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be achieved with llamport distributed mutual exclusion algorithm

- Nitish December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You could refer to ZooKeeper documentation for its architectural style to answer this question.

- saidubbaka December 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You might also want to check the Chubby lock service by Google

- Alex M. May 26, 2016 | 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