This was stolen from a hiring manager with Microsoft Office when I went through one of the strangest interview loops of my life. Maybe I’ll talk about that another time, but suffice it to say that if another multinational technology company tries to hire me they shouldn’t try to do it in an office park in Las Colinas (Dallas suburb) in a room with no windows under absurd “This offer expires at the door” conditions. But I don’t want to talk about the past, I want to share a pretty mind bending interview question. If you’ve found this because I’m going to be interviewing you, please mention that you found this entry. I will be impressed that you did research in advance on your interviewer.
As with all good interview questions this one is best done in C. Imagine a singly-linked list who’s data is a pointer to another node in the list or is null. So you’ve got something like:
struct Node {
Node* next;
Node* data;
}
Write a function that when passed a linked list makes a deep copy. By which I mean that if you had the following
| Node | Next | Data |
|---|---|---|
| A | B | C |
| B | C | null |
| C | null | C |
the function would return:
| Node | Next | Data |
|---|---|---|
| D | E | F |
| E | F | null |
| F | null | F |
Well, a pointer to D, but you knew that already. Writing any function that successfully implements the problem description is passing, but the bonus points come when you do it without using any additional memory (with the obvious exception of the new Nodes that need to be created). To be considered all answers must be in linear time (multiple iterations of the list are acceptable, but it should be a constant number of times, but you knew that when I said linear time)