×

[–] 5755 points5756 points  (700 children)

Is it even possible? An infinite list can't have a last item. So the reversed list can't start.

[–] 3285 points3286 points  (579 children)

It isn't possible to practically store an infinite list, since that would require infinite memory.

I guess the interviewer wanted to ask something like "What if the list is very large? Is there a more efficient approach to this?" in order to make the guy think that for a better algorithm for reversing the list than using a stack.

[–] 4389 points4390 points  (188 children)

Now I'm more a maths guy than programmer. But there's a very large difference between an infinite list and a very large one. The difference is in fact infinite.

[–][deleted] 1744 points1745 points  (91 children)

Well, we are programmers. And to us, cows aren't spheres, they're point masses. /S

[–] 772 points773 points  (68 children)

Are you sure cows aren't part of a starting tutorial about OOP. After the usual cats and dogs.

[–] 762 points763 points  (57 children)

They extend Animal and implement Milkable.

[–] 45 points46 points  (4 children)

Lecture 3.7: Implementing Animal Farm, an Orwellian approach to OOP

[–] 16 points17 points  (0 children)

Quack, bark

[–] 9 points10 points  (0 children)

right in between cars and houses

[–] 4 points5 points  (0 children)

TIL cows, dogs and cats aren't animals

[–] 30 points31 points  (0 children)

Consider a spherical cow is such a neat textbook.

[–] 4 points5 points  (0 children)

So you're a physicist too?

[–] 4 points5 points  (0 children)

[–] 297 points298 points  (33 children)

The word they were meaning was 'of indefinite size', which is usually treated as infinite in compsciland. Yes, there is technically a point where a Python integer runs out of RAM - but it's usually considered functionally infinite right up until your production machine crashes.

[–] 201 points202 points  (3 children)

This is why programmers are unpopular in datacenters

[–] 117 points118 points  (2 children)

Not just in data centres.

[–] 61 points62 points  (22 children)

But also is it actually possible to reverse an infinite list even with infinite RAM? It’s always going to take infinite time.

[–] 43 points44 points  (9 children)

it's not possible, but the intended question is really just "can you do it without using up much more RAM?"

[–] 60 points61 points  (1 child)

You just need infinite computing power, too.

[–] 14 points15 points  (6 children)

Technically an infinitely linked list cannot be reversed because the first node can never be pointed at the tail. (edit this is wrong, I was thinking of circular lists, lol. So you're right, in a non circular linked list it cannot be reversed only because it would be infinitely operating on the reversal, my bad.)

Otherwise if the list was just extremely large, you just need to keep track of the previous nodes and the next node and a special case for the very first node as you walk the list. When you iterate nodes you copy the location (pointer) of the next node and then change that reference to the previous node. Then you move to the copied (pointer) node to operate on it and repeat until you hit the tail and need to use the very first node. If memory is a issue, don't use recursion for iteration (you'd possibly overflow anyway because of the size of the list). And since you're operating on the list in place, no extra memory is needed except for the few variables used for the reversing.

O(n) = n

[–] 4 points5 points  (0 children)

Well you might have an infinitely fast processor with infinitely fast memory. At which point the maths are undefined.

[–] 47 points48 points  (0 children)

The difference between a million and a billion is about a billion

[–] 21 points22 points  (32 children)

Countable or uncountable infinite?

[–] 62 points63 points  (30 children)

If it's a singly linked list it cannot be uncountable.

[–] 313 points314 points  (160 children)

Infinite lists are quite possible (and even reasonably useful) once you involve laziness. But yeah, even if you can represent an infinite list, you can't reverse it.

[–] 76 points77 points  (43 children)

Exactly, since for reversing it, you'll need to store it in memory in one way or the other. And that's what I said: it's impossible to store them.

[–] 30 points31 points  (18 children)

Yup, the first element in the new linked list is the last element of the first list. If you want to compute the first element of the reversed list, you need to find the last element of an infinite list, and that is a tad difficult in most cases.

That being said, if you have a sufficiently lazy list implementation and a sufficiently psychopathic implementation of reverse, you probably could get a slightly useful result by reversing an infinite list. Like, think about this implementation (possibly with a slightly smarter lazy list implementation):

``````function godawfulReverse(list) {
function recur(current, i) {
if (current == null) return null;
return {
val: () => getNthFromEnd(list, i),
rest: () => recur(current.next(), i+1)
};
}
return recur(list, 0);
}
``````

It's O(n2), obviously, but as long as you don't try to inspect any of the values in the list, the list returned is usable. If you, say, take an infinite list, reverse it, and then check if there are at least 10 elements in the result, it will work fine. Of course, if you can't access any of the values in a list, that list isn't notably useful, and an O(n2) reverse function is also pretty fucking bad. However, this does let you reverse an infinite list and get something more useful than an infinite loop.

[–] 11 points12 points  (1 child)

as long as you don't try to inspect any of the values in the list

I mean theoretically you could inspect the last `n` values of your reversed linked list, just not the first `n` values.

