Another Microsoft interview question

[poop]

A friend of mine said that microsoft asked him this question:
You have a linked list in memory. It either ends in a null pointer, or it loops. It is not a 'true' linked list, as the loop does not necessarily point back to the beginning, but may point to some place in the middle, making a loop partway through. How do you traverse the list without looping on forever (either by hitting the end, or realizing you looped)?

Stipulations:
1. The list may take up nearly all available RAM, so you cannot store list information to track it. (other than a couple of counters, perhaps)
2. The list is singly-linked
3. The list may be modified, but has to be fixed upon the end of traversal.

This is a tough one.

 

[Pretender]

If I weren't tired, I'd be able to answer this. Contact me in the morning and I may be able to think.

[edit]Ok, I got a preliminary answer: Make a pointer to the beginning of the list (or wherever you're starting. Keep going thru the list, and compare the current pointer with the one you made in the beginning, until it's terminated or you're back to the original pointer in the list. If it ends, then you just traversed the list. If you come back to the beginning again, then you know it's an infinate loop, and just go thru it one more time.[/edit]

 

[poop]

That would work if you knew where the loop went. It is not that simple, though. Read my description again, and look at these pics:

OK, ASCII art is a no-go...

The point is that the list may loop to the middle. So if you only keep track of the start, then you may still enter the loop without passing the starting point again.

 

[DAM]

wait if the pointer points somewhere in the middle of the list and you do not know this, then how can you figure out when is the beginning? it would indefenetly loop and you would assume that, that point in the middle is the beginning.






dam()

 

[poop]

The beginning is the beginning. You always have a start pointer.

The last object/struct on the list may end in one of two ways:
1. Null terminated
2. It points to some other object/struct in the list, creating a loop.

Here is another try at ASCII: (ignore the periods)

Possibility 1:
->->->->->->->

Possibility 2:
->->->->->
........^....|
........|....v
........<-<-

 

[DAM]

can you check every obj in the list for null? and if it is not null then do make it a null.




its been a while since ive taken a cs class so i might be talking out of my ass.





dam()

 

[$pade]

how about storing the list on hardrive

 

[poop]

DAM - I am not really sure what you are trying to say...

$pade - That is one of the most novel answers I have heard so far. I guess that would work, but it would be as slow as Christmas. Truly the Microsoft way, I guess

There are 2 really good solutions I have heard, though. One is insanely simple, and only involves a max of 3 list traversals. The other is q bit more complex, but more scientific in its approach.

 

[falconx88]

poop:

this algorithm works but you have to make a copy of the link list somewhere.
this algorithm will run through the link list once and will find the loop node in the list for ya

LoopIsNotFound = true
while LoopIsNotFound do

• check the pointer of the next node

• if the pointer = null then

• • the pointer points to the loop node in the list

• • LoopIsNotFound = false;

• else

• • goto the next node and make the previous node point to null

end while

 

[$pade]

by the way that is a good question, my ms interviewer only asked me to write a function to reverse the word order in a string.

 

[$pade]

falcon, unfortunately the link list is supposed to take up almost all availabe ram and using a hardrive may be out of the question. I guess another of my lame answer would be to change the struct of the list to include a bit variable that you can set as you traverse the list. maybe reversing the list might help as well?


poop can you email me the awnswer?

 

[falconx88]

pade:

 

[falconx88]

pade:


in that case i would do a memory stack dump and show a bluscreen


poop:
post the answer if u have it

 

[poop]

You cannot copy the list. You may not have enough memory. That was a nice try, though.

edit:
Unless you copied it to the hard drive, that is. The algorithm would be ultra-slow then. There are 2 possible ways to do it in a short amount of time, all in memory.

 

[Engine]

Ok, here's something a little weird, and I'm not sure if it's allowed, but I think it might work.

Make three variables to track info, one that's a counter, and two that are pointers to a node.

Start by storing the &quot;next&quot; pointer for the first node in one of the temp variables, a pointer to itself in the other temp var, and setting the &quot;next&quot; pointer for the first node to null. Then start looping through the list, and as you trverse to each new node, store its &quot;next&quot; pointer and a pointer to itself in the temp variables and set its next pointer to the previous node, all the while incrementing the counter.

End the looping when you hit a null &quot;next&quot; pointer.

When you hit a null, loop through the list again, except use a FOR loop with the counter you incremented the first time. This _should_ set the list back to its original state.

This way, if you hit a null you are either at the beginning or the end if the list, because if the list's end node points back to somewhere in the middle, all of the nodes will be pointing back in the direction of the first node, which has a null &quot;next&quot; pointer.

 

[slipperyslope]

Do you have enough room for a simple pointer?

If so all you do is traverse the list adding something like a 1 to each node as you go. Also have a trailing pointer that points to the previous node. Always check the list as you go for a 1. If you hit a 1 then the trailing pointer is at the end. Just let the node continue through the list removing the 1 until it is equal to the pointer.

I think that works if it makes any sense.

Jim

 

This must have been some time ago. Microsoft is so hurting to hire people now that all it takes to get a job there is knowing how to use a keyboard and mouse.

 

[poop]

SlipperySlope: You may overflow your memory if you add a new var to each node. You have an undetermined # of nodes, and you may add too many bytes/ints.

Engine has one of the solutions. Granted is the more complicated of the two I have heard, it is a workable solution. A little tweaking to that answer, and you can actually find where the last node loops to.

 

[falconx88]

poop:

alright i think i got the answer

from what i understand, you have a link list that can either be circular or not circular...
so the way you would find out if it is circular is as follows:

you make two pointers A and B...they could start at the same place or at differenct places in the list..but B must be after A. The amount of nodes you move for each pointer is different....ie pointer B will move twice as fast as pointer A in the list. and you would just traverse the list with these two pointers...if both of the pointers points to null then you have a non-cirucular loop...but if pointer B= pointer A then you have a cirucular loop.

if this list is circular it might take a few loops before B = A so its not the most efficient but i think this should work.

 

[Engine]

falconx88: Hey, good one!
/me slaps himself on the head for not seeing the easy solution.

 

[slipperyslope]

Nevermind.....made a slight error in thought

Jim

 

[nd]

mmm, tough one.. in an interview I would tell them that's the wrong problem to solve, as the best solution is to fix your list producing code!

Here's an idea I came up with, which seems feasible:

As you go through the list, &quot;mark&quot; your territory by setting the pointer value to the negative counterpart (i.e, 0x12345 to -0x12345). You'll know you hit the end when you arrive at a negative pointer, in which you'll then proceed to 'fix' the list by setting it back (and stopping when you hit a positive pointer).

I don't particularly like this solution though, because it makes platform-dependent assumptions about pointers.

Edit: Oh, and btw, this solution appears superior because:

1) Zero unnecessary iterations before discovering the loop (one needed at the end though to 'fix' it)
2) Zero temporary variables needed

