gadhacoder
BAN USER- 0of 0 votes
AnswersYou need to implement a versioned stack, i.e. version of stack will increment after each push/pop. Apart from push/pop, implement a method print(n) which would print stack state corresponding to version 'n'. For example:
- gadhacoder in India
-> initially stack is empty.
-> Version 1: 11 is pushed
-> Version 2: 8 is pushed
-> version 3: pop. only 11 left
-> Version 4: 15 is pushed
....
And so on.
Print(n) should print state at version 'n'.
Here 1 should print 11, 2 should print 8, 11...
All methods should be as efficient as possible.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
Sorry Mat. Because of my typo, description of print method became confusing. I should have said:
"print which would print stack STATE corresponding to stack version"
I am not sure how hash table helps here.
I guess giving an example would be better:
-> initially stack is empty.
-> Version 1: 11 is pushed
-> Version 2: 8 is pushed
-> version 3: pop. only 11 left
-> Version 4: 15 is pushed
....
And so on.
Print(n) should print state at version 'n'. Here 1 should print 11, 2 should print 8, 11...
Hope I made it clear.
My solutions:
1. Copy complete stack at each version and keep in an array or something. Huge space complexity & push/pop both are O(n) as you need to copy state at each step.
2. Keep a log of operations at states. As in, for the above example I would keep:
[0] push 11
[1] push 8
[2] pop
[3] push 15
...
Since on one extra step is required during push/pop, they are still O(1). Print is expensive. Basically I need to rerun all operations start from 1 till 'n' to get the state of version 'n'.
He wasn't very satisfied with my solutions and wanted me to improve. During my telephonic interview, I couldn't.
However now I can think of one trick. Basically a middle ground of both solutions. After 'm' steps, I'll copy the stack state. Say after every 10 operations. I mean:
-> keep log of operations from 1 to 9.
-> keep copy of stack state for version 10.
-> keep log of operations from 11 to 19.
-> keep copy of stack state for version 20.
....
Larger 'm' will tend to reduce the space but will make print expensive.
Can anybody do better?
@lol
- gadhacoder September 17, 2011So how will your print work after V6 let say, if you want to print version 2?