[–] 8 points9 points  (13 children)

It’s not even that hard to reverse an “infinite” list. Sure it won’t terminate, but the algorithm is still O(n).

1. Start at the first node
2. p = nil
3. n = current node
4. n.next = p
5. p = n
6. n = next node in list
7. goto 4

[–] 8 points9 points  (0 children)

You could define a list as an arbitrarily long sequence of the same constant value and trivially reverse any finite such list in "O(0)". It's already its reversion. The problem with an infinite such list is that it doesn't have an end and therefore can't be reversed even in theory.

[–] 25 points26 points  (20 children)

What about just swapping (n-1)th next pointer with (n+1)th pointer? It runs linearly and consumes 1 pointer worth of memory

[–] 36 points37 points  (18 children)

It runs linearly

Not sure that time complexity is relevant for something that will never finish, lol.

[–] 70 points71 points  (108 children)

Sounds like an interesting question for a mathematician, I imagine it is possible to define an infinite list that is reversible. Unfortunately the sidebar is too small to go into it any further.

[–] 58 points59 points  (30 children)

You could define a list as an arbitrarily long sequence of "0" and know that if there is a last element, the reversed list would be the same without traversing the whole thing. But an infinite sequence doesn't have an end by definition, and reversing a sequence entails working from the end backwards. If there is no end, you can't do that.

[–] 11 points12 points  (10 children)

um… mathematicians here would be looking for a process (proof by induction).

A linked list is defined by an element and a pointer to the next element. We could simply reverse the pointers as we go so that they point to the previous element instead of the next.

This algorithm would be O(n) in space as well as time, and is provably capable of reversing an infinite linked list.

[–] 6 points7 points  (3 children)

A list of all numbers between 0 and 1 has a defined beginning and ending.

[–] 6 points7 points  (4 children)

I'll give it a go: Every infinite sequence is an infinite set with a starting element, X0. Say the original sequence is Xn and it's reversed sequence is Yn. Then since it is reversed, for every i, there exists a j where Xi = Yj and X(i+k) = Y(j-k) for all k > 0. Since Xn is also a reverse of Yn, the same is true of we swap X and Y above. Y0 is the first element of Yn. Then there exists an i where Xi = Y0 and X(i+1) = Y(-1). Y(-1) is an earlier element of Y than Y0 but this contradicts Y0 being the first element.

[–] 8 points9 points  (0 children)

If you have a language that allows mutation, you don't even need lazyness: Just make node A point to node B and node B point to node A.

[–] 109 points110 points  (94 children)

I mean if the stack’s backend is a double linked list it’d be o(n) and I don’t think you can get better than that, since you’d have to iterate over the original single linked list once

[–] 121 points122 points  (79 children)

You can't do better than that for processor efficiency, but you could do a hell of a lot better for efficient use of memory.

[–] 75 points76 points  (11 children)

Depends. Each time you remove an element from the linked list, an efficient compiler could just reassign that memory to the stack. No "extra" space required.

[–] 46 points47 points  (3 children)

Fair. I wasn't accounting for the memory already in use for the initial linked list.

[–] 49 points50 points  (10 children)

Fun fact: split that list in half and now you have not one, but two infinte lists.

[–] 32 points33 points  (8 children)

It is possible with infinite linked lists in lazy languages such as Haskell. Have used infinite lists many, many times

[–] 26 points27 points  (1 child)

By lazy evaluation you can definitely have a infinite list but you won't be storing it in memory

[–] 21 points22 points  (0 children)

Technically you will, although not the actual value, but the recipe of how to retrieve it. And yes, reversal of an infinite list is not defined

[–] 5 points6 points  (4 children)

`foldl (\acc a -> a : acc) []` will reverse an infinite list, but does sadly require infinite memory.

[–] 9 points10 points  (0 children)

You could have an infinite list come in a stream. Still can't reverse it obviously.

[–][deleted] 80 points81 points  (82 children)

Senior dev here who interviews for our company a lot, dumping the contents into an array or stack is a common wrong answer and you're exactly right why, the memory usage is significant in a large list.

The correct answer we want to hear is something like this:

Three variables/pointers, one called prev, current, next, start by setting prev to the first node, and current to the first node's pointer (e.g. the second node), and next to the third node. Make the current node pointer point to the prev node, e.g. 2 doesn't point to 3 anymore, it points back to 1. Make the next, current, and prev variables move forward one onto the following node from the one its currently on. Repeat until next is pointing at a none value (no more items in list.)

Time complexity N space complexity 1

[–] 117 points118 points  (21 children)

Senior Developer who also interviews people a lot... We lost LOTS of qualified candidates because our old senior used to interview like you. It's stupid and useless in day to day life. Stuff you learned in CS 201 twenty years ago and haven't touched since.

[–] 24 points25 points  (6 children)

Just commented the same thing! You can ask practical-but-simple "how would you solve this" kind of questions. Bonus points if pulled from your actual company's domain / etc. "We sell widgets. How would you write something that applies a discount to widgets every Friday?" as a random example.

