5 ms·

I have a similar story with Microsoft when I interviewed with them my senior year also. I feel like I nailed everything except for the puzzles, and also got den

I have a similar story with Microsoft when I interviewed with them my senior year also. I feel like I nailed everything except for the puzzles, and also got denied. My favorite one I "failed" on was: Given a node of a linked list, delete that node. The expected answer: Copy the next node's contents into the given node. Then delete the next node. Just simply never occurred to me to use a memory copy in a linked list. And this is despite the fact that I could immediately reason about the solution he gave me and point out a flaw in it (deleting the last node is impossible).

boomzilla 14y ago
but that is not a puzzle, it's real code if you don't access to a collection library
- jdmichal 14y ago
  No, it's a puzzle for two reasons: 1. It's not a normal operation for a linked list. A normal linked list will expose operations to deal with items, not nodes. 2. There was an expected answer, and that answer was something other than the normal linked list delete operation of "traverse the list to find the node containing the item, while also keeping a trailing pointer to the previous item so that you can remove that item's node." Even if you are exposing nodes, and you do implement the given operation, then TheCoelacanth is absolutely correct that that operation just invalidated all references to the node after the one you thought you had just deleted, but not any references to the node you thought you had deleted. (Though those references are now pointing to a different data instance.)
TheCoelacanth 14y ago
In addition to not being able to delete the last node, it also invalidates any pointers to the node after the one you're deleting.
- jdmichal 14y ago
  Great point, and not something I had thought of. Just makes the "expected" solution even more odd... If you're exposing nodes enough to get an operation to delete a particular node with no context, then the given solution just invalidated a completely different node, but not the one you asked it to delete. No, the one you asked it to delete is still valid, just with different data associated.

boomzilla 14y ago

but that is not a puzzle, it's real code if you don't access to a collection library

jdmichal 14y ago
No, it's a puzzle for two reasons: 1. It's not a normal operation for a linked list. A normal linked list will expose operations to deal with items, not nodes. 2. There was an expected answer, and that answer was something other than the normal linked list delete operation of "traverse the list to find the node containing the item, while also keeping a trailing pointer to the previous item so that you can remove that item's node." Even if you are exposing nodes, and you do implement the given operation, then TheCoelacanth is absolutely correct that that operation just invalidated all references to the node after the one you thought you had just deleted, but not any references to the node you thought you had deleted. (Though those references are now pointing to a different data instance.)

TheCoelacanth 14y ago

In addition to not being able to delete the last node, it also invalidates any pointers to the node after the one you're deleting.

jdmichal 14y ago
Great point, and not something I had thought of. Just makes the "expected" solution even more odd... If you're exposing nodes enough to get an operation to delete a particular node with no context, then the given solution just invalidated a completely different node, but not the one you asked it to delete. No, the one you asked it to delete is still valid, just with different data associated.