Gaming CS Interviews | Hacker News Reader

Gaming CS Interviews

transitivebullsh.it

103 pointsEntICOnc156 comments

> Guidance is expected; a great interview should be more of a conversation than a one-sided question and one-sided answer.

I had a particularly awful interview at Google where the interviewer scoffed at me needing assistance.

And in an interview at Twitter with a xoogler they asked me what I knew about number theory and I said "nothing" and they said they majored in it and proceeded to ask me number theory questions. For a Django tooling position. He asked me how many prime numbers there were and I said "optimus prime" and he looked at me and asked if I was serious and if he should record my answer. I said yes followed by "autobots roll out"

Such a waste of my time to fly out there.

In such situations I tend to ask that question directly:

"It was my understanding that you looking for someone who will help you with Django tooling. I can do that. Although number theory sounds interesting, I never felt the need of diving into it in order to solve any Django-related issue. I would be happy to learn more about how you think number theory relates to Django tooling should I start working here."

When people try to be important like that, it is paramount to take them at face value. In a lot of geek environments this happens all the time. People trying to push that one niche topic they really know about, because this is their comfort zone. The problem is: that one niche topic will rarely be a natural fit for any given conversation. More often than not just asking how they think this relates to the conversation at hand is enough to tame them a little bit.

Many times the stuff people say will contradict with the stated (or implicit) goals of a conversation. in this case the chosen topic was one with which the interviewer felt at home.

So another approach would have been to make it even more about them by e.g. instead of answering their question showing that you did your research: "Ah number theory! I saw you majored in number theory, I admittedly never had the need to dive too much into it — what role does number theory play in $Companyname?"

Great answer. Connect with the current position.

I would add here, that you may ask in a polite way, how number theory relates to the position at hand, here Django. This way, the interviewer has to open up specifically. There might be something, that could be important and interesting or simply a bluff.

Not exactly the same situation, but from a snarky interviewer I've gotten the answer equivalent to

"lol I was told you were the Django expert? According to your resume? Are you not supposed to know that?"

Still it does tell you that you have to work with this massive asshole, so it's a worthwhile approach to get more info about the workplace you'll be in.

> get more info about the workplace you'll be in.

or about the bullet you just dodged...

if someone connected django with number theory in their head and assumed everyone else can see the connection just as spontaneously, i'd much rather leave than try to handle that arse.

Tell him "I use Django Modules, not Django Modulus."

This doesn't always work - many software engineers believe that you should be a bit of a generalist. However, if you ask the question about Django tooling, you are at least keeping the door open.

Asking the "what role does number theory play" question is a way to send a message and lose your chance at the job, but so does "optimus prime."

You SHOULD be a generalist for software development, but I would argue college level number theory is not a "general" mathematical thing. For example, in my college degree program, I was expected to be broadly introduced to math and science concepts. To that end I took low level physics, chemistry, and math classes, including calculus, discrete math, and linear algebra.

I was not expected to know how to calculate the static load on bridge segments like my engineer friends, but I was expended to learn the basic motion equations and be able to apply them. Equally, I did not take organic chemistry, though I had the option. I can balance an equation but not tell you what an "amine" or an "aldehyde" is.

My college's opinion, and one that meshed really well with my personal opinions on learning, was that you are better off having some surface level understanding so when you are asked to implement some sort of very complex algorithm about a domain specific problem, you will be better equipped to understand the domain expert and understand the common pitfalls that you should avoid.

My friend was a math major (and other majors) so he took number theory. I didn't totally understand all the things we talked about, but thanks to my understanding gathered from other higher level math classes like calculus and discrete math, he could dumb down his information a little less, and I could follow things like how it was funny when he was able to "prove" something on a test by doing every possibility, since there were only 24 possible outcomes, and why that displeased his professor.

Depends. I am a decent software dev by all the standards I can observe. Yet I don't know a lot about number theory. I know a ton about other fields like e.g. control theory. If I now interviewed a django dev and asked them about control theory or hardware registers, I wouldn't even ask them whether they know that, because the answer is not really relevant to their position. I might ask them just our of curiosity, but then I would not care so much if they don't know it, I would care about how they handle dealing with something they don't know.

If they go all optimus prime that would be a red flag. If they show curiosity a green one.

I remember being told once in an interview "I'll be your google, your stackoverflow, so anything you'd usually search for on there ask me".

Eventually I got to the point where I forgot how to do something simple where you'd usually just google it to refresh your memory. I decided to take his advice seriously and asked him, to which he responded to me basically by rephrasing my question as another question back to me.

I can tell you now there is no chance Stackoverflow would be as big as it is if the responses you got back where riddles.

A more realistic answer would have been, "[duplicate] Closed 4 seconds ago."

I agree in principle, but also see how the interviewer might have felt that there's a good opportunity there to assess your reasoning skills about that thing. I actually like it when an interview takes some small detours.

I had an interviewer say something very similar to that to me once during a live pair coding session. I got to a point where I asked him a question about how javascript worked and he said "Hmm, I don't know. Let's see!" We spent the rest of the interview trying to figure out if javascript did indeed work that way. I didn't get the job.

At least the person who wanted to be your google didn't collect all your personal information then serve you targeted ads.

That sounds like a lame pick-up line, and they sound like a crazy stalker!

My google coding interview was much l33t.

He asked me a graph search question. However at the time I didn’t know what a graph was. I’m self taught.

But I did understand the ask, which was to find a path through a series of locations.

I also happened to have some experience with slime mold finding optimal paths and once even tried to simulate it using a genetic algorithm.

That was the best solution I could come up with, a genetic algorithm that would optimize a path through a series of locations based on a reward system.

However, I did not say the word “graph” and its not an optimal solution.

I didn’t pass.

I view the situation as both “I wasn’t prepared” and “google missed an opportunity to hire someone who might approach things a bit differently”.

> and its not an optimal solution.

Therein lies your problem, and you can see it writ large on everything Google does. Because they're so dominate at so many things (search, video hosting / streaming, etc.), anything that doesn't fall under "optimal solution" and "immediately profitable" goes to the waste bin near immediately.

There are entire websites dedicated to how fast Google kills a project that could have been really great with a year or two of love and care.

They've come to expect overnight success because it's been so dramatic for the past two decades. This blinds them to a lot of opportunities, and it comes, pretty much, from the top down and has filtered into nearly everyone.

> “google missed an opportunity to hire someone who might approach things a bit differently”.

That isn't what they want. See above. Optimal solutions, instant / near-instant profitability.