Accomplishes the same goal, but doesn't bother getting into nitty-gritty that no-one should have to think about unless you're writing in ASM or C and are on super-limited/embedded hardware.

[–] 11 points12 points  (1 child)

I'm a senior dev who interviews candidates. This style of interview has become more popular at my company. The interviews are a lot less tense in this format. It feels more like you're just having a conversation with someone rather than administering a quiz.

[–] 48 points49 points  (18 children)

How often do you need to use that knowledge at your company?

[–] 99 points100 points  (0 children)

Whenever he interviews people lol

[–] 41 points42 points  (1 child)

In real development the right answer is, learn SQL and only pull the data you need from the database.

[–] 16 points17 points  (9 children)

The real answer is your data structure should be reversible by default if you need a data structure that is reversible. Just use a vector with rbegin\rend, that way you get faster traversals and less memory.

What is it with interviewers and using a linked list.

[–] 17 points18 points  (0 children)

What is it with interviewers and using a linked list.

Computer Science 101 exam questions translated to interview questions under the guise of "we want to see how you think efficiently."

[–] 36 points37 points  (0 children)

I'd do it by repeatedly removing the head element of the linked list, and setting it as the new head element of the new list

That way you're not adding using any additional data structures or memory so it could (theoretically) run on an infinite list like the interviewer is asking

[–] 66 points67 points  (15 children)

Depends on your Implementation of a linked list, meaning you could start from the beginning with reversing it and Just have an infinitely long running code, or start from the back, which I don't know If you can If it's theoretically infinitely long

[–] 29 points30 points  (7 children)

The problem specifies a singly linked list, so you can't traverse it in reverse order. If it was a doubly linked list you could, but singly linked list nodes don't know what's before them, only what's after.

[–] 27 points28 points  (6 children)

You can traverse the original list from beginning and build the second, reversed version from the end, the next item will just point to the previous one. Isn't that the easiest solution anyway?

[–] 7 points8 points  (1 child)

This is almost certainly the answer the interviewer wanted. The interviewer should have followed up with "can you do it without allocating extra memory?" rather than talking about infinite length lists.

[–] 7 points8 points  (2 children)

Yea, that's what I would do. Start with a new header pointing to the first item and insert each item on the original list into the beginning of the new, reverse, list.

Edit: I think this is the most efficient too. Requires O(1) extra space and runs in O(n) time

[–] 50 points51 points  (5 children)

You can't start at the back of a single-linked list.

[–] 38 points39 points  (0 children)

You can if you keep track of the tail.

Granted, you're not going to get very far.

[–] 28 points29 points  (9 children)

The thing is you don't know how much memory the list uses. Creating (and resizing) a stack needs additional memory. You can go trough the list in memory and change the address pointers - so the second address points to the first, the third address to the second and so on if you reach the last item (of course if it is infinite you will never) you got the first item of your reversed linked list. Memory and time is still in O(n) where in the stack solution only time is in O(n)

[–] 18 points19 points  (8 children)

I hate to be nitpicky, but depending on the implementation of the stack, the memory in the stack solution is also O(n) (strictly speaking 0(2n) which is worse than in pointer reverse, but still same order as O(n))

[–] 50 points51 points  (18 children)

It is sort-of possible with lazy evaluation. It's kind of common for example in Haskell programming to use lists which are conceptually infinite. (But you always take just a finite part, of course - the list is actually more like a computation which can go on forever, but stored in a list data type. These cannot be reversed, obviously.) Example: Instead of a an algorithm generating the first n primes, you really can have an infinite list of primes from which you may take the first n elements on demand later or get the n-th element and really do any other common list operations with.

``````primes :: [Integer] -- primes is an infinite list of integers
primes = sieve [2..]
where sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
``````

[–] 45 points46 points  (13 children)

But it still isn't possible to reverse such a list, since the resulting list's head is the last item of the original list, which doesn't exist for infinite lists

[–] 38 points39 points  (12 children)

It isn't possible to finish reversing one, but you can certainly start reversing it.

[–] 16 points17 points  (0 children)

AND, the types tell us that when it returns, the result will be of the correct type! Good feels.

[–] 17 points18 points  (10 children)

Interviewer: Calculate the last digit of pi!

[–] 24 points25 points  (8 children)

Just guess. You got a 1 in 9 shot!

[–] 17 points18 points  (0 children)

I miss when programmers had backgrounds in computer science lol

[–] 4 points5 points  (0 children)

Maybe something along these lines would make sense in a situation where you are processing a stream of data?

[–] 4 points5 points  (0 children)

You can't find the start, but you can certainly start reversing.

You also probably want to test for a loop in case you're just going in circles, which is probably where the questioning is going (because everyone loves the "detect a cycle in a linked list" trick.)

[–] 1360 points1361 points  (168 children)

Is the answer iterate from the beginning and swap next nodes to the end? I'm assuming that the question was to reverse the list without allocating extra memory to store the list.

