12 ms·

Sleeping through the technical interview (2022)

279 points by xena 3y ago

fb03 3y ago
Super interesting on the sleepsort thing, amazing stuff! But for some reason, the tone and the excessive acrobatics/"bragging" kind of get the best of the article away for me. Okay, if the interviewer had properly done 5 minutes of research on this candidate, they would know know that the candidate is "way over their pay grade". I found all that dance that the article author did a little bit... unnecessary? Kind of how killer whales play with their prey before the kill. Overkill. Sorry, my answer probably isn't productive, I am merely sharing how I felt after reading it. I am now off to educate myself on SleepSort :-)
- wahahah 3y ago
  https://news.ycombinator.com/item?id=2657277 https://news.ycombinator.com/item?id=2657277 Archive (slightly NSFW text) https://archive.tinychan.net/read/prog/1295544154 https://archive.tinychan.net/read/prog/1295544154
- xwolfi 3y ago
  It's the mark of a toxic person probably. But aren't we all to some extent ? I too am fed up of candidates so shit we need to grind them through linked list and sorting exercise to find the one that can actually code a simple function, out of the 50 we interview that couldn't even start writing. People have no idea how many candidates try to apply to backend dev job in an investment bank for 100k a year in China with NO experience in banking, computer science or life in general. Between the guys telling you their dream job is to do nothing and be paid for it, and the dude looking beyond his screen at his friend filling the exercise for him, I've seen it all.
- procinct 3y ago
  The tone is styled off another popular series :) https://aphyr.com/posts/341-hexing-the-technical-interview https://aphyr.com/posts/341-hexing-the-technical-interview
- httpsterio 3y ago
  it's not an article though, it's a fictitious story, so of course everything is embellished for comedic effect.
- mikro2nd 3y ago
  Seriously? I can't think of a single instance where an interviewer has spent more than a cursory 5 seconds reading a candidate's CV before interviewing them. Many times not even that much courtesy.
  - xena 3y ago
    God yes. In case it's funny, I have a bit that I left on the cutting room floor where it's like: Jeff started again to speak, maybe he actually read your resume. That would be a first. "So it says here that uhhhh-". Alas, he did not. You wonder why you make that thing if nobody is going to actually read it. You even spent the extra time putting it into normal human language too. The travesty of recruiting continues. Or something like that. There is so much about the job seeking process that is just stupid and frankly funny. I'm considering giving Palima an intern in the next article, just because that would be hilarious to me.
barrenko 3y ago
I used to think all this aphyr-like "jargon" about coding as snatching stuff up from the void was a joke, nowadays I am not so sure.
- bitwize 3y ago
  Again, we etch runes into stones, and by imbuing the runes with lightning, make the stones come alive and do our bidding. Tell me again computers aren't magic!
- xena 3y ago
  The best jokes are always the truth!
- odyssey7 3y ago
  For an earlier example of a related vibe, I recommend checking out sicp: https://web.mit.edu/6.001/6.037/sicp.pdf#page29 https://web.mit.edu/6.001/6.037/sicp.pdf#page29
- btown 3y ago
  When the void is the norm, it is no longer the void. This is what everyone in tech aspires to.
jiggawatts 3y ago
It’s a cute story but it’s not constant-time in any sense. Creating ‘N’ threads and adding them all to a sorted wake list will be between O(N log N) and O(N^2), depending on the OS and/or language runtime. There is either a sorted list, a heap, or an N^2 algorithm somewhere behind the scenes. Similarly, the sleep sort itself is at least linear time. You have to wake N threads to output N sorted items. Worse, in wall clock time it also scales with the values. You could compress the range by first finding the minimum and maximum values, but that’s also … linear time.
- Paul-Craft 3y ago
  Everything's constant time in a universe with a finite lifetime. https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#Theories_about_the_end_of_the_universe https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
  - libealistand 3y ago
    Sure, but in such a world asymptotic complexity has little meaning. For practical purposes it's useful to make simplifying assumptions that are done in complexity theory.
- amalcon 3y ago
  In theory, since the argument to the sleep must necessarily devolve to an integer eventually, it could use a radix-sort or similar to perform in linear time. There are problem spaces where that can be a win, even after introducing a dependency on the magnitude of the largest value. In practice, of course, no system actually does this. Syscall timeouts just aren't a place where this is typically beneficial. Also, naturally, it would be better to just directly apply a radix-sort which only scales with log(max_value) rather than linearly with max_value.