As a counterpoint to this, I interviewed at Google and was sure I had flunked. On every one of the follow-up questions, I didn't produce a working solution, let alone an optimal one.

I still got the offer.

Truthfully I do attribute much of it to luck. From what I have heard, most people had more difficult questions than I did, often with more strict interviewers. It's a high variance process for sure. If I were to interview for the same position now, I would most likely not pass the interviews.

Congratulations. I hope you enjoy working there. A close friend of mine used to work there in a very high position and they left after about a year or two, but left for what I consider to be pretty ridiculous reasons.

I'm not quite sure how much I could share without revealing their identity, but essentially they were sat down and told to work on their appearance. They had enormous technical chops (probably in the top 10 people in the entire world at what they do), but at least 60 lbs. overweight, no sense of style or fashion, etc., and as unfortunate as it might be to hear it... when you reach Director-level / C-suite positions, you need to physically project that OR you have to be so absolutely dominant at what you do that they cannot ignore you. They aren't that dominate.

A shame really, but they went off to work for a private startup and seem to be quite happy anyway.

I did okay in my interview with google but was passed over. The truth is they are always interviewing, so I think being hired has more to do with the timeframe of your interview than anything else. It's very similar to how the military drops many "requirements" of a soldier when what they need are bodies.

At some points, google is spinning something up, and at those points they need more devs, so they hire more of the interviewees. I think the rest of the process is basically random, based on the gut feelings of an entire team of random people.

I think you're a bit full of yourself here. There are objectively correct ways to search a graph, and it sounds like your solution was nowhere close.

You didn't get rejected because you "did not say the word graph", you got rejected because your solution was very wrong.

Software engineering is not just about knowing syntax, CS degrees include a Data Structures & Algorithms class for a reason.

> There are objectively correct ways to search a graph

Objectively false.

Years ago I was talking to some sort of CS professor who had been specializing in networking. He mentioned that within an organization you typically see network's being mapped out with dijkstra, but between them (with BGP for example) you actually see packets routed the long way around. He claimed service providers did this because it allowed them to charge their competitors more money when they had to use their network. Although, a more charitable interpretation is perhaps that a service provider will naturally want its own traffic to have the best experience and will send their competitors traffic the long way so that they don't over saturate the network of their primary customers.

Perhaps the best of all worlds would be mapping your network such that your primary customers get the optimal path using dijkstra. Then you figure out how to get your competitor's traffic routed as fast as possible without dropping your primary customer's packets. Maybe something a genetic algorithm might be good at figuring out?

There are some objective things in this world. The optimal way travel from point a to point b in a graph is one of them. However, this is the optimal way to travel, not the objectively correct way to travel.

I once traveled home from work using the backroads in a move that cost me probably 30 extra minutes. Roads are a graph. I followed the objectively non-optimal path. However, the way the clouds were that day formed something like 20 rainbows. Which I got to gawk at the whole way home. Objectively non-optimal, but not objectively incorrect.

The path is still optimal, but the weight of the edges are not speed or distance but a complex utility function that best represents the needs of the business.

It's also not about thinking creatively all the time. When I did interviews at a FAANG, there were many interviewers whose questions ranged from understanding basic CS to inventing new algorithms in specific circumstances. Generally, the second set of questions rarely had optimal solutions that took longer than O(n), and the first set of questions had answers that come out of a CS textbook.

In other words, the first set of questions is about doing normal tasks in the normal way, and the second set of questions is about solving relatively simple problems in a way that scales up massively.

When you are doing something that has a well-known optimal solution, your colleagues will expect it to be done in the well-known way. They don't want to have to read through your "creative" code to determine that you are just doing a graph search in a different way than they are used to. Engineering at a place like Google isn't about doing cool things: it's about doing things that are kind of cool in a way that a mediocre CS grad from a high-ranked school can understand and extend your solutions.

In my interview for my current job, I was asked to implement an algorithm that finds the edit distance between two strings. This is a classic algorithm, one that I had learned and implemented about a year before in my algorithms class, and loved for its utility, but I could not remember a specific little detail!

However, neither did my interviewers! So we worked together trying to re-derive the algorithm from the problem, the expected output, and the rough idea of how it worked. We did not succeed, but we did demonstrate an ability to work through things together, an ability to stand up and point out incorrect things, an ability to reason through a problem, etc. I got the job.

I would have hired you on the spot based on your slime mold experience!

Google notoriously hire Megatron supporters. You should have known!

Well what do you expect from a person who majored in number theory but makes a living working on django tooling in a company that doesn’t really use django to begin with? Delay and reschedule interviews until you get an interviewer whose LN profile does not clearly indicate a mismatch

Really sounds like the guy wanted to talk about himself instead of actually interview you. I hope you were able to send some feedback to his superior, since they missed a hire because of his shit.

They were well aware of how he acted. I was warned by another interviewer earlier.

"Whats the rest of your day?"

"Oh. X is from Google and he still does their style of interviewing"

Then having him still in the interview chain is an organization failure and a great signal to the interviewee (you) that team dynamics are going to be a problem.

I want to believe this is satire but I know it's not even an egregious example.

Whist number theory may never come up in Django tooling. "Something you don't know" always will; it is valid to try and determine how people respond to questions they don't know the answer too.

If the candidate says they don't know a topic, that is a valid response. It's not worthwhile to ask detailed questions about the topic. That's a sign of an inexperienced and/or unprepared interviewer.

Asking someone "how many prime numbers are there?" seems pretty valid to me. It's an easy question. The two valid answers are: "a lot" or "infinite" (with "more than 10" also being a fine answer IMO). I'm not sure the interviewer was expecting the actually correct answer here (infinite) - lots of programmers don't know that there are infinite prime numbers - I think he was trying to set up for an explanation of an algorithms problem.

By saying "Optimus Prime," OP has shown that he prefers to cover up gaps in his technical knowledge with snark and being an asshole rather than taking a stab at it and working in good faith. That answer would have disqualified him in my opinion. Even respectfully saying "I thought I was intervieweing for a Django tooling position" would have opened the door to further conversation.

This was a ways in to the interview and I do not think I was being as asshole. I didn't say it in a mean way or anything. I was laughing about it and said I had no clue and wasn't something I was interested in. He came in ready to grill me and I did not then, nor do I now, see any benefit to adversarial interviews.

I said I knew nothing when he asked about number theory. I never tried to cover up anything in my gaps. The interviewer proceeded to ask questions about it.

