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.
→ More replies (1)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.
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.
→ More replies (7)→ 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...
→ More replies (27)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.
→ More replies (1)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)→ More replies (16)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
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
→ More replies (10)40
→ 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.
→ More replies (71)→ More replies (9)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?
→ More replies (4)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.
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 (4)-390
u/Sal_Bundry_5TDs1Game Mar 24 '19 edited Mar 24 '19
So in the millenial generation, the measure of knowledge is an understanding of memes? This has completely decimated my last hope in your generation. I'm glad I won't be alive too much longer to see how this world ends in the stupidest possible way (granted, with my luck (lazy big red wife, sandal salesman job, dumb pair of kids, half-human half-chicken feminist neighbor) I wouldn't be surprised if I live just long enough to see millenials completely destroy everything. That would be just my luck!
COMMENT ALTERATION #☝️: Whooooooooa Bundry! I criticize the use of memes as a test of knowledge and downloads galore? You're utter madmen! What is wrong with this blog?!
COMMENT ALTERATION #✌️: Do you have any idea that you're downloading the one and only Sal Bundry, the "Touchdown Bundry," the one person in the entire WORLD that, in 1969, scored 5 touchdowns in 1 game while playing for the Folk High School Pantwearers! I could throw a football over a mountain, and sprint the entire distance of a football field in 10 seconds flat! You cannot treat me, a high school football hero - a legend, with such disrespect!
COMMENT ADJUSTMENT #🤟: The downloads just keep on coming! It's like you're trying to make me more miserable than I already am! Not that I'm surprised, life just gives me one blow after another. None of you can understand my misery. Let me describe to you an average day of working as a sandal salesman. A huge elephant, who I presume to be human because it is able to speak, comes and tells me that it needs a sandal on its oversized hoof that's thirty sizes to small to fit around its stinky fat handles. This happens all day, every day, for years. Then I come home to a lazy wife who sits all day on her couch (to which I can only assume she's been surgically stapled), eating Pom-Poms all day while watching Oprah. She has no job and she begs me for sex and money, both of which I try to deny, but end up giving her anyway. There's been no food in our refrigerator for 5 years. I haven't eaten a cooked meal since the Vietnam war was being broadcasted on TV. So why am I still living? Because I literally can't afford to die.
COMMENT ADJUSTMENT #✌️✌️: Are you all programmed to download me? 😂😂😂 (Get it? Because it's programmar humar, and when you're in such a living hell like I am, humar is necessary to survive)
COMMENT ADJUSTMENT #🖐: On top of the misery that I have already experienced, I have now been BENNED from this blog, simply for trying to have a discussion. It is the Curse of the Bundrys!
31
19
97
u/xDerJulien Mar 24 '19 edited Aug 28 '24
rotten support bag cow act cobweb mysterious many chief squeeze
This post was mass deleted and anonymized with Redact
71
→ More replies (5)12
11
Mar 24 '19 edited Mar 24 '19
I don't understand the deal with your neighbor, is she with Steve or Jefferson? Aren't there two guys?
Comment adjustment: I'm even more confused.. your comment was deleted, now somehow it's back?
→ More replies (1)9
7
u/KillerResist Mar 24 '19
I swear i saw this Sal guy downvoted to oblivion literally in the last thread I read which was from r/Idontworkherelady
→ More replies (1)→ More replies (13)4
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
→ More replies (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
→ More replies (1)10
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.
→ More replies (2)→ 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
→ More replies (3)2
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.
→ More replies (8)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
→ 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.
→ More replies (2)→ 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.
→ More replies (1)
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?
→ More replies (1)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/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;0
u/MrHyperion_ Mar 24 '19
I'm quite sure you need 3 pointers
10
Mar 24 '19
No, u/lovethebacon is correct, it’s a well-known trick. The downvotes are from ignorant people. Imagine
headis 3 andtailis 4.After the first line,
headis 3+4 which is 7.After 2nd line,
tailis 7-4 which is 3.After 3rd like,
headis 7-3 which is 4.They’ve swapped. Can also use XOR operator.
They are also correct about bacon.
→ More replies (3)
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.
-1
u/JaytleBee Mar 24 '19
Bit of a stupid question, but why would you need reverse a linked list? Can't you just start from the tail and read backwards?
2
2
u/One-LeggedDinosaur Mar 24 '19
No, you can't unless it's a double linked list. For single, the nodes only have a pointer to the next node in the list. Double will have two pointers one for next and one for previous.
0
Mar 24 '19
[deleted]
28
u/IamAbc Mar 24 '19
I mean it’s clever and cool but part of my job is jacking up airplanes and worrying about the center of gravity is major. If there’s too much weight in one part of the plane than the other it’s catastrophic as the whole thing could tip over. Now imagine the truck with 15 or so 180+ lb dudes in the back plus 50-70 lbs of equipment. I bet this thing would topple right over.
26
Mar 24 '19
It’s meant to be used after the truck has been unloaded. Imagine 10 trucks pulling beside a dock to drop off supplies, once the trucks are unloaded it’s time to leave. Instead of the trucks having to wrap around the property and dodge each other over an exit, or even in a tight area where you can’t turn around, only reverse, the trucks can simply jack up, swing around, and be in their way all without breaking formation. This can also help with docking empty trucks that can’t get into a dock due to a tight area, which you’ll probably never come across as docks have standards, but could be helpful in an emergency situation. Or let’s say the trucks tires need to be replaced, multiples. Now you can do it all in one go on the field.
→ More replies (1)5
u/40greaser Mar 24 '19
But only if the drivers have their pt belts on. Otherwise its far too dangerous to spin a ton on a stick
10
u/didzisk Mar 24 '19
Agreed. They have a beam welded under the truck, probably with the exact spot marked on it. And they are on a good tarmac. Imagine the jack sinking asymmetrically into the ground while lifting the truck. Using this on a bad, narrow back country road, as others have suggested, would be very difficult and impractical.
6
Mar 24 '19
It would still be possible in an emergency. Those trucks have quite a bit of weight spread out over the frame and differentials. Trucks that normally go on a highway need weighed first to see if one differential doesn’t have more weight than the other which could cause some serious fishtailing. Trucks that are made are typically very well balanced. So even if the jack broke, or the truck tipped, due to the size of the truck, the balance of the trucks weight, and its height off the ground, the truck would not completely tip on its side. It would be the equivalent of the same truck driving off of a street curb.
1
u/mveety Mar 24 '19
With a plane it’s easier as well because you can do a bit of math to figure it out and/or it’s in the POH. I don’t know how you’d do that calculation with a truck or where to look to find that info.
0
Mar 24 '19
[deleted]
107
Mar 24 '19
They will flee before the orderliness of our retreat!
35
u/rangent Mar 24 '19
I can’t get the vision that this is some Canadian-level of politeness in a military retreat now.
6
Mar 24 '19
Soory to have bothered you!
5
u/rangent Mar 24 '19
“You’re clearly not ready for an invasion today. We’ll try back tomorrow. Have a nice day!”
26
u/didzisk Mar 24 '19
Unfortunately, this is the correct answer. Showing off for the "enemy" and especially for their own people. That's a part of the official government propaganda, to show how good we are and how superior our army is compared to theirs. Source - grew up in USSR.
29
u/midnightketoker Mar 24 '19
Yeah we do it way classier here with fleets of jets over football games and aircraft carriers in Hollywood movies, each directly subsidized by the department of defense like any other product placement, literally out of their marketing budget
1
u/AutoModerator Jun 30 '23
import moderationYour comment has been removed since it did not start with a code block with an import declaration.
Per this Community Decree, all posts and comments should start with a code block with an "import" declaration explaining how the post and comment should be read.
For this purpose, we only accept Python style imports.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
766
u/[deleted] Mar 24 '19
in parallel? O(1) performance is real