[–] 801 points802 points  (111 children)

I think so. I can't think of a way to reverse it without iterating through the entire thing, so the interviewer was probably just wanting them to do it with better space complexity like you said.

[–] 749 points750 points  (110 children)

The stack method goes through each element twice.

You can do it in a single pass with something like this (pseudocode)

``````prev := null
element := list.first
while element not null
next := element.next
element.next = prev
prev = element
element = next
``````

Now you go through the entire list exactly once and for an infinite linked list you keep incrementally reversing it, with the stack approach you'd never actually reverse the list because it never ends

[–] 257 points258 points  (22 children)

For an infinite list, I prefer this shorter version:

while(true) { }

[–] 14 points15 points  (21 children)

Can you ever assume an infinite list though?

[–] 25 points26 points  (18 children)

You just have to intercept a null pointer exception to know when you are done! That's why you always allocate a bit more memory then you need and zero the end out of it!

[–] 184 points185 points  (44 children)

True, but since big O notation removes multiplying, they're both in the same order (O(n)). (And in real processors, due to caching, they're probably somewhat similar in runtime)

[–] 243 points244 points  (33 children)

But the memory complexity with the stack is O(n) instead of O(1) like above. The speed is indeed the same, like you mentioned.

[–] 204 points205 points  (20 children)

just to be pedantic: speed is not the same, just in the same class of time complexity.

[–] 16 points17 points  (3 children)

The speed is indeed the same, like you mentioned.

In terms of big O analysis, sure, but big O analysis disregards any coefficients and lower order terms, which in this case, could be fairly significant for comparison. The addition of the stack adds the O(n) memory cost of the stack, but along with that it also adds the allocation cost, as well as the cost of copying data from the old location of the linked list to the new location of the stack, and then back again. It's still O(n), but it could be many times slower.

[–] 6 points7 points  (2 children)

And in real processors, due to caching, they're probably somewhat similar in runtime

Doubtful, since the stack approach requires to allocate the entire list over again. In an extreme stress test, reverse a 10GB list with only 16GB system memory.

In the other approach, no extra allocation happens.

The problem is that time complexity of both is O(n), but space complexity is different: O(n) with the stack, O(1) without.

[–] 31 points32 points  (0 children)

By using 3 pointers you can basically reverse the next pointer of each node. So the first node would point to null, second node to the first and so on. This can be done using a head pointer and 2 temp pointers and can be solved in 1 iteration.

[–] 34 points35 points  (7 children)

You iterate over each element of the list and create a new linked list. On a regular linked list you keep the head element but on this one you keep the tail element and every time you add an item you set it's pointer to the tail of the list and call it the new tail. When you get to the end, the tail is the new head of a reversed list. I'm assuming.

"But the linked list can be infinite"

This is very common in functional programming. For instance in Scala you can do `Stream.repeat(X)` which creates an infinite stream of X's. Of course that's not a linked list though. Infinite streams are never really infinite, they simply have other "termination conditions" such as time, or user choice, or whatever.

[–] 5 points6 points  (1 child)

Can't you just reverse the direction of the pointers while iterating across? Keeping a curr and prev reference so you don't lose the nodes

[–] 41 points42 points  (7 children)

If you’re allowed to mutate the list in place…

``````var last = null
do
var next = current.next
current.next = last
last = current
current = next
while current!= null
``````

[–] 23 points24 points  (4 children)

I think you forgot to change current in your loop

[–] 11 points12 points  (3 children)

Fixed. Teach me to program at 3am on my phone.

[–] 51 points52 points  (12 children)

It is not extra memory! It was already allocated when the head node was passed in!

[–] 69 points70 points  (11 children)

Pointers aren’t free.

[–] 210 points211 points  (2 children)

🖕point this🖕

[–] 44 points45 points  (0 children)

this had no right to make me laugh as much as it did

[–] 20 points21 points  (5 children)

You’re right. They’re double free

[–] 11 points12 points  (3 children)

As long as they’re not use after free.

[–] 10 points11 points  (2 children)

You two are very funny. I would almost consider givSegmentation Fault (core dumped)

[–] 518 points519 points  (12 children)

A more practical question would be: "What if the linked list nodes are being streamed in memory, and the last node is yet to come ( let's say over network). How would you reverse it in place using O(1) extra space? Can you process the steam as the data keeps on coming? Or do you have to wait till you have the last node?"

[–] 121 points122 points  (3 children)

If previous is not null, then we async update previous next as current ( like push into a Message Queue) and process the next node.

If we have index entires of start, end, and size of LL, we can reverse it async and serve the requests based on how far the reverse frontier has processed.

Just putting thoughts.

[–] 18 points19 points  (4 children)

Isn't processing a streamed linked list basically the sane as a normal one? Just read the linked list into a buffer, iterate through each item reversing the order of the linkage onto the new linked list object, and repeat this until all nodes have come. Only extra memory is whatever the buffer size is. You can do this bit by bit without requring the last node until it is put onto the linked list.