I don't have a CS degree, I have never claimed I did or that I enjoy or even want algorithms heavy jobs. This was an internal tool to manage datacenter component ordering.

I would never ask a bunch of questions about something borderline esoteric to someone that has already said they don't know anything about the field. I have had plenty of interviews where I am doing the hiring and when I realize the candidates are in over their heads I politely ask some fielding questions (like, do you know number theory is great, and fair) and then just conclude the interview kindly or toss them a different set of questions depending on how the interview has been going.

I assume you were flustered by that point due to a previous interview, and feeling a little frustrated or defeated. I've been there, when I think it's not going well but they still want to talk.

Nevertheless, it appears to me that those were setup questions for his real problem to figure out how to explain it. If you had approached it with a more open mind, you may have gotten the job. You would have at least heard the question.

I know that most people here hate the Google-style algorithm problem, but I think the question he was going to ask would be about computing the nth prime or counting the primes less than k.

I will also point out that many people who know nothing about number theory know that there are infinite prime numbers. It's not necessarily redundant.

If the job had been some sort of super low level position requiring a lot of hand written advanced data structures, then I might agree with you. Hashes, priority queues, skip lists, etc all rub up against more math heavy topics (number theory, statistics), so you would expect a candidate to at least have some familiarity with prime numbers.

However, for a web framework? Like, primes are pretty simple, but they're also pretty niche. What range of 'easy' questions that are not directly or indirectly related to the job are allowed to be asked? Can we ask questions about the correct leavening agents to use for different types of bread? I mean technically we're just trying to see how they cover up gaps in their technical knowledge. And all questions are 'easy' for the right people.

If you lure someone into a place with the promise of gainful employment and then waste their time with niche questions that are unrelated but you happen to have warm fuzzies about, then you should probably expect to get a bit of snark.

Still, whether or not the question was valid/appropriate/useful doesn't really matter. On the job, sometimes you will be asked things you don't know, or things you shouldn't even be responsible for knowing. The way this person responded to receiving a question like that indicates that they might be a difficult person to work with.

The interviewer sounds probably bad. After the person made it clear they didn't know about number theory, they should have moved to a different topic. But still, answering "Optimus prime" just suggests immaturity or even combativeness in the face of a difficult situation, which isn't someone you want to hire. There are a thousand better answers. Even snarky answers are fine as long as the person is meaningfully engaging.

"I don't know. Probably a lot"

"Maybe infinite. I'm not sure."

"It's an interesting question. Am I allowed to look it up?"

(As someone else said) "Definitely more than 10. Outside of that I'm not sure."

"I don't know. But here is how I would write a script to figure it out"

It comes back to the "move mt. fuji" style questions mentioned in the article. The point of an interview is not to determine whether you would be able to move mt. fuji anymore than whether you are able to answer the number of primes. It's about how you communicate and approach a problem. "Optimus prime" is such a non-starter that it doesn't even allow for a discussion.

I'm speaking as someone who passed a google interview and worked there for several years, so there may be some reason to believe my feelings around interview approaches are based in fact.

I think if you're going to ask a subsequent question about an algorithm for predicting when bread is done proving, you are allowed to ask about leavening agents. That way, you can bypass the long explanation, and just say "Given n loaves of bread with X characteristics, design an algorithm to predict when they are done proving." That might actually be a decent data science interview question.

I used to ask an algorithms interview question based on bridge (the card game), and I asked a setup question of "have you ever played a trick-taking game?" That lets me see if I need to use the short explanation or the long explanation, and if you answered that you knew how to play bridge or spades in a follow-up question, I would ask a much harder version. If you've never played a card game in your life, I would switch questions (this has happened several times). In real life, most people understand that this kind of question is a setup for a subsequent algorithms problem, not a quiz of your knowledge of bridge or prime numbers (particularly after you say that you don't know number theory).

The interviewer didn't care how much you know about prime numbers any more than I cared about whether you knew how to play hearts/bridge. The interviewer was almost certainly trying to figure out how much he needed to explain in the problem statement for the algorithms problem.

Responding with snark only shows that you are not willing to work with them in good faith, and you are not willing to see where the question is going. It shows that you think you know what they should be asking you, and you have contempt for them because they are not running the interview the way you prefer.

By the way, if the primes thing was actually a quiz question that didn't go anywhere, I would encourage any Django programmer to say a gentle "fuck you" at the end of the interview. I certainly would.

I think this is an 'okayish' position to take. There are some people who absolutely can't handle being wrong, and I've personally seen them wreck havoc when they get out of their depth.

However, there has to be a limit to the nature of the questions that are being asked. If I'm spending my free time to go check some place out because they're telling me that they might be willing to give me a job, then I'm going to be kind of put out when they start asking me questions about what the 50th letter is in shakespeare's macbeth. The questions have to be somewhat on point. This isn't a medieval system of patronage where I have to be subject to every whim of my patron. We owe each other to not waste each other's time. And if they're going to 'break trump' then I don't see why I shouldn't as well.

I can hear the objection though, 'oh primes are relevant to development.' But are they really? Maybe for advanced data structures like hashes, but what are you doing with a web framework that necessitates you write your own hash function? Besides, if you know about prime numbers, but not weak primes, strong primes, strong pseudo primes, safe primes, etc do you really know about primes and their CS applications? No, you just picked up some random trivia in high school and you're put out that everyone isn't as excited about it as you are.

I think you forget that even technical interviews are still aimed at examining soft skills.

"What is the 50th letter in macbeth?" could easily be interpreted as "How would you go about finding the 50th letter in macbeth?" which is plenty relevant to basic scripting.

"Do I have a source I can pull macbeth from?", "How does that source work?", "Can I query it for individual characters/words/chapters/etc.?"

I think a fundamental problem a lot of people in the comments section are missing is that these interviews are designed to examine the approach to solving problems, not the actual answer to the problem. Sure, if you get a question about traversing a tree, they probably just want you to repeat some basic knowledge.

Maybe something that will illustrate my point: If you happened to know the 50th letter of macbeth off the top of your head, it would defeat the purpose of the question. The point is to examine your problem solving process. If you were to just answer "r", then the interview would quickly pivot to: "Ok, what is the 307th?" or "Ok, what is the 50th letter of Othello?" The point is not to answer the question, so much as to establish the person's ability to answer questions. Any answer that was a straight up answer isn't useful in any way.

