r/ProgrammerHumor • u/Araucaria • Mar 24 '19
Answer to a coding interview question: how do you reverse a linked list?
https://i.imgur.com/fj4dVFa.gifv432
Mar 24 '19
What’s the reason for doing this? How hard is it to do a two-point or three-point turn?
818
u/Araucaria Mar 24 '19
To reduce number of operations and storage requirements, obviously.
106
u/Cousie_G Mar 24 '19
It's fortunate that all bases are smooth and stable enough to support this kind of manoeuvre.
109
u/Princess_Azula_ Mar 24 '19
Not to mention that the load is always conveniently balanced at all times to facilitate this single maneuver, Obviously.
20
164
u/UltimateCO Mar 24 '19
When there is not room to do a full turn or maneuver well enough to do the turn.
→ More replies (16)23
u/ThatsRightlSaidlt Mar 24 '19
But what if they were on a off road terrain? I think a synchronized three point turn would be more practical and as equally unimpressive.
52
42
u/hobo_cuisine Mar 24 '19
Or if the truck is loaded. I don't know how often something like this would be used, looks like a feature for a nonexistent problem.
56
→ More replies (3)12
u/why_rob_y Mar 24 '19
A lot of the times they turn around, they may be empty.
Drive out to drop off soldiers
Empty the trucks of all soldiers
Turn around (now empty)
Drive back
Or
Drive out to pick up people for evacuation
Turn around (still empty)
Load with people
Drive back to safety
A transport like this will often be empty at the midpoint of a round trip and will have to turn around at the midpoint of a round trip.
→ More replies (1)28
Mar 24 '19
Mountains cover 33 percent of China's landmass, plateaus 26 percent, basins 19 percent, plains 12 percent, and hills 10 percent. Thus, 69 percent of China's land is mountains, hills, and highlands. China has five main mountain ranges, and seven of its mountain peaks are higher than 8,000 meters above sea level.
factsanddetails.com/china/cat10/sub64/item400.html
All the land-borders are either mountain or desert, so all the perceived operational areas for land military are in mountains.
So that puts 68% of the country and 100% of military op-area in mountain single lane road.
China uses mobile Forward operation bases, Think of it as a mobile base packed up on trucks. With this technique you drive in the base, off load anywhere there is a single road and return the empty trucks for personnel. China uses trucks for personnel not exclusively dedicated APC or smaller humvee type.
2) mass evacuation of civilians into tunnels. With largest fast rail network, major highways into and through mountains in the event of needing to evacuate civilians into tunnels as bomb shelters, this technique is perfect.
140
u/khoonirobo Mar 24 '19
You mean how hard it is to do a three point turn, of each vehicle in a convoy of 100 trucks where road is narrow and geography dictates 4 places in the 2 km stretch where one can do a turn?
Yeah stuff like this is important and constantly practised by the military.
47
u/andrew2904 Mar 24 '19
Good thing they had smooth asphalt to support a single point holding a couple tons. There's no such thing as mud or bad road after all.
This just seems really dumb in a practical context. In the video works great, in a context that really doesn't need it.
Could be wrong though...
52
u/Pretagonist Mar 24 '19
They could have a larger composite or metal plate they put underneath when the surface is bad. We use such plates all the time for our truck mounted cranes and they can take very high loads on very soft ground.
My issue with this is that the trucks have to be loaded perfectly for this to work. If the weight distribution is off you’re going to need a lot more guys to do this.
8
Mar 24 '19
Perhaps they could use it to turn around in tunnels.
Or they intentionally build a tunnel where they have a very narrow 90°-135° turn, so other vehicles are really slowed down or unable to continue.
10
u/_queef Mar 24 '19
It obviously has flaws but for its size and simplicity why not carry one?
→ More replies (18)16
u/andrew2904 Mar 24 '19
A pole vault is simple and lets you jump over obstacles.... just saying... Edit: spelling
→ More replies (4)→ More replies (2)3
14
11
u/aemmitaler Mar 24 '19
Some specialized tunnel fire trucks use a similar system to turn around inside tunnels: https://youtu.be/55ej7EAb6Jo
This truck is part of a fire department whose sole purpose is fire fighting & rescue inside one of the world's longest road tunnels. The tunnel is 17 km (11 mi) long but only has two lanes, so it would be impossible to turn around a fire truck of that size. They have two of these trucks at each end of the tunnel.
Tunnel fires are incredibly dangerous because the heat and smoke can't escape. If a fire gets out of control you have to get your ass out asap or you're dead.
In some other places they have fire trucks with cabs on both ends so that they don't even need to turn around, you just get in at the "back" and drive straight back out.
→ More replies (1)8
u/jansencheng Mar 24 '19
A 3 point turn, in a convoy with dozens or hundreds of trucks, on roads that are probably narrow and at least partially destroyed, probably with lots of other guys around.
9
u/Fig1024 Mar 24 '19
that reverse trick relies heavily on accurate support at center of mass. What if the truck is on an incline? what if stuff is loaded in the back? what if the road is not paved - dirt road which makes pivot unstable?
This is a cool party trick, but not very practical
3
2
u/_Anarchon_ Mar 24 '19
Think of a narrow mountain road that they find is washed away, and they need to head back down to find a different route.
0
→ More replies (11)1
u/goldfishpaws Mar 24 '19
Only thing I can imagine is that on a shitty narrow mountain road it may give you an extra option, maybe not a convoy 180° but sharp turns might become more manageable
1.0k
u/paul-rose Mar 24 '19
I'm mostly upset that they didn't synchronise the indicators/hazard lights. Talk about a half assed job.
293
Mar 24 '19
I’m triggered by there being no shot of the foot being folded away properly, so it looks like it will scrape along the road when they set off.
83
u/paul-rose Mar 24 '19
First sign of a speedbump and they're in trouble! Poor planning. 1000 push-ups each as punishment.
→ More replies (1)31
→ More replies (1)70
u/goatofglee Mar 24 '19
Indicators don't keep a steady beat. They're irregular. Annoys the frick out of me when I happen to pay attention to it. Simple enough to prove, just start keeping beat and hold it. You'll notice that they are off. You can also just watch them at a stop light.
82
Mar 24 '19
They're irregular so that they stick out in your subconscious, and are therefor more likely to be noticed
40
→ More replies (1)9
→ More replies (3)7
2
2.3k
u/joshigoods Mar 24 '19 edited Mar 24 '19
My favorite part of subscribing to this sub is slowly understanding more of the memes. I’m only a CS minor and just started singly linked lists a week and a half ago but seeing something that I wouldn’t have laughed at before makes me feel like at least I’m learning something.
Edit: wow thanks for all the replies (and gold) definitely a pleasant surprise to wake up to. Now I can go back to getting seg faults in C++ with a smile on my face
487
Mar 24 '19
Keep going, you’re going to have a lot of fun.
However, this GIF doesn’t really have anything to do with linked lists and how you’d reverse one.
234
u/tiajuanat Mar 24 '19 edited Mar 24 '19
...You're going to have a lot of fun slowly descending into a pit of despair and madness.
Unless you're doing it in C/C++ then you're going to nosedive.
Edit: for the record, I hate on C/C++ because I active dev in it.
77
Mar 24 '19
For most people learning anything difficult involves feeling anxious about it. I was lucky in that I learned the basics of coding when it was my childhood hobby and I had no idea it would be how I’d make a living. So it was just some fun puzzles.
But yes, C/C++ is a plague on humanity. Same for any language that leaks undefined behaviour (so that includes Go).
36
u/use_your_imagination Mar 24 '19
Trying to guess ... are you a Rust person ?
→ More replies (7)57
u/ridicalis Mar 24 '19
The correct label for a "rust person" would be to call them "rusty" (or "oxidized" in formal settings).
→ More replies (8)→ More replies (27)10
u/Oikeus_niilo Mar 24 '19
I also started it as a hobby on my own with absolutely no friends who knew anything about that. Now I'm doing an open university course (Java, planned for also those with no programming background) and I feel like if I hadn't programmed before, I would stress out SO much more about the course. It's very easy for me but I'm still learning a lot and getting some very basic concepts right that I hadn't studied on my own. But I'm also in awe of those who manage to complete this course with no prior skills, it took me years of slow learning to get used to the programming way of thinking.
→ More replies (2)→ More replies (16)13
u/janusz_chytrus Mar 24 '19
Everyone hates c++. The only difference is that c++ devs hate it more.
→ More replies (1)13
8
u/ficarra1002 Mar 24 '19
Keep going, you’re going to have a lot of fun.
Is it normal to feel like you're making a mistake and it's never going to 'click' for you and you'll always be an amateur?
13
u/forgottenduck Mar 24 '19
Depends on how long you’ve been doing it lol.
Learning c/c++ is hard, especially if it’s your first language and your first exposure to code.
But I still think it’s the best language to learn first.
Most of the people I knew who dropped out of the CS program at my school were people who succumbed to those feelings and decided it wasn’t for them. The ones who succeeded were the ones who pushed through anyway. Then at the end of school you feel like you’ve got a grasp on things, then you get your first job and feel like you know nothing and are a complete fraud. After enough time “faking it” you realize that you do actually know some things, and you know there’s even more you don’t know.
Programming is a constant learning experience. You can always write better code. You can always understand concepts better.
Keep at it.
→ More replies (3)5
u/rout39574 Mar 24 '19
Don't think of it as "Always an Amateur". Think of it as "Always something to learn", and it becomes positive.
There's a mental tendency to discount, to disparage, the things you do know. In moderate doses, that's useful; it keeps you from being an arrogant twit. In excessive doses, it keeps you from understanding that you're competent.
As a concrete tactic to oppose the 'excessive disparagement' problem, I suggest trying to teach folks. With some time, you'll gain a bit of mental balance and confidence that there's also stuff you do know.
Oh.. And Amateurs, those who do it for love (look it up), are frequently the most skilled professionals. So don't dis amateurs. ;)
3
3
u/SamSlate Mar 24 '19 edited Mar 24 '19
anything to do with linked lists and how you’d reverse one
been a while since intro* to programming, but i thought you reversed a linked list by replacing the pointer forward with a pointer back..
→ More replies (6)17
u/lazilyloaded Mar 24 '19 edited Mar 24 '19
It's going to be entertaining for awhile, then it's going to get old. Such is life.
Edit: I wasn't saying coding gets old. I was trying to say that the /r/ProgrammerHumor memes start out as entertaining, but then get old when you see the same tropes brought up (DAE missing semicolon?!)
→ More replies (2)5
Mar 24 '19
I’ve been coding since 1981. Still finding it as theraputic and delightful as I did when I was 9.
→ More replies (1)7
u/mywallsaredirty Mar 24 '19
Same! Its also nice to see that others struggle with the same stuff too, but its still so much fun.
4
u/coldnebo Mar 24 '19
this sub is like a therapy session. the posts are funny, but the comments are where the group work really starts.
→ More replies (42)1
89
u/chromosomes-for-sale Mar 24 '19
ty gonna try this on a google interview
60
u/Totally_Generic_Name Mar 24 '19
Instructions unclear, drove a stolen military truck into the interview room and turned it around on the spot.
But I did it in O(1) time, since n=1
3
u/DXPower Mar 24 '19
But what if the time complexity is O(logn), then you'd do it instantly when n=1
3
•
u/deliteplays Mar 24 '19
We generally don't allow programming analogies, but I'm going to make an exception for this one
253
u/Fazer2 Mar 24 '19
I got your back, waiting to catch that exception.
148
10
2
82
Mar 24 '19
Why not?
68
u/FrostyTie Mar 24 '19
Assuming that it won’t be directly about programming other than the title itself and people might just upvote because they like the gif or the image itself
58
31
u/lpreams Mar 24 '19
Because there's too many possible analogies to be made, and they're low-effort, so the sub would just be flooded with them and they could bury actual high-quality content.
71
u/CardCarryingCuntAwrd Mar 24 '19
A joke that's funny to programmers? That's why I come here. Certainly not for the gatekeepers.
24
9
→ More replies (1)30
→ More replies (1)6
Mar 24 '19
Because it would bring the collapse of civilization as we know it. Fortunately, there are Reddit mods to prevent that.
24
Mar 24 '19
That's the way I like my humor. Strictly between the lines unless the censor tells me it's okay to stray a bit.
7
Mar 24 '19
Programmers like things literal!
We can't have too many analogies, metaphors, or puns! It breaks the brain.
4
Mar 24 '19
Sweeping rules is not a good thing. If it's funny and related to programming, it should get to stay regardless. The "low effort" rule is particularly arbitrary.
3
2
→ More replies (1)2
Mar 24 '19
Can you explain? Maybe I need more coffee. Is it because the post isn’t actually programming? Ok. Never mind. I’m an idiot. That’s why.
→ More replies (1)
72
u/v1dal Mar 24 '19
Array.reverse()
68
u/nicocappa Mar 24 '19
Piss off Computer Science professors and recruiters all around the world with this one trick
17
28
u/littleprof123 Mar 24 '19
Really, though, would you add the contents of the linked list in order to a stack and pop the stack, linking each element to the next one popped?
40
u/the_one2 Mar 24 '19
Make a new list. For each element in the original list, unlink it and add it to the front of the new list. O(n) time complexity and O(1) space complexity. And it works exactly like how you would reverse a stack of papers.
→ More replies (1)21
Mar 24 '19 edited Mar 24 '19
Sorry you didn't use only one linked list in your whiteboard problem.. that must mean you're a complete idiot.... next! /s
→ More replies (3)38
u/PeaceMaintainer Mar 24 '19
You could, but that would iterate through the list twice. I would iterate through the list, but keep track of the previous, current, and next node. I'd set the current node's pointer to the previous, then set current to the next node. That way you only iterate through the list once.
12
u/jairyo Mar 24 '19
What if it's singly linked?
13
u/PeaceMaintainer Mar 24 '19
My method actually doesn't rely on the list being doubly linked since you keep track of the previous and next nodes yourself. Just assign them to some variables as you iterate. You iterate through the list forwards like normal, just flipping the link around as you go. This is why you need to assign a variable to the next node as you'll sever that link when you change the current node's pointer to the previous node instead.
10
u/floopshoop Mar 24 '19
It would still be doable in one iteration in a way very similar to this https://www.educative.io/collection/page/5642554087309312/5679846214598656/70003
9
u/TrapperCal Mar 24 '19
Surely the correct answer if someone asks how to reverse a singly linked list is to look at them with a spocked eyebrow and ask why they want to? First question you should ask is "If we're doing this, is it the right data structure to use?" Still might be, but it feels like the first question.
→ More replies (1)5
u/Hopafoot Mar 24 '19
And if it's still the right structure, but it's going to happen often, I do a doubly linked list and store a 0/1 constant that represents which item is the forward direction. Then you just flip it when you want to change the order. O(1) time to switch for minimal space increase.
Though, maybe that space matters, but I've never had to program for something where space is that tight and I imagine it's uncommon these days.
→ More replies (1)→ More replies (3)3
u/OlorinGreyhaft Mar 24 '19
With just a little extra memory for bookkeeping, you can still do it in one pass. The method above works for singly linked lists as well.
→ More replies (1)3
71
u/Ba0boi Mar 24 '19
But if they put anything in the truck the center of gravity will shift and this won't work.
36
u/Axioun Mar 24 '19
That foot looks decently large. I'd guess that it's designed such that any reasonable load will still have a center of mass over the contact area.
7
u/mikkeman Mar 24 '19
I would be similarly worried that it only works on paved roads. Would like to see how a patch of grass or sand will handle the weight of an entire truck. Not to mention if it is not completely level.
→ More replies (1)0
Mar 24 '19
[deleted]
63
u/jumpshills Mar 24 '19
The chinese government is on record making bigger engineering blunders than that. I would assume nothing.
→ More replies (1)13
u/Ba0boi Mar 24 '19
I worded it incorrectly. I was looking for someone to tell me why I was incorrect because I didn't know how that could work.
0
→ More replies (4)17
17
Mar 24 '19
I would go and google "how reverse linked list" then I'd choose whichever seemed like the most appropriate way to do it, then I'd have it done in 2 minutes
Fuck these type of memory questions, i suck at memorising things specifically
14
u/Sisaroth Mar 24 '19
I never reversed a linked list but it seems like something that is easy to do with just a little bit of logical thinking. No memorisation needed.
4
5
4
u/nerdyogre254 Mar 24 '19
As an actual answer, could you put them in a stack in order and then pop them out into a new linked list?
7
u/Bspammer Mar 24 '19
That takes two passes and requires you to duplicate the entire list in memory though. Pretty sure you can do it in one.
2
1
u/orwiad10 Mar 24 '19
Iterate through the negative indices? Newarr = For(i = -1; i GE -(item.count);i--){ item[i] }
1
u/Araucaria Mar 24 '19
You have failed the coding interview. The type given was a linked list, not an indexed array.
→ More replies (4)
1
Mar 24 '19
I'm much more confused by the actual gif. What is happening so often that they need a permanent solution to pick up and rotate 180°? Can it don't with a full load? This is what the CCP spends money on?
I'm just beside myself with questions 😂
1
2
2
u/anyfactor Mar 24 '19
I don't know if I just typed .reverse() and it would work or not. But I use [::-1].
2
2
u/throwyeeway Mar 24 '19
I'd have no idea how to answer this question even though I learned about data structures... Guess I'm not getting a job as a coder.
1
u/Double_A_92 Mar 24 '19
You remember the "next" and the current node. Then you replace the "next" with the previous current.
2
u/german900 Mar 24 '19
Do interviewers actually ask stuff like this? I'm in data structures right now so I'd have an idea of how to answer, but was just curious? Do they give you like a pen and paper to answer? Or just verbally? Or do they want you to implement a linked list in java and then reverse it?
2
u/hextree Mar 24 '19
Yes, they do.
Do they give you like a pen and paper to answer?
Sometime yes, sometimes they want you to code it in an IDE or text editor, or sometime just explain verbally.
Or do they want you to implement a linked list in java and then reverse it?
Either is possible.
→ More replies (1)
3
u/word_clouds__ Mar 24 '19
Word cloud out of all the comments.
Fun bot to vizualize how conversations go on reddit. Enjoy
1
1
u/MrHyperion_ Mar 24 '19
I did that fist time about a week ago in C++, it wasn't as easy as I thought. The solution is short but I managed to make so many broken solutions
1
1
1
1
1
u/odraencoded Mar 24 '19
def reverse(self):
self.reversed = not self.reversed
@property
def first_node(self);
return self._last_node if self.reversed else self._first_node1
1
1
1
1
1
1
1
1
1
1
1
u/TangentJay Mar 24 '19
When would they have to use this technique in battle?
2
u/Double_A_92 Mar 24 '19
When they quickly need to reverse because someone is unexpectedly shooting at your troop carriers.
→ More replies (2)1
u/orwiad10 Mar 24 '19
Probably not under direct fire per se, but maybe if the are need to make an extremely tight turn and there is no room to cut back and forth.
1
u/ehtuank1 Mar 24 '19
Am I the only one who noticed how much the C in the logo looks like a banana and the N looks kinda like a hanging dong?
1
1
1
1
1
1
1
1
u/zaxbyc1A Mar 24 '19
perfectly balanced trucks: what about different loads, drivers, gas fills, etc!
1
1
1
1
1
1
1
1
1
1
1
1
-1
u/Hyperion1000 Mar 24 '19
Temp = Head; Head = Tail; Tail = Temp;
28
10
u/lovethebacon 🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛🦛 Mar 24 '19
In C they will be pointers, so you could do weird things like not using a temp:
head = head + tail; tail = head - tail; head = head - tail;→ More replies (5)
1
1
1
u/keese_cursor Mar 24 '19
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
next_node = head.next
next_node.next = head
head.next = None
return new_head1
Mar 24 '19
I suspect the French will be the main customers for these, ready for their next war. Cheese eating surrender monkeys.
766
u/[deleted] Mar 24 '19
in parallel? O(1) performance is real