Interview Question Trap!

There's a trap in interviews today, and I'm wrestling with how to address it.

Let's take for example the classic question of how to reverse a singly-linked list. The traditional answer is to create temp pointers so that nodes don't get lost in the shuffle, and flip the pointers from forward to backward:

n1 -> n2 -> n3 -> n4 -> n5
n1 <- n2 <- n3 <- n4 <- n5

Here I find myself caught between a rock and a hard-place. If I model the problem using C-style structures, or C++ classes, as nodes, it's easy for the interviewer to assume that I do not have knowledge of std:: data structures. Furthermore, I really want to demonstrate my std:: knowledge by modeling the problem with std::forward_list

Now the std:: happily provides a .reverse() method:
http://www.cplusplus.com/reference/forward_list/forward_list/reverse/

With this, I could easily scribble out this one liner:

myForwardList.reverse();


..and ask if we get the job. This would probably be greeted with a patient smirk and a request to solve the problem without using library functions.

NOW, here's the real trap. If I use std::forward_list to model the data:
- I can't use the .reverse() method
- I can't easily flip the pointers, because I don't have direct access to the underlying structures!

What's the best way to approach this issue?

Thanks, Keith :^)

Last edited on
Hi @kmiklas,
I have never used the "std::forward_list", but I do have some knowledge on lists and "std::string".
Looking at the components of the class, I have come up with an Idea that you can try:
Count the number of nodes if you don't already know the number.
Use insert_after method to place the node before the last one, after it. Do this until you get to the first node, which will turn the list into a palindrome [node0-nodex-node0].
Use erase_after(0, numberOfNodes), and then you will have the [nodex-node0] part.
Hope this helps.

EDIT:

Let me use a more intelligible explanation: do a for loop from last component to first component, and you just copy the current component to the end of the list. After that just erase the first n-1 components.
Last edited on
Interviewers generally are interested in your thought process. You could say something like : "Now, I will write my own structures similarly to how std::forward_list is implemented" - this demonstrates that you know- and are aware of the standard, while not converging on one-liners.
as an interviewer, I would love it very much to see you throw a well-deserved std::forward_list::reverse() back at me for that question - that will be a definite +1 from me at post-interview feedback - but if it's a face-to-face interview, one of my most important goals there is to see you write (more than one line of) code, so after poking at the limits of your knowledge there (what is its runtime and space complexity? does it allocate? does it invalidate iterators? does it invalidate references? what happens if an exception is thrown halfway? (trick question)) I will have to say "now how would you implement that member function? Please write code"
Last edited on
Topic archived. No new replies allowed.