[HN Gopher] Sleeping through the technical interview (2022)
___________________________________________________________________
Sleeping through the technical interview (2022)
Author : xena
Score : 125 points
Date : 2023-07-07 17:46 UTC (5 hours ago)
(HTM) web link (xeiaso.net)
(TXT) w3m dump (xeiaso.net)
| bmacho wrote:
| 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
| taeric wrote:
| Sorting networks are a thing. I don't think it really changes
| your point, of course. :D
| enriquto wrote:
| 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 wrote:
| 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 wrote:
| Yes, the algorithm suffers from a race condition. Time is not a
| synchronization primitive.
| greiskul wrote:
| 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 wrote:
| return(4)
| [deleted]
| xena wrote:
| Hey all! If you like this, there's a sequel of sorts in 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.
| fb03 wrote:
| 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 wrote:
| https://news.ycombinator.com/item?id=2657277
|
| Archive (slightly NSFW text)
| https://archive.tinychan.net/read/prog/1295544154
| Arnavion wrote:
| 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.ht... )
| tikhonj wrote:
| 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 wrote:
| _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 wrote:
| 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.
| hgomersall wrote:
| 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.
| shae wrote:
| I wasn't expecting lojban! "The drink of the gods"
| colanderman wrote:
| Esperanto, not lojban
| barrenko wrote:
| 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.
| larperdoodle wrote:
| I handed in an assignment in my C class in college that used this
| algorithm for the sorting part of the assignment.
| xena wrote:
| 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 wrote:
| [dead]
| mlazos wrote:
| 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.
| bmacho wrote:
| I don't think that sleepsort is any more constant time, than
| any other sorting algorithm. For sleepsort to be constant time,
| you must - have an upper bound on the input
| (largest number) - you must not count some arbitrary
| things, like reading and processing the input, or spawning
| threads
|
| But if are allowed to do these things, all the other sorts will
| became constant time. (I believe only one of them is enough.)
| [deleted]
| AshamedCaptain wrote:
| Well they were indeed sleeping through the interview. Otherwise
| I don't know how could one possibly claim that a program whose
| first statement is a sequential loop over all values of the
| input has "constant time" asymptotic complexity.
| kadoban wrote:
| As with everything in algorithm analysis, it depends on your
| model of computation. That is, it depends what you're
| counting.
|
| For sorting (comparison sorts), one fairly typical model is
| to just count how many comparisons you do. Which, this does
| none (kind of, not really, they're really just implicit or
| hidden in the OS).
|
| It's just playing around with computational models, not a
| serious proposal. It's either just a joke, a troll, or an
| parable about the need to be careful about what metric you're
| measuring. Or some combination of those.
| jnwatson wrote:
| It isn't really linear. Sleeping is a heap insertion which
| takes O(log n).
| bmacho wrote:
| You still have to _read_ all the inputs at least, which is at
| least linear time, in the size of the input.
| QuadmasterXLII wrote:
| Each sleep is log n for the heap insertion, so the overall
| complexity is at least n log n
| xena wrote:
| 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.
| upon_drumhead wrote:
| I don't understand how wall clock time is constant.
|
| Sorting [5, 50] is faster wall time then [6, 60].
| xena wrote:
| The constant is the biggest number in the array
| NotYourLawyer wrote:
| If runtime depends on the input, it's not constant time.
| addaon wrote:
| It's constant with regards to the length of the input
| array, which is the usual metric for sort algorithm
| performance. That is, d(runtime)/d(len(input)) can be
| constant, even though d(runtime)/d(max(input)) is not, if
| you assume that len(input) is independent from max(input)
| (which is inconsistent with input having uniformly
| distributed random members, which is probably the more
| common assumption).
| recursive wrote:
| It's constant with respect to the number of elements,
| just not the maximum magnitude of those elements.
| shimmy568 wrote:
| The time to spawn the threads is just inconsequential
| compared to the time to wait for the threads to exit for
| small sizes of N. But by doubling the number of numbers to
| sort you do double the time (actual wall clock time) that it
| takes to spawn those threads. O(N + 10000000) is still O(N)
|
| Not to mention for the OS to handle N threads would likely
| take some kind of non-linear time, at least N^2 if I had to
| take a shot in the dark. But I imagine it'd depend on the OS
| and how the hardware handles interrupts. Even if the thread
| is sleeping it still takes resources to schedule it
| colanderman wrote:
| Linux's CFS is O(log _N_ ) to insert; O(1) to switch tasks
| ( _N_ being number of threads). [1] So O( _N_ log _N_ ) it
| seems.
|
| [1] https://en.wikipedia.org/wiki/Completely_Fair_Scheduler
| #Algo...
| 29athrowaway wrote:
| 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]
| Paul_S wrote:
| Sleep sort - invented by 4chan.
|
| The rest of the short story also reads like it came straight from
| r9k
| sleep_sort_ wrote:
| 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/l...
| autumn-antlers wrote:
| 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-
| in...
| xena wrote:
| I have another one here but it's not very good:
| https://xeiaso.net/blog/voiding-the-interview-2017-04-16
| thatcherc wrote:
| 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-
| intervie...
| lvncelot wrote:
| I never fail to re-read the entire series when it's brought up
| and will do so right now.
| metadaemon wrote:
| I was going to link to this as it immediately rang similar in
| my mind!
| AceJohnny2 wrote:
| 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/
|
| 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.
___________________________________________________________________
(page generated 2023-07-07 23:00 UTC)