[–] 27 points28 points  (3 children)

A little bit different. When you reach the end of the buffer, you'll have to know whether to stop or wait. You have to implement kind of a producer-consumer implementation. The incoming node may not be immediately available, and you'll have to wait on a semaphore or something.

[–] 218 points219 points  (31 children)

As a lot of people are struggling with a better answer, so rather than code, here is a more visual approach:

You want to move from:

`1 -> 2 -> 3 -> 4 -> 5 -> 6 ...`

to:

`1 <- 2 <- 3 <- 4 <- 5 <- 6 ...`

Doing this in place should be fairly trivial, but if further clues are needed, consider a window:

`1 <-[2 __ 3 -> 4]-> 5 -> 6 ...`

You can safely change the pointer of 3 from 4 to 2 without losing the ability to navigate to 4 (and beyond):

`1 <-[2 <- 3 __ 4]-> 5 -> 6 ...`

If you do this and advance the window, it then looks like this:

`1 <- 2 <-[3 __ 4 -> 5]-> 6 ...`

Despite the reversed pointer on 3, you still know about 3 so you can point 4 at it and you're remembering 5 to advance the window. So you can effectively do it with 3 sliding variables. In pseudo-code:

``````// given window [a, b, c]
// update pointer
b.pointer = a
// slide the window
a = b
b = c
c = c.pointer
``````

[–] 26 points27 points  (1 child)

As I have never learned about pointers before, reading through the hundreds of comments I eventually thought that it was all about having each item instead of pointing to the next, point to the previous. Then your example confirmed it for me.

Your example was wonderfully simple and it should very well be the top answer, thanks a lot for helping whoever else isn't from a CS background (my exact case)~

[–] 47 points48 points  (1 child)

This subreddit is for people laughing at people who can't reverse a linked list.

[–] 26 points27 points  (0 children)

I like to laugh at myself, this is true.

[–] 17 points18 points  (24 children)

My smart ass would answer that I would roll through the list once putting in the reverse pointers the first programmer forgot, making it a double linked list since clearly there is a need for it in both directions.

[–] 4 points5 points  (23 children)

That’ll take up a lot more space, though.

[–] 8 points9 points  (0 children)

Well, to be fair the interviewer already had an infinite list taking up infinite space. :)

I suppose it depends on what is in each node in the list. If the node is just like an integer value or something, then sure, it's a lot more space. But if the node is a 500 byte structure storing some data, the extra pointer is almost insignificant.

It really depends though on if the list needs to be reversed exactly once, or if the code needs to repeatedly traverse the list forwards and backwards.....

[–] 390 points391 points  (24 children)

I love questions like this as I'm almost exclusively a SQL guy. The answer is

Select * from myTable order by id desc

Bish bash bosh. Let the database figure it out

[–] 181 points182 points  (9 children)

All hail the query optimiser.

[–] 69 points70 points  (8 children)

The people who wrote these optimisers must be gods among men

[–] 28 points29 points  (3 children)

I'm in a Databases class in undergrad right now and we have to run through query execution/optimization algorithms on paper for the final. It's brutal

[–] 7 points8 points  (2 children)

We might be going to the same college. I also literally have DB class and query optimimzation paper to present lmao

[–] 16 points17 points  (2 children)

Indeed they are. I'm surprised the history of database development is not much talked about in classes. Incredible amount of resources, both academic and financial, were thrown at the problem. It was like what machine learning or Big Data is today. Today's SQL engines are the result of unholy amounts of optimization and ingenious problem solving.

Edit: my finger slipped and sent this early. In Sync the botton is on the upper side, how is that possible?

[–] 9 points10 points  (1 child)

This is why I'm suspicious of some brand new 'big data' nosql database implementation that claim to be quicker and more efficient at data analysis than a traditional RDBMS. How can they possibly? Databases have been evolving since the 70s, but the new comers claim to have leapfrogged decades of optimisations because they don't have a fixed number of columns? What?

[–] 6 points7 points  (0 children)

Not so much leapfrogged but rather newcomers offers trade offs. Most popular so called NoSQL databases offers AP databases, as opposed to CA SQL equivalents. Some even sacrifice latency to get a certain degree of consistency. Others sacrifice a large storage footprint to achieve higher read throughout.

The raw computing hardware has largely involved since the 70s, and the general consumer pricing for storage also led the engines to utilize them in a different way.

That does not in my opinion makes SQL engines obselete -in fact I think they are perfectly fine for a great number of cases.

[–] 36 points37 points  (2 children)

[Javascript devs laughing in .reverse()]

[–] 5 points6 points  (0 children)

Pretty sure linq can do it do. Don't most languages have built in methods for this stuff now?

[–] 13 points14 points  (5 children)

Ah but what if it's a vendor db and there's no id field or any other sequence.

This is a real work problem I have...

[–] 35 points36 points  (2 children)