There are all sorts of ways your example could be expanded into a useful examination of someone's programming abilities. If prompted, the interviewer might provide: "Let's say we have an api for querying the text of a given shakespeare work" "Could we expand that to other historical plays?" "What if we wanted a service to provide an arbitrary letter from an arbitrary play?" "What if we wanted to allow the user to specify between several options for the api we might use?" "How could we handle differing responses from different apis?" "Should we be counting punctuation or whitespace?"

It isn't so much that a certain subject (historical plays) might be relevant to the job requirements, it's that these questions are more about examining problem solving approaches.

Alternatively, this could be taken to fall into the bucket of brainteasers, where a good answer might be "e", since it's the most frequently occurring letter in the alphabet in english texts.

The fact that the twitter interviewer introduced themselves as a xoogler is absurd.

You would be surprised how common this is. Lots of startup companies also love to brag about how many xooglers they have recruited. I once interviewed at a startup and the CTO introduced himself as "xoogler". After the interview I checked his Linkedin profile and he had a summer internship at Google 7 years ago.

Now I’m really curious if they pronounce it “zoogler” or an “exoogler”. Either way seems to be another “how do you know if a man went to Harvard or the Marines” type cliche.

What the heck is a xoogler? Sounds like some sci fi slime mold monster.

Here ya go: https://www.quora.com/In-Google-recruiting-what-does-Ex-Goog...

Xoogler is a slang term for someone who used to work at Google (ex-googler).

And MeToogler is a slang term for someone who used to work under Andy Rubin at Google, and won part of the $310 sexual harassment lawsuit settlement.

https://www.cnbc.com/2020/09/29/googles-310-million-sexual-m...

https://www.cnbc.com/2018/11/01/google-employees-walk-out-in...

Oh, this is hilarious. Well done for the 'Autobots roll out'! :D

Do you think they blacklisted you from twitter after that encounter? :P

If you're using an interview that bares 'little relevance to an employee’s day-to-day work' and that requires dedicated prep to pass, then what you're doing is optimising a process for finding people who will tick boxes and jump through meaningless hoops.

That's fine - some jobs do require that - but it does mean that any 'best and brightest' rhetoric should be shelved. Everyone knows that tech hiring is broken, but still the trumpets sound about how it really means something to get through one of these processes. It is almost a counter-signal.

> If you're using an interview that bares 'little relevance to an employee’s day-to-day work' and that requires dedicated prep to pass, then what you're doing is optimising a process for finding people who will tick boxes and jump through meaningless hoops.

You mean all those jobs requiring college degrees? Or is that different somehow? The main reason is that difficult tests has positive signal even if they are partly irrelevant or tedious, and interview prep has nothing on 4 years spent full time, and on top of that you have to pay for college.

> The main reason is that difficult tests has positive signal

They provide a signal, but I don't think the evidence suggests that it's necessarily a positive one. "Can you play Czardas on the tuba" is a difficult task that would provide a strong hire/no hire signal, but that doesn't mean it would be a good signal to use when looking for developers.

The big tech companies themselves admit that a bunch of their employees are not sufficiently competent [1]; clearly, current hiring practices are suboptimal. Just because a test exists doesn't mean it's valid.

> You mean all those jobs requiring college degrees

There are many jobs where high performance doesn't require a college degree, and for those jobs, requiring a degree is again an exercise in box-ticking that should be replaced with a more meaningful measure. There are also jobs were significant education in the topic is important, and a degree provides better evidence of that that many other things, so can be a useful signal.

We know that tech hiring is broken, but whenever it's criticised, the people invested in this system get outraged. "What do you want us to do, just hire everyone?" etc. No one is saying - or has ever said - that assessing applicant competence is a bad idea, just that assessing the ability to rote learn is not the best use of time when hiring developers.

The current system is not the only way, and for an industry that prides itself on being filled with problem solvers and hackers, it's bizarre to me how much people rest on the idea that the existing system is imperfect but present, and so should be left alone.

[1] https://www.reuters.com/technology/exclusive-meta-girds-fier...

Maybe it is not the best system, but isnt it at least relatively fair and transparent in compare to "having luck on interviewer's stack/xp"?

Why would that be the only other option? That's exactly the same kind of hoop-jumping, perhaps even a little more honest.

This is exactly what I was talking about above. The solution for a known-to-be-broken system isn't another known-to-be-broken one, and it isn't keeping the broken system because it's already in place.

Development isn't about rote memorisation or slavishly repeating past mistakes. Knowing the Voight-Kampff algorithm doesn't make you a good developer, nor does claiming 20 years of experience with a decade-old technology, nor does being the CEO's nephew. All of those things provide (at best) a totally irrelevant signal.

What if we used better methods? Ones that actually assessed and evaluated the skills/traits necessary to do the job well? Ones that couldn't be gamed as easily by "grinding". I'm not saying there's globally-applicable silver bullet just waiting to go, but there are definitely avenues to explore.

One process I went through quite recently asked me to bring along a single line of code I'd written - any language, any project. Then we had a conversation about it: what it actually did, how it fitted into its context, why I'd written it like that. It provided me with an opportunity to show my understanding, and for the interviewer to probe particular areas they were focused on. I enjoyed the process, and I could see how it was providing relevant information to them.

Again, it's an imperfect process, but I think there's potentially a lot of mileage in 'talking to developers' when hiring them, with any number of different twists. At the very least, we should be experimenting and trying to find a fit-for-purpose process.

The question I have in regards to your suggestion is, how scalable is it ? Can/could it be applied to a FAANG-sized company ? I'm not rejecting any of your points, its just that every time someone critiques the current hiring practices they fail to provide an alternative system that does not introduce other problems (the first and most notable one is scalability, but there are many others)

I think a conversation is eminently scalable. If an organisation cannot devote 30 minutes to checking if someone they're about to hire is at all competent, then that organisation has much, much bigger problems than hiring.

The current process also requires dedicated employee time to administer, after all - this takes no more time, involves less employee prep, and (crucially) might be valuable.

YMMV but in college I learned lots about

- having to work together with assholes towards a common goal

- how sometimes you can cram for a deadline, but sometimes you can't

- how, often, how well you do is just politics and networking

Obviously fuck everything I learned about however pushdown automata worked. That's not relevant to my career now. All the above still is.

Meanwhile I learned about SQL, statistics, product development, industry best practices, algorithms both optimal existing ones and designing new ones, data structures both how to make one and what makes good ones, and how operating systems are designed and function. Specifically, I wasn't just shown a vague example in a twenty minute youtube video, I was made to demonstrate my knowledge in projects and tests that were designed by an intelligent domain expert and educator to separate the wheat from the chaff and often did just that.

