Model N Interview Question for Applications Developers


Country: United States
Interview Type: Phone Interview




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

Use hashtable + doubly linked list.

- Loler September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please elaborate?

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

Can you please pay me money?

- Loler September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the problem states that search should be of order O(1).
Using Hashtable might cost O(n).

I feel, along with doubly linked list of nodes, an array of nodes should be used. the insert 'value' can be index and value is the 'node' in the doubly linked list.

The doubly linked list will help in maintaining 'Recent' and 'Oldest' node.
This will result in insert, delete, search ops in the O(1)

- bluesky September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous:

Hashtable contains a pointer to a node in the linkedlist.

On access of a key, you move the node to the head of the linked list.

On eviction, you remove from the tail.

@bluesky: Yes this is expected O(1) and could potentially degrade for some keys. The question does not say guaranteed O(1), and besides this is the "standard" implementation.

As to your array idea, you are assuming the keys will be integers and small enough that your array won't be prohibitively large. Why should that be the case? (And if you try to map the keys to bounded integers, you are in fact trying to hash them!).

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

The previous Anonymous was me.

@Impersonator: You are an idiot.

- Loler September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the key here is cache associativity. If the cache is n way associative (but not fully associative), meaning each cache unit size can only be mapped to 1 of n location in the cache where n is constant, then the insertion, deletion and search time becomes a predetermined constant in the worst case. Although you will need a linked list at the same time to track least recently used caches, recently used are put to the head and not used cache are automatically left towards the tail. Deletion, insertion, and taking the tail element of the linked list are also constant time operations.

- guest October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think using doubly linked list will be more appropriate

- Fargushan October 03, 2012 | 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