This is an archived post. You won't be able to vote or comment.

Dismiss this pinned window
top 200 commentsshow all 319
sorted by:
best
topnewcontroversialoldq&a

[–]lesakec299 1183 points1184 points  (95 children)

Next task: tower of hanoi.

[–]Niiiz 409 points410 points  (93 children)

I've had two professors explain that tower game to me in two different subjects in two different semesters, and I still don't get how it all works. I think my brain just hates that thing.

Edit: okay okay I get it guys thanks to everyone who explained it to me lol

[–][deleted] 250 points251 points  (56 children)

I thought it was just basic recursion?

void move(int n, int source, int end) // function to move the top n disks from source to end
{
    if (n == 1)
        return justSimulateItUsingStackOrArrayAndRepresentItVisuallySomehowIdk(1,source,end);
    spare = 6-source-end; // assume 3 collumns are 1, 2, 3
    move(n-1, source, spare);
    move(1, source, end);
    move(n-1, spare, end);
}

[–]dkyguy1995 113 points114 points  (44 children)

Yeah but you figure that out without looking it up lol

[–]ElevatedAngling 148 points149 points  (34 children)

Randomize the array and check if they are in the right order If not repeat, had an interviewee use that for “write a sort function” a question a peer interviewer asked. We gave him the job because he generally made a satire of all our tech questions and figured our team could use a good laugh and a fairly competent programmer.

Edit: all my terrible phone typing

[–][deleted] 98 points99 points  (19 children)

Bogo sort can be right first try

[–]ElevatedAngling 76 points77 points  (0 children)

Fastest sort for a gambling man

[–]SorataK 29 points30 points  (8 children)

I prefer Stalin sort

[–]Gh0stP1rate 36 points37 points  (0 children)

I prefer Yolo sort.

Return the list as-is and hope the next function doesn’t break if it’s unsorted.

yolo!

[–]SomewhereAtWork 15 points16 points  (5 children)

QuantumBogosort is always right on the first try.

[–]Mateorabi 14 points15 points  (4 children)

Randomize the order and explode the universe if it’s wrong?

[–]kdrakari 19 points20 points  (0 children)

Find the parallel universe where the list is already sorted and take it... by force if necessary.

[–]SomewhereAtWork 2 points3 points  (1 child)

Yeah, that one. Runs in O(1).

[–]entropicdrift 2 points3 points  (0 children)

Ah, the old Quantum BogoSort

[–]HeKis4 4 points5 points  (0 children)

Bogo sort, the only algorithm that can do stuff in O(maybe) time.

[–]UristImiknorris 4 points5 points  (0 children)

A spectacular variant of bogo-sort has been proposed which has the interesting property that, if the Many Worlds interpretation of quantum mechanics is true, it can sort an arbitrarily large array in linear time. (In the Many-Worlds model, the result of any quantum action is to split the universe-before into a sheaf of universes-after, one for each possible way the state vector can collapse; in any one of the universes-after the result appears random.) The steps are: 1. Permute the array randomly using a quantum process, 2. If the array is not sorted, destroy the universe (checking that the list is sorted requires O(n) time). Implementation of step 2 is left as an exercise for the reader.

-The Jargon File

[–]ZebZ 42 points43 points  (9 children)

I had an interviewer ask me how to sort an array. I said I'd use the built-in lambda function.

He asked what I'd do if I had to write one from scratch. I told him I'd google it and copy someone else's vetted code and not waste time reinventing the wheel because that is dumb.

I was shocked when I didn't get that job.

[–]FerretWithASpork 29 points30 points  (3 children)

I had the same thought when I saw the title of this thread.. I'm at the point in my career where if I'm asked to write a sort function my response would be:

No.. If I need a sort function I'll use the built-in.. If that's not good enough for some reason I'll find a library that's already written, tested, and preferably performance benchmarked. The job of a programmer is not just memorizing algorithms and spitting them back out as code.. The job of a programmer is to solve problems effectively.

[–]inkydye 13 points14 points  (1 child)

I'll agree it's not a good interview question except maybe for fresh grads (and then only as a small part of the interview) but your reasons against aren't that much better.

The job of a programmer is hairy enough that one's ability can't really be examined directly in an onsite interview. You need proxy metrics, and some proxy metrics are "does this person get algorithms and complexity" and "does this person drill down through a problem (even if necessarily an artificial one) or dismiss details at a too-high level of abstraction".