I use most of that every single day, and I'm basically a web app developer. Can you learn how to program from learning yourself? Sure. Einstein taught himself calculus, but that doesn't mean most people can adequately teach themselves difficult subjects.

Writing a for loop might not be a difficult subject, but understanding what makes a for loop slower than another method, or why maybe you don't need to loop at all if you engineer things differently is an entirely different thing.

The automata class I took years ago has been one of the more relevant to my career.

TBH I was struggling to come up with a class that was relevant enough that I recalled it, but not relevant enough that I never used it ;). It's been a while since I graduated, so I probably suppressed a lot of memories about courses like Advanced Partial Differential Equations.

>interview prep has nothing on 4 years spent full time

that's just the problem with these interviews. It's kind of obvious that a fresh grad who prepares for 2 weeks for those whiteboard interviews will completely outclass known most productive programmers and engineers in the world (take whatever example you want, I would name someone like John Carmack) who takes the test fresh and unprepared. The modes of thinking and toolboxes required are just entirely different.

That should tell enough about the quality of that style of interview if you are using them for anything other than to weed out people who can't code at all in a phone screen.

> a fresh grad who prepares for 2 weeks for those whiteboard interviews will completely outclass known most productive programmers and engineers in the world (take whatever example you want, I would name someone like John Carmack) who takes the test fresh and unprepared

This extreme take is highly unlikely. World class programmers are typically extremely good in maths (and possibly have an active interest in it)/algorithms, and problem solving in general. In addition to J.Carmack (who is definitely very good in linear algebra and problem solving), another random example is F.Bellard (who calculated the largest known prime, and most digits of pi). L.Torvalds is surely extremely good with algorithms, S.Wozniak with problem solving (given his extremely good design skills in electronic engineering); another one that comes to my mind is P.Bonzini, with his 40 GB/S fizzbuzz :)

This happens in any high paying industry where candidates vastly outnumber their capacity to interview well. Graduates of top schools have to jump through tons of hoops to get a Goldman interview or work the (virtual) mailroom at a talent agency.

> Strings are just arrays of characters, so any algorithms you learn for arrays also applies to strings.

I.e. don't believe the anti-American propaganda on Unicode.org.

This is roughly true. Obviously with UTF-8 or UTF-16 you'll have O(n) access times for an arbitrary code point, but you can always convert to UTF-32 and that encoding is just an array of code points so you get O(1) random access back.

But random access to codepoints is still useless for all purposes.

UTF-32 !== UCS-2 and makes no guarantees about fixed code point size like UCS-2 did (and is considered deprecated because of that). There's an encoding issue with UTF-16 extending past the current "Astral Plane", but neither UTF-8 nor UTF-32 have that problem. We have no current idea at all what we might ever think to encode past the "Astral Plane", but that doesn't mean you should ever assume UTF-32 is UCS-2 and free of surrogate code points.

You gave me enough doubt that I went and looked this up.

> UTF-32 is a fixed-length encoding used to encode Unicode code points that uses exactly 32 bits per code point... The main advantage of UTF-32 is that the Unicode code points are directly indexed. Finding the Nth code point in a sequence of code points is a constant-time operation.

https://en.wikipedia.org/wiki/UTF-32

> The [UTF-32] Unicode encoding form that assigns each Unicode scalar value to a single unsigned 32-bit code unit with the same numeric value as the Unicode scalar value.

> Because surrogate code points are not included in the set of Unicode scalar values, UTF-32 code units in the range 0000D80016..0000DFFF16 are ill-formed.

https://www.unicode.org/versions/Unicode5.0.0/ch03.pdf (page 40)

> As a consequence, UCS-4 can now be taken effectively as an alias for the Unicode encoding form UTF-32, except that UTF-32 has the extra requirement that additional Unicode semantics be observed for all characters.

https://www.unicode.org/versions/Unicode5.0.0/appC.pdf (page 7)

Yeah, I did briefly confuse UCS-2 (16-bit) and UCS-4 (32-bit) in my terminology, but the point still stands: lots of people expected the optimism in Unicode 1.0 that Unicode stopped at UCS-2 (16-bits) and never expected the "Astral Plane" to open up (and UCS-4 added). There was lots of software (including Windows) that had to do a lot of work to fix assumptions that UCS-2 was "the last word" on Unicode encoding and switch to UTF-16 or UTF-8.

That "except" there is still doing a lot of work pointing out that UTF-32 is not exactly UCS-4, so that point still stands. There's no surrogate code points allowed in UTF-32 today, but again if you want to assume "future compatibility" you shouldn't assume that UTF-32 is UCS-4 and will never have surrogate codepoints. As I said, we don't know if that next "plane" will ever open up into UCS-8 (64-bit) encodings, but if you are assuming it will never open up you are making the exact same sorts of assumptions that Unicode 1.0 users made with UCS-2 and had to consequently fix a decade later.

(And some of those same applications would have to fix again if 64-bit encodings opened up, because like I said UTF-16 has a math bug that its surrogates can't encode there, though UTF-8 is fine, and UTF-16 may be the worst of all Unicode encodings in the long run, but its legacy lives on so much because of all the early bets on UCS-2 being the last word and "easiest" Unicode that turned out to be bad assumptions when the "astral plane" opened up.)

Every squiggle language transliterates to 7 bit ascii without loss of fidelity anyway. ¯\_(ツ)_/¯

Of course, eg.

{lefthandraised}\_({eyes}{slantedmouthkindabelowtheeyes})_/{righthandraised}

~\_:)_/~

For the mildly curious who never bothered to look it up:

シ - shi, pronounced like the word "she"

ツ - tsu

(Japanese katakana)

The conflation of "amortized" with "expected" feels a bit off to me.

Amortized O(f) strongly suggests that the sum of n operations is very very close to O(n×f). I wouldn't say hashmap insertion is amortized O(1), because if you craft input that always incurs a hash collision, then n insertions is much worse than O(n). I would say that it's expected O(1), meaning that with high probability an insertion takes constant time.

Conversely, "amortized" is only a useful description when it is known that some operations will take much longer than others, yet the total time is bounded. (If you bring up amortized time, you're pretty much implying that the distribution of times is uneven, otherwise you wouldn't have mentioned it.)

For example, if you're doubling the length of an array on overflow, then I would say the amortized time of a push is O(1). It would seem weird to say that the expected time is O(1). If I wanted to be more complete, I'd say "normally a push is constant time, but when the array needs to be expanded then it's O(n). The amortized time is still constant, though."

