Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

Implement your own doubly linked list. Use this as a queue with elements in front as oldest and elements at back as newest.
Then implement your own data structure which contains the list as a member variable. It also contains a hashmap with key as integer and value as pointer to node in the list.
To insert, simply check in map if the variable exists.If it doesn't add to the end of linked list. If it exists, then simply return.
To delete, check in map if the integer exists. If it does, then get the pointer to the node in the linked list and directly access the linked list node and remove it.

- MK August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why can't singly linked list be used?

- alex August 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

with singly linked list the deletion will not be O(1)

- Anonymous August 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are correct.
IT is LRU cache

- ashishbansal1986 September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

This can be solved using hashtable and singly linked list.

- googlybhai August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

LinkedHashMap is the datastructure for this use case.

- OTR August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Queue plus hash table

- alex August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

take an array, a, of size=10
initialize array to 0;
now whenever u enter a number, check if a[num]==1, if not then enter the number in the queue and put a[num]=1, else check the next number.
deletion operation can be done normally!

- Aarushi Sharma August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This wont work.
For Eg. if the array size n is 10 and num 15 is to be added to array, a[15] =1 would threw IndexOutOfRange exception.

- Bharry December 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

ArrayBlockingQueue

- Suneer August 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For eg:Assume the input of 8 elements is coming from array and n is 6

#include<unordered_map>
#include<iostream>

using namespace std;

int a[8]={3,8,12,9,-1,2,1,0};
int main()
{
    int i=0;
    unordered_map<int ,int> s;
    while(i<8)
    {
        if(i>5)
        {
            s.erase(i%6);
        }
        s.insert(pair<int ,int >(i,a[i]));
        i++;
    }

    for(auto d=s.begin();d!=s.end();++d)
    {
        cout<<d->first<<"\t"<<d->second<<"\n";
    }


}

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

Queue backed by Singly Linked List and HashTable will resolve it.

- OTR August 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hashtable doubly linked with an lru

- georgy August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hashtable doubly linked with an lru

- georgy August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's one possibility:
We need to maintain the following ensemble of structures:
1. Queue: it stores all the elements that are unique as per their order of arrivals.
2. Hash_Counter: it maintains the total number of elements received so far, including the duplicates.
3. Hash_Table[Value]=Frequencies.
Then we can implement the following (pseudo code):

for every new element, value, do 
{
if(Hash_Counter +1 != n)
{
Hash_Counter++;
if(Hash_Table[value]==0)
   addQ(value);
Hash_Table[value]++;
}
else  // once we are at this point, we don't need to manipulate the Hash_Counter anymore as it will equal n. In other words, we remove the first inserted and then add the new value, hence the counter remains constant
{
v=DeleteQ();
Hash_Table[v]--;
if(Hash_Table[value]==0)
  addQ(value);
hash_Table[value]++;
}
}

Queue insertion and deletion is O(1). Hash table insertion, key increase, and key decrease is also O(1). Furthermore, searching a new value can be done in O(1) since we are using the actual values as keys to insert them to the hash table. However, space requirement is an issue particularly if these values are coming from a very broad range.

- Anonymous September 06, 2013 | 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