Interview Question for Software Engineer in Tests


Country: United States
Interview Type: In-Person




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

Data Structures to be used are : Queue for cache and hashtable for constant lookup.
We can use a queue implemented as a doubly linked list to keep the page frames in the cache. So basically any frame that we access from the memory will be put into the queue at the front.

Also use a hashtable that will have page number as the key and the address of the frame in the queue as the value for the key.

Whenever there is a frame i.e it is not in cache but in memory, we bring the frame as a new entry at the top of the queue in the cache.

Then if we need a frame that is already present in the cache or the queue, then detach that frame from the queue and put it infront of the queue.

Now if the queue is full then we take the frame that is at the rear of the queue and place the new frame at the top of the queue.
So searching of a frame and updating it can happen in constant time.

- dhirajb1989 May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain this part:
Also use a hashtable that will have page number as the key and the address of the frame in the queue as the value for the key.

- Rakesh Roy May 23, 2014 | Flag


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