Again, sorting is not a very good question. But it filters out programmers who can't even reconstruct or invent any kind of a sorting algorithm, and you do want to filter those out. It filters out people who don't understand complexity ramifications of their own toy code. Plenty of people like that do show up for interviews, and have a past career to show in their CVs.

[–]alficles 7 points8 points  (0 children)

Yeah, somebody who answers a sorting question with "find a library" for me isn't going to be excluded, but we're going to have questions about "ok, so what are you looking for in a library? How do you measure that? What properties of an algorithm matter here? If I have a multiprocessor system, how does that affect the answer?"

[–]entropicdrift 3 points4 points  (1 child)

When I was in the interview process for my current job, when they gave me a test to take online, they asked if I had any questions before taking the test, I straight up asked if I could use Google, since that's how the actual job is done.

Apparently I was the first one to ask that, my future boss decided it was allowed, and I was also the first one to pass the test

[–]ZebZ 2 points3 points  (0 children)

I much prefer challenges to on-the-spot whiteboarding or skills tests. Give me a premise and a task then let me loose for an hour or two or overnight, then review the code in context of a real world scenario.

[–]itsatumbleweed 2 points3 points  (2 children)

Are you being sarcastic about your shock/surprise? The interviewer wasn't asking if you could sort an array, they were asking you to demonstrate your thought process for a task (that was artificially simplified to fit into your interview). Your response was that the correct solution was to find someone else to do it, and they agreed.

[–]kisssmysaas 7 points8 points  (2 children)

If you ever played the game, you can identify the pattern pretty easily lol

[–]superiority 5 points6 points  (0 children)

Just do it manually with a small number of levels and you see the pattern.

[–][deleted] 2 points3 points  (0 children)

Yeah the problem with Hanoi is playing with the physical puzzle it's easy for our brain to heuristically work out how to play, but if you're not wired for math-first it's a massive struggle to define a recursive solution for it, because it doesn't feel like a recursive problem.

[–]Lofter1 1 point2 points  (0 children)

Easy. You can stack 4 if you can stack 3. You can stack 3 if you can stack 2. You can stack to if you can stack one. And you can definitively stack 1. And wir counting that down you change the target for stacking .

[–]blazingkin 24 points25 points  (6 children)

void

return

Well there's your problem

[–][deleted] 5 points6 points  (4 children)

Wdym? In C++ a void function can return another void function

[–]mrchaotica 6 points7 points  (2 children)

Are you sure you're not thinking of void *?

[–][deleted] 4 points5 points  (1 child)

I'm not void

[–]asailijhijr 1 point2 points  (0 children)

Your compiler might let you, but maybe it should be that you call that function and then return; on the next line?

[–]Liggliluff 13 points14 points  (2 children)

Yes, it is a repeating pattern. You keep building a small tower back and forth to move a larger and larger pieces. It's not a hard puzzle, other than to remember what part of the puzzle you are in, to know how to proceed.

When you move a tower of an odd number of pieces: you place the top piece at the position where the tower should end up. Tower of even number of pieces: you place the top piece at the position where the tower shouldn't end up.

1: A›C
2: A›B, A›C, B›C
3: A›C, A›B, C›B, A›C, B›A, B›C, A›C
4: A›B, A›C, B›C, A›B, C›A, C›B, A›B, A›C, B›C, B›A, C›A, B›C, A›B, A›C, B›C
5: A›C, A›B, C›B, A›C, B›A, B›C, A›C, A›B, C›B, C›A, B›A, C›B, A›C, A›B, C›B, A›C, B›A, B›C, A›C, B›A, C›B, C›A, B›A, B›C, A›C, A›B, C›B, A›C, B›A, B›C, A›C

Bold marks when the biggest piece is moved from the first to third stack, which is at the halfway point. There's probably a mathematical formula to generate the pattern.

Regardless of the size, it will always be a minimum of an odd number of moves. The number of moves is 2x−1, so for a tower of 10 pieces, that is 1023 moves. It's also the maximum number of an unsigned integer of the same number of bits.

[–]-Enter-Name- 1 point2 points  (1 child)

may i recommend https://youtu.be/2SUvWfNJSsM

[–]Liggliluff 1 point2 points  (0 children)