So it's pretty fast and doesn't waste memory

Edit again: Bah, on second thought.. I think most pointer types are unsigned, so this wouldn't work. But I think the idea of &quot;marking your territory&quot; in the element somehow is on the right track.

 

[nd]

^^^

Are you going to post the &quot;simple&quot; solution?

 

[Engine]

nd, I had thought about the 'marking your territory' thing, too, but it made my brain hurt so I discarded that idea I had thought that by coming up with some kind of unique bit pattern or something and appending it to the data in the node. When you come across that bit pattern you know you've been there before. I had problems with this, though.

How could I append a bit pattern to the data without changing the data type? And if I added data, wouldn't that make a huge increase in memory requirements? Maybe if you could come up with some way to _change_ the data in the node to flag it as already 'seen', but still be able to reverse that change at the end. I couldn't think of any way to do this so that it would be flagged as 'seen', and would apply for any data type, so I scrapped that idea.

Honestly, I think that falconx88's idea is the simplest one. Just start two pointers iterating through the list, one 1 node at a time, the other 2 nodes at a time. If they are both null, then the list ends with a null. If at any point (after the first node, of course) they point to the same node, then the faster one had reached the end and looped back through.

Do you _have_ to hit every single node in the list? If so, then I guess this solution might not work.

 

[nd]

<< How could I append a bit pattern to the data without changing the data type? And if I added data, wouldn't that make a huge increase in memory requirements? Maybe if you could come up with some way to _change_ the data in the node to flag it as already 'seen', but still be able to reverse that change at the end. I couldn't think of any way to do this so that it would be flagged as 'seen', and would apply for any data type, so I scrapped that idea >>


Yeah, I considered some bit pattern too, but there's no way to tell if it's valid or not. The interesting part about modifying the pointer is that you don't have to add anything - you just change what's there.

Another thing you could probably do is increment the pointer by 1. This is assuming each element is at least 1 byte (not including the pointer) in size. Beyond that, it'd be difficult to determine when you loop still.

I don't really like the idea of using 2 starting points and waiting for them to coincide.