Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

I'm not sure if this is what you want, but I guess it is important to note that small bags can fit in small, medium, and large slots. Medium can fit in medium and large slots, but can't fit in small slots. And large bags can only fit in large slots (can't fit in small or medium slots). Here, we see that the token numbers should give the greatest flexibility to small bags, medium flexibility to the medium flexibility to the medium bags and low flexibility to the big bags. You can simply have 3 hashtables, one for each bag type. In the small bag hashtable, you have k slots. In the medium bag hashtable, you have 2k slots (for every possible k bags, there are 2 spots reserved- one for medium one for small). In the large bag hashtable, you have 3k slots ( 3 spots reserved - one small, one medium, one large). You can definitely set up the token number so that the token number used is flexible because of the space that is reserved for the different kinds of bag.

- SK February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This sounds like a hashtable problem with multiple buckets that handle collisions. However, the hashtable will need to be modified. The unique token is the value generated by the hash function.

With the exception that there will only be three buckets per hashtable row (representing small, medium, large compartments).

When the hash token is generated you can look cycle through the three buckets in the hash table to either insert into an empty space or do a swap.

- Alex February 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually now that I'm thinking about it, this probably won't work because each token for each passenger is unique. a collision means two passengers have the same token.

- Alex February 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Maybe each row in the hash table should point to the same list in memory (small, medium, large compartments) This will allow for all tokens to be unique.

- Alex February 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can create 3 objects small , medium , and large with current_size , max_size, and two hashtables. One to store bags and one to store token numbers mapping to other objects hashtable. So if replaced from one place the token number will have a key value which will say that it is replaced(not literally say) , then use the other hashmap to look up the location of that bag. in case the other objects also shifts the bag then the token number mapping will increase. Somehow we have to manage that, one thing can be that if token again comes back to the same object then mapping should be restored to normal and kill all mapping links for that bag between different objects

- Ajak March 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is to map from customer token to container slots. Also keep stacks of free customer tokens, free slots, and misplaced slots for each container.

So a customer comes in. You pop a free customer token. You find the object size and try to pop progressively larger containers till you find a free slot. Associate the customer token with the container slot. If the slot is bigger than it needs to be, push that customer into the misplaced slots stack for that container. If you find nothing and its a large object then look in the misplaced slots and see if you also have free slots in the smallest free stack. Remove one of them while keeping customer token and add it back to the smallest free stack, then proceed with adding the large object since freeing made a space available.

- babesh March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you assuming that there slots within a container which I don't think are.Should not a single container be a continuous space.
Are there only three bag sizes or are they varying divided into 3 ranges?

- Ramesh April 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you assuming that there slots within a container which I don't think are.Should not a single container be a continuous space.
Are there only three bag sizes or are they varying divided into 3 ranges?

- Ramesh April 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you assuming that there slots within a container which I don't think are.Should not a single container be a continuous space.
Are there only three bag sizes or are they varying divided into 3 ranges?

- Ramesh April 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How a small bag will come in large container is small container have empty space???

- Nick April 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys this is simple. Just keep a pointer to the internally transferred location in the actual token locations.

- abhishek08aug May 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is token itself may change during the course.
Create 2 hashtables, bag_hash, token_hash
Idle Condition : first bag comes insert it at appropriate place according to size generate a unquie token number and put the object in bag_hash.
Replacement Condition : Insert a bag in new location, follow idle condition and generate a token number , hash the old token number in token_hash table to insert this new token number. If the bag is moved again follow idle condition generate the token number , hash the old token number again and if there is already a entry replace that entry with new one.

Searching: use original token number in token_hash table , if entry is there use that entry to find bag in bag_hash table other wise use same token to search in bag_hash table.

- Vikas Korjani May 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution might be to use a bloom filter per container, where each container contains that XOR of all the unique tokens in that container. Moving a luggage is just a matter of XOR the unique ID with the current container and then with the new container. Depending on the size of the containers you can choose appropriate token sizes.

- inki March 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create an object for every item and map it to token. This object should store item size and container type(S/M/L).
Create 3 MinHeap (Small,Medium,Large) which represent three containers. Also maintain 3 variables which store the capacity of the 3 containers.
For any item which cannot be inserted in any of the three containers, check if the total capacity is large enough to place the current item. If yes, try to rearrange the items in containers.
For removing any item from a container, the item size should be smaller than the current item to be placed

- Iram22 March 08, 2017 | 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