- mostlylurks 3y ago
  > Creating ‘N’ threads and adding them all to a sorted wake list will be between O(N log N) and O(N^2), depending on the OS and/or language runtime. This is not a fundamental limitation of scheduling systems, especially if you take into account the possibility of special hardware allowing for constant-time-with-respect-to-number-of-threads scheduling. For example, it is trivial, though economically infeasible for any practical purpose, to construct a scheduler that performs scheduling by bouncing infopackets via laser beams off of a gargantuan set of mirrors of varying distances back onto a detector connected to the computer, relying on the speed of light to perform a delay of the specified duration. This shows that sleep sort does not inherently rely on the hidden algorithmic complexity of whatever thread scheduling approach is used, since that can be optimized to O(1) in theory, if not in practice.
Paul-Craft 3y ago
> "Yeah, I'm here. I've just never seen that before. It's a very...inventive sorting algorithm. How would you optimize it?" > In a flash, one line of code is changed: -forM_ values (\time -> forkIO $ threadDelay (100000 * time) >> writeChan chan time) +forM_ values (\time -> forkIO $ threadDelay (10000 * time) >> writeChan chan time) > "It is now ten times faster." Related: https://thedailywtf.com/articles/The-Speedup-Loop https://thedailywtf.com/articles/The-Speedup-Loop
withinboredom 3y ago
Didn't read the article. But I hate these things... I had a remote interview with Meta once, the dude was eating in the microphone the entire time. It was so distracting I forgot how to write a for-loop.
- Roark66 3y ago
  Hmm, I much prefer remote recruitment. I remember the old days. You had a brief chat with a recruiter or HR, than you had to suit up, drive/fly to some far place (often it would take an entire day - if you're working at the time it necessitates a day off). You would stress, am I wasting my limited days off on these guys? Will there be parking there? Will I get there on time? Then you'd have a half an hour "initial interview", then you'd wait, sometimes for weeks to either get an invite for the interview proper, or to never hear from them again... The whole process could take a month, require at least 2 days off and significant amount of travel. Today? A recruiter/HR person rings you and asks, can we have a video call? You have that 15~20 min call the same day, they submit your CV to whoever makes the decisions, then they schedule one or more video interviews/tech sessions, some companies ask you to do behavioral/skill tests from the comfort of your own home. All of it can be done during a lunch break if you're a remote worker... What's not to like? Yes, the communication bandwidth face to face is much higher, but only remote allows me to interview for a company in Tel Aviv in the morning, Warsaw midday and a Californian one in the evening all on the same day.
proxiful-wash 3y ago
[flagged]
- fouc 3y ago
  > Hopefully the important parts would be done in time for the call. implies this was no mistake in writing
- rcbdev 3y ago
  The implication made here is that the interviewee is presumably running an OS such as Gentoo or similar which has the spirit of compiling everything from source. Or this person only compiles their browser from scratch which has some privacy benefits (removing unwanted telemetry, no hidden surprises in the binary, etc.) and can help performance. I have known some people who compiled their own Chromium. While the person who wrote the article might seem odd and I would not have hired them, your condescending tone while nitpicking a perfectly valid technical statement strikes me as weird.
- libealistand 3y ago
  Some parts that are done can already be running while other parts are still compiling. I'm seriously concerned about all the besserwissers in this thread.
  - juancb 3y ago
    I want you to know that I'm enjoying your replies as much as the linked post, if not more.
- xena 3y ago
  Yes, I'm aware that this is impossible in plane 432. This is part of the framing of Palima as some kind of programming/SRE god that is able to do things previously thought impossible. It's fiction, belief can be suspended just that little bit.
_pastel 3y ago
Not only is it not constant time, it's not even polynomial - it's psuedo-polynomial. Also it'll fail on negative numbers, right? You'll need something like `10000 * log(time + min(time) + 1)` to be linear in the bits used to represent the inputs. > In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time
- libealistand 3y ago
  > Not only it not constant time, it's not even it's polynomial You understand that this is part of the joke, right? If we really want to get down to the details and kill the joke, then you don't actually need to wait real time. Computational complexity is concerned with steps in a computational model, not how much time passes on a clock. Sleep sort uses OS scheduler properties and in a virtual time environment, time advances to the next scheduled event. That's what brings you back to actual polynomial complexity, if you assume this kind of thing as your computational model. > - it's psuedo-polynomial. If you lecture people then please at least get your spelling right.
  - orangesite 3y ago
    This is really what makes the joke work IMO. Haskell's runtime and the OS it executes on exist only as a transient implementation detail of what is, literally, a pure environment!
    - bmacho 3y ago
      I still don't get it. Sleep sort still needs O(n) Haskell-steps, while for example sorting in bash is just 2 bash-steps, calling it, and receiving the output. I fail to see the joke, really. I only see false and nonsense statements, which still could be funny or interesting, but I don't see how?
lemper 3y ago
that sleep sort is one of the genuinely "inventive" discoveries out of 4chan.
WWLink 3y ago
Hahahaha I'm in love. Thanks for sharing that one lol.
moffkalast 3y ago
> I am looking at joining a smaller company > Against all odds, they wanted to hire you. For a significant amount of money A small company not trying to cheapskate? Literally unreadable.
jhaenchen 3y ago
Meh. Smells of "rockstar developer" thinking. I'll pass. This is a job.
ncphil 3y ago
This was really funny. Got lost in it, and the site, for a while yesterday. Made for an enjoyable week end. Many thanks to the author.
Tainnor 3y ago
I'm also one of these people who doesn't "get the joke". This could be a mildly interesting example of a sort that doesn't need to do any comparisons, but it's certainly not "constant time" given that it needs to loop over all the input values (twice actually). In the end, this is basically just bucket sort, only that the buckets are managed by the OS. And nobody has ever claimed that bucket sort is constant time.
mlazos 3y ago
I mean, isn’t spawning 1000 threads at least linear time? You could get it to log maybe but I’m not sure that code does that automatically.
- xena 3y ago
  Depends on what you mean by "time". Going by algorithmic complexity time it's at least linear yes. Going by wall clock time (the more important one for interview code) it's constant time.
  - fenomas 3y ago
    You're forgetting that algorithmic complexity deals with asymptotic behavior. An algorithm that takes N inputs, does N operations, and then sleeps for 10 seconds is not constant time, because in the asymptotic case the N iterations will take longer than the sleep.
  - upon_drumhead 3y ago
    I don’t understand how wall clock time is constant. Sorting [5, 50] is faster wall time then [6, 60].
    - xena 3y ago
      The constant is the biggest number in the array
      - saagarjha 3y ago
        It’s not constant; the algorithm runs in pseudo-polynomial time.
      - NotYourLawyer 3y ago
        If runtime depends on the input, it’s not constant time.
        3y ago
thatcherc 3y ago
As the author notes, this is very much in the style of the aphyr's Interview series of stories like "Rewriting the Technical Interview" - [0] - which are all great reads as well. [0] - https://aphyr.com/posts/353-rewriting-the-technical-interview https://aphyr.com/posts/353-rewriting-the-technical-intervie...
- metadaemon 3y ago
  I was going to link to this as it immediately rang similar in my mind!
- lvncelot 3y ago
  I never fail to re-read the entire series when it's brought up and will do so right now.
- AceJohnny2 3y ago
  In a very different writing style, but also mocking the technical interview: "Fizzbuzz in Tensorflow" (2016) https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ To whet your appetite: > interviewer: Um, you understand the problem is fizzbuzz, right? > me: Do I ever. So, now let's talk models. I'm thinking a simple multi-layer-perceptron with one hidden layer.
  - xena 3y ago
    It would be very easy to turn that into the kind of story that is being shown here though. Just make the interviewee seem mystical or whatever and reply in terms like "now the machine must learn, please join me in the prayers needed to ensure the safety of the journey" and then have a giant paragraph of Buddhist sutra translated into Lojban or something.
    - deleted 3y ago
      [deleted]
  - rqtwteye 3y ago
    This is actually a nice tutorial
shae 3y ago
I wasn't expecting lojban! "The drink of the gods"
- colanderman 3y ago
  Esperanto, not lojban
enriquto 3y ago
This blog has nice stories, but what really does it for me are the cute interjections using random conlangs. Here it was a well-known one, but I recall having seen some toki pona another day (can't find it now).
humbleharbinger 3y ago
Very cool but will the threads necessarily wake up deterministically? One may wake up before another but not get cpu before it correct? (forgive me if I'm misunderstanding the code)
- colanderman 3y ago
  Yes, the algorithm suffers from a race condition. Time is not a synchronization primitive.
  - greiskul 3y ago
    Yup. If we are being pedantic, and I am sure the author of this loves being pedantic, any number of factors could cause this algorithm to be incorrect. Put it in a slow enough cpu for instance, and it will output the wrong answer. And correctness is the single most important part of an algorithm. We can do any problem in constant time if we don't mind our answers are not correct.
    - MPSimmons 3y ago
      return(4)
deleted 3y ago
[deleted]
xena 3y ago
Hey all! If you like this, there's a sequel of sorts in Protos: https://xeiaso.net/blog/protos https://xeiaso.net/blog/protos I'm working on more stories in this "universe" but it takes a while for the satire juice to build up. Maybe the next one will be on spatial computing.
- kagevf 3y ago
  > Just in time for his calendar to fire a reminder that his standup meeting was about to start Sounds like our universe . . . I think that universe is better at naming things.
- Zababa 3y ago
  It was fun, I especially liked the commute and optimisation! I'm always happy to see new articles on your blog, thanks for writing and sharing it.
larperdoodle 3y ago
I handed in an assignment in my C class in college that used this algorithm for the sorting part of the assignment.
- xena 3y ago
  That is incredible. What did the teacher say? I actually got away with using SleepSort in an interview for my current job. It got me the job.
draw_down 3y ago
[dead]
sleep_sort_ 3y ago
sleep sort originated in /prog/ [0] . There's quite a few HN lurkers that were active in the sleep sort thread. Perhaps xena is also one of them? :) [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/lectures/52Tries.pdf https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...
- jackblemming 3y ago
  If I load gunpowder into a cannon based on the current number, such that bigger numbers get more gunpowder and are launched farther, and then I walk the distance and collect the numbers along the way, is this a physics sort?
  - oneshtein 3y ago
    You can just make holes bigger and bigger, until the [number] will fall in. For example: https://www.youtube.com/watch?v=ZKbJ1REQ-EA https://www.youtube.com/watch?v=ZKbJ1REQ-EA
    - weard_beard 3y ago
      My favorite physics sort: https://youtube.com/watch?v=Nz8ssH7LiB0 https://youtube.com/watch?v=Nz8ssH7LiB0
- gybon 3y ago
  Haven't thought of /prog/ for a very long while. My favourite post was someone's apprentice programmer inventing the "<=>" operator, for when you want to test for less than or equal to or greater than. Genius!
  - unnah 3y ago
    Then someone submitted <=> to the very serious people at the C++ standards committee, and they went on to ratify it in the standard.
bmacho 3y ago
Computer sorts require at least linear time, as you need to read the input (if you don't know other things about the input, say it has an uniform distribution). There are several linear time sorts, sleepsort, postman sort, counting sort. (For a bounded set of numbers or sortable keys.) But there is an (almost) truly constant time sort, using an abacus instead of a computer: https://en.wikipedia.org/wiki/Bead_sort https://en.wikipedia.org/wiki/Bead_sort
- deleted 3y ago
  [deleted]
- taeric 3y ago
  Sorting networks are a thing. I don't think it really changes your point, of course. :D
Arnavion 3y ago
Actually, if the thread runtime maintains its own concept of time, the algorithm doesn't even need to sleep in real time. Once all the threads have been created, the thread runtime can notice that all threads are idle and that the next thread to be scheduled is the one at time N, so it can simply update the current time to N and start executing that thread. Repeat for each thread and you'll have your sorted array out without any sleeps. After all, all the sorting work was already done when the threads started sleeping, having registered themselves with the orchestrator (timer wheel etc) that will eventually wake them up. Actually performing the sleep is not necessary. I don't know about Haskell, but with Rust the tokio runtime lets you do this using start_paused ( https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.html#method.start_paused https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht... )
- tikhonj 3y ago
  My understanding is that this is basically how discrete-event simulations work under the hood. You have a frontier of future events in an appropriate data structure (say, a heap) and then alternate between adding future events into the heap and pulling the next event off the heap. So, modulo several layers of abstraction and a bunch of implementation details I'm glossing over, using a scheduler like this to sort values is just a heapsort :)
- johnday 3y ago
  Actually, if you start working out which one is the next to run, you have reinvented selection-sort and you are no longer linear time. (Hence why this is not a sensible sorting algorithm in reality :) )
  - Arnavion 3y ago
    Which is why I wrote: >After all, all the sorting work was already done when the threads started sleeping, having registered themselves with the orchestrator (timer wheel etc) that will eventually wake them up.
autumn-antlers 3y ago
I keep a list of these sorts of creative-writing-programming posts here[1] (forgive the bare and broken theme, i dont actually post so work on the site has not been started, let alone finished) please let me know if you have any suggestions thet might fit in, and I'd be glad to even include less mystical folklore like the story of mel but clearly have a theme goin here 1: https://www.illucid.net/posts/homages-to-aphyrs-technical-interview-series.html https://www.illucid.net/posts/homages-to-aphyrs-technical-in...
- xena 3y ago
  I have another one here but it's not very good: https://xeiaso.net/blog/voiding-the-interview-2017-04-16 https://xeiaso.net/blog/voiding-the-interview-2017-04-16
  - deleted 3y ago
    [deleted]
  - autumn-antlers 3y ago
    > but it's not very good My criterea don't involve judgement calls :p The tough choice was to exclude projects without prose; I myself am more comfortable writing code. My own contribution is still down the road, and I bear a great respect for those who have put their words (and themselves) into the world.
hgomersall 3y ago
It occurs to be that this might actually be a practical algorithm on an FPGA. It would need a couple of refinements to handle multiple of the same value, but for constrained length lists to sort it could be a useful technique.
29athrowaway 3y ago
Sleep sort is a meme. If you pick a small unit of time you can make it faster but if the values are sparsely distributed it gets slower.
- deleted 3y ago
  [deleted]
Paul_S 3y ago
Sleep sort - invented by 4chan. The rest of the short story also reads like it came straight from r9k

279 points by xena 3y ago

fb03 3y ago

Super interesting on the sleepsort thing, amazing stuff! But for some reason, the tone and the excessive acrobatics/"bragging" kind of get the best of the article away for me. Okay, if the interviewer had properly done 5 minutes of research on this candidate, they would know know that the candidate is "way over their pay grade". I found all that dance that the article author did a little bit... unnecessary? Kind of how killer whales play with their prey before the kill. Overkill. Sorry, my answer probably isn't productive, I am merely sharing how I felt after reading it. I am now off to educate myself on SleepSort :-)

wahahah 3y ago
https://news.ycombinator.com/item?id=2657277 https://news.ycombinator.com/item?id=2657277 Archive (slightly NSFW text) https://archive.tinychan.net/read/prog/1295544154 https://archive.tinychan.net/read/prog/1295544154
xwolfi 3y ago
It's the mark of a toxic person probably. But aren't we all to some extent ? I too am fed up of candidates so shit we need to grind them through linked list and sorting exercise to find the one that can actually code a simple function, out of the 50 we interview that couldn't even start writing. People have no idea how many candidates try to apply to backend dev job in an investment bank for 100k a year in China with NO experience in banking, computer science or life in general. Between the guys telling you their dream job is to do nothing and be paid for it, and the dude looking beyond his screen at his friend filling the exercise for him, I've seen it all.
procinct 3y ago
The tone is styled off another popular series :) https://aphyr.com/posts/341-hexing-the-technical-interview https://aphyr.com/posts/341-hexing-the-technical-interview
httpsterio 3y ago
it's not an article though, it's a fictitious story, so of course everything is embellished for comedic effect.
mikro2nd 3y ago
Seriously? I can't think of a single instance where an interviewer has spent more than a cursory 5 seconds reading a candidate's CV before interviewing them. Many times not even that much courtesy.
- xena 3y ago
  God yes. In case it's funny, I have a bit that I left on the cutting room floor where it's like: Jeff started again to speak, maybe he actually read your resume. That would be a first. "So it says here that uhhhh-". Alas, he did not. You wonder why you make that thing if nobody is going to actually read it. You even spent the extra time putting it into normal human language too. The travesty of recruiting continues. Or something like that. There is so much about the job seeking process that is just stupid and frankly funny. I'm considering giving Palima an intern in the next article, just because that would be hilarious to me.

barrenko 3y ago

I used to think all this aphyr-like "jargon" about coding as snatching stuff up from the void was a joke, nowadays I am not so sure.

bitwize 3y ago
Again, we etch runes into stones, and by imbuing the runes with lightning, make the stones come alive and do our bidding. Tell me again computers aren't magic!
xena 3y ago
The best jokes are always the truth!
odyssey7 3y ago
For an earlier example of a related vibe, I recommend checking out sicp: https://web.mit.edu/6.001/6.037/sicp.pdf#page29 https://web.mit.edu/6.001/6.037/sicp.pdf#page29
btown 3y ago
When the void is the norm, it is no longer the void. This is what everyone in tech aspires to.

jiggawatts 3y ago

It’s a cute story but it’s not constant-time in any sense. Creating ‘N’ threads and adding them all to a sorted wake list will be between O(N log N) and O(N^2), depending on the OS and/or language runtime. There is either a sorted list, a heap, or an N^2 algorithm somewhere behind the scenes. Similarly, the sleep sort itself is at least linear time. You have to wake N threads to output N sorted items. Worse, in wall clock time it also scales with the values. You could compress the range by first finding the minimum and maximum values, but that’s also … linear time.

Paul-Craft 3y ago
Everything's constant time in a universe with a finite lifetime. https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#Theories_about_the_end_of_the_universe https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
- libealistand 3y ago
  Sure, but in such a world asymptotic complexity has little meaning. For practical purposes it's useful to make simplifying assumptions that are done in complexity theory.
amalcon 3y ago
In theory, since the argument to the sleep must necessarily devolve to an integer eventually, it could use a radix-sort or similar to perform in linear time. There are problem spaces where that can be a win, even after introducing a dependency on the magnitude of the largest value. In practice, of course, no system actually does this. Syscall timeouts just aren't a place where this is typically beneficial. Also, naturally, it would be better to just directly apply a radix-sort which only scales with log(max_value) rather than linearly with max_value.
mostlylurks 3y ago
> Creating ‘N’ threads and adding them all to a sorted wake list will be between O(N log N) and O(N^2), depending on the OS and/or language runtime. This is not a fundamental limitation of scheduling systems, especially if you take into account the possibility of special hardware allowing for constant-time-with-respect-to-number-of-threads scheduling. For example, it is trivial, though economically infeasible for any practical purpose, to construct a scheduler that performs scheduling by bouncing infopackets via laser beams off of a gargantuan set of mirrors of varying distances back onto a detector connected to the computer, relying on the speed of light to perform a delay of the specified duration. This shows that sleep sort does not inherently rely on the hidden algorithmic complexity of whatever thread scheduling approach is used, since that can be optimized to O(1) in theory, if not in practice.

Paul-Craft 3y ago

> "Yeah, I'm here. I've just never seen that before. It's a very...inventive sorting algorithm. How would you optimize it?" > In a flash, one line of code is changed: -forM_ values (\time -> forkIO $ threadDelay (100000 * time) >> writeChan chan time) +forM_ values (\time -> forkIO $ threadDelay (10000 * time) >> writeChan chan time) > "It is now ten times faster." Related: https://thedailywtf.com/articles/The-Speedup-Loop https://thedailywtf.com/articles/The-Speedup-Loop

withinboredom 3y ago

Didn't read the article. But I hate these things... I had a remote interview with Meta once, the dude was eating in the microphone the entire time. It was so distracting I forgot how to write a for-loop.

Roark66 3y ago
Hmm, I much prefer remote recruitment. I remember the old days. You had a brief chat with a recruiter or HR, than you had to suit up, drive/fly to some far place (often it would take an entire day - if you're working at the time it necessitates a day off). You would stress, am I wasting my limited days off on these guys? Will there be parking there? Will I get there on time? Then you'd have a half an hour "initial interview", then you'd wait, sometimes for weeks to either get an invite for the interview proper, or to never hear from them again... The whole process could take a month, require at least 2 days off and significant amount of travel. Today? A recruiter/HR person rings you and asks, can we have a video call? You have that 15~20 min call the same day, they submit your CV to whoever makes the decisions, then they schedule one or more video interviews/tech sessions, some companies ask you to do behavioral/skill tests from the comfort of your own home. All of it can be done during a lunch break if you're a remote worker... What's not to like? Yes, the communication bandwidth face to face is much higher, but only remote allows me to interview for a company in Tel Aviv in the morning, Warsaw midday and a Californian one in the evening all on the same day.

proxiful-wash 3y ago

[flagged]

fouc 3y ago
> Hopefully the important parts would be done in time for the call. implies this was no mistake in writing
rcbdev 3y ago
The implication made here is that the interviewee is presumably running an OS such as Gentoo or similar which has the spirit of compiling everything from source. Or this person only compiles their browser from scratch which has some privacy benefits (removing unwanted telemetry, no hidden surprises in the binary, etc.) and can help performance. I have known some people who compiled their own Chromium. While the person who wrote the article might seem odd and I would not have hired them, your condescending tone while nitpicking a perfectly valid technical statement strikes me as weird.
libealistand 3y ago
Some parts that are done can already be running while other parts are still compiling. I'm seriously concerned about all the besserwissers in this thread.
- juancb 3y ago
  I want you to know that I'm enjoying your replies as much as the linked post, if not more.
xena 3y ago
Yes, I'm aware that this is impossible in plane 432. This is part of the framing of Palima as some kind of programming/SRE god that is able to do things previously thought impossible. It's fiction, belief can be suspended just that little bit.

_pastel 3y ago

Not only is it not constant time, it's not even polynomial - it's psuedo-polynomial. Also it'll fail on negative numbers, right? You'll need something like `10000 * log(time + min(time) + 1)` to be linear in the bits used to represent the inputs. > In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

libealistand 3y ago
> Not only it not constant time, it's not even it's polynomial You understand that this is part of the joke, right? If we really want to get down to the details and kill the joke, then you don't actually need to wait real time. Computational complexity is concerned with steps in a computational model, not how much time passes on a clock. Sleep sort uses OS scheduler properties and in a virtual time environment, time advances to the next scheduled event. That's what brings you back to actual polynomial complexity, if you assume this kind of thing as your computational model. > - it's psuedo-polynomial. If you lecture people then please at least get your spelling right.
- orangesite 3y ago
  This is really what makes the joke work IMO. Haskell's runtime and the OS it executes on exist only as a transient implementation detail of what is, literally, a pure environment!
  - bmacho 3y ago
    I still don't get it. Sleep sort still needs O(n) Haskell-steps, while for example sorting in bash is just 2 bash-steps, calling it, and receiving the output. I fail to see the joke, really. I only see false and nonsense statements, which still could be funny or interesting, but I don't see how?

lemper 3y ago

that sleep sort is one of the genuinely "inventive" discoveries out of 4chan.

WWLink 3y ago

Hahahaha I'm in love. Thanks for sharing that one lol.

moffkalast 3y ago

> I am looking at joining a smaller company > Against all odds, they wanted to hire you. For a significant amount of money A small company not trying to cheapskate? Literally unreadable.

jhaenchen 3y ago

Meh. Smells of "rockstar developer" thinking. I'll pass. This is a job.

ncphil 3y ago

This was really funny. Got lost in it, and the site, for a while yesterday. Made for an enjoyable week end. Many thanks to the author.

Tainnor 3y ago

I'm also one of these people who doesn't "get the joke". This could be a mildly interesting example of a sort that doesn't need to do any comparisons, but it's certainly not "constant time" given that it needs to loop over all the input values (twice actually). In the end, this is basically just bucket sort, only that the buckets are managed by the OS. And nobody has ever claimed that bucket sort is constant time.

mlazos 3y ago

I mean, isn’t spawning 1000 threads at least linear time? You could get it to log maybe but I’m not sure that code does that automatically.

xena 3y ago
Depends on what you mean by "time". Going by algorithmic complexity time it's at least linear yes. Going by wall clock time (the more important one for interview code) it's constant time.
- fenomas 3y ago
  You're forgetting that algorithmic complexity deals with asymptotic behavior. An algorithm that takes N inputs, does N operations, and then sleeps for 10 seconds is not constant time, because in the asymptotic case the N iterations will take longer than the sleep.
- upon_drumhead 3y ago
  I don’t understand how wall clock time is constant. Sorting [5, 50] is faster wall time then [6, 60].
  - xena 3y ago
    The constant is the biggest number in the array
    - saagarjha 3y ago
      It’s not constant; the algorithm runs in pseudo-polynomial time.
    - NotYourLawyer 3y ago
      If runtime depends on the input, it’s not constant time.
      - 3y ago

thatcherc 3y ago

As the author notes, this is very much in the style of the aphyr's Interview series of stories like "Rewriting the Technical Interview" - [0] - which are all great reads as well. [0] - https://aphyr.com/posts/353-rewriting-the-technical-interview https://aphyr.com/posts/353-rewriting-the-technical-intervie...

metadaemon 3y ago
I was going to link to this as it immediately rang similar in my mind!
lvncelot 3y ago
I never fail to re-read the entire series when it's brought up and will do so right now.
AceJohnny2 3y ago
In a very different writing style, but also mocking the technical interview: "Fizzbuzz in Tensorflow" (2016) https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ To whet your appetite: > interviewer: Um, you understand the problem is fizzbuzz, right? > me: Do I ever. So, now let's talk models. I'm thinking a simple multi-layer-perceptron with one hidden layer.
- xena 3y ago
  It would be very easy to turn that into the kind of story that is being shown here though. Just make the interviewee seem mystical or whatever and reply in terms like "now the machine must learn, please join me in the prayers needed to ensure the safety of the journey" and then have a giant paragraph of Buddhist sutra translated into Lojban or something.
  - deleted 3y ago
    [deleted]
- rqtwteye 3y ago
  This is actually a nice tutorial

shae 3y ago

I wasn't expecting lojban! "The drink of the gods"

colanderman 3y ago
Esperanto, not lojban

enriquto 3y ago

This blog has nice stories, but what really does it for me are the cute interjections using random conlangs. Here it was a well-known one, but I recall having seen some toki pona another day (can't find it now).

humbleharbinger 3y ago

Very cool but will the threads necessarily wake up deterministically? One may wake up before another but not get cpu before it correct? (forgive me if I'm misunderstanding the code)

colanderman 3y ago
Yes, the algorithm suffers from a race condition. Time is not a synchronization primitive.
- greiskul 3y ago
  Yup. If we are being pedantic, and I am sure the author of this loves being pedantic, any number of factors could cause this algorithm to be incorrect. Put it in a slow enough cpu for instance, and it will output the wrong answer. And correctness is the single most important part of an algorithm. We can do any problem in constant time if we don't mind our answers are not correct.
  - MPSimmons 3y ago
    return(4)

deleted 3y ago

[deleted]

xena 3y ago

Hey all! If you like this, there's a sequel of sorts in Protos: https://xeiaso.net/blog/protos https://xeiaso.net/blog/protos I'm working on more stories in this "universe" but it takes a while for the satire juice to build up. Maybe the next one will be on spatial computing.

kagevf 3y ago
> Just in time for his calendar to fire a reminder that his standup meeting was about to start Sounds like our universe . . . I think that universe is better at naming things.
Zababa 3y ago
It was fun, I especially liked the commute and optimisation! I'm always happy to see new articles on your blog, thanks for writing and sharing it.

larperdoodle 3y ago

I handed in an assignment in my C class in college that used this algorithm for the sorting part of the assignment.

xena 3y ago
That is incredible. What did the teacher say? I actually got away with using SleepSort in an interview for my current job. It got me the job.

draw_down 3y ago

[dead]

sleep_sort_ 3y ago

sleep sort originated in /prog/ [0] . There's quite a few HN lurkers that were active in the sleep sort thread. Perhaps xena is also one of them? :) [0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/lectures/52Tries.pdf https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...

jackblemming 3y ago
If I load gunpowder into a cannon based on the current number, such that bigger numbers get more gunpowder and are launched farther, and then I walk the distance and collect the numbers along the way, is this a physics sort?
- oneshtein 3y ago
  You can just make holes bigger and bigger, until the [number] will fall in. For example: https://www.youtube.com/watch?v=ZKbJ1REQ-EA https://www.youtube.com/watch?v=ZKbJ1REQ-EA
  - weard_beard 3y ago
    My favorite physics sort: https://youtube.com/watch?v=Nz8ssH7LiB0 https://youtube.com/watch?v=Nz8ssH7LiB0
gybon 3y ago
Haven't thought of /prog/ for a very long while. My favourite post was someone's apprentice programmer inventing the "<=>" operator, for when you want to test for less than or equal to or greater than. Genius!
- unnah 3y ago
  Then someone submitted <=> to the very serious people at the C++ standards committee, and they went on to ratify it in the standard.

bmacho 3y ago

Computer sorts require at least linear time, as you need to read the input (if you don't know other things about the input, say it has an uniform distribution). There are several linear time sorts, sleepsort, postman sort, counting sort. (For a bounded set of numbers or sortable keys.) But there is an (almost) truly constant time sort, using an abacus instead of a computer: https://en.wikipedia.org/wiki/Bead_sort https://en.wikipedia.org/wiki/Bead_sort

deleted 3y ago
[deleted]
taeric 3y ago
Sorting networks are a thing. I don't think it really changes your point, of course. :D

Arnavion 3y ago

Actually, if the thread runtime maintains its own concept of time, the algorithm doesn't even need to sleep in real time. Once all the threads have been created, the thread runtime can notice that all threads are idle and that the next thread to be scheduled is the one at time N, so it can simply update the current time to N and start executing that thread. Repeat for each thread and you'll have your sorted array out without any sleeps. After all, all the sorting work was already done when the threads started sleeping, having registered themselves with the orchestrator (timer wheel etc) that will eventually wake them up. Actually performing the sleep is not necessary. I don't know about Haskell, but with Rust the tokio runtime lets you do this using start_paused ( https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.html#method.start_paused https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht... )

tikhonj 3y ago
My understanding is that this is basically how discrete-event simulations work under the hood. You have a frontier of future events in an appropriate data structure (say, a heap) and then alternate between adding future events into the heap and pulling the next event off the heap. So, modulo several layers of abstraction and a bunch of implementation details I'm glossing over, using a scheduler like this to sort values is just a heapsort :)
johnday 3y ago
Actually, if you start working out which one is the next to run, you have reinvented selection-sort and you are no longer linear time. (Hence why this is not a sensible sorting algorithm in reality :) )
- Arnavion 3y ago
  Which is why I wrote: >After all, all the sorting work was already done when the threads started sleeping, having registered themselves with the orchestrator (timer wheel etc) that will eventually wake them up.

autumn-antlers 3y ago

I keep a list of these sorts of creative-writing-programming posts here[1] (forgive the bare and broken theme, i dont actually post so work on the site has not been started, let alone finished) please let me know if you have any suggestions thet might fit in, and I'd be glad to even include less mystical folklore like the story of mel but clearly have a theme goin here 1: https://www.illucid.net/posts/homages-to-aphyrs-technical-interview-series.html https://www.illucid.net/posts/homages-to-aphyrs-technical-in...

xena 3y ago
I have another one here but it's not very good: https://xeiaso.net/blog/voiding-the-interview-2017-04-16 https://xeiaso.net/blog/voiding-the-interview-2017-04-16
- deleted 3y ago
  [deleted]
- autumn-antlers 3y ago
  > but it's not very good My criterea don't involve judgement calls :p The tough choice was to exclude projects without prose; I myself am more comfortable writing code. My own contribution is still down the road, and I bear a great respect for those who have put their words (and themselves) into the world.

hgomersall 3y ago

It occurs to be that this might actually be a practical algorithm on an FPGA. It would need a couple of refinements to handle multiple of the same value, but for constrained length lists to sort it could be a useful technique.

29athrowaway 3y ago

Sleep sort is a meme. If you pick a small unit of time you can make it faster but if the values are sparsely distributed it gets slower.

deleted 3y ago
[deleted]

Paul_S 3y ago

Sleep sort - invented by 4chan. The rest of the short story also reads like it came straight from r9k