linked list

[jamihuq]

Hello,
I got an interview question and didn't understand a concept being asked
for. Here is the question:
Write a function that would: return the 5th element from the end in a
singly linked list of integers, in one pass, and then provide a set of
test cases against that function.



What does "in one pass" mean and can you give an example?????

Thanks
Jami

 

[Ben Pfaff]

I got an interview question and didn't understand a concept being asked
for. Here is the question:
Write a function that would: return the 5th element from the end in a
singly linked list of integers, in one pass, and then provide a set of
test cases against that function.



What does "in one pass" mean and can you give an example?????

One way to do this is to go through the linked list counting the
number of elements, then go back through it again and return the
5th from the end. That takes two passes.

The interview question is asking you to find a way to do so
without making the second pass. I can think of two ways,
off-hand; one requires modifying the list, the other does not.

 

[Eric Sosman]

jamihuq wrote On 04/24/06 11:37,:

Hello,
I got an interview question and didn't understand a concept being asked
for. Here is the question:
Write a function that would: return the 5th element from the end in a
singly linked list of integers, in one pass, and then provide a set of
test cases against that function.



What does "in one pass" mean and can you give an example?????

This is an algorithms question, not a C language
question, so a forum like comp.programming would be a
better place to ask it.

<off-topic>

"One pass," in this context, probably means that
you may traverse the list only once. Imagine that
each reference to the "next" pointer in a node of the
list costs you a dollar, and look for a solution that
minimizes your out-of-pocket expense. By contrast, a
"two-pass" solution might walk the entire list once to
count the number of nodes, N, and then start over at
the beginning of the list again and walk over the first
N-5 nodes. This costs 2N-5 dollars (with a quibble about
whether getting a pointer to the first node is or isn't
free); can you find a cheaper solution?

</off-topic>

 

[Kenneth Brody]

Hello,
I got an interview question and didn't understand a concept being asked
for. Here is the question:
Write a function that would: return the 5th element from the end in a
singly linked list of integers, in one pass, and then provide a set of
test cases against that function.

What does "in one pass" mean and can you give an example?????

