Technical Test - singular linked list | The Coffeehouse

alexmac

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

Sven Groot
My name has 9 letters. Coincidence? I think not...

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?

alexmac

In reply to Sven Groot

#May 22nd @ 1:09 AM

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.

Sven Groot
My name has 9 letters. Coincidence? I think not...

In reply to alexmac

#May 22nd @ 1:15 AM

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

alexmac

In reply to Sven Groot

#May 22nd @ 1:22 AM

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!

AndyC

In reply to alexmac

#May 22nd @ 1:33 AM

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.

Sven Groot
My name has 9 letters. Coincidence? I think not...

In reply to alexmac

#May 22nd @ 1:33 AM

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

Dr Herbie
Horses for courses

In reply to AndyC

#May 22nd @ 1:49 AM

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

joechung

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

alexmac

In reply to joechung

#May 22nd @ 2:09 AM

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.

SimonJ

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

blowdart
Peek-a-boo

In reply to Sven Groot

#May 22nd @ 1:54 AM

Which can make for an awkward date.

elmer
I'm on my very last life.

In reply to SimonJ

#May 22nd @ 2:19 AM

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.

RoyalSchrubber
One. How many time travellers does it take to change a lightbulb?

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.

ManipUni
Proving QQ for 5 years!

In reply to RoyalSchrubber

#May 22nd @ 2:30 PM

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

ManipUni
Proving QQ for 5 years!

repost

AndyC

In reply to blowdart

#May 22nd @ 2:23 AM

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

alexmac

In reply to AndyC

#May 22nd @ 3:01 PM

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.

figuerres
???

In reply to alexmac

#May 23rd @ 12:53 AM

perhaps also point them to the topic hear so they see what other folks say... might help them see why you are asking them etc..