Expected time refers to a single operation. Amortized time describes the mean time of a series of operations.

Fun fact: you can make the time of a push unconditionally O(1) at the cost of extra memory as well. This is useful if you really can't afford the unpredictable spike in performance. The trick is to slowly already start copying data into the next larger buffer as you're filling the previous buffer. As an example in pseudocode C++:

    template<class T>
    struct ConstantTimeVector {
        T* buf;
        T* next_buf;
        size_t len;
        size_t cap;

        void push(T x) {
            if (len == cap) {
                free(buf);
                buf = next_buf;
                cap *= 2;
                next_buf = alloc(cap);
            }
            
            buf[len] = x;
            next_buf[len] = x;
            next_buf[len - cap / 2] = buf[len - cap / 2];
            len += 1;
        }
    }

You can apply a similar trick to hash tables to get expected O(1) time inserts without amortization, by already building the re-hashed table during the building of the previous table.

Hah! That's awesome.

I'm not sure how well it would work in practice, since you're depending on alloc() giving you uninitialized memory—if it zeroes it, then it's back to being O(n). But that's kind of an unfair quibble.

And of course, it adds a branch to the lookup. Still O(1), but you'd need to check which buffer to find a given index in. Really not a problem here since as you say, the whole point is to bound the latency, not minimize it.

It does not necessarily add a branch to the lookup, look more closely: all current data exists in buf in its entirety. It is duplicated into next_buf.

This might be problematic depending on T in C++ as it would need to invoke copy constructors. In Rust all types can trivially be memcpy'd into another location if you own it, so this design would be entirely valid (as long as next_buf is not publicly accessible at all, and we do not provide mutable access to the data). EDIT: after thinking a bit more, due to interior mutability you can't provide access at all, or you would need to invoke a branch like you said in Rust.

If you want to provide mutable access to a piece of data and/or avoid copy constructors in favor of move constructors, then, yes you would need to do a branch.

Doh! You are right, of course. My head is stuck in the standard doubling approach. You are pre-copying into an upcoming buffer.

Which, as you say, is going to be weird with the language model, since the "same" thing exists in two different places. In C++, it would encounter problems with either a destructor or a copy constructor.

I still think it's a cool trick for a realtime setup for arrays of trivial types.

> Expected time refers to a single operation. Amortized time describes the mean time of a series of operations.

Pardon my ignorance but I don't see the difference between these two sentences.

Expected time of a single operation = Sum of time taken for all possible input cases / Number of cases (assuming each input case is equally likely to occur). Is it not?

Isn't it then the same as amortized time?

They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call the same operation multiple times (it has nothing to do with randomness).

Hash maps provide O(1) expected lookups. This running time relies on randomness, and it is the average running time of one operation. If you are very unlucky (or if an attacker can predict your random number generator), then it is possible for every single lookup to run in O(n) time.

Dynamic arrays (vector in C++, ArrayList in Java) provide O(1) amortized push calls. Dynamic arrays sometimes have to copy every element in the array into a new allocation when you call push. However, by doubling the size every time this happens, the copies happen so rarely that if you push k times (starting with an empty array), then the total running time of all k calls is O(k), even though a small number of the calls are much more expensive than O(1).

So, unlike expected running times, an amortized running time of O(f(n)) is an absolute guarantee that calling it k times in a row never runs slower than O(k*f(n)).

A difference is in the number of times you use some operation.

For example, you expect to do a lot of pushes in vector so you can say about amortized time because it will hold on average and you can calculate running time from it and expected number of pushes somewhat precisely (with unknown constant multiplier which is independent of input data, on theoretical hardware at least).

On the other hand, an individual array is usually sorted only once. Here it is more appropriate to speak about average or expected complexity of quicksort which is O(NlogN) but in you particular run it may become either better or worse and this will noticeably affect running time, by a factor dependent of N value.

You can say about amortized time of quicksort though if you expect to sort different arrays a lot of times and you know their distribution, or at least the fact that they are sufficiently random shuffled or maybe sufficiently sorted beforehand.

Ah! Finally it clicked! Thanks for the nice example in your comment.

Ordinary hash maps are still amortized expected O(1) — they will hit an O(n) case, guaranteed, when they need to grow the array, and it’s expected that the amortized runtime is O(1).

Being merely “expected O(_)” would be appropriate for algorithms that lack amortization, such as quick sort.

Hmm I feel like the best way to "game" these interviews is just to learn solutions to the top 100 leetcode questions and then act as if you're figuring it out on the spot. That's what I started doing in preparation for a Facebook interview but I think that's not actually going to happen in the end anyway due to the hiring freeze and also the ridiculous H1B situation.

Recently gave an interview where they asked me to open my Leetcode profile, and checked if there are any prior submissions to the asked questions. ¯\(ツ)/¯

I sincerely hope you walked out of that interview without accommodating that request. Would hope you mind naming the company only so others can avoid it?

Treating a candidate as suspects seems to be a new low, even for the tech industry.

An interview is a two way street. That person probably did you a favor though by letting you know what your potential coworkers and/or company culture was about.

Interesting! I suppose one could prepare for that by having a second profile with just a few questions solved?

Solve all the questions you don't want them to ask!

Seems like a flawed system. I would just use a fake profile or say I only used CTCI as prep.

Nice, so now everyone has to further game the system by deleting their real profiles, making fake ones, and saying, "I don't use Leetcode."

>One common subtopic I would recommend having a basic familiarity with is amortized big-O, aka expected big-O, whereby you use some neat probability theory to say that the expected value of an operation is, for instance, O(1) even though sometimes it may be O(n) for individual calls.

Isn't he mixing two terms here?

If I recall correctly amortisation shows up in deterministic algorithms where some steps might frontload work that consecutively makes others easier. For instance you have some graph algorithm that looks at all the neighbours of some node in every iteration which means the runtime theoretically depends of the degree of the node, but if you can guarantee that each edge will only be inspected once your total time complexity only depends on the number of edges.

On the other hand expected time complexity is used when you run a probabilistic algorithm like quicksort, where individual sort calls actually have a variance in time complexity.

The first time I encountered a "riddle" type interview question, I'd already held 5+ jobs and I nominally had 8 years' experience in IT.

The job was for a Unix sysadmin job in academia. The interviewer described a room with two lightbulbs in it, and a room down the hall with two switches, and I was supposed to figure out which switch controlled which bulb without going back-and-forth so much.