Exactly what it sounds like -- "in one pass". In other words, you are
not allowed to go through the list more than once (ie: "more than one
pass".)

An example of a two-pass solution:

Pass one: Go through the list and count the number of items in
the list.

Pass two: Go through the list again, until you hit the 5th element
from the last (ie: item N-4).

The question at hand is "how do you do it without using a second pass?"

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[void * clvrmnky()]

Exactly what it sounds like -- "in one pass". In other words, you are
not allowed to go through the list more than once (ie: "more than one
pass".)

An example of a two-pass solution:

Pass one: Go through the list and count the number of items in
the list.

Pass two: Go through the list again, until you hit the 5th element
from the last (ie: item N-4).

The question at hand is "how do you do it without using a second pass?"

[OT]
Is it cheating if your linked-list stores its current size in a struct
member? I almost always do that so that I can implement various "Count"
functions trivially. That is, I assume the small amount of time and
space to update the count on insert (and decrement on remove) pays off
if you can minimize walking the entire list (or a portion thereof) for
some actions.

 

[Ben Pfaff]

Is it cheating if your linked-list stores its current size in a struct
member? I almost always do that so that I can implement various "Count"
functions trivially. That is, I assume the small amount of time and
space to update the count on insert (and decrement on remove) pays off
if you can minimize walking the entire list (or a portion thereof) for
some actions.

There's a tradeoff:

* If you make the "count" operation constant-time, by
storing and updating the item count explicitly, then
the "splice" operation that moves an arbitrary number
of items from one list to another becomes O(n) in the
number of items.

* If you make "count" O(n), then "splice" is easy to make
O(1).

I suppose there's the possibility of making each iterator know
where it is in the list, so that both operations can be O(1), but
that sounds difficult to implement reliably and would increase
the cost of traversal.

 

[edware]

>
> The question at hand is "how do you do it without using a second pass?"
>

Can't someone tell how to do it? I'm curious

 

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Can't someone tell how to do it? I'm curious

As the old joke goes: "Watch for the end, and get off 5 stops before."

Think about it.

- --

Lew Pitcher, IT Specialist, Corporate Technology Solutions,
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFETQ+hagVFX4UWr64RAp8dAKDIiJ8eYbkqIS5VB1hWN066qezvZgCdHVkz
MaHshI2P+WA/jGrRFvbktho=
=Rqu9
-----END PGP SIGNATURE-----

 

[prabhu.ts]

Can't someone tell how to do it? I'm curious

It's simple to find the fifth item from last in singlelink list in
singlepass.
I shall give u logic here.

counter = 0;
fifthnode = list->getnode(); //assigning firstnode

while(list->getNext() != null)
{
if(counter >= 5)
fifthnode = fifthnode -> next();
else
counter++;
list->goNext();
}

if(counter < 5)
return -1; //list contains less then five
else
return fifthnode->getVallue();

 

[void * clvrmnky()]

There's a tradeoff:

* If you make the "count" operation constant-time, by
storing and updating the item count explicitly, then
the "splice" operation that moves an arbitrary number
of items from one list to another becomes O(n) in the
number of items.

* If you make "count" O(n), then "splice" is easy to make
O(1).

Ah. Therein lies my ignorance. I've never implemented a splice
operation. My typical usage is a single list maintained for some
smallish amount of time.

Point taken.

 

[Eric Sosman]

It's simple to find the fifth item from last in singlelink list in
singlepass.
I shall give u logic here.

counter = 0;
fifthnode = list->getnode(); //assigning firstnode

while(list->getNext() != null)
{
if(counter >= 5)
fifthnode = fifthnode -> next();
else
counter++;
list->goNext();
}

if(counter < 5)
return -1; //list contains less then five
else
return fifthnode->getVallue();

I would not call this a single pass, but two passes
that execute in parallel. Of course, "pass" is imprecisely
defined, and it's possible the O.P.'s interlocutor might
have been pleased with this solution. I don't think so,
though, since there is at least one solution that visits
each node just once.

 

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Can't someone tell how to do it? I'm curious

Here's a second hint...

Assuming a list node defined something like

struct node
{
struct node *next;
int valu;
};

and a cursor into the list that looks like
struct node *cursor;

then
cursor points to the current node
cursor->next points to the 1st node after the current one
cursor->next->next points to the 2nd node
cursor->next->next->next points to the 3rd node
cursor->next->next->next->next points to the 4th node
cursor->next->next->next->next->next points to the 5th node

If cursor->next->next->next->next->next points to the end of the list,
then cursor must point to the entry that is fifth from the end of the list.

Go to the end of the list, and get off five nodes before.





- --

Lew Pitcher, IT Specialist, Corporate Technology Solutions,
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFETRmnagVFX4UWr64RAjBhAKCgGYKivyDfhuXkSG+6z/d5f/BCzgCghwxo
FlBMeW/AXNHsDRPgaLDC2pY=
=p7Oi
-----END PGP SIGNATURE-----

 

[edware]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Here's a second hint...

Assuming a list node defined something like

struct node
{
struct node *next;
int valu;
};

and a cursor into the list that looks like
struct node *cursor;

then
cursor points to the current node
cursor->next points to the 1st node after the current one
cursor->next->next points to the 2nd node
cursor->next->next->next points to the 3rd node
cursor->next->next->next->next points to the 4th node
cursor->next->next->next->next->next points to the 5th node

If cursor->next->next->next->next->next points to the end of the list,
then cursor must point to the entry that is fifth from the end of the list.

Go to the end of the list, and get off five nodes before.

But when incrementing the cursor pointer to the next node,
(it has to do that right? in order to traverse the list),
wont the cursor->next->next->next... statement dereference
the next pointer five additional times? Doesn't that break
the rule Eric Sosman pointed out?

Anyway, if I'm wrong, how do one accomplish this with an arbitrary
number instead of 5?

 

[tedu]

There's a tradeoff:

* If you make the "count" operation constant-time, by
storing and updating the item count explicitly, then
the "splice" operation that moves an arbitrary number
of items from one list to another becomes O(n) in the
number of items.

* If you make "count" O(n), then "splice" is easy to make
O(1).

or 3) have splice set count to -1, and recalculate when needed.

 

[Kenneth Brody]

Can't someone tell how to do it? I'm curious

Here's a "gedanken experiment" for you to help figure it out.

Picture the singly-linked list as a series of rooms, each with a door to
the next. (You can't go back out the door you came in, and you can't go
out the "out" door until you have closed the "in" door.) The end-of-list
is signalled by a locked "out" door. Each room has a piece of paper with
an address written on it. Tell me the address written down in the next-
to-last room. (Remember, you can't peek into the previous room, as you
already closed the door.)

How would you go about doing that?

What if you needed the one before the next-to-last room?

What if you needed the fifth-from-last room, as in the original post?

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:[email protected]>