Adobe Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




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

The solution you provided in the previous comment does not guarantee O(1) amortized time. It covers many cases, but it still has cases when pop operations (pop-front and pop-back) are performed in O(N) amortized time (the case when we alternate pop-back, pop-front, pop-back, pop-front, ...).

In general amortized time doesn't mean 'average time' across all the possible inputs (because that is what we call average time). Amortized time is an average time we need to make a single request in a single run (input) of the algorithm. The meaning of O(1) here is as follows: if you make O(N) operations on your data structure, it will take O(N) time to perform (and it should be a guaranteed estimate).

I can offer another solution which is guaranteed to meet this property. We are going to maintain one stack always empty (it can be used in pop operations as a buffer), 1 stack for back operations and 1 stack - for front operations. Push-back and push-front to the deque are simple: just push the incoming value to the stack corresponding to the end you push. The cost is O(1).
Pop-back and pop-front can be either light or heavy. Let's call a pop operation light if the stack corresponding to the end of operation is not empty. Then you can just pop a value from it which costs you O(1) operations. If the stack is empty then we are facing a heavy pop. We are going to revert THE HALF of the non-empty stack using some second stack as a buffer, then revert it again using the third stack. After that we revert the remaining HALF of the initial stack using the second stack as a buffer. So as a result we get 2 new HALF-stacks: one for front operations and one for back. After that, again, just pop a value from the corresponding stack. Such an operation costs O(K) operations where K is a number of elements in a non-empty stack. But after performing this operation we can guarantee, that at least K/2 elements will be popped with a light O(1) operation. So we can share O(K) cost between these K/2 + 1 guys and get a O(1) average cost per each of them.

- Pavel Kalinnikov October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This questions requires a firm understanding of a deque. A deque has the ability to add/remove elements from the front and the back. A stack on the other hand operates on a LIFO (Last In First Out) system meaning you can only add and remove elements from the end. Lastly, the word amortized simply means average. You will typically hear of amortized run time analysis when dealing with an algorithm like merge sort or quick sort. This is because there is a random element to the operation on the function. At it's worst it could be O(n^2), but on the average these run in amortized O(n log N) time. So apply the concept of random run time and average outcome to this problem. We are saying that on average we expect our insert/remove functions to operate in near constant time, but understand that there may be cases where it can run longer.

Now with the definitions out of the way, how will we work on this? The hint lies in the very specific number of stacks we get - namely 3. We use one stack for front operations, the second stack for tail operations, and the last stack becomes a buffer that we use to perform reverse operations on either end as needed. Let's walk through an example:

Add these elements to the head: 1,2,3
Add these elements to the tail: 6,5,4

3 - 4
2 - 5
1 - 6

Now if I remove from head or remove from tail, I will get true O(1) constant time removal. But what if I remove more than 3 elements from either end? Then I have to reverse the other end by popping from the other stack to my buffer. This take O(n) operations and then I can resume my O(1) removal after they have been shifted to the buffer stack. The next time I want to add to the buffered end, I have to move items out of the buffer back into the correct stack so that my order is maintained, which is O(n) operation with a O(1) insert operation for the new element.

So knowing how this works, how do we prove O(1) amortized run time? Well, consider that most operations on a deque are bulk load or bulk remove, you can see that you would only have to do a O(n) buffer swap in cases where the entire list is traversed AND there are elements that have been inserted from both the head and tail. So while we will SOMETIMES see a O(n) operation to swap stacks and get the proper order, we will mostly be doing O(1) operations to insert/remove in bulk. Over the lifetime of the data structure this should make the average operations per function call land between 1 - 2, which constitutes an amortized run-time of O(1).

With that in mind, understand that there are certain algorithms that would be considered pathological for this data structure. Those would include algorithms where there are many inserts and deletes at both ends with frequent removals that 'cross the line' between the head and tail stacks. If these occurred frequently then the amortized run-time migrates closer to O(n) which completely nullifies the O(1) run time estimate.

- masterjaso October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{can one provide algo or program for it}

- niyati palit October 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What we need is a solution who's amortized (average) costs are O(1). ie. Mostly the cost of each operation is O(1) except a few, where the cost rises to linear bounds o(n). Basically we will need to balance the queue on every non trivial pop/popFront operation.

Let Q1, Q2, Q3 be the three stacks.
After N pushes Q1 = { 1,2,3,4,5,6}
Transform it so that its divided equally among two stacks as { 4,5,6} and {3,2,1}
For example :
Pop 3 elements into q2, and 3 into q3.
So Q2 = {6,5,4} Q3 = {3,2,1}
Pop back Q2 into Q1 , so that Q1 = {4,5,6}

Now, popFront() will take O(1), and its a pop on Q3.
Pop() will take O(1), and its a pop on Q1.
Push ()will take O(1) and its push on Q1.

Use similar mechanisms to balance the queue when you run out of pops or pop fronts.

- HK-47-rudra April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What we need is a solution who's amortized (average) costs are O(1). ie. Mostly the cost of each operation is O(1) except a few, where the cost rises to linear bounds o(n). Basically we will need to balance the queue on every non trivial pop/popFront operation.

Let Q1, Q2, Q3 be the three stacks.
After N pushes Q1 = { 1,2,3,4,5,6}
Transform it so that its divided equally among two stacks as { 4,5,6} and {3,2,1}
For example :
Pop 3 elements into q2, and 3 into q3.
So Q2 = {6,5,4} Q3 = {3,2,1}
Pop back Q2 into Q1 , so that Q1 = {4,5,6}

Now, popFront() will take O(1), and its a pop on Q3.
Pop() will take O(1), and its a pop on Q1.
Push ()will take O(1) and its push on Q1.

Use similar mechanisms to balance the queue when you run out of pops or pop fronts.

- HK-47-rudra April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Two Stack are enough to implement Queue, On Q.add(data), keep adding element in Stack1 and on calling Q.pop() or Q.dequeue(), First move element from One Stack1 to Stack2 and Call Stack2.pop() and Again all elements , pushed back to Stack1.

- Anonymous August 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You can do it with two stacks:
Stack1- use only for enqueue
Stack2- use only for dequeue
Only when Stack2 is empty on dequeue request is when you lock both stacks and 'pure' the data from Stack1 to Stack2.

Worst case for a single dequeue is-
N enqueue and then N dequeue
enqueue is always O(1)
first dequeue is O(N) but the next N-1 dequeues are O(1)

- avico81 December 29, 2014 | 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