Amazon Interview Question for Software Engineer / Developers


Country: India




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

Not possible to have O(1) for each.

If it was, you could sort in O(n) time.

Interviewers are getting dumber by the day.

- Anonymous February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is the answer

- waiging.lau February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is possible if we restrict the problem domain a little bit. For example if all of the elements being inserted or deleted are in a range & no constraints on the memory, an array and couple of heaps could satisfy this. Note that there is no access of any other element other than min & max.

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

Anonymous, the last time I checked remove min (or max) is a log(n) operation for a heap since you have to walk through it to ensure data strucuture integrity

- Mathcomp February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Are you serious ??? Why are you tarnishing Amazon's name? Please refrain.

- Bevan February 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about counting sort? that is o(n) with unlimited space

- Sexi boy February 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about counting sort? that is o(n) with unlimited space

- Sexi boy February 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well, counting sort or bucket sort radix sort is counting on certain kind of the input data. the question doesn't not say anything about the input data.

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

Even if you use count sort delete min,delete max, find min find max wont be O(1)

- Anonymous March 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use a Magic Carpet data structure. Be careful though, as it is running so fast that it is getting way to hot.

- Andersen G.Ch. February 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure, I can give you a link.

There is something I want you to do for me before that.
Go to Canada and count all cows there. Then count cats and dogs. Divide cats by dogs and take a square root from that number.

After you do the task, you will get the link.

- Andersen G.Ch. February 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

btw, Magic Carpet can also brew coffee and cook rolls.

- Anonymous February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If the elements of the data structure only supports comparative sorting, then those kind of data structure does not exist. Because according to the feature list, people can achieve the a sorting algorithm wit O(n) time complexity:
1> You put elements in to the data structure one by one
2> Then you get max or min from it one by one.
So time complexity O(2n).
But it is told that comparative sorting could only achieve O(nlogn). So it is impossible for existence of such data structure in this case.

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

Use a Magic Carpet data structure. Be careful though, as it is running so fast that it is getting way too hot.

- Andersen G.Ch. February 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use a hashtable + 2 stacks (to track min/max)... it will give all O(1) operations

- Rahul Arakeri February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

LOL.

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

I think he is right. If the interviewer wants constant time, then he/she should be ready to spend extra memory on this. The hash map will be pointing to a vector to do delete in constant time.

- Second Attempt March 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Stack is not enough to store min and max. Consider a sequence as [1,2,10,11,12,3].
Where is placed 3 in the max stack?

- M@rco March 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Will Fibonacci heap have O(1) complexity for all the operations mentioned??

- swapna February 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, fibonacci heap has O(log n) complexity for deletemin operation

- Anonymous February 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

can be done with the help of one LinkedList,one array,two stack.... think

- samrat February 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

How will you find next min and max after delete operation in o(1).

- gdb February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the min and max are preserved in aux stacks..the logic is the same as for pop operation of the stack that has min/max functions..the example of implementation can be found at stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1

- S.Abakumoff February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sample of c# code:

class Node<T> where T : IComparable<T>
	{
		public T Value { get; set; }
		public Node<T> Next { get; set; }
		public Node<T> Prev { get; set; }
	}
	class O1DataStructure<T> where T:IComparable<T>
	{
		private readonly Stack<Node<T>> _mins = new Stack<Node<T>>();
 		private readonly  Stack<Node<T>> _maxes = new Stack<Node<T>>();
		private Node<T> _head;
		private Node<T> _tail;
		public void Delete(Node<T> node)
		{
			
			var prev = node.Prev;
			var next = node.Next;

			if (prev != null)
			{
				prev.Next = next;
				if (next != null)
				{
					next.Prev = prev;
				}

			}
			else
			{
				_head = node.Next;
			}
			if (_maxes.Peek() == node)
				_maxes.Pop();
			if (_mins.Peek() == node)
				_mins.Pop();
		} 
		
		public T Max
		{
			get
			{
				if (_maxes.Count == 0)
 					throw new InvalidOperationException("no values exist");
				return _maxes.Peek().Value; }
		}
		public T Min
		{
			get
			{
				if(_mins.Count == 0)
					throw new InvalidOperationException("no values exist");
				return _mins.Peek().Value;
			}
		}
		
		public void RemoveMax()
		{
			if(_maxes.Count == 0)
				throw new InvalidOperationException("unable to delete the max");
			Delete(_maxes.Peek());
		}
		
		public void RemoveMin()
		{
			if (_mins.Count == 0)
				throw new InvalidOperationException("unable to delete the min");
			Delete(_mins.Peek());
		}

		public Node<T> Insert(T value)
		{
			var node = new Node<T> {Value = value, Prev=_tail, Next = null};
			if (_head == null)
			{
				_head = _tail = node;
			}
			else
			{
				_tail.Next = node;
				_tail = node;
			}
			if (_maxes.Count == 0 || _maxes.Peek().Value.CompareTo(value) < 0)
			{
				_maxes.Push(node);
			}
			if (_mins.Count == 0 || _mins.Peek().Value.CompareTo(value) > 0)
			{
				_mins.Push(node);
			}
			return node;
		} 
	}

- S.Abakumoff February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if I insert [5, 4, 3, 2, 1] and call DeleteMax twice.

I think your are storing only values greater then max.peek() which in this case, maxes stack will have only 5. Once you delete 5 your maxes stack will be empty.

- Gautam February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

insert(1); insert(2); insert(3);
delete(1);

How do you achieve this "delete" in O(1)?

- Xipan Xiao February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

kalyan u r rit, xipan dude it is not about deleting random .so dont assume from ur side that they r not asking for deleting random.
koi na kalyan.u r rit.enjoy

- go4gold February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

2. delete: Delete from HashTable O(1). If item is top of min or max stack, pop it.

But what happens if item is in the middle of stack?

- AndrewJD February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ahh good catch. Then just don't worry about it. But the assumption would be that items in the stack could have been deleted already. So when it comes to relying on its value, like when determining largest or smallest value, check to see if the item on stack is actually in the hashtable first. Still O(1) though.

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

No... this is not right. Suppose you want to delete the min then ask what's the new "min", then your hashtable tells you that the value suggested by your min stack is not in the hashtable, then you needs to find the next next one in the min stack, what if that value is again not in the hashtable? I am not sure this is an O(1) operation.

- Chih.Chiu.19 February 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah you are right. The stale data causes O(n) run time. The O(1) requirement on the delete is the killer here I think.

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

Besides the insertion still need to be done on the heaps too, otherwise the new "min" may only exist in the hash table. But as we realized by the top post that O(1) time is impossible, I still think your solution is so-far the best choice, well, in which case the hash table is unnecessary, and all operations take O(lg n) time.

- Chih.Chiu.19 February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Who ever downvoted this answer are dumbasses... This is the perfect answer... Use one hash table to insert/delete/lookup at O(1) time. Simultaneously maintain 2 stacks, one max and one min which will have max/min elements on the top of stack which can be retrieved at O(1)... duh !

- Rahul March 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rahul: LOL! Do you even think before you write?

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

Not correct. This will not work if the prev pointer is deleted first & then this current node gets deleted.

- Anonymous February 22, 2013 | 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