Author |
Topic: MS Interview Question (Read 961 times) |
|
minniekp
Newbie
Gender: 
Posts: 3
|
 |
MS Interview Question
« on: Aug 16th, 2007, 1:24am » |
 Quote  Modify
|
This was asked in a Microsoft Phone in interview for a SDE role.
How do you test a stack??
Does anyone know how to do it ?
The answer I gave was writing test cases to push elements and pop elements from a stack and printing them out.
Thanks
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: MS Interview Question
« Reply #1 on: Aug 16th, 2007, 3:24am » |
Quote Modify
|
There's a number of other things you could test for. For example the behaviour when you try to pop elements from an empty stack. Or when you try to push elements on a full stack (or if there even is a limit).
You could also test its performance, how fast are pop and push operation. And someone might be interesting in which direction in memory the stack grows (or if it's even in a definite direction; a stack implemented as list wouldn't necessarily gro in a set direction).
Corrupting the stack, and seeing if it can somewhat recover might also be interesting, depending on what the stack is for.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: MS Interview Question
« Reply #2 on: Aug 16th, 2007, 6:47am » |
Quote Modify
|
One point is that you cannot test a stack (or anything) if you don't have a specification that tells how it is supposed to work. How should it react if you pop() from an empty stack and how should it report a stack overflow?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MS Interview Question
« Reply #3 on: Aug 16th, 2007, 7:01am » |
Quote Modify
|
Maybe the goal of the test is to figure out what the specification might be 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: MS Interview Question
« Reply #5 on: Aug 17th, 2007, 1:30am » |
Quote Modify
|
on Aug 16th, 2007, 11:48pm, minniekp wrote:
You may want to read the link again carefully. What it tests for and what Grimbal asked you earlier are two different things.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
GowriKumar
Junior Member
 
Gender:
Posts: 55
|
|
Re: MS Interview Question
« Reply #6 on: Aug 17th, 2007, 1:52am » |
Quote Modify
|
Assuming that it is testing the "stack data structure" (and not the program stack), I would probably say the following things:
Say that the operations allowed on stack are:
push
pop
top
A few scenarios to look at would be:
- How does the stack handle push on a full stack
- pop on an empty stack
- top shouldn't remove element from the stack
(calling top any number of times should return the same value)
- push and pop immediately should return the same element
- top and pop would return the same element. but pop should remove the element from the stack.
- take a string push all the characters in the string and now pop all the elements from the stack into a new string. the new string must be reverse of the original string.
- push and pop ideally should be constant time operations (they shouldn't be dependant on the number of elements on the stack). If the stack is implemented as an array with the dynamic resizing probably there might be a performance bottle neck at some place.
- assuming the stack supports more than 1 million entries, push 1 million entries into the stack and pop all of them (and now see if there is any leak in the memory)
Regards,
Gowri Kumar
http://www.gowrikumar.com
|
|
IP Logged |
www.gowrikumar.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print