I was stumped & didn't really know how to proceed, so I just gave up. They hired me anyway. Afterward they explained the answer to me. Start with both bulbs dark; turn on one switch, wait a few minutes, then turn on the other and touch the bulbs. The hot bulb corresponds to the first switch. (This only makes sense in the age of incandescent bulbs.)

I thought it was nice and a clever touch to see whether a candidate can think outside the box, and of course I was grateful to be hired even though I couldn't do so.

Oftentimes I'll report for an interview and it's more like a preliminary onboarding and tour of the premises. Sometimes a company has already made that hire decision before they call you in-person. This might raise a red flag for you, if a company is so desparate to put you at a desk that they don't even make you run the gauntlet, so think about it.

Obviously I don't get the question. But, two switches, two lightbulbs, can't you just turn one switch on, leave one switch off, and see which lightbulb is lit? You only interact with each room once. Unless there's some funny business going on?

Edit: oh, the bulbs need to be off at the end? Nah

I guess the idea is you turn both on for a while, then turn one off. The hottest one is the one that was recently turned off

but then wouldn't one of the switches still be on? therefore one of the lights would be on, so you could correlate which switch was on with the on light?

You'd turn off the second switch right before entering, so that the bulb associated with it would be hotter.

I had this same question on my first IT job interview. Stumped me also... I think now I'd probably do some interview prep next time. I didn't get the job. :-)

Why is the heat thing even necessary? Turn on one switch, walk down, see which light is on, process of elimination for the other one. Am I missing something?

I remember this version of the riddle:

- 1 light bulb and 3 switches outside. Determine which switch powers the bulb while only entering the room once.

There's also one with 3 switches and 3 bulbs; the solution is the same except you leave the third one on.

Bulbs nowadays are LED and don't get warm.

As an aside, this isn't really true. LEDs are way more efficient (more watts in visible light and not just heat), but not 100% so. They still get warm and need heat sinks and sometimes airflow, etc. or they can still overheat.

If you leave a LED bulb on for a while next to one that's been off, you can definitely feel the heat difference with your bare hands.

