A colleague and I were on the train talking about various things when the topic of job interviews came up. He’s done a few interviews in order to find new employees and he was lamenting about how the questions frequently asked during these interviews didn’t really give enough insight into how the mind of the potential candidate worked. Fair enough I guess. It’s good to toss a question that might not necessarily have a direct answer but may require some semblance of a thought process to solve, know what I mean?
Well, as an example he posed a programming question out loud: “how would you go about reversing a simple linked list?” At first, I was kind of repulsed by it because, hey, I left work to not think about such things, right? However, the longer the words sat in my mind, the more I could figuratively feel the gears starting to turn in my head. I had to hearken back to some of my old programming courses in university.
Oh man…
So, OK. Let’s assume that it’s a linked list where each node just has a pointer to the next node. He mentioned that some people might solve the problem with a loop. I thought about using a loop, but something about that method seemed pretty nasty. I didn’t understand why I felt that way about the solution. He also said that some people could solve it with one pointer of sorts. Yeah…wasn’t sure how that would be done as well. Well, I stashed the problem away in the back of my mind thinking that I wouldn’t come back to it. Interestingly enough, it did come back to me as I was driving home and I thought of a solution that was sort of cool. I put it all away in the back of my mind again, but then it came back to the forefront when I was sitting on the can. I wasn’t sure why the solutions were good or bad up until I actually then.
So. Here lies a big big big disclaimer for the following stuff. I don’t know if my solution is sound. I certainly don’t think it’s the best solution. I don’t know if what I’m going to be blabbering on about makes sense: I could be tossing terms around without knowing exactly what they mean. Nonetheless…this sort of makes a little bit of sense in my mind, at least. And if it’s completely wrong, well…so be it.
So, say you’re using some sort of ugly loop to grab the pointers off the end each time. If you traverse the list each time you’re going to come up with the solution in O(n2) time, aren’t you? That’s because you’re doing some triangular number of node accesses [ {n(n+1)}/2 ]. OK. So…I was thinking why not traverse it right to the end with a recursive function? Each time the function is called, it calls itself again if it finds a next pointer value. When the function finally gets a node, it just tacks on its own next value and returns that. When everything returns, you’ll have that reverse list you wanted. Since you’re only going through the list once, you’re getting it in linear time O(n), right? Caveat: the list can’t have some sort of weird circular reference thing going or else this would fail.
I was actually able to think of a good visual analogy for all of this techno-nonsense. That recursive solution is sort of like putting your hand in a long tube sock, pinching the end, then pulling it inside out. The loop solution is like…doing suicide runs in gym class–you’re covering the same terrain over and over again.
OK. I’ve got to let the question go. I don’t plan on losing any sleep over it. Thanks.
Possibly related posts:
Recent Comments