Technical Test - singular linked list

Hi all,
I recently had to do a technical test as part of a job application. This consisted of 3 questions that you had to code an answer for.

The second question asked you to create a singular linked list and then retrieve 5 items from the tail. I then got told my answer was incorrect as I approached the problem by iterating through from the head. My understanding is that in a singular linked list you can only move from the head to the tail as its singular linked. Is this incorrect?

Am happy to be wrong on this but wanted to check.

Thanks,

Alex

That sounds right to me.

Of course, knowing in advance that you'll be retrieving items from the tail, you can keep a pointer to the tail instead of the head and have all your links in reverse. Maybe that's what they wanted?

Sven Groot said:

That sounds right to me.

Of course, knowing in advance that you'll be retrieving items from the tail, you can keep a pointer to the tail instead of the head and have all your links in reverse. Maybe that's what they wanted?

Maybe but the exact feedback I got was "was approached  from the head instead of the tail" which doesnt imply they were looking for a pointer. It was also written in C# which okay has pointers but I think I have had a reason only once to use them.

alexmac said:

Sven Groot said:

*snip*

Maybe but the exact feedback I got was "was approached  from the head instead of the tail" which doesnt imply they were looking for a pointer. It was also written in C# which okay has pointers but I think I have had a reason only once to use them.

For C# freely read "pointer to the tail" as "reference to the tail", it makes no difference.

Sven Groot said:

alexmac said:

*snip*

For C# freely read "pointer to the tail" as "reference to the tail", it makes no difference.

The exact question said given a singular linked list which implies its already set up find the nth item from the tail which surely the only way to find would be to iterate through from the head?

Ah well never mind dont think I would have got much further in their process given that was the first stage!

alexmac said:

Sven Groot said:

*snip*

The exact question said given a singular linked list which implies its already set up find the nth item from the tail which surely the only way to find would be to iterate through from the head?

Ah well never mind dont think I would have got much further in their process given that was the first stage!

Did you ask them for the answer? I can't see any other way of accomplishing it unless, as Sven said, the list is constructed in reverse.

alexmac said:

Sven Groot said:

*snip*

The exact question said given a singular linked list which implies its already set up find the nth item from the tail which surely the only way to find would be to iterate through from the head?

Ah well never mind dont think I would have got much further in their process given that was the first stage!

It sounds to me like they were using the terms head and tail in reverse.

AndyC said:

alexmac said:

*snip*

Did you ask them for the answer? I can't see any other way of accomplishing it unless, as Sven said, the list is constructed in reverse.

Of course, there's wlays the possibility that they are wrong! Never assume your interviewer knows more than you do (and I should know I've been an interviewer!).

I would write to them and ask for the correct answer.  If they don't respond then they're probably not the kind of people you would want to work for anyway ...

Herbie

Maybe the point of the question was to get you to question their correction.  Sometimes people are too easy to submit to authority.

joechung said:

Maybe the point of the question was to get you to question their correction.  Sometimes people are too easy to submit to authority.

It was a test that was emailed in and they then said I was unsuccessful in application. I then queried as to why this was and received this answer this morning.

Sadly even through looks as if I answered this question was correct I got another wrong. To have answered the other correctly I would have needed a knowledge of geometry which for a general programming job is a strange ask?

Dont get me wrong I agree with the principal of technical tests to weed applicants out but suggest they should not depend on other knowledge to answer correctly and should be focussed on programming skills.

Terms such as head and tail can be confusing. It depends which direction you consider the links to point (towards the tail or towards the head). The terms Start and End are better because they imply directionality more clearly.

There's little point keeping pointers to both the start and end of a singularly linked list except to get to the last item quickly (for instance to add an item to the end of the chain).

A pointer to the Start item will give you access to that item and along the chain to all the others. A pointer to the End item end will only give you access to that one item. It has no pointer back up the chain, because this a singularly linked list, so you can't go to that end of the chain and count back five items.

Simon Jones
Contributing Editor
PC Pro Magazine

SimonJ said:

Terms such as head and tail can be confusing. It depends which direction you consider the links to point (towards the tail or towards the head). The terms Start and End are better because they imply directionality more clearly.

There's little point keeping pointers to both the start and end of a singularly linked list except to get to the last item quickly (for instance to add an item to the end of the chain).

A pointer to the Start item will give you access to that item and along the chain to all the others. A pointer to the End item end will only give you access to that one item. It has no pointer back up the chain, because this a singularly linked list, so you can't go to that end of the chain and count back five items.

Simon Jones
Contributing Editor
PC Pro Magazine

Perhaps they are trying to differentiate between use of a linear and circular linked list ?

With a linear list, you point to the start, which points to the next, etc etc, and the end points to null.

With a circular list, the end points to the start, which points to the next, etc etc... hence by pointing to the end, you often have a faster solution.

Pointing to the end of a circular linked list can be more efficient if adding to a large list.

There are obviously many solutions to your problem. If linked list has its length (n) written in its head then solution is easy, you just walk till you hit (n-4)th element. Otherwise there are two more solutions if you are looking for last m elements in n element list. If n is big maybe you don't want to walk it twice and you use array with (m-1) elements and you just fill it as you walk from head till you get to the tail (rewriting array every (m-1) steps). If n is small (or n is not much bigger than m) then allocating (m-1)-sized array and then filling it with values is not so optimal, so you want to walk it twice, first to get n and then to get to the (n-m+1)th element.

Then, maybe your solution was right and the email you received was a trick. If boss says you to do something wrong and you do it then this is not good for the company. Maybe they are testing if you are a yes-man, and so every candidate that did not complain to this email would not get the job.

RoyalSchrubber said:

There are obviously many solutions to your problem. If linked list has its length (n) written in its head then solution is easy, you just walk till you hit (n-4)th element. Otherwise there are two more solutions if you are looking for last m elements in n element list. If n is big maybe you don't want to walk it twice and you use array with (m-1) elements and you just fill it as you walk from head till you get to the tail (rewriting array every (m-1) steps). If n is small (or n is not much bigger than m) then allocating (m-1)-sized array and then filling it with values is not so optimal, so you want to walk it twice, first to get n and then to get to the (n-m+1)th element.

Then, maybe your solution was right and the email you received was a trick. If boss says you to do something wrong and you do it then this is not good for the company. Maybe they are testing if you are a yes-man, and so every candidate that did not complain to this email would not get the job.

But often you don't know (and shouldn't assume you know) the length of the Linked List.

repost

blowdart said:

Sven Groot said:

*snip*

Which can make for an awkward date.

Well if you either get head or tail, it's usually considered a pretty successful date overall.

AndyC said:

blowdart said:

*snip*

Well if you either get head or tail, it's usually considered a pretty successful date overall.

I cant make head or tail of it.. (sorry)

Thanks for the replies guys. I agree the head/tail terms can be a bit confusing. The solution I implemented was as RoyalSchrubber suggests to just walk till you hit (n-4)th element. I have sent an email querying this as dont want them failing anyone else on this who bothers to read the question properly.