473,320 Members | 1,940 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

linked list

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

Apr 24 '06 #1
14 2661
"jamihuq" <ja*********@yahoo.com> writes:
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.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Apr 24 '06 #2


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>

--
Er*********@sun.com

Apr 24 '06 #3
jamihuq wrote:

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:Th*************@gmail.com>

Apr 24 '06 #4
Kenneth Brody wrote:
jamihuq wrote:
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?"

[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.
Apr 24 '06 #5
"void * clvrmnky()" <cl**************@hotmail.com.invalid> writes:
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.
--
"IMO, Perl is an excellent language to break your teeth on"
--Micah Cowan
Apr 24 '06 #6
Kenneth Brody wrote:

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 :)
Apr 24 '06 #7

edware wrote:
Kenneth Brody wrote:
>
> 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 :)


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();

Apr 24 '06 #8
Ben Pfaff wrote:
"void * clvrmnky()" <cl**************@hotmail.com.invalid> writes:
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).

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.
Apr 24 '06 #9
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

edware wrote:
Kenneth Brody wrote:

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 :)


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+hagVFX4UWr64RAp8dAKDIiJ8eYbkqIS5VB1hWN0 66qezvZgCdHVkz
MaHshI2P+WA/jGrRFvbktho=
=Rqu9
-----END PGP SIGNATURE-----
Apr 24 '06 #10


pr*******@gmail.com wrote On 04/24/06 13:50,:
edware wrote:
Kenneth Brody wrote:
>
> 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 :)

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.

--
Er*********@sun.com

Apr 24 '06 #11
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

edware wrote:
Kenneth Brody wrote:

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 :)


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-----
Apr 24 '06 #12
Lew Pitcher wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

edware wrote:
Kenneth Brody wrote:
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 :)


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?
Apr 24 '06 #13
Ben Pfaff wrote:
"void * clvrmnky()" <cl**************@hotmail.com.invalid> writes:
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).


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

Apr 24 '06 #14
edware wrote:

Kenneth Brody wrote:
>
> 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 :)


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:Th*************@gmail.com>

Apr 24 '06 #15

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

11
by: C++fan | last post by:
Suppose that I define the following class: class example_class{ public: example_class(); void funtion_1(); void function_2(); protected:
5
by: Dream Catcher | last post by:
1. I don't know once the node is located, how to return that node. Should I return pointer to that node or should I return the struct of that node. 2. Also how to do the fn call in main for that...
10
by: Kent | last post by:
Hi! I want to store data (of enemys in a game) as a linked list, each node will look something like the following: struct node { double x,y; // x and y position coordinates struct enemy...
6
by: Steve Lambert | last post by:
Hi, I've knocked up a number of small routines to create and manipulate a linked list of any structure. If anyone could take a look at this code and give me their opinion and details of any...
12
by: Eugen J. Sobchenko | last post by:
Hi! I'm writing function which swaps two arbitrary elements of double-linked list. References to the next element of list must be unique or NULL (even during swap procedure), the same condition...
12
by: joshd | last post by:
Hello, Im sorry if this question has been asked before, but I did search before posting and couldnt find an answer to my problem. I have two classes each with corresponding linked lists, list1...
51
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort...
1
by: theeverdead | last post by:
Ok I have a file in it is a record of a persons first and last name. Format is like: Trevor Johnson Kevin Smith Allan Harris I need to read that file into program and then turn it into a linked...
0
by: Atos | last post by:
SINGLE-LINKED LIST Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be...
7
by: QiongZ | last post by:
Hi, I just recently started studying C++ and basically copied an example in the textbook into VS2008, but it doesn't compile. I tried to modify the code by eliminating all the templates then it...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.