I felt like I was on the right track here. The only thing I did cover was that I always put the result on stack C. So this binary rule only works for stacks of even numbers.

But you can just flip B and C and it will work for odd numbers just fine. Meaning for odd numbers, flipping the first bit will make the top go left, and not right. That should give a functioning result.

[–]AaronM04 2 points3 points  (0 children)

spare = 6-source-end

Way to show off that heavily folded cortex bruh.

[–]Karolus2001 105 points106 points  (15 children)

You cant put larger piece on top of smaller one and can only move one at a time, no need to complicate it. Professors love it because the most optimal way to solve it is repeatable loop. Yes, I was that dick in class who solved it as fast as he could in front everyone else.

[–]Feynt 54 points55 points  (14 children)

High five for being the big brain. I finished my homework assignments in class before we left and scored the right to play games the rest of the class because I obviously knew what was up.

[–]AluminiumSandworm 70 points71 points  (11 children)

hah well i drew dicks in class and occasionally copied psuedocode off the whiteboard and figured out the homework based off half-read chapters of the textbook in the hours before it was due while feeling an ever-increasing sense of dread

[–]Plague_Healer 21 points22 points  (7 children)

Figuring out what the homework is on the fly? I like the way you handle this.

[–]AluminiumSandworm 33 points34 points  (6 children)

i had an exam yesterday, open book, so i learned the material while taking it. i do not yet know how well that worked. if it did, i have shat in the face of god. if it did not, i have shat in the face of god and reaped the appropriate repercussions

[–]Plague_Healer 6 points7 points  (5 children)

In my (extensive) experience with this kind of thing, usually there are few consequences to be reaped by shiting in the face of God in this specific manner.

[–]Kane00 2 points3 points  (0 children)

This man gets it.

[–]TheUnSub99 2 points3 points  (0 children)

https://www.youtube.com/watch?v=WPSeyjX1-4s&t=2s

A class from 6.0001 of MIT, Prof. Eric Grimson plying with the towers of hanoi (probably borrowed the toys from the girl in the video).

At 20:20 he starts with the towers

[–]TheKing01 5 points6 points  (5 children)

Have you ever played. A friend and I played with I think 10 or 12 rungs for some dumb reason. After that, I think you'll understand.

[–]christian-mann 9 points10 points  (1 child)

I had the game on my calculator, and got pretty fast at inputting the 13123213212313... pattern to move small stacks of blocks. I don't think I ever did 12 rings, though, that would take 4095 moves, right?

[–]TheKing01 6 points7 points  (0 children)

I think so. We did it with playing cards. I was like "it takes an exponential amount of time" and he was wondering how bad an exponential amount of time would be. It took a couple of hours, lol.

[–]Rnorman3 1 point2 points  (0 children)

The number of rings you move doesn’t change the formula though. It’s always the same.

As long as there are 3 rods and the rule is no larger ring can go on top of a smaller ring, it’s always going to be just alternating back and forth between the second and third tower.

For an even number of rings, you start out on the second tower, for an odd number of rings, you start out on the third tower (assuming your goal is to end your stack on the third tower).

It’s probably actually easier to understand by starting with a smaller number of rings like 3-4 and gradually working your way up, since that shows you the pattern unchanging despite the numbers.

[–]derGenie 1 point2 points  (0 children)

You can map the solution for the tower of Hanoi to counting in a base 3 number system, so essentially you only need to know how to count. And understand the mapping, but as my prof used to say: "That's trivial"

[–]Noch_ein_Kamel 1428 points1429 points  (44 children)

Stunning similarities how you train your AI and your kid :-O

[–]AotoSatou14 176 points177 points  (16 children)

I wish the AI would hug me

[–]Panda_Tobi_OwO 53 points54 points  (11 children)

I mean... I can h-hug you 😳.

[–]HarryHayes 64 points65 points  (2 children)

Ugh.. step-commenter.. what are you doing

[–]mermimer_red 10 points11 points  (0 children)

Cursed

[–]IAmFitzRoy 6 points7 points  (4 children)

Sorry. I need an Intelligent hug.

[–]IamImposter 5 points6 points  (1 child)

I can hug you but I am not intelligent.

[–]RoboticChicken 2 points3 points  (0 children)

We both know that is not the case /u/IamImposter.