This is especially true at the higher end of lumen output, where you're optimizing for peak brightness instead of max efficiency. The power vs brightness curve isn't linear for a given emitter (and the human perception of brightness isn't linear either).

A LED that's twice as bright will be more than twice as hot. If you have a bright headlight it will typically be in metal housing that also doubles as a heat sink, and probably have internal thermo regulation to turn itself down before overheating.

It's also the big reason why low price LEDs barely last longer than incandescent did. The LED itself is not burning out, but the heat it generated cooks the capacitor used to generate the correct power output, which dies pretty quickly under heat stress.

Nowadays everyone and their mother has a smartphone on them. Place down your smartphone and start recording. Move to the switches and flip them as needed. Check back the recording to provide your answer.

LEDs themselves don't really get warm, but LED bulbs that plug into a wall socket have a transformer in their base to step mains voltage down to something the LED can handle, and that can get quite warm.

Turn on one. Wait a few years. Turn on the other. The one that is off has burned out so it is the first one.

You never touched a LED light bulb uh?

I was already halfway through the article when I realized I'd misunderstood the title: It's not about about using games to interview people (Factorio style), which still might have made sense to test self-taught engineers, but about how to game the interview process.

And honestly, it's not really about gaming the process, but succeeding in it. Gaming the process sounds to me like you are abusing some weakness in the system without doing the work required. That is not the case here imho.

For real, if you spend 100+ hours studying algorithms and system design you are not gaming anything. Gaming me would be finding out the questions before hand and memorizing the solutions.

I thought gaming was taking the optimal path, ie: min/maxing. Abusing a weakness in the system sounds more like "cheating" or "fraud."

I thought this article was about game development interviews.

Man I didn’t it read it as either of those. I was expecting it to be about interviewing at companies that make games (Blizzard, Rockstar, EA, etc.).

>Many companies in the tech industry have started moving away from traditional, technical whiteboard interviews, because they tend to bare little relevance to an employee’s day-to-day work

What companies? I have literally never interviewed anywhere that didn't run the standard cargo cult gamut.

The article is 5 years old. At the time, a lot of non-FAANG companies were moving away from this style of interview in favor of take home tests. That didn't last long.

Now they do take home tests and whiteboarding. Yippee!

Not to my knowledge, no.

I've seen people ask questions they can't answer on their own. Always ask self if you really want to work in a place that have this type of people in commanding positions.

Also given the saturation of the market with job offers YOU choose not they EMPLOYER. This might change in future but be aware of this current balance, you can game it.

Also even if you have infinite skill you might be not liked by random reason. That happens, bad/good days happen, interview is harder for interviewer than interviewee usually.

You are showing Your GOOD sides and he is assesing your BAD and GOOd sides.

There may a saturation of job offers but the offers aren’t not good. I’m not getting staff offers for $500k+/yr from random enterprise IT consultancy. I’d be lucky if I even got granted stock at many of these companies - let alone a $200k+ salary.

where do I apply for 500k USD/year job ?

FAANG offers plenty. See levels.fyi

> Given an array of integers, write a function that will remove all duplicates. (be sure to add the obligatory followup, what is its runtime?)

> The “aha” moment here comes if you realize that by sorting the input, you can just walk along the array with all duplicates being next to each other, resulting in an efficient solution.

You could also stick all the numbers in a set, since it seems like order doesn't matter…

Yeah, which improves the time complexity too. Plus many languages offer easy list to set conversion

It doesn't change the time complexity. Both are O(n). Your point about convenience stands, though.

Actually, if you go into fully pedantic mode, the set version is worse. Hash-based set insertion is commonly taken to be O(1), but that depends on hash comparison being O(1), which depends on using single-word hash values, which means your n is bounded by eg 2^63 (50% occupancy) or whatever. Honestly fine in practice, but hash lookup isn't "as" O(1) as indexing into an array. (ie, it requires a less realistic cost model.)

You also need your keys' length to be bounded by a constant. Otherwise just hashing everything will exceed O(n).

O(1) indexing into an array is a much bigger lie in practice than relying on single-word hash values. It breaks down much, much sooner which is why we have multiple levels of caches to try and hide this.

In reality random indexing is O(sqrt(n)) for 2D memory chips, and at best O(cbrt(n)) in our 3D physical world.

And adding two numbers is also O(m+n) where m, n is their length in bits, sure.

Does it? Set insertion is O(log n) and you need to insert n items.

Not if you use a hash set. This is expected O(n) time to de-duplicate an array of integers while maintaining the original order (more explicitly written than I normally would in Rust for didactical purposes):

    let mut hash_set = HashSet::new();
    let mut len = 0;

    for i in 0..arr.len() {
        if !hash_set.contains(&arr[i]) {
            hash_set.insert(arr[i]);
            arr[len] = arr[i];
            len += 1;
        }
    }

    arr.truncate(len);

Good point but it's not exactly a free lunch. You're trading memory for the speedup.

You can also use radix sort for what I'd like to call "fake" O(n) sort since physical hardware puts an upper limit on the hidden constant.

Radix sort generally places far more restrictions on the keys than a set would.

But to order a list is O(n log n)

In the worst case, you need to insert every element into your set to find out if there's no duplicate hence it'll take O(n log n) too

Not with a hash set - that gives you expected amortized O(1) insertion (yes, both expected and amortized). In contrast, a generalized sort is O(n log n), but you can sort numeric types in O(n).

So basic data structures and their Os, trees, proficiency with strings, sorting and recursion?

It doesnt feel like something really hard

The issue isn't telling people about basic things like you learn in a CS major - it's about taking random problems and solving them on a whiteboard without any errors (syntactically or otherwise) while explaining the solution, alternative solutions, and figuring out any gotchas that they love to throw in less than 20 minutes. An easier one would be something like this - https://leetcode.com/problems/combination-sum-ii/

By the time they've stated the problem and you went through the usual gotcha questions - you've already lost 5 minutes of the <20m you have.

It's just very intense and allows for very little margin of error. You have to be exceptionally on your game and used to solving these types of questions outside of an interview in <10 minutes.

I’ve been solving leetcode questions for a few months now. Primarily for fun because coding interviews aren’t really a thing in my country (salaries comparable to the US aren’t either).

It is a really interesting exercise and as you mentioned, there is a world of difference between knowing the basics and actually being able to solve those kind of problems on an interview level. It’s not uncommon for me to check the first test cases, submit my solution and then be screwed by the one edge case I did not think about.

Doing all of this in a 20 minute interview seems insane to me. I occasionally check out commonly asked FAANG questions on Leetcode and how people actually solve these kinds of problems in such a short time while communicating with an interviewer is beyond me.

Very important callout about the time.

Solving the problems alone in your personal environment is a completely different experience compared to being judged on the spot + knowing the person interviewing you is determining whether you get a 2x compensation boost + you need to solve the problem in 15 minutes and a single mistake in your reasoning steals precious time that you may not be able to recover.

I was comfortable solving mediums in about 30 minutes before I committed to my Facebook interview. I was devastated to find that not only is 30 minutes more than the 20 minutes they give me before moving on to another question, I was so stressed that my thinking process was significantly slowed.

I've seen some very bad interviewers that will fault you for non-perfect solutions, but most will have some sort of reasonable leeway in what they will take as a solution.

This experience varies too much for the individual. I've been given almost no leeway with all of my interviews. Most of my peers are in a similar bucket but I will admit - I seem to get some of the worst experience out of my peer group. I am often given more LC hards than my peers and still rejected even if I give multiple solutions with optimal complexity. At this point, we all suspect it's due to superficial factors but can't obviously do anything about it.

Some people I know who are URT would not even have to solve the problem to get a passing grade. Some know this and actively take advantage of it (and good for them) but others are blissfully unaware and are shocked when they find out that what they experience isn't the norm.

What is URT?

UnderRepresented Talent.

Given your clear technical expertise here and on Twitter, I would argue that you might just be performing better than most people, so "most interviewers" are more reasonable with you specifically.

I appreciate the confidence in my abilities, but I meant this more as a “good interviewers are ok with you making syntax errors (I mean, you usually don’t have a compiler) and minor issues with your code”. In fact I actually prefer to ignore off by ones and other annoying bits to ensure the interviewer understands that I know what I’m doing with the general algorithm, then go back and do a pass where I ensure these are correct to preempt a “can you run this on some input for me/how would you test this/why do you think it is correct”. If you indicate what you’re doing as you do it “this might be off by one, I’ll fix this bound later” it has usually worked for me. Not to discount your point; I can’t speak for everyone’s experiences of course, but this has been mine.

Take a stroll through LeetCode and you'll see that the hard part isn't memorizing all the "good approaches", it's understanding when to apply each and also whether you need to pull out parts of the algo or apply multiple.

Many of the questions don't have obvious solutions unless you've answered similar questions multiple times (or you have good recall and recall a pattern after seeing it just once), or you're able to tease out the "real problem" from the obfuscating English.

> a sorting algorithm may take O(n log(n)) runtime which is pretty common but be able to operate on an array in-place, only requiring O(n) storage.

If it's in-place the sorting might only require constant space and it can be O(1 ) [edit: in terms of space complexity]

Did you mean O(n)? It seems hard to sort n items without at least touching all of them once, which would make the time complexity linear (O(n)) instead of constant (O(1)). Or are you talking about storage needs? Then it sounds very hard to go sub-linear ... I'm confused.

I'm certainly not a good theoretical computer scientist, but I did quickly google this and I couldn't find any trace of constant-time sorting (unless you goalpost it to have O(n log n) processors, but that is kind of cheating, here).

The fiddly detail here is that big-O notation can be used to measure the usage of any resource, not just time. The poster above noted that an in-place sort might have constant space complexity -- although this only makes sense if you discount the space required for the input anyhow (which is literally linear in the input size!).

Wikipedia distinguishes two measures of space, "total" (including the input) and "auxiliary" (excluding the input). The poster above you is likely referring to auxiliary space.

Sorry, wasn't clear. Was talking about the space complexity. If you sort in-place you don't need O(n) space, you can do with O(1 ). Not talking about time complexity

They mean the amount of storage, and they're only counting additional memory allocated by the algorithm, and not the memory containing the input.

Well... sorting a shuffled deck of cards can be done in O(1) time.

    def sort(self):
        pass

    def __getitem__(i):
        suit = int(i / 13)
        rank = i % 13
        return f"{rank} of {('diamonds', 'hearts', 'spades', 'clubs')[suit]}"

O(1) would mean same storage requirement regardless of element count.

Yes. Simplest in-place example would be bubble sort. You might need a temp element for swaps, but that's it. Heap sort can also be done with constant space. You need of course O(n) space to store the original data; but that is not part of the sort algorithm.

PlEaSe WrItE a FizZBuZz In ThIs NoTePaD

writes fuzzbuzz on a notepad and shows it to the camera

Reply on news.ycombinator.com