Sleeping Through the Technical Interview (2022)

Re:Sleeping Through the Technical Interview (2022) by xena on Saturday July 08, 2023 @05:25AM (#36642781)

To risk killing the joke: when I said "constant time", I alluded to the words and art of time complexity analysis but actually did not mean to go there. This is a double entendre that uses two conflicting views of the word "time" because yes it is impossible to make a sorting algorithm constant time in complexity analysis terms. The joke is that the actual intent of the statement is wall clock time. This is the time that is more relevant in job interviews (and realistically when people pull the "write an integer sort function" thing out of their ass for me to defecate code onto the screen, they don't use numbers smaller than like 100, meaning that this program will be almost perceptually instant to run).

It's a subtle metalinguistic joke. It's supposed to poke fun at understandings of how computer science works by turning them on their head.

I'm sorry the joke didn't land on you.

[ Parent | on HN ]

Re:Sleeping Through the Technical Interview (2022) by ctenb on Saturday July 08, 2023 @06:03AM (#36642960)

Can the wall time be considered constant if it depends on the magnitude of the numbers to sort? A list of numbers between 1 and 1000 will be much faster to sort than a list of numbers between 1 and 10^100. EDIT: I did get the joke when I read your post, and laughed to myself, so well done :)

[ Parent | on HN ]

Re:Sleeping Through the Technical Interview (2022) by xena on Saturday July 08, 2023 @06:05AM (#36642971)

The constant is the biggest number in the list multiplied by the sleep multiplicand. That plus overhead gets you the approximate runtime of the function.

[ Parent | on HN ]

Re:Sleeping Through the Technical Interview (2022) by ctenb on Sunday July 09, 2023 @03:21PM (#36657932)

Yeah, but technically that doesn't qualify as a constant since it depends on the input. If you explicitly constrain the problem space such that the magnitude of the numbers in the list is bounded by a fixed upper bound, then it works out. That's fine though, but then it's not a fully general sorting algorithm, like e.g quicksort

[ Parent | on HN ]

Re:Sleeping Through the Technical Interview (2022) by Tainnor on Sunday July 09, 2023 @09:19PM (#36660897)

If you just repeat the same number a million times, then the threads will all be scheduled to run at the same time, but of course, your computer doesn't have a million cores, so the threads will have to be executed partially in sequence. That means, even if you assume the largest integer is a constant (valid for some integer types, but notably not Integer in Haskell), the runtime will be proportional to the number of elements in the list.

[ Parent | on HN ]

Re:Sleeping Through the Technical Interview (2022) by Tainnor on Sunday July 09, 2023 @09:12PM (#36660848)

It's not a "subtle metalinguistic joke". You're just redefining words. The algorithm isn't constant in complexity theory terms and it's also not constant in "wall-clock time" (I'm not sure why you think the two are unrelated?), except if you use a model of computation that is so bonkers that it would be of no value.

Maybe it works as a sort of dadaistic literature, like the ones where they redefine "chair" to mean "table" and so on, but beyond that?

Both your article and this comment of yours show that you're annoyed at algorithmic interview questions, so you're trying (well, at least in this fantasy) to one-up your interviewers by being smarter, and technically correct, but in an unexpected way. I understand the sentiment, but unfortunately, this only works when you're actually at least technically correct.

[ Parent | on HN ]