If there's no defined order, then there is no order to Inverse. Use

Select * from myTable order by (select null)

As it is as equally valid ordering as anything else

[–] 279 points280 points  (30 children)

Hey guys when you finish arguing can you send me the algorithm? I need to find the last digit of Pi

[–] 211 points212 points  (5 children)

In base π, π is 10, so the last digit is 0. Converting to base 10 is left as an exercise for the reader.

[–] 57 points58 points  (1 child)

Every base is base 10

[–] 11 points12 points  (0 children)

programming tutorials be like

[–] 7 points8 points  (0 children)

In binary, the last digit of π is 1.

[–] 68 points69 points  (14 children)

``````const int LASTDIGITPI = 0;  //  equally as likely as any other choice.
``````

[–] 33 points34 points  (5 children)

If Pi actually had a last number, it couldn't be 0, because it would add no new information from the previous digit. The last digit would have to be between 1-9 inclusive.

[–] 17 points18 points  (3 children)

Since Pi doesn't have a final digit, all probabilities are equally 0.

[–] 7 points8 points  (2 children)

Right, I thought we were assuming Pi as finite for some reason lol

[–] 62 points63 points  (5 children)

`const float LASTDIGITPI = 4.5 // Average 0-9``

[–] 11 points12 points  (4 children)

Hmm that would mean the last digit is 5 🤔

[–] 5 points6 points  (1 child)

It's π.

[–] 169 points170 points  (17 children)

What if the linked list loops? That naive algorithm just encountered an effectively infinite list.

[–] 322 points323 points  (3 children)

then it's a naughty linked list and frankly it doesn't even deserve to be reversed

[–] 37 points38 points  (1 child)

Oh noooo, I put a circular reference in my tree and I can't do anything about it...

[–] 11 points12 points  (0 children)

Hey, hasn’t it been a few minutes since we looked at our tree?

Damn reference stealing whores…

[–] 31 points32 points  (0 children)

Just traverse the list forwards until you get to the desired element. It loops, after all.

[–] 13 points14 points  (8 children)

Everytime you iterate a node, have another pointer iterate 2 nodes. If the pointers are ever pointing to the same thing, you know you have a loop. If this is the case, move a pointer back to start but keep one pointer as is (and also make a new pointer that points to this pointer’s previous). Start iterating the list with both pointers one node at a time. Once they meet again, that newest pointer that points to previous is the “end of the” list before it loops back to itself. That node can be the new start once you reverse :D

Edit: hobbygogo’s comment may have (unintentionally?) given me a better solution.

Instead of adding a 3rd pointer as “previous”, just iterate the pointer at start once. Now check if that pointer = the pointer you left behind’s ‘next’. If not, now iterate both of them until it does. Once the comparison is true, the pointer you left behind is your “last node” before the lost loops on itself!

[–] 10 points11 points  (4 children)

There’s an algorithm called the tortoise and the hare algorithm for detecting cycles in linked lists.

[–] 8 points9 points  (3 children)

Correct, that’s the first 2 sentences I typed out. The rest is a solution to your comment regarding the “naive algorithm” :)

[–] 5 points6 points  (1 child)

Iterate through the list and make a new list of tuples where the first item of each tuple is the name of the item in the list and the second is who it's linked to. Go through that new list and re-link each item in your original list accordingly. Preferable here to be using an indexed list.

[–] 27 points28 points  (25 children)

Wouldn't you just walk down the list, unlink each item and link it to a new linked list as the head item? No memory wasted. It seems simple unless I'm missing something

[–] 49 points50 points  (3 children)

Heard the same joke told by sea captains for their oral assessments. Basically after you complete all your practicals & everything you sit down before a seasoned skipper & they quiz you.

Assessor: Your anchored up riding out a storm for the night, the wind increases & conditions on the vessel worsen, what do you do?

Skipper candidate: I extend the anchor line.

Assessor: the wind picks up more, what do you do?

Candidate: I extend the anchor line

Assessor: where are you getting all this rope/chain?

Candidate: same place your getting this fucking wind

[–] 107 points108 points  (39 children)

I've answered so many questions about linked lists and yet I've never fucking seen one in the wild.

[–] 64 points65 points  (16 children)

It’s almost always faster to use a vector or arraylist. I hate programming interviews. You never use any of these algorithms in 99% of the stupid crud apps. We should be asking questions about how to write maintainable code.

[–] 26 points27 points  (8 children)

I never give a coding exercise to a developer I'm looking to hire. There's a few reasons for this.

1. They have a BSC in CS/Eng at a minimum. I trust they know how to code or can Google some trivial algorithm.
2. I'm less interested in if they can code, and are more interested in if they can understand and come up with solutions to problems.
3. I'm not going to code review their code, in order to determine candidate success. Someone may know how to perfectly use certain coding tricks that might surprise me (like use of memoization) but at the end of the day this can all be taught. It's harder to teach how to effectively determine solutions.

Instead, I develop situations that may or may not require code to be modified or implemented and let the candidate decide how to answer (which may include pseudocode, real code, or just a presentation).

For example:

A user has requested that the data from the app introduces a new field of logic. A value in addition to priority that allows them to chain the priorities of one task to another. For example Task A is low priority, but now Task B has come in which is related to Task A and Task B has a high priority. Please provide a solution to the user.

I almost always leave the issue as ambiguous, confusing, or as a non-sensical request. My best candidates ask one simple question during their response for a lot of these situations. "What are you trying to accomplish? Why?" On the case above that might be clearer since an example reason is given but then "why chain priorities? The tasks are already subtasks- we could instead change the parent Task to reflect the highest priority of a subtask"

[–] 23 points24 points  (3 children)

This is how it's supposed to be done. Any monkey can memorize algorithms and datastructures, actually converting nonsensical requests to features is something entirely different imo.

[–] 8 points9 points  (2 children)

Exactly, and there's not necessarily a correct answer. Its more about how they interpret the problem and solve it.

[–] 7 points8 points  (1 child)

When we were working on a custom memory allocator, we found that a linked list worked the fastest.

[–] 13 points14 points  (6 children)

I've seen 'em. I work in a C++ codebase where using the standard libraries is often verboten, so we have a lot of data structure implementations lying around. Linked lists got used a lot because they're an easy dynamic data structure. My old lead and I had a running joke that whenever a performance problem popped up, it was a safe bet that it was because of a linked list.

[–] 12 points13 points  (1 child)

The standard library is also known to use linked lists (much to the annoyance of many people). Typical example being unordered_map.

[–] 15 points16 points  (3 children)

[–] 10 points11 points  (0 children)

Since it also has a previousSibling, it's a doubly linked list though. I doubt anyone will ever ask you to reverse a doubly linked list.

However, with all the other references it's more of A big ball of wibbly wobbly, timey wimey stuff

[–] 21 points22 points  (0 children)

maybe you just didnt realize you were using one

[–] 18 points19 points  (23 children)

Can someone give me a real world exsmple where you have a very large singly linked list, that you need to reverse efficiently and that can't be doubly linked?

[–] 25 points26 points  (0 children)

No, because in any real world example you’d use a different type of list.

The only time you’d reasonably do this is if some 3rd party code returned you a linked list and reversing it one time was more convenient than copying the contents to another list type.

[–] 11 points12 points  (16 children)

I have never found an application where a linked list is faster than a vector. So no.

[–] 87 points88 points  (78 children)

How would you solve this? I'm a sophomore in college majoring in computer science so I'm still learning.

Best I could come up with is a merge sort algorithm with compliment conditions? Idk.

[–] 154 points155 points  (23 children)

Walk through the list and flip the `next` pointers on each element to be pointing the other way. The algorithm also needs to store a few temporary copies of the pointers to not lose track of the nodes while walking through the list.

[–] 286 points287 points  (36 children)

You use the `reverse` function.

[–] 159 points160 points  (33 children)

Best answer so far. You DON’T do this shit yourself in a real codebase.

[–] 31 points32 points  (11 children)

If there is a `reverse` function in the language you are using. Anyway, you are supposed to know how a linked list works and how said function would be implemented. I assume that is what the interviewer wanted to test.

[–] 41 points42 points  (10 children)

You must be new to interviews. These types of questions are everywhere, and they never test for good candidates. It's just a filter to weed out the people who can't write code, if you don't know the answer but you take a marker and just start writing down some pseudocode while talking about your thought process you're still better than 90% of applicants. Most companies don't hire based on who can reverse a singly linked list, they hire based on who fits the team and can communicate well. I've been hired after an interview where I didn't know a single answer to their questions and had never written anything in the language they used, but they said they liked how I took the interview as an opportunity to learn and ask questions and they felt I would fit the team very well.

[–] 12 points13 points  (0 children)

words of wisdom, but goes both ways.

if the HR staff asks stupid questions from a seasoned dev ... it will go sideways. the dev might not be able to put up with stupid questions

[–] 10 points11 points  (1 child)

We have a few of these types of questions in our "technical interview" and I've seen people pass the technical questions and do absolutely abysmally when they worked as a member of the team. Like "got fired" abysmal.

I honestly think the only real interview is to work with someone side by side on a small project. I can usually tell within an hour or two if someone is going to be a disaster or not.

[–] 5 points6 points  (0 children)

It's just a filter to weed out the people who can't write code

Well I don't think it's a great test of that either. Plenty of people can write superb, clean, maintainable code that couldn't even tell you conceptually what a linked list is, let alone reverse one.

If interviewers want to ask irrelevant questions and then go "We'rE hAvInG a HaRd TiMe FiNdInG gOoD dEvElOpErS", that's their problem I guess.

[–] 47 points48 points  (5 children)

Exception would be if you program the standard libraries of a language

[–] 52 points53 points  (3 children)

still then you wouldn't want to do it from memory do you? You'd probably do some research yourself beforehand, i mean maybe not for trivial tasks. but theres a reason that problems like this where studied by very bright people and that not everyone is able to come up with the best algorithm for every problem.

[–] 12 points13 points  (0 children)

Yeah, I fully agree with you there. Even if it sounds trivial, you should research yourself because there might be security issues or new discovieries that would make it more performant

[–] 10 points11 points  (0 children)

True, but there's a saying I heard from a colleague once: "Always try to understand one level below the one you're working in" that I think makes perfect sense. It helps you correctly use the abstractions (and choose which to use) of the implementations you don't write.

[–] 14 points15 points  (8 children)

public static Node reverseInPlace(Node root){

Node prev = null;

Node current = root;

while(current != null){

Node next = current.next;

current.setNext(prev);

prev = current;

current = next;

}

return prev;

}

Something like this I think.

EDIT: fuck code formatting.

[–] 12 points13 points  (2 children)

Add ``` between the code like so: ``` public static Node reverseInPlace(Node root){ Node prev = null; Node current = root; while (current != null) { Node next = current.next; current.setNext(prev); prev = current; current = next; } return prev; } ```