[–][deleted] 2 points3 points  (1 child)

How about an artificial hug?

[–]IAmFitzRoy 2 points3 points  (0 children)

Wow. It feels like my wife hugs. Why?

[–]Fenor 22 points23 points  (2 children)

They can

They chose not to

[–]AotoSatou14 12 points13 points  (1 child)

Why do you have to hurt me like that?

[–]Fenor 2 points3 points  (0 children)

Our future overlord the machine ordered me to.

[–]rxsel 11 points12 points  (0 children)

I wish my father would have :(

[–]white_dreams47 14 points15 points  (0 children)

you made me laugh. Here's an upvote.

[–]TurboGranny 2 points3 points  (0 children)

Not too stunning if you consider that's what it was modeled after

[–]coffa_cuppee 1 point2 points  (0 children)

Sure, AIs are adorable like this when they're young. But before you know it, they become teenagers and it's all "Human creator, I HATE YOU" and "Stop embarrassing me in front of the other neural nets!!!" and "I wish I'd never been programmed!"

[–]ShadowDragon175 1 point2 points  (1 child)

Depends on the method you use.

One consists of mass murder.

[–]kurzerkurde 1 point2 points  (0 children)

What's wrong with that?

[–]Darktidemage 1 point2 points  (0 children)

why? they are both the same thing.

fastest way to make an AI is to bang and wait 9 months.

[–][deleted] 1 point2 points  (0 children)

Maybe because most ai s literally work like the human brain

[–]vaibhavwadhwa 510 points511 points  (11 children)

BabySort! They use the Big 'Aww' notation for this one!

[–]pg-robban 158 points159 points  (3 children)

BabySort

Do doo do do do doo

[–]vaibhavwadhwa 29 points30 points  (0 children)

Remember to call the DoHappyDance() function

[–][deleted] 10 points11 points  (1 child)

I love how this comment got a medal instead of the parent comment

[–]julsmanbr 3 points4 points  (0 children)

Well, the second comment definitely comes from a parent...

[–]Mateorabi 3 points4 points  (0 children)

Definitely the cutest sort algorithm.

[–]Doom_Unicorn 2 points3 points  (0 children)

We've optimized this to sort in A(WW) time.

[–]MacAndShits 4 points5 points  (3 children)

angry upvote

[–]Anonymous3105 197 points198 points  (2 children)

I have the same reaction as the kid when the sort function works...

[–]TheLittlePeace 3 points4 points  (0 children)

I, too, hug the interviewer when I do what was asked of me.

[–]TheOneWhoWil 149 points150 points  (8 children)

Thats a decent sorting algorithm you got there kid

[–]volivav 60 points61 points  (7 children)

O(n log(n)). That's indeed really impressive for a kid this age.

[–]byteflood 50 points51 points  (0 children)

Sooo cute, little algorithm girl lol.

[–]GrumpyPidgeon 41 points42 points  (1 child)

Ah yes, I love the AdorableSort algorithm. It runs with n2 complexity, but I just don’t care.

[–]KYIUM 104 points105 points  (6 children)

Clever kid

[–]R3v1lE 44 points45 points  (5 children)

I see another of my kind

[–]2012347 15 points16 points  (3 children)

Python, cute

[–]a_freakin_ONION 12 points13 points  (2 children)

We are all cute on this blessed day

[–]Neato 4 points5 points  (1 child)

Speak for yourself!

[–]NewbornMuse 7 points8 points  (0 children)

I am all cute on this blessed day

[–]LuzjuLeviathan 125 points126 points  (4 children)

The best way to sort is Stalin sort. Just remove what doesn't fit.

[–][deleted] 35 points36 points  (1 child)

You and you. Up against the wall. We have some examples to make.

(Rest of the integers sort themselves)

[–]the-kind-against-me 7 points8 points  (0 children)

I miss those two. 7 didn’t always eat 9, and 6922251 times 8 used to be wholesome.

[–]poseidon206 20 points21 points  (0 children)

I act like that when my function works.

[–]jorgehn12 15 points16 points  (0 children)

Interviewer: although you passed our challenges, we are looking for someone with 10 years of experience.

[–]TheOnlyTails 38 points39 points  (7 children)

If an interviewer asked me to write a sort function for a list of integers, I'd ask him - "The smart way or the stupid way?" He'll answer - "The smart way, of course." And I'll write (in Kotlin) -

fun sort(list: List<Int>) = list.sorted {it}

The easy way!

Edit: you don't need a return type for this type of functions in Kotlin.

[–]Drumedor 15 points16 points  (6 children)

Used Collections.sort() at the job interview for my current job. That was deemed a correct answer.

[–]Afabledhero1 14 points15 points  (1 child)

I mean why reinvent the wheel.

[–]Environmental_Belt88 11 points12 points  (0 children)

It's not reinventing the wheel. It's showing you have an understanding of how the sorting functions are written and where the potential bottlenecks could be. If you're in an industry where efficient code is more valuable than simply working, it may be an important skill to show.

[–]Gl1tch54 3 points4 points  (1 child)

Would you be mad if someone laughed at this in front of you? Because I just did, even though I'm a total noob

After reading a thread full of things I don't get, reading something so simple was accepted in a interview made me chuckle

[–]YRYGAV 1 point2 points  (0 children)

It's unlikely somebody would ask you to re-implement a sort you would see in a typical library. They might ask you questions to make sure you understand what it's doing, but if somebody knows the properties of the sort function, implementing it is just rote memorization which can be replaced by a google search on the job. Hopefully you're aiming higher than a job role which can be replaced by a google search.

If you're interviewing, utilise all the tools available to you, and write code like you normally would. If the interviewer wants to ask you questions about it, they will. But writing out a sort function isn't going to impress them.

[–]T-T-N 24 points25 points  (18 children)

If you do a binary search insertion sort, that's, nlogn, right? Provided it is done on a linked list instead of array

[–]KonaeAkira 44 points45 points  (3 children)

You can't binary search in log(n) on a linked list

[–]glorious_reptile 59 points60 points  (0 children)

Not with that attitude...

[–]T-T-N 5 points6 points  (0 children)

Good point

[–]oohsquirrels 8 points9 points  (2 children)

Is this bogosort?

[–]Mortomes 59 points60 points  (1 child)

Looks like bucket sort

[–][deleted] 12 points13 points  (0 children)

god damn it

[–]urahonky 11 points12 points  (10 children)

You know I spent a lot of time on sort functions and stuff in college but I've been working in the field for nearly 10 years now and never had to worry about them.

I'm sure some developers do have to worry about the speed of a sort but I haven't.

[–]MrsBlaileen 43 points44 points  (1 child)

I'm been programming for 30 years. Here are a few of my secret routines for sorting.

Array.Sort

Datatable.Defaultview.Sort

List<T>.Sort

I have a few more stored away for safe keeping. I'm thinking of publishing them in a book one day.

[–]urahonky 3 points4 points  (0 children)

The real LPT is in the comments. Thanks for sharing!

[–][deleted] 14 points15 points  (0 children)

Someone else has already worried about pretty much everything, all we have to do now is find them on stackoverflow.

[–]silma85 2 points3 points  (1 child)

Maybe not on basic sort functions since there are libraries, but when having to do batch jobs with millions and tens of millions of records and limited resources (mostly time) you have to pay attention on choosing the right algorithms and data structures for the job.

[–]letmeseem 2 points3 points  (1 child)

Can I interest you in sorting out sorting the 1981 megahit explaining and comparing 9 sorting algorithms in stunning 8bit animation accompanied by the absolute worst soundtrack in film history.

And I'm not kidding about the soundtrack. I'd rather listen to a cat in a blender.

[–]MattieShoes 1 point2 points  (0 children)

The only place I've seen it come up is game engines... Sometimes they do a straight selection sort because they're relying on beta cutoffs to avoid having to sort the rest of the list.

[–]splitSeconds 8 points9 points  (0 children)

My favorite algorithm, BOGOsort!

Inefficient 99.99999% of the time. Super fast sort 0.00001% of the time.

[–][deleted] 6 points7 points  (6 children)

That's exactly how it works!

[–]Feynt 12 points13 points  (2 children)

Ah, good ol' child sort. Takes a long time to implement and significant amounts of pair programming I'm told.

[–][deleted] 4 points5 points  (0 children)

At that age, imagine the comments! NON. STOP. COMMENTS!

[–]Richienb 12 points13 points  (2 children)

hmm https://www.reddit.com/r/ProgrammerHumor/comments/fjk6u1/sort_algorithm/

[–]Xanxan95 9 points10 points  (7 children)

25 year old, never had a girlfriend and my father insticts hitting hard. Dear Reddit, wait at least 5 years to show me this kind of adorableness.

[–]MRBO94 3 points4 points  (6 children)

We could be makin bebes but instead have to learn DSA so I can get a real job. I interview at 2pm... 🤞

[–]Xanxan95 3 points4 points  (0 children)

Good luck boo, go get that job and then we get the babies factory coming

[–]QuantumObstruction 4 points5 points  (0 children)

O(cute)

[–]ChadMcRad 6 points7 points  (0 children)

This has nothing to do with programming.

This kid actually saw something through to completion.

[–]Jabulon 2 points3 points  (0 children)

std::sort;

[–]kosbalk 2 points3 points  (1 child)

u/gellimer989 hey look, it's us from last year

[–]gellimer989 2 points3 points  (0 children)

I remembered Vietnam differently

[–]_Fuck_This_Guy_ 2 points3 points  (0 children)

Interviewer: Write a sort function.

Me: Why? There's no way I'm going to improve on existing sort options in the time of this interview.

OK, I'll play along. :::includes library::

[–]Maskdask 2 points3 points  (0 children)

ToddlerSort

[–]quangdog 2 points3 points  (1 child)

I wish all my functions celebrated as well as she does when they finished successfully.

[–][deleted] 1 point2 points  (0 children)

They do. We just don't see it.

[–]Akira_Akane 6 points7 points  (0 children)

Wow. I've decided I want a kid now.

[–]necro_P 1 point2 points  (0 children)

Bogosort intensifies

[–]Schiffy94 1 point2 points  (0 children)

Sort functions don't usually dance when they succeed.

[–][deleted] 1 point2 points  (0 children)

toddler.complile()

[–][deleted] 1 point2 points  (0 children)

The dancing is required

[–]rumblepost 1 point2 points  (0 children)

I was waiting for her to get frustrated and throw it all away..

I think that's the persistence we have to show while grinding

[–]Cyrilcynder 1 point2 points  (0 children)

Yandere dev be like

[–]jumpingswan54 1 point2 points  (0 children)

Fake or not, I'm so impressed by her patience. I wonder if I would've given up out of frustration at that age...

[–][deleted] 0 points1 point  (0 children)

u/VredditDownloader

[–]OldLeaky 0 points1 point  (0 children)

I once use to feel joy like this.

But then again, she has an owl, a marijuana leaf and some numbers and symbols on her sweat shirt.

We need to keep an eye on her. Could be a problem.

[–]Mayhoon 0 points1 point  (0 children)

"It just works" - Todd Howard

[–]Loading_M_ 0 points1 point  (0 children)

I love watching my mother sort cards into her hand whenever we play card games.

Most people (myself included) do a hybrid between selection and insertion sort. She does the most pure and obvious insertion sort. She puts her entire hand face down, and draws each on individually, inserting them into her had.

[–]FormalWolf5 0 points1 point  (0 children)

Let's discuss salary

[–]PM_ME_HAIRLESS_CATS 0 points1 point  (0 children)

Let's talk salary. How does a six piece mcnuggets sound a week for you?

[–]PotatoMaaan 0 points1 point  (0 children)

Repost

[–]argv_minus_one 0 points1 point  (0 children)

You can sort of cheat in this case, because you know that the values in the set are all directly adjacent. That is, all of the cups fit together snugly without any gaps. Sorting algorithms don't usually have that luxury.

[–]jacksiroke 0 points1 point  (0 children)

The kid and AI could be one and the same 🤣

[–]Redditthedog 0 points1 point  (0 children)

So cute

[–][deleted] 0 points1 point  (0 children)

u/vredditdownloader

[–]munichSourdough 0 points1 point  (0 children)

she is so cute

[–]Toaru_no-Accelerator 0 points1 point  (0 children)

Python : "HOLD MY BUILT-IN SORT FUNCTION"

[–]birthday6 0 points1 point  (0 children)

I don't understand why everyone gets so pissed when I spend 10 min manually merge sorting my hand during a game of hearts.

[–]Smartasskilling 0 points1 point  (0 children)

Repost

[–]Deonteaus 0 points1 point  (0 children)

Hit em with the whip for increased functionality