Prasanna Raman

Ranch Hand

Posts: 410

posted 3 years ago

I came across this question in this book:

I was able to find a solution, but not one that runs in O(n) time. I did try to work out the steps on a piece of paper as many of you here recommend, but the solution they have doesn't seem intuitive to me. I do understand how the solution works but I don't know if I would have ever solved it.

So, I just wanted to ask around and see how some of the experienced programmers here would have approached this problem. Is there a way to approach these kind of questions? Or does it just mean that I have work to do?

`A "postings list" has a data field, a field for the next pointer and a jump field - the jump field points to any other node. The last node in the postings list has next set to null; all other nodes have non-null next and jump fields.`

Implement a function that a postings list as input and returns a copy of the list, in O(n) time and O(1) storage beyond that required for the nodes in the copy. You may modify the original list but must return it to its original state before returning.Implement a function that a postings list as input and returns a copy of the list, in O(n) time and O(1) storage beyond that required for the nodes in the copy. You may modify the original list but must return it to its original state before returning.

I was able to find a solution, but not one that runs in O(n) time. I did try to work out the steps on a piece of paper as many of you here recommend, but the solution they have doesn't seem intuitive to me. I do understand how the solution works but I don't know if I would have ever solved it.

So, I just wanted to ask around and see how some of the experienced programmers here would have approached this problem. Is there a way to approach these kind of questions? Or does it just mean that I have work to do?

posted 3 years ago

Off the top of my head, I'd say you have to iterate through the list once to find how many nodes there are O(n).

Then, generate a random number from 1 to n-1 O(1);

then iterate through the list to that node, skipping over/not counting the current node who's value you are trying to set. O(n).

Once you have that node, you can point to it.

Time = O(n) + O(1) + O(n) = 2 * O(n) + O(1)

Since you drop the lowest order term (O(1)), and the coefficients, that leaves O(n).

I'm not sure this works...but I don't see any obvious flaws...

Then, generate a random number from 1 to n-1 O(1);

then iterate through the list to that node, skipping over/not counting the current node who's value you are trying to set. O(n).

Once you have that node, you can point to it.

Time = O(n) + O(1) + O(n) = 2 * O(n) + O(1)

Since you drop the lowest order term (O(1)), and the coefficients, that leaves O(n).

I'm not sure this works...but I don't see any obvious flaws...

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Prasanna Raman

Ranch Hand

Posts: 410

posted 3 years ago

Fred, I don't see how to amend your idea to copy the list. I especially don't see any place for the random generator, as I understand that the task is to copy the topology of the list exactly. And I must admit I still don't see a solution that would meet both speed and storage constraints. It's easy to meet one or the other, but not both.

Matthew Brown

Bartender

Posts: 4568

9

posted 3 years ago

I've seen one like this before. I think the trick is that you're allowed to temporarily change the links in the existing list, as long as you reinstate them by the time you finish copying.

So I think you can do it in three passes:

- First pass: copy each node, but also update the "next" pointer of the original nodes to point to the copy, and the "next" pointer of the new nodes points to the next original node. You've effectively interleaved the new nodes with the old ones in the linked list.

- Second pass: for each new node, work out where the jump node needs to point to, and set it. This is possible because of the interleaving.

- Third pass: set the correct values for the "next" pointers (which involves reinstating the original values for the original nodes).

Does that sound like the solution you've been given?

So I think you can do it in three passes:

- First pass: copy each node, but also update the "next" pointer of the original nodes to point to the copy, and the "next" pointer of the new nodes points to the next original node. You've effectively interleaved the new nodes with the old ones in the linked list.

- Second pass: for each new node, work out where the jump node needs to point to, and set it. This is possible because of the interleaving.

- Third pass: set the correct values for the "next" pointers (which involves reinstating the original values for the original nodes).

Does that sound like the solution you've been given?

It is sorta covered in the JavaRanch Style Guide. |