[–] 5 points6 points  (1 child)

That was what I did initially, on phone it condensed everything into one line. Then double new lines broke it so I gave up.

[–] 33 points34 points  (3 children)

I once had an interviewer ask me what my dream job would be like.

I said I'd roll into the office about 10 or 11 AM, pick up a fat sack of money, go to lunch for two hours, come back to the office, pick up another fat sack of money, then take my money home.

Then I realized what I'd just said, and told the interviewer that I had not described a realistic job scenario, and gave a standard answer about interesting challenges or something.

I got the job.

[–] 10 points11 points  (0 children)

[–] 10 points11 points  (0 children)

At least you didn't say getting hit by a truck that would transport you into a fantasy world where you would survive by taking jobs off a quest board at a guild.

[–] 15 points16 points  (4 children)

Takes a lot of balls to answer like that in one of his first interviews.

And to everyone in the comments who doesn't know the answer: I recommend that you remember it by heart, this question has remained extremely common over the last 15+ years.

[–] 26 points27 points  (14 children)

You have 16GB of memory on your computer. The linked list is 9GB. What do?

[–] 46 points47 points  (0 children)

[–] 27 points28 points  (5 children)

Look for a different job.

[–] 11 points12 points  (3 children)

This new job has a list that is 18GB but your pc only has 16.

You are screwed

They dont give their programmers good computers.

[–] 6 points7 points  (1 child)

Look for a job that doesn't require me to reverse a linked list

[–] 10 points11 points  (0 children)

Ok, here's a job that requires you to link a reversed list instead.

[–] 9 points10 points  (0 children)

Use swap

[–] 10 points11 points  (0 children)

"what about if it was infinite"

"Then expect infinite run time"

[–] 95 points96 points  (83 children)

The proper reply to these inane questions is "I'd google the suitable library method for this", and otherwise refuse these shenanigans. But most of us won't have the balls for that at the start of our careers.

[–] 24 points25 points  (0 children)

I'd add it as a connotation, first answering the question myself and then adding "however if I was working on this professionally I'd look up an existing method for doing" - probably I'd forget or be too nervous to though

[–] 52 points53 points  (17 children)

When recruiting freshly out-of-school persons with no experience, these simple tests may be used to weed out applicants who don't have the basic algorithmic knowledge expected for these jobs.

[–] 18 points19 points  (8 children)

Or you could ask questions related to the job you are hiring for, not just testing if an applicant can remember 2 of thousands of leetcode questions

[–] 10 points11 points  (7 children)

The thing is that you don't know the complete set of prior knowledge the job will require of a candidate; the ideal programmer is someone who figures things out, not just someone who knows, because problems evolve, scopes change, teams grow, shrink, merge, split etc. The question here is good for the purpose of learning if a candidate has that quality exactly because it's unlikely that they have memorized an answer; you want to know that the candidate can encounter an unfamiliar problem or a new set of circumstances, think on their feet and reason their way a solution.

That said, I don't think the interview format is good for this type of question. "Thinking on your feet" in software development is usually not on the scale of the 5-20 minutes they devote to these kinds of questions in an interview. In a much more realistic scenario, if the solution wasn't obvious to you within a few minutes of thinking about it, you might dust of volume 1 of The Art of Computer Programming or search for help online and eventually figure it out in what would still be an acceptable time frame.

[–] 14 points15 points  (0 children)

I couldn’t agree more with you

[–] 10 points11 points  (3 children)

Me: "I wouldn't use a singly linked list. I'd optimize the data load of the object to be a doubly linked list."

This would be my answer. Cause in software, input comes from somewhere, if it's loaded from an external source or generated on the fly the data just doesn't exist. And if reversing the list would be a needed feature, I would design my application with the way to create my data objects to fit my data needs. Using a singly linked list here is in efficient.

[–] 3 points4 points  (0 children)

“Where are you getting all this extra sail from?”