C++ interview Question
Pages: 12
I suppose you could gauge their personality on how nervous they are as well. If they're not nervous at all, they're probably arrogant and don't really need the job. If they don't really need the job, they're less likely to work very hard. If they're nervous, they probably need the job and will therefore work harder.
"But CodedoC, you didn't answer my question."
jsmith, sorry, I thought it was obvious from the breakdown I had provided. Honestly, I'm not sure if my BONUS 1 solution is on the net as I have not searched. I was trying not to give it away as per the comments made about not posting answers people can just look up. But here it goes...
(a) 1 cycle at end, but could be of any size up to the size of the list where the last link points back to the root node.
(b) O(n^2) Keep a separate list of next pointers that you come across. Linearly search through list to see if you "recognize" a pointer. If reach null, then OK, but if see repeat pointer, then not coherent.
(c) O(n log n). The search list is an AVL tree where insertion and searching is O(log n).
(d) O(n) After processing each next pointer to get to the next node, change that pointer to a value that could never represent a valid heap memory address, such as 1. If you come across a pointer with a value of 1, then you know you are in a loop. One could also use a hash table here, but the hash function should be carefully chosen due to the way the heap may be allocated. But O(n) is not guaranteed, although likely to be very close to O(n) if hash table is large enough and a great hash function is chosen.
(e) O(n) Same as d, but keep a list of next pointer addresses that you restore back to the original list. Or you can just build another list as you go on and de-allocate the first one. Change head to point to the new list.
BONUS 1: jsmith, this is my own question, so I'm going to pass this one back to you.
BONUS 2: Same as Bonus 1, but use recursion, passing p->next. On popping back, undo what you did in BONUS 1. This should be only a few lines of code.
I'm sure there are many other ways of skinning this cat--perhaps more clever or more obvious than mine.
jsmith, sorry, I thought it was obvious from the breakdown I had provided. Honestly, I'm not sure if my BONUS 1 solution is on the net as I have not searched. I was trying not to give it away as per the comments made about not posting answers people can just look up. But here it goes...
(a) 1 cycle at end, but could be of any size up to the size of the list where the last link points back to the root node.
(b) O(n^2) Keep a separate list of next pointers that you come across. Linearly search through list to see if you "recognize" a pointer. If reach null, then OK, but if see repeat pointer, then not coherent.
(c) O(n log n). The search list is an AVL tree where insertion and searching is O(log n).
(d) O(n) After processing each next pointer to get to the next node, change that pointer to a value that could never represent a valid heap memory address, such as 1. If you come across a pointer with a value of 1, then you know you are in a loop. One could also use a hash table here, but the hash function should be carefully chosen due to the way the heap may be allocated. But O(n) is not guaranteed, although likely to be very close to O(n) if hash table is large enough and a great hash function is chosen.
(e) O(n) Same as d, but keep a list of next pointer addresses that you restore back to the original list. Or you can just build another list as you go on and de-allocate the first one. Change head to point to the new list.
BONUS 1: jsmith, this is my own question, so I'm going to pass this one back to you.
BONUS 2: Same as Bonus 1, but use recursion, passing p->next. On popping back, undo what you did in BONUS 1. This should be only a few lines of code.
I'm sure there are many other ways of skinning this cat--perhaps more clever or more obvious than mine.
My solution is floyd's algorithm, here:
http://en.wikipedia.org/wiki/Cycle_detection
Uses constant memory, runs in O(n) time, and does not trash the data structure.
http://en.wikipedia.org/wiki/Cycle_detection
Uses constant memory, runs in O(n) time, and does not trash the data structure.
jsmith,
Without checking your link, driving home from work I came up with an algorithm that turns out to be identical to Floyd's except that I did not attempt to (trivially) find the length of the loop (thus, yes O(μ) rather than O(λ+μ)) for pure "detection". The only hint I had was that you had convinced me that there was a non-destructive O(n) algorithm. BTW, my destructive algorithm (granted, probably useless) is still faster (not in complexity but overall run-time).
I find that many people, including myself, often stop searching for better solutions unless prodded to do so. I've been in interviews where the interviewer says, "OK, now do it without blah blah..." and they do this to truly find the limits of the interviewee while observing their thinking skills. What happens is that we come up with better solutions thinking, wow, I might not have thought of that had I not been pushed to do so.
But the real point is this: If someone were in an interview and said, "I'd just use Floyd's algorithm" that would tell me that they have great knowledge, but nothing about their problem solving skills. If I got an answer like this, I'd still ask for the other solutions, and I'd probably move onto another problem that they didn't already know the answer to.
For what it's worth, my own set of solutions resulted from absolutely 0 references, and 1 hint, and I was able to demonstrate my ways of thinking--I realize you'll just have to take my word for it. The total time spent thinking was maybe 5 minutes on my initial set of solutions, and about 10 minutes on coming up with Floyd's algorithm in my head. I was not able to recall any cycle detection algorithms from college or grad school in C.S--only the methodologies required to solve such problems obtained from my data structures, algorithms and complexity theory, and finite automata classes.
Cheers
Without checking your link, driving home from work I came up with an algorithm that turns out to be identical to Floyd's except that I did not attempt to (trivially) find the length of the loop (thus, yes O(μ) rather than O(λ+μ)) for pure "detection". The only hint I had was that you had convinced me that there was a non-destructive O(n) algorithm. BTW, my destructive algorithm (granted, probably useless) is still faster (not in complexity but overall run-time).
I find that many people, including myself, often stop searching for better solutions unless prodded to do so. I've been in interviews where the interviewer says, "OK, now do it without blah blah..." and they do this to truly find the limits of the interviewee while observing their thinking skills. What happens is that we come up with better solutions thinking, wow, I might not have thought of that had I not been pushed to do so.
But the real point is this: If someone were in an interview and said, "I'd just use Floyd's algorithm" that would tell me that they have great knowledge, but nothing about their problem solving skills. If I got an answer like this, I'd still ask for the other solutions, and I'd probably move onto another problem that they didn't already know the answer to.
For what it's worth, my own set of solutions resulted from absolutely 0 references, and 1 hint, and I was able to demonstrate my ways of thinking--I realize you'll just have to take my word for it. The total time spent thinking was maybe 5 minutes on my initial set of solutions, and about 10 minutes on coming up with Floyd's algorithm in my head. I was not able to recall any cycle detection algorithms from college or grad school in C.S--only the methodologies required to solve such problems obtained from my data structures, algorithms and complexity theory, and finite automata classes.
Cheers
I don't think it's wrong to prod for better solutions in the general case. It has just been my experience that the above problem is hard enough that only a small percentage of candidates will be able to come up with multiple algorithms.
Yes, as I mentioned in a previous reply, if someone were to come up with Floyd's algorithm--be it by name or not--I would wonder if they solved the problem on the spot or just knew the answer ahead of time. That's why I prefer candidates not come up with the optimal solution.
Yes, as I mentioned in a previous reply, if someone were to come up with Floyd's algorithm--be it by name or not--I would wonder if they solved the problem on the spot or just knew the answer ahead of time. That's why I prefer candidates not come up with the optimal solution.
discssion is going on ... but it is good when you are part of good discussion.
I start this thread with the intension to know some basic question which ask interviwer during interview which we do not use day to day life... ...
I want to add one more point ( ignore if silly idea). Could we start one forum or blog or sub forum on this forum also where we express our experience with topic by topic.
i.e. for example Constructor ... we should share all experience or question or knowledage about the constructor and make a useful one single page.
These kind of information will be useful for intermediate programmer becuase They know "what is constructor and some couple of question about constructor" which They have read in books or encounter one or two time in day to day life but did not have exposure on live issue of constrcutor....
If I summarize, we have discussed about interviewer question which they can ask or what they are looking for. but we can create subforum where we can share all information about one topic which will helpful to increase thinking level (truly speaking I do not have)and understand proper way about c++ concept
I hope I have conveyed my message ....
I start this thread with the intension to know some basic question which ask interviwer during interview which we do not use day to day life... ...
I want to add one more point ( ignore if silly idea). Could we start one forum or blog or sub forum on this forum also where we express our experience with topic by topic.
i.e. for example Constructor ... we should share all experience or question or knowledage about the constructor and make a useful one single page.
These kind of information will be useful for intermediate programmer becuase They know "what is constructor and some couple of question about constructor" which They have read in books or encounter one or two time in day to day life but did not have exposure on live issue of constrcutor....
If I summarize, we have discussed about interviewer question which they can ask or what they are looking for. but we can create subforum where we can share all information about one topic which will helpful to increase thinking level (truly speaking I do not have)and understand proper way about c++ concept
I hope I have conveyed my message ....
Last edited on
| chrisname wrote: |
|---|
| I suppose you could gauge their personality on how nervous they are as well. If they're not nervous at all, they're probably arrogant and don't really need the job. If they don't really need the job, they're less likely to work very hard. If they're nervous, they probably need the job and will therefore work harder. |
Alternatively, they could be nervous because they apply for a job they actually do not like or are actually not good at. If they aren't nervous at all, they could actually just really be confident or have a really open personality.
Never take conclusions too fast.
closed account (oz10RXSz)
Yes, as I mentioned in a previous reply, if someone were to come up with Floyd's algorithm--be it by name or not--I would wonder if they solved the problem on the spot or just knew the answer ahead of time. That's why I prefer candidates not come up with the optimal solution. |
I would come up with the linear algorithm using the additional structure on the heap. After being asked if I could do better, wothout additional structure, I would come up with the Floyd algorithm (well, I didn't know it had a name, just made it up in 5 minutes, while reading this thread, prior to someone posted the link). The bonus 2 part - making it recursive is obvious. So I don't know if I wouldn't be regarded as "knew the answer before" :D
Topic archived. No new replies allowed.
Pages: 12