First they say they don't like tricky questions, and then goes on to admit the "spec" is ambiguous. True, candidates are permitted to ask questions, but perhaps they are trusting of the interviewer and expect the question to be actionable as is? Or just the same, the candidates don't trust the interviewer and don't ask questions because they fear that'll result in a penalty? If you come from an environment where questions aren't rewarded - and there are plenty of those - then silence is likely.
Finally, it's worth mentioning, while the question + answer might correlate well with the hiring decision there's no mention to how well it predicts future performance. That said, there's a survivor bias at play so using it against performance might be iffy.
The skill under test is for that part is “can solve ambiguous problems”, and what you want to see is that the candidate is able to recognize that a problem is ambiguous.
I think the hard part is recognizing that a problem is ambiguous. Telling someone that a problem is ambiguous kind of defeats the point. IMO, it’s not about reading someone’s mind, but recognizing that there are multiple interpretations to what somebody has SAID. That seems less like a mind-reading technique and more like, you know, a communication skill.
I have gotten lots of ambiguous problems during my career, it seems only fair to have them appear during an interview.
The interviewer is expecting the interviewer to violate standard interview protocol? While the interviewee is perhaps desperate for a job? And the interviewer is - in his/her mind - thumping their chest about what a great and experienced interviewer they are?
I can't see how that's a success-minded plan for anyone involved.
I think what the author meant is that they dislike questions that require too specialized knowledge, so once you know the trick the question is easy to answer, but whether the candidate knows that particular trick is not otherwise correlated with candidate skill.
Frankly, I don't want to hire people who are too timid to ask a simple clarifying question in an interview.
A big part of this job is dealing with ambiguity and communication. If you feel the requirements of your task aren't clear, then go to the person who made the task and clarify them.
What's the alternative, exactly? Staying silent and waiting? Wasting time implementing the wrong solution?
Then make it clear that it's "real world" and that they can and should ask questions about aspects of it that they need more information on, rather than just hoping they do so.
Usually all interviewers will say “please take some time to consider the problem and ask any clarifying questions if you have any”. This is standard for all Amazon interviews.
That feels very formulaic, which is I guess par for the course for behemoth corporations.
If it were me, I would try and frame it like "this is an attempt to be a bit more 'real-world' where we've received some initial direction on what the results are supposed to look like from management, but don't consider any of it set in stone and I'm happy to talk you through it as if we were working together...". IDK the exact verbiage, but something that gets people in that mindset without straight up telling them "this is meant to be ambiguous, wink wink".
You're assuming the nervous stressed candidate can read your mind? That's not going to yield the best candidates. It's going to yield the candidates who are best "tuned" for the process.
I've already explained simple and obvious scenarios where the context can impact the candidates in sub-optimal ways.
If someone says, "Solve this" and the canidate attempts to do so, but that's not what was really expected? That's trickery (and foolish). On the other hand, if the interviewer wants, "Here's a problem, let's discuss..." then *that* is what the interviewer should lead with.
So context doesn't matter? And they're to blindly trust you? Because you said so [1]? Because they've never been screwed by an interviewer before? My sense is, you don't get out enough (i.e., be the candidate).
I hope the next time you do an interview the candidate asks, "Why should I trust you?" or "When was the last time you were the interviewee?"
[1] That's not how trust works. It is, by definition, earned.
It just sounds like you're projecting your poor interview experiences onto me.
If you can't take a statement as unambiguous as "feel free to ask questions at any time" at face value, then why even bother interviewing?
And for the record, I've been the candidate in plenty of interviews. I've done the 5-hour FAANG interviews and know how shitty they are. It's why I specifically designed the coding interview process at my company to be much more candidate friendly.
I agree with this... you're asked to do something and the interviewer is purposefully holding back information wanting you to come out and ask about it. That feels a bit tricky to me.
I do agree, the real job would habe to deal with ambiguity. But this is the interview. The interviewee has a completely different mindset going in. "Playing games" to see how they respond...that's for the likes of the NSA, CIA, etc.
"We can't find good candidates"? Nah. Your hiring process sucks. Get a mirror.
I have practically never seen a prd that did not have some ambiguity. I realised spotting ambiguity and asking questions is an essential and invaluable skill that needs to be selected for.
One of my teams was very surprised that I rejected a prd for being too vague and put my foot down that it will not be picked up until specific questions are answered. They were, I would not say meek, but resigned to the inevitability of product managers pushing poorly thought PRDs and not having any say in the matter.
I took my time training them to say no and spot ambiguities, and I like to think they have all become better developers and product managers for it. I always pick questions that have more than one obviously correct interpretation to see if the candidate notices it.
The idea that you trust your interviewer to provide a directly actionable question is strange. I would expect that in campus hirings, and for entry level fresh grads, but not to anyone with even a year of experience. At senior levels, it becomes more and more important to spot ambiguities and clarify them before they result in misunderstandings, wasted efforts, and worse. I trust a good interviewer to have a question that can provide them useful data points on candidates experience, skill, thought process and attitude.
Whether spotting ambiguities in the question has any correlation with future performance is harder to answer, but methodical people with attention to detail are preferrable to the alternative.
If the candidate comes from an environment where questions are penalised, they would be a bad fit for a team that values and expects questioning. It is somewhat unfair, but either way, the interviewers are selecting for their preferred qualities.
My username at a large org is my first name. In any situation where someone wants to link to me or mention me, typing my username brings up a list of every person at the org with my name, alphabetically. My last name inevitably sorts me down toward the bottom.
You would think that an exact literal username match would have priority, but no. Typing any prefix of my name similarly sorts everyone else before me too.
IMO, this interview question is going to get you amazing developer who fail to build anything of value.
I don't like the trick of failing candidates if they don't ask a question. 90% of this style of interview want candidates to rifle through solutions. If you want to talk about requirements, be explicit about it.
I'm really amazed that this "best interview" question really just boils down to leetcode for a _Senior Staff_ level interview. I don't know about y'all, but the _Senior Staff_ and _Principal_ developers I've worked with aren't wasting their time of shit like this. They're ironing out requirements. They're working with stakeholder. They're architecting systems. They're figuring out how to deliver the value the customer wants - and they're ensuring that it's actually the customer wants.
-----
There's a place for performance, but the fast running turd is still a turd.
> I'm really amazed that this "best interview" question really just boils down to leetcode for a _Senior Staff_ level interview.
A good interview should involve more than just a coding problem. But it should absolutely require at least one coding problem. It’s mind boggling the number of “senior” people with good resumes I’ve screened out in interviews over the years because, simple as a problem like this is, they really had no idea how to even start solving it.
I don’t know about the poster, but when I’ve done interviews - especially for senior people - there are a lot of different types of assessment I’d want to do before hiring them. I’d also want to assess their social skills somehow (eg get them to present to the team about something interesting). And ask some high level systems architecture questions, talk about their background, and more.
> Same with Microsoft's search in the start menu. Doesn't find Excel if I type "exc".
What do you get? I tried just now, and `E` gives me Excel. In fact, I typed "Esc" first on accident, and I got something different for "Es" but "Esc" gave me Excel too.
Ah, maybe the difference is that I disabled web search completely so it's limited to locally-installed stuff. If it's suggesting web results, I wonder if that's a deliberately-bad result for advertising reasons
Amazon’s VP of Search used to be Udi Manber, who literally wrote the book on Search. The crappiness of their search is deliberate, it is there to serve Amazon’s business objectives, not your needs.
The three solutions (n^2 time 1 space, n lg n time k space and n time n space) are basically the three strategies to perform a join in a relational database: a full table scan, a merge-join and a hash-join respectively.
"explain select" is a cool source of interview questions :)
Don't get me wrong - it's a totally fair question, frankly one I would have been happy to receive when I was interviewing for those roles.
I'm also a fan of whiteboarding coding interviews in general as a way of evaluating talent so no objections there.
There were just something about this specific question that just struck me as boring, souless, like who cares? I think my objection might be that it too closely resembles a menial task I might actually be given - something that I hope to God the upcoming LLM advances automates away.
yeah, unfortunate "hard studying student who eats algorithms for breakfast" compared to "boring reality". I'm sure there's a fancy data structure for this. In reality, I'd make three buckets (one for each day, and a "isLoyal" byte buffer), and update them as I scan along. O(N) time, O(N) space.
"they don’t know the size of the data upfront", okay. I spend a scan finding the highest customer number and probably make some 10MB index-assossiated buffer. If I'm fancy I find the range and use offset indices to reduce the overall size. You already said it fits in memory and I'm not a distsrubuted programmer. Space is cheap in boring reality
I guess it's one of those cool brain teasers that gets you excited to use your skills from college. Not many get to in reality. Or they prefer other domain-specific skills.
It's a good question, and the author explains it and the logic really well.
As someone going through this style of interview at the moment (but not having interviewed at Google, Microsoft or Amazon), two things jump out at me:
- If you're going to ask this question and get it done in 1 hour, does the code really matter? I'd argue that if you can get to a good or optimal solution, 99 times out of 100 you can write the code. If I got this question and didn't know better, I'd be stressing about writing the code within an hour. Knowing that we wanted to spend most of the time discussing the algos and data structures would be really useful to me. Maybe Google/Amazon/Microsoft interviews really stress this in their preamble, I don't know.
- The big "issue" I see with this question is that it relies on the interviewer knowing exactly how to steer the conversation. I think I could get to this solution with the hints, and the author seems to imply that it's ok to need a few hints. But an interviewer that doesn't know the right hints to give (or phrases them poorly) is going to turn this question into a train-wreck. This isn't an issue for the author, they clearly know this questions backwards and forwards. But giving this question as a 'standard' question that others will deliver? I think it could easily end up being too conservative and cutting out a lot of otherwise smart developers.
In general, that's my criticism of this style of question: they all claim that they're about 'seeing how you think'. But I think expecting interviewers to be able to elicit a conversation that really shows 'how a candidate thinks' is much more on the interviewer rather than the interviewee. You're expecting people whose primary job is writing software to be really good at delivering interviews.
Instead, you're going to have candidates who most of the time will do well if they can pattern-matching against problems they've seen in the past, and poorly otherwise. I can see how questions like this seem good on paper, and I'm glad this question works for the author. But it's the combination of interviewer and question that makes it effective, not just the question alone. A better title for this post might be 'My favourite way of interviewing candidates', because this post is mostly to do with the author's mental model of how to run an interview with this question.
You could get to something working and relatively bug free in 15 minutes with a shell script consisting of little more than cut, head, sort -u, and grep.
Sorting, merging, then just a clever unique was basically the only thing I'd consider.
If I used this question I'd add to it.
"Pretend you have to do the work on an Arduino uno, which has very little resources. Your uno can request input and produce output from the disk where these are stored at whatever offset you wish. The log files are 100GB each and sit on a desktop computer with a modern Linux on it. Each log line is 512B. You can create files if you need to through some unspecified protocol with the desktop computer. But the desktop computer must be dumb. It will only write to and read from disk. You can send it any disk system call you wish. Step 2; Now do it without sorting or something absurdly slow"
The point is to ask for actual creative solutions instead of the pattern recognition problems that most of these problem formats are.
You want something that a weekend of drilling won't change the result of
And my favorite answer to questions like this is, "Can I just use grep (or shell commands in general)?"
Grep, uniq, wc, and a few others can be treated as pipeline data transformers to answer questions like this interview question. As long as you make some smart decisions about the order of operations, you can usually get performance on par with what you might write custom code for.
And one of the appropriate questions would be, “Is this a one-off or rare request, or does this need to be productionized? And how sensitive is the response time? And if it must be fast and frequent, then why are we not using some form of indexed db”
> I’ve actually expressed the problem in an ambiguous way.
> Did I mean 2 unique pages per day or overall?
The author needs a course in logic. "They visited at least two unique pages." is not ambiguous. Visiting page A on day 1 and visiting page B on day 2 makes the sentence true.
Assuming the quoted wording is the actual question he gives, it's not ambiguous. With the given wording, a person hearing it and understanding that it's stated precisely without ambiguity shouldn't be dinged for not questioning the interviewer's ability to recognize the requirements are unambiguous. Because it's an _interview_ by a technical professional who thought about the problem beforehand and not someone who you should be worried about not understanding what they are asking. In fact, I can imagine another interviewer that would ask you the exact same thing and ding you for asking a stupid question.
Interviews are just not the same thing as real life requirements gathering, so people's thought processes will not be the same. Even if you try to roleplay as someone that doesn't understand how to state requirements precisely, all of the normal procedures and thought processes for sussing that out are compromised due to the inrerview setting. And your ability to assess those processes are compromised due to how familiar you are with the question and how much you've deconstructed it.
It's not the time to be tricky (though somehow simultaneously believing it is and is not a trick question). There's so many more interesting things that could be gleaned from a person's interview performance that "is this interviewer playing fuck-fuck games with me" doesn't rate whatsoever.
Does visiting pages A and B on day 1 and visiting page A on day 2 also make the sentence true? I think that's the source of ambiguity (or maybe it's ambiguous to me only because English is not my native language).
The user has visited A and B on day 1, and A on day 2.
So the total page hits is (A, B, A). Remove duplicates and you have (A, B) which makes the sentence true.
The noun is not the issue but rather the scope of uniqueness:
>Now, given two log files (log file from day 1 and log file from day 2) we want to generate a list of ‘loyal customers’ that meet the criteria of: (a) they came on both days, and (b) they visited at least two unique pages.
It appears to me that the requirement could be interpreted as either:
"(visit on day 1) AND (visit on day 2) AND (total unique pages count > 2)"
a clearer way to put it would be "visited at least two unique pages in total"
or
"(visit at least two unique pages on day 1) AND (visit at least two unique pages on day 2)"
a clearer way to put it would be "visited at least two unique pages on each day"
Most people typically do not form sentences based on pure logic, and many things could reasonable be misinterpreted even if purely logically it's unambiguous. Language is not math.
For fun, I fed this interview question to GPT-4 with aider. See the chat transcript linked below.
The data structures look sensible and it did most of what the interviewer wanted on the first try.
It did make the wrong initial assumption that we wanted 2 unique pages per day. When prompted with a clarification, it made a sensible fix.
When asked to optimize, it went for big hammers like parallel processing and caching. As opposed to saving memory by only storing one file in the data structure as the author discussed.
Asking candidates to come up with this kind of solution in an interview setting where they are under all kinds of pressure is honestly dehumanizing.
There's a lot of good insight in the article about the correct way to approach the problem, but asking anyone to come up with it on the spot is unrealistic. You have the benefit of having seen the problem before with time on your side to reflect on it. They haven't.
When I do interviews like this, I prefer to talk them through the problem together, like we were actual teammates working on a problem together. That more closely relates to life on the job, which to me is the point of interviewing someone.
Many people (especially from big tech backgrounds), treat interviews as "the time for the candidate to prove that they are good enough to work at my company". I, like you, prefer to use the time for collaborative problem solving to try and get as much signal as possible about whether it would be fruitful for us to work together, while also trying to figure out if we would want to work together.
The "is this person good enough for me" interview allows geniuses who are assholes through. I prefer to filter for good teammates.
The question asked doesn’t involved any computer science algorithm knowledge at all, nowhere near leet code complexity.
Only the basics that are close to everyday programming work: write a for-loop, know what a Map/dict is, and Google for “how to read a file”. If a candidate can’t do that, they can’t really program. ChatGPT can probably code this answer.
If this is considered dehumanizing, I'm concerned for the future of our industry. Anyone with even a first undergraduate algorithms course should immediately spit out "sort by customer and page, then stream the output".
I wouldn't expect everyone to immediately see the optimizations -- you can sort the days individually, you can drop all but a small number of pages per customer -- immediately, but I would be disappointed if someone couldn't be hinted there by the end of a 30 minute interview.
Failing to even get the O(n log n) solution tells me that someone should never have graduated.
> Failing to even get the O(n log n) solution tells me that someone should never have graduated.
This is something I wonder about in my comment sidethread - to me, the natural solution is the O(n) one in O(n) space.
I see that the O(n log n) solution requires O(1) space to run. But it requires O(n) space to return a result! Is that actually better than O(n) time and O(n) space?
Either of those solutions is ok from a junior developer.
From a senior developer, I would expect a discussion of in-core vs. out-of-core operations, and the fact that hash tables (even if they fit into RAM) aren't really O(1) time per operation since random access to large address spaces runs into e.g. TLB misses.
Given that the depth of the page table tree is fixed at 3/4/5 depending on the architecture and kernel, I think most people would be confused if asked whether the average complexity of a hash table lookup is always really O(1).
Even senior developers that understand the TLB would likely think of it as "O(1), but with a big constant factor".
On a side note, one thing that the article doesn't mention is the possibility of using a Bloom filter. It trades an extra scan of a file for smaller hash tables/smaller set to sort with external sort.
Yup, was surprised bloom filters weren't even mentioned in passing. I suck but still it's crazy to see some people genuinely would have a problem getting the O(n) solution when they've been in the industry for more than 5-10 years
Whether you get a cache miss or hit is part of 'c', or whether those bytes are fetched over WAN. Big oh of one just means lookup time is a constant and is independent of data size. The big oh doesn't change if move from a SSD to a tape drive
Thus, those operations are really O(1)
Big oh is the infimum function such that for an arbitrarily large N, the runtime of the algorithm is then strictly larger than C times the big oh function. (Paraphrasing there a bit, and on a phone, apologies for not pasting the exact definition)
In a formal sense, anything you can compute on a computer is O(1) since there's only a finite number of states. But we tend to hand-wave that away.
Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.
> In a formal sense, anything you can compute on a computer is O(1)
I don't think the definition of Big-Oh supports that conclusion.
"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity." [1]
"For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n^2 − 2n + 2.... As n grows large, the n^2 term will come to dominate,... say that the algorithm has order of n^2 time complexity" [1]
> Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.
Indeed, but I can choose a value "C" that is large enough to negate any of the differences between cache miss or hit.
Let's say "N" is the number of lines in one of our text files. Once we have put that data into a hashtable, the claim is then that lookup time is O(1). You counter, and state, no, the lookup time is potentially 30ms, or even 100ms (making up the numbers). For my claim that the lookup time of O(1) to be true, I can pick any value of 'C'. So I choose 1 million. I'm basically saying, lookup times will always be under 1 hour. Given our precondition that we have built this hashtable, no matter how we get the data, yes - it will be under 1 hour. If we used carrier pigeon with USB stick, we could just choose a larger value for C and still be correct.
The idea is basically, if you have something like N^2 + N^1, eventually when N is large enough, n^2 will become so dominant that you could multiple by it by a fixed value to wash away all the other terms in the expression.
Thus, while the actual lookup time can and will vary, it is still bounded. Keep in mind as well there are different functions for best case and average case performance. These notations do take into account that the per-instance lookup time can vary.
> Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.
Wait, don't the inner nodes of the page table contain the _physical_ addresses of its child nodes? Wouldn't that make it a most one TLB miss per hash table lookup (assuming key and value are adjacent in the hash table bucket)?
It depends how you define "TLB miss". Read it as "paging table reads" if that's clearer.
If you have a 64-entry TLB and 4kB pages, then you can do random memory accesses (aka hash table accesses) up to 256 kB without any paging table reads; up to ~16 MB with one paging table read per operation; and up to ~1GB with two paging table reads per operation. (This, of course, is why large databases use superpages when possible; but while that pushes the limits back it doesn't eliminate them.)
In virtual machines there's further overhead since you have "virtual physical" addresses...
Bounded by a constant does not mean constant lookup time.
Let's say the runtime of some function is (x1n + x2n + x3n), where x1, x2, and x3 represent the L1,L2 l3 cache lookup times.
A function F is called big-oh of function G if there exists a value C such that CF is strictly greater for all sufficiently large values of N
For the above example, let's say I choose the value one billion for C. Is it true that 1 billion times n will be greater than the sum of (x1+x2+x3)n. The answer is yes, thus, f(n) = n is big-oh
(x1+x2+x3)n. In other words, at a certain size of n, we can pick a constant multiple that dominates the other terms. This is in part why asymptotic functions are independent of hardware. Even if L3 cache were actually virtual and fetched over a network, I could still just choose a larger constant. If you can't choose such a constant, then chances are you need a faster growing function like n-squared
I'd expect talking about TLB misses as a junior engineer thing. That's stuff you learn in school.
Id expect senior engineers to talk about how they will monitor this system, and to bring up things like customers we know we don't trust.
A senior engineer might tell you that running into TLB issues makes a suggestion that your approach is wrong and it's about time to move the solution to your data warehouse
With the sorting solution, you can stream the result directly to a file _without_ holding the entire file in memory. So it can be better if you are memory constrained (e.g. if the files are bigger than what you can hold in memory), or if you want to hold the working set inside the CPU L3 cache as 'cperciva is alluding to.
> If this is considered dehumanizing, I'm concerned for the future of our industry. Anyone with even a first undergraduate algorithms course should immediately spit out "sort by customer and page, then stream the output".
Well yes, but that's not what this is about. It's about social pressure, not ability.
I could program this for you right now if I wanted to; most "optimisations" seemed the "obvious ones" to me, so I guess I would have passed. I could also program it in a hurry at ludicrous speed under pressure because all of production is down or whatever.
But ... I wouldn't be able to program this in an interview setting.
Last time I was asked a bunch of even easier things (in a timed interview, no less), where I literally have some exact code on my GitHub. I just couldn't finish it. Not because I can't "get" it, but because programming while two strangers are judging your every keystroke and commenting on what you're doing is just nerve-wrecking.
I have a non traditional background (non comp sci) and while I understand complexity I wouldn’t have immediately arrived at the solution like this.
I think that rather, I would have done well because I know after doing hundreds of these both as the interviewer and the interviewee that using some sort of Map along with some vague rumblings of “space/time complexity tradeoff” is very often the solution for these types of questions. So I would have immediately gone there first by instinct.
Sadly I know plenty of Seniors with 15 or so years of experience. That would write brute force and it still wouldn't work right.
Senior in a perfect world sure but the reality is that for decades ppl have been desperate for talent and so you don't have to do much to get by.
I knew a popular principle engineer at a fortune 50 company who was loved by execs. He would check in 5 or 10 of the same file. Opposite of the dry principle.
I don’t about that, I mean - if you’re going to be in a position where this level of craftsmanship is necessary, then why shouldn’t the interviewer require that you demonstrate your ability to do so? It’s not a trick question, it isn’t unrealistic or impractical, it just spotlights a particular programming focus, performance.
Agree. Our interview technique is a trimmed down but somewhat realistic coding exercise. We do it as a pair programming exercise and we tell them up-front that this should be an interactive and positive experience, we're not trying to trick them or put them under pressure. It'll test the candidates ability to actually do the job they'll be doing if we hire them, which is to write code in an IDE. We do it with them, so they can ask questions on libraries they're not familiar with and so on. Obviously we're not going to solve the problems in exercise for them, but if they do get stuck, we'll help move them forward.
The coding exercise will involve writing tests, deisgn of classes, working with floating point arithmetic, working across thread barriers, some fairly standard maths, and so on.
I actually can't say we're hired a bad candidate yet and they all report that the interview is a positive experience.
In my fairly long career I've been through about 10-15 interview processes. A few of them were quite toxic and those were the "just cram leetcode for months" type. I never want to inflict that on someone else.
While I like your approach better than his by a considerable margin... I would say his approach has merits since he's a principle engineer at google(maybe hiring there) and was an engineer hiring at amazon. the problems they face would definitely have this applicability of a large volume of data needing to be worked on efficiently.
I actually think the question from the blog is a good one and I've used similar at previous roles. It may consist of one part of the interview process. I think in hindsight I was more responding to the overall ethos were some interviews are conducted in an unduly abrasive manner.
> I prefer to talk them through the problem together, like we were actual teammates working on a problem together.
If a colleague came to me to discuss a question this basic, I'd want them PIPed out. This is miles from the complexity of problems that require collaboration. It's a shell pipeline that I'd write with sort/uniq in less than five minutes. I just did it to make sure my estimate wasn't wrong:
Maintainable? No. Done iteratively in less than five minutes? Yes.
If your perspective is that it's unrealistic to ask anyone to come up with an answer to this question on the spot, you should take a long, hard look at yourself and the quality of your colleagues.
As mentioned over and over. This isn't about the ability to do it. This is about making it less of a hazing ritual that generally only seeks to make the interviewer have a sense of importance.
How isn't remotely relevant to being able to accomplish the task.
I only know how certain SQL engines implement queries because I was tasked at that point to increase the speed of the queries, and went deep into the debugging level detail to understand the exact cost of each action.
But I haven't done that in 7 years, and couldn't tell you much more than the tools used to figure it out.
I cannot remotely understand the requirements people make up for our jobs that have nothing to do with doing our jobs.
I've become partial to interview questions where the interviewee just has to build something like a rock paper scissors game or command line to do list app. Simple prompt, easily extendable as well. It's jarring how many people with 5+ years of experience completely fail on this kind of interview.
Any experienced engineer should have no trouble with it. There's no hiding here. - candidate just needs to deliver something working, something relatively clean, and be reasonably pleasant to pair with. No leetcode grinding necessary, though I have found that those who did well on this problem also generally got high scores from my colleagues who do ask LC questions.
I somehow ended up responsible for the coding interview part at a small startup, and I'm pleased to say that it doesn't involve any niche algorithm memorization or specific language knowledge.
It's really just a scenario with some mockup third-party API docs, where the applicant needs to write some paeudocode that checks different conditions, arranges the data, and ties together the different calls.
It might not be testing every possible skill the applicant has, but at least it's in-line with one of the tasks we actually expect them to perform regularly.
> No great engineer should ever settle for an O(n²) algorithm, unless bound by memory or some other unmovable constraint.
What if this is a one-off to produce a business report? Would it make sense to use programmer time to create an O(n) structure in memory, or just loop through the files line by line and let the CPU take a minute or five, or thirty? What is the programming language - something that has a library for this or something very low level where we’d read the file byte by byte?
If we’re dealing with the latter, a small amount of data, and a one off report, I don’t care at all in my work whether an engineer I’m managing somehow writes it in O(n^3).
It’s interesting how quick to judge the author is - ask this question for points, don’t even think about that, don’t mention arrays because they’re fixed size (despite implementations for dynamically allocated arrays totally existing and the candidate might be coming from that), and so on. Some humility would be nice.
Although I think what they wrote is very valuable, as this is how many interviews go. And I have to at least appreciate the author’s approach for trying to start a conversation, even if he still takes a rather reductive approach to evaluating candidates.
I used a brute force-y approach that meets the requirements, saves millions in operational costs (vs hiring engineers to build and maintain the complex non-brute-force solution).
Unfortunately people don’t think about actual engineering cost of “optimal” solutions. Engineering costs are part of operational costs and need to be juxtaposed against compute.
You can get a lot more mileage out of running the largest EC2 instance for a year vs hiring a junior engineer.
Why would only the non-bruteforce solution require hiring an engineer to maintain it? Does the brute force solution spontaneously manifest and maintains itself?
It's not just hiring one engineer, it's hiring a whole engineering department because that solution involves symbolic execution plus a few other things that I can not speak about without compromising my employment. The two solutions are in entirely different leagues in terms of engineering complexity.
The bruteforce solution is simple enough that can be maintained by junior engineers.
Add a few mid and senior engineers, and it can become significantly more efficient, without requiring the resources of the optimal solution while still being classified "brute-force".
It is yet another way the bitter lesson manifests [1].
The highest core count machine you can get on EC2 is like 45k per annum, which is peanuts compared to the cost of the team required to build the perfect solution.
The issue here is not brute-force vs optimized. It is over engineering. Why spend 10 minutes optimizing your program when you can spend two weeks over engineering it.
Had I been in your shoes, I'd accept that there things I am not privy to, and therefore I can't have the full picture and thus I can't exercise judgement. Instead I'd try to understand what the other person is telling me - especially on HN - instead of jumping to conclusions.
A complete and efficient solution would take 2+ years plus a very senior, very specialized engineering team chasing a moonshot.
A brute-force approach that can leverage compute is far more efficient in engineering time, operational costs (eng time vs compute), and opportunity cost.
This isn't something that can be optimized in 10 minutes, and insinuating that while digging further suggests that haven't dealt with truly complex engineering problems.
I would argue that in most cases where performance isn’t a constraint, the first algorithm that comes to mind is probably the most optimal choice. He even says:
> About 80% of the candidates go for the naive solution first. It’s easiest and most natural.
The “naive solution” will be easier to understand and maintain. Why make it harder if it doesn’t add value?
The nearly optimal solution is effectively just as easy to understand and maintain and frankly should come even more naturally to an engineer than the O(n^2) version.
But even more importantly, with a slightly better solution I don’t get woken up in the night once a week because some buffoon left behind a hundred of these little performance landmines that worked great when the table had ten rows on their dev box but causes an outage in prod the second we hit some critical threshold of data.
This takes all sorts of forms from people using quadratic time or quadratic memory to my personal favorite: pulling entire database tables across the network to do basic analytics.
The authors always have the same excuse, that “it worked good enough for what was needed at the time”, ignoring the simple fact that the version which wouldn’t have caused an outage would have been just as easy from day one.
Of course, using the correct date structure is least an engineer can do. But the point is that it doesn’t matter quite often. You’re describing a situation where it matters. Which it doesn’t always.
It doesn't always, but I'll be blunt: if you find yourself frequently writing O(n^2) or O(m * n) algorithms where n, m aren't fundamentally small values, you are doing a massive disservice to your coworkers. There is very rarely any meaningful cost to using something better, and that better thing should come more or less instinctively for the overwhelming majority of cases by the time you have even a little experience as a software engineer. These types of algorithms should immediately jump out at you as a least an orange flag if not a red one.
If you aren't doing better because you don't care, you're inflicting the costs your apathy on everyone else around you. If you aren't doing better because nested for loops is the most ergonomic solution for virtually every problem in your language of choice, you need to reevaluate your choices.
Everything doesn't have to be overengineered to death, but that's a far cry from being okay with regularly and intentionally choosing the actual worst solution that is all but guaranteed to blow up under any kind of growth.
The thing is, compilers are pretty amazing beasts. CPUs are pretty amazing beasts. "10,000" is a very small value of "N", given those two factors.
I've worked with a lot of engineers that considered anything O(n^2) to be a red flag, and half the time the actual performance profiling favored the naive method simply because the compiler optimized it better.
That means that if you actually care about performance, you've got to spend 30 minutes profiling for most real world scenarios. Yeah, O(n^2) is obviously a crazy bad idea if you ever expect to scale to ten million records, but the vast majority of software being written is handing tiny 10K files, and a very large chunk of it doesn't care at all about performance because network latency eclipses any possible performance gain.
And this is how we end up with situations like GTA5 taking several minutes to parse a JSON in production, because nobody did actually test it with real-world values of n (or at least didn't expect it to increase over the product lifetime)
The right lesson to learn here is "manage and maintain your software as it's used in the real world, as that will tell you where you need to invest time" not "prematurely optimize every algorithm just in case it becomes a problem".
No, the right lesson here is that quadratic algorithms are a particularly nasty middle ground of seeming to work for the small n of development and initial rollout but falling over for the medium to large n of living in production.
Luckily they’re typically easy to notice, and better approaches are often as easy as sorting your input first or caching items in a hash table.
An engineer should therefore catch these things when writing them or in code review and make sure a slightly better option is used in any situation where the size of input has a reasonable chance of growing.
The cost is nearly nothing and the benefit is not shipping code that will virtually guarantee slow response times and bloated scaling costs at best and humans being woken up at night for outages at worst.
Unless you are in a very hot path and know with absolute certainty that n will remain very low, I'd say you are doing clear premature optimization by comparing and choosing the O(n^2).
I say very small because to me, n=10_000 sounds like a number that could easily and quickly grow higher since yoy are past a basic enumeration of a few choices.
I said “regularly or intentionally”, because I wanted to differentiate that that is what I have a particular problem with.
And yes, a really one-off business report is fine. As long as it runs and produces an anccurate answer, that is fine. Which is why I distinguished that if you find yourself regularly writing these kinds of algorithms and not having alarm bells going off in your head, that is almost certainly a problem.
I have never in 25 years encountered someone who spent noticeably too long optimizing running time for software that wasn’t performance critical. I have had to respond to at least two to four cases per year where somebody assumed a small case would remain small forever (or just didn’t think about it at all) and caused an outage, a severely bloated AWS bill (unbounded autoscaling + quadratic), or some other completely avoidable hell.
The problem is even if this is "known" upfront things always end up changing.
Unless the code is truly throw away code and not checked into source control.
I'm maybe guilty of being too harsh with this sometimes but the amount of times half-assed code has woken me up has trained me to be very critical of assumptions like this.
There's places where writing bad shitty code doesn't matter but frankly I'd rather be at places and rather have colleagues and an environment where we don't write bad shitty code.
The attempts to circumstantially excuse away shitty answers goes against the desire to just not be shit.
The author here seemed able and willing to talk through constraints & issues. Their first paragraphs practically begged for it, as a sign of maturity. Rather than just excuse away shitty solutions, my hope is, even if you are not a super competent can-do coder, you at least can talk through and walk through problems with people that are trustable, to arrive at reasonably competent capable answers.
Even you are doing some one off analysis, having to wait several minutes can be annoying. And the non-quadratic solutions are not harder than the quadratic one.
You can do a little better than that. Each item in your map has exactly 3 states:
- We’ve seen this customer visit one unique page with (xx) url on the first day
- We’ve seen this customer visit two unique pages - but only on the first day.
- We’ve seen the customer visit one unique page (xx) and they’ve visited on both days.
In the second state you don’t actually care what the URLs are. And I think the logic for the 3rd state is identical to the logic for the 1st state - since you only add them as a “loyal customer” by visiting them again on the second day. So I think you can get away with using an Option<Url> to store the state instead of a Set or a list. (Though I’d probably use a custom parametric enum for clarity).
It’s a great problem to model using a state machine.
Ah yes where have I heard that "oh my question is so non tricky that you just have to think rationally and I am only looking for your willingness and ability to converse and you will do fine. But most people fail it because they can't have normal conversations".
"Let us hire this person because they dint solve the problem but were a great conversationalist problem solver" - said nobody at a standardized hiring committee!
I worked with someone who was hired because they were likeable, even though they didn’t meet the technical bar. It was a really good decision. They improved the overall atmosphere of the office and made it a nicer place to work.
I think likeability is way too penalized these days (bias). Likeability is actually a useful trait in a team for cohesion and empathy as long as you have processes and culture to identify/manage coasting, sociopathy and toxic behavior.
> In theory you could write a pretty simple SQL query, and sure, Big Tech companies have giant data warehouses where you can easily do this sort of thing. But for the scope of a coding interview, you wouldn’t want to. Since this is not a distributed systems problem and the data fits in memory, why introduce the additional complexity and dependencies of a database for something that you can solve with 20 lines of simple code?
My first thought on an actual implementation was, if this is a one-off request, to import it into sqlite. No need to set up a big system, and I think it would be easier/faster than writing those 20 lines of code. Also a hell of a lot easier to iterate on minor spec tweaks like the unique pages overall vs per day clarification. And probably less likely to have off-by-one type of bugs, since the simple logic is handled by the database itself. Bonus, it does handle the case where the dataset is larger than memory!
Yep. I estimate if the files are over 10 million lines, I'd rather use SQLite. They'd probably still fit into memory, but that's where I'd put up with the up-front hassle of SQLite so that I don't have to reparse CSV in Python / Lua / whatever I'm writing this script in
But a point lost because you may need to go out of your way to avoid hitting row limits. “I’m using a proprietary tool that has serious issues with more than 2^20 rows” is not so awesome.
It wouldn't surprise me if the O(n log n) sorting solution is faster than the O(n) hashing solution, because of better memory locality.
The first answer that popped into my head was a shell pipeline, "cat file1 file2 | sort -k [pattern for customer ID] | awk -f ..." where the awk part just scans the sort output and checks for both dates and two pages within each customer-ID cluster. So maybe 10 lines of awk. It didn't occur to me to use hash tables. Overall it seems like a lame problem, given how big today's machines are: 10,000 page views per second for 2 days, crunching each record into 64 bits, means you can sort everything in memory. If 10 million views per second then maybe we can talk about a hadoop cluster. But 10k a second is an awfully busy site.
I actually had a real-life problem sort of like this a while back, with around 500 million records, and it took a few hours using the Unix command line sort utility on a single machine. That approach generally beat databases solidly.
It uses whatever amount of RAM you tell it to. I think the default is 1MB, which is way too small. It uses external sorting which means it uses O(1) RAM and O(N) temporary disk space. Oversimplified: it reads fixed sized chunks from the input, sorts each chunk in RAM and writes each sorted chunk to its own temp disk file, then merges the sorted disk files. If there are a huge number of temp files, it can merge them recursively, converting groups of shorter files into single longer ones, then merging the longer ones. I'd set the chunk size to a few GB depending on the amount of ram available.
That is basically how everything worked back when 1MB was a lot of memory. The temp files were even on magtape rather than disk. Old movie clips of computer rooms full of magtape drives jumping around, were probably running a sorting procedure of some type. E.g. if you had a telephone in the 1960s, they ran something like that once a month to generate your phone bill with itemized calls. A lot of Knuth volume 3 is still about how to do that.
These days you'd do very large sorting operations (say for a web search engine indexing 1000's of TB of data) with Hadoop or MapReduce or the like. Basically you split the data across 1000s of computers, let each computer do its own sorting operation so you can use all the CPU's and RAM at the same time, and then do the final merge stage between the computers over fast local networks.
I've used the Unix sort program on inputs as large as 500GB and it works fine with a few GB of memory. It does take a while, but so what.
If the job is log file processing, it's an entirely reasonable question.
But most jobs are not log file processing.
It's ridiculous to generalise this sort of thing:
"We are cooking soup here at Amazon Soup Kitchen. My favorite interview question is to ask candidates to bake a cake, that's the real test of any cook."
The question is not about log processing; that is just a framing device. The interviewer does not care whether you can process log files, specifically; the interviewer cares whether you understand basic data structures and know how to make reasonable tradeoffs between time and space complexity, generally.
The people who criticize these questions do so out of insecurity - they know they aren't at the level required to solve it, which is embarrassing because it's pretty simple stuff, so they try to poke holes in it and justify their ineptitude with comments like the one you're responding to.
This article mentions "good" and "great" candidates many times.
How is the author determining which candidates are great? Do "great" candidates answer the questions the best, or is the interviewer following up 1-2 years after hire and examining the impact of the person?
Great candidates aren't those who can answer DS & algorithms questions the best, but it seems that the author thinks that way.
I agree with most points in the article except for the database part.
> Since this is not a distributed systems problem and the data fits in memory, why introduce the additional complexity and dependencies of a database for something that you can solve with 20 lines of simple code?
Because this is a question about getting the right data, and SQL Databases are...extremely good for filtering, sorting and grouping... data. Besides, every page visit from every client is a unique observation, and the principle of...tidy data suggests that every observation use a database row.
Why solve this with 20 lines of code, when you can solve it in a 4 line SQL query?
236 comments
[ 6.6 ms ] story [ 3074 ms ] threadFinally, it's worth mentioning, while the question + answer might correlate well with the hiring decision there's no mention to how well it predicts future performance. That said, there's a survivor bias at play so using it against performance might be iffy.
What’s the old xkcd: “communicating poorly then acting smug when you’re misunderstood is not cleverness.”
I think the hard part is recognizing that a problem is ambiguous. Telling someone that a problem is ambiguous kind of defeats the point. IMO, it’s not about reading someone’s mind, but recognizing that there are multiple interpretations to what somebody has SAID. That seems less like a mind-reading technique and more like, you know, a communication skill.
I have gotten lots of ambiguous problems during my career, it seems only fair to have them appear during an interview.
I can't see how that's a success-minded plan for anyone involved.
That aside, the candidate definitely has to err to the side of caution. There's also typically a time limit, yes?
That's protocol.
A big part of this job is dealing with ambiguity and communication. If you feel the requirements of your task aren't clear, then go to the person who made the task and clarify them. What's the alternative, exactly? Staying silent and waiting? Wasting time implementing the wrong solution?
Source: Conducted 250+ interviews in Amazon.
If it were me, I would try and frame it like "this is an attempt to be a bit more 'real-world' where we've received some initial direction on what the results are supposed to look like from management, but don't consider any of it set in stone and I'm happy to talk you through it as if we were working together...". IDK the exact verbiage, but something that gets people in that mindset without straight up telling them "this is meant to be ambiguous, wink wink".
I've already explained simple and obvious scenarios where the context can impact the candidates in sub-optimal ways.
If someone says, "Solve this" and the canidate attempts to do so, but that's not what was really expected? That's trickery (and foolish). On the other hand, if the interviewer wants, "Here's a problem, let's discuss..." then *that* is what the interviewer should lead with.
I hope the next time you do an interview the candidate asks, "Why should I trust you?" or "When was the last time you were the interviewee?"
[1] That's not how trust works. It is, by definition, earned.
It just sounds like you're projecting your poor interview experiences onto me.
If you can't take a statement as unambiguous as "feel free to ask questions at any time" at face value, then why even bother interviewing?
And for the record, I've been the candidate in plenty of interviews. I've done the 5-hour FAANG interviews and know how shitty they are. It's why I specifically designed the coding interview process at my company to be much more candidate friendly.
1) You don't understand human nature in the context of interviews.
2) You're making it about you and how exceptional you are, and have forgotten you're only half - at best - of the process
3) You've forgotten that - directly or indirectly - you are also being interviewed (by the candidate).
4) It's (all but) 2024. 20th Century mindsets need to die already.
This isn't about my experience(s). This is about having a proper and healthy understanding of the paradigm / process.
I appreciate your input. I hope you appreciate mine (but I doubt it).
I do agree, the real job would habe to deal with ambiguity. But this is the interview. The interviewee has a completely different mindset going in. "Playing games" to see how they respond...that's for the likes of the NSA, CIA, etc.
"We can't find good candidates"? Nah. Your hiring process sucks. Get a mirror.
One of my teams was very surprised that I rejected a prd for being too vague and put my foot down that it will not be picked up until specific questions are answered. They were, I would not say meek, but resigned to the inevitability of product managers pushing poorly thought PRDs and not having any say in the matter.
I took my time training them to say no and spot ambiguities, and I like to think they have all become better developers and product managers for it. I always pick questions that have more than one obviously correct interpretation to see if the candidate notices it.
The idea that you trust your interviewer to provide a directly actionable question is strange. I would expect that in campus hirings, and for entry level fresh grads, but not to anyone with even a year of experience. At senior levels, it becomes more and more important to spot ambiguities and clarify them before they result in misunderstandings, wasted efforts, and worse. I trust a good interviewer to have a question that can provide them useful data points on candidates experience, skill, thought process and attitude.
Whether spotting ambiguities in the question has any correlation with future performance is harder to answer, but methodical people with attention to detail are preferrable to the alternative.
If the candidate comes from an environment where questions are penalised, they would be a bad fit for a team that values and expects questioning. It is somewhat unfair, but either way, the interviewers are selecting for their preferred qualities.
I don't mind O(n²) if I get good result but Amazon's search seldom gives me good results.
Same with Microsoft's search in the start menu. Doesn't find Excel if I type "exc".
My username at a large org is my first name. In any situation where someone wants to link to me or mention me, typing my username brings up a list of every person at the org with my name, alphabetically. My last name inevitably sorts me down toward the bottom.
You would think that an exact literal username match would have priority, but no. Typing any prefix of my name similarly sorts everyone else before me too.
I don't like the trick of failing candidates if they don't ask a question. 90% of this style of interview want candidates to rifle through solutions. If you want to talk about requirements, be explicit about it.
I'm really amazed that this "best interview" question really just boils down to leetcode for a _Senior Staff_ level interview. I don't know about y'all, but the _Senior Staff_ and _Principal_ developers I've worked with aren't wasting their time of shit like this. They're ironing out requirements. They're working with stakeholder. They're architecting systems. They're figuring out how to deliver the value the customer wants - and they're ensuring that it's actually the customer wants.
-----
There's a place for performance, but the fast running turd is still a turd.
A good interview should involve more than just a coding problem. But it should absolutely require at least one coding problem. It’s mind boggling the number of “senior” people with good resumes I’ve screened out in interviews over the years because, simple as a problem like this is, they really had no idea how to even start solving it.
I don’t know about the poster, but when I’ve done interviews - especially for senior people - there are a lot of different types of assessment I’d want to do before hiring them. I’d also want to assess their social skills somehow (eg get them to present to the team about something interesting). And ask some high level systems architecture questions, talk about their background, and more.
What do you get? I tried just now, and `E` gives me Excel. In fact, I typed "Esc" first on accident, and I got something different for "Es" but "Esc" gave me Excel too.
"explain select" is a cool source of interview questions :)
Don't get me wrong - it's a totally fair question, frankly one I would have been happy to receive when I was interviewing for those roles.
I'm also a fan of whiteboarding coding interviews in general as a way of evaluating talent so no objections there.
There were just something about this specific question that just struck me as boring, souless, like who cares? I think my objection might be that it too closely resembles a menial task I might actually be given - something that I hope to God the upcoming LLM advances automates away.
"they don’t know the size of the data upfront", okay. I spend a scan finding the highest customer number and probably make some 10MB index-assossiated buffer. If I'm fancy I find the range and use offset indices to reduce the overall size. You already said it fits in memory and I'm not a distsrubuted programmer. Space is cheap in boring reality
I guess it's one of those cool brain teasers that gets you excited to use your skills from college. Not many get to in reality. Or they prefer other domain-specific skills.
As someone going through this style of interview at the moment (but not having interviewed at Google, Microsoft or Amazon), two things jump out at me:
- If you're going to ask this question and get it done in 1 hour, does the code really matter? I'd argue that if you can get to a good or optimal solution, 99 times out of 100 you can write the code. If I got this question and didn't know better, I'd be stressing about writing the code within an hour. Knowing that we wanted to spend most of the time discussing the algos and data structures would be really useful to me. Maybe Google/Amazon/Microsoft interviews really stress this in their preamble, I don't know.
- The big "issue" I see with this question is that it relies on the interviewer knowing exactly how to steer the conversation. I think I could get to this solution with the hints, and the author seems to imply that it's ok to need a few hints. But an interviewer that doesn't know the right hints to give (or phrases them poorly) is going to turn this question into a train-wreck. This isn't an issue for the author, they clearly know this questions backwards and forwards. But giving this question as a 'standard' question that others will deliver? I think it could easily end up being too conservative and cutting out a lot of otherwise smart developers.
In general, that's my criticism of this style of question: they all claim that they're about 'seeing how you think'. But I think expecting interviewers to be able to elicit a conversation that really shows 'how a candidate thinks' is much more on the interviewer rather than the interviewee. You're expecting people whose primary job is writing software to be really good at delivering interviews.
Instead, you're going to have candidates who most of the time will do well if they can pattern-matching against problems they've seen in the past, and poorly otherwise. I can see how questions like this seem good on paper, and I'm glad this question works for the author. But it's the combination of interviewer and question that makes it effective, not just the question alone. A better title for this post might be 'My favourite way of interviewing candidates', because this post is mostly to do with the author's mental model of how to run an interview with this question.
For reference: http://www.leancrew.com/all-this/2011/12/more-shell-less-egg...
If I used this question I'd add to it.
"Pretend you have to do the work on an Arduino uno, which has very little resources. Your uno can request input and produce output from the disk where these are stored at whatever offset you wish. The log files are 100GB each and sit on a desktop computer with a modern Linux on it. Each log line is 512B. You can create files if you need to through some unspecified protocol with the desktop computer. But the desktop computer must be dumb. It will only write to and read from disk. You can send it any disk system call you wish. Step 2; Now do it without sorting or something absurdly slow"
The point is to ask for actual creative solutions instead of the pattern recognition problems that most of these problem formats are.
You want something that a weekend of drilling won't change the result of
Grep, uniq, wc, and a few others can be treated as pipeline data transformers to answer questions like this interview question. As long as you make some smart decisions about the order of operations, you can usually get performance on par with what you might write custom code for.
I would love to interview a candidate that can show they can use command line tools effectively.
> Did I mean 2 unique pages per day or overall?
The author needs a course in logic. "They visited at least two unique pages." is not ambiguous. Visiting page A on day 1 and visiting page B on day 2 makes the sentence true.
Interviews are just not the same thing as real life requirements gathering, so people's thought processes will not be the same. Even if you try to roleplay as someone that doesn't understand how to state requirements precisely, all of the normal procedures and thought processes for sussing that out are compromised due to the inrerview setting. And your ability to assess those processes are compromised due to how familiar you are with the question and how much you've deconstructed it.
It's not the time to be tricky (though somehow simultaneously believing it is and is not a trick question). There's so many more interesting things that could be gleaned from a person's interview performance that "is this interviewer playing fuck-fuck games with me" doesn't rate whatsoever.
The user has visited A and B on day 1, and A on day 2. So the total page hits is (A, B, A). Remove duplicates and you have (A, B) which makes the sentence true.
Imagine he said:
> They bought at least two unique products
What would you expect the requirements to be?
>Now, given two log files (log file from day 1 and log file from day 2) we want to generate a list of ‘loyal customers’ that meet the criteria of: (a) they came on both days, and (b) they visited at least two unique pages.
It appears to me that the requirement could be interpreted as either:
"(visit on day 1) AND (visit on day 2) AND (total unique pages count > 2)"
a clearer way to put it would be "visited at least two unique pages in total"
or "(visit at least two unique pages on day 1) AND (visit at least two unique pages on day 2)"
a clearer way to put it would be "visited at least two unique pages on each day"
The data structures look sensible and it did most of what the interviewer wanted on the first try.
It did make the wrong initial assumption that we wanted 2 unique pages per day. When prompted with a clarification, it made a sensible fix.
When asked to optimize, it went for big hammers like parallel processing and caching. As opposed to saving memory by only storing one file in the data structure as the author discussed.
https://aider.chat/share/?mdurl=https://gist.github.com/paul...
There's a lot of good insight in the article about the correct way to approach the problem, but asking anyone to come up with it on the spot is unrealistic. You have the benefit of having seen the problem before with time on your side to reflect on it. They haven't.
When I do interviews like this, I prefer to talk them through the problem together, like we were actual teammates working on a problem together. That more closely relates to life on the job, which to me is the point of interviewing someone.
The "is this person good enough for me" interview allows geniuses who are assholes through. I prefer to filter for good teammates.
Only the basics that are close to everyday programming work: write a for-loop, know what a Map/dict is, and Google for “how to read a file”. If a candidate can’t do that, they can’t really program. ChatGPT can probably code this answer.
I wouldn't expect everyone to immediately see the optimizations -- you can sort the days individually, you can drop all but a small number of pages per customer -- immediately, but I would be disappointed if someone couldn't be hinted there by the end of a 30 minute interview.
Failing to even get the O(n log n) solution tells me that someone should never have graduated.
This is something I wonder about in my comment sidethread - to me, the natural solution is the O(n) one in O(n) space.
I see that the O(n log n) solution requires O(1) space to run. But it requires O(n) space to return a result! Is that actually better than O(n) time and O(n) space?
From a senior developer, I would expect a discussion of in-core vs. out-of-core operations, and the fact that hash tables (even if they fit into RAM) aren't really O(1) time per operation since random access to large address spaces runs into e.g. TLB misses.
Even senior developers that understand the TLB would likely think of it as "O(1), but with a big constant factor".
On a side note, one thing that the article doesn't mention is the possibility of using a Bloom filter. It trades an extra scan of a file for smaller hash tables/smaller set to sort with external sort.
Whether you get a cache miss or hit is part of 'c', or whether those bytes are fetched over WAN. Big oh of one just means lookup time is a constant and is independent of data size. The big oh doesn't change if move from a SSD to a tape drive
Thus, those operations are really O(1)
Big oh is the infimum function such that for an arbitrarily large N, the runtime of the algorithm is then strictly larger than C times the big oh function. (Paraphrasing there a bit, and on a phone, apologies for not pasting the exact definition)
Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.
I don't think the definition of Big-Oh supports that conclusion.
"Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity." [1]
"For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n^2 − 2n + 2.... As n grows large, the n^2 term will come to dominate,... say that the algorithm has order of n^2 time complexity" [1]
[1] https://en.wikipedia.org/wiki/Big_O_notation
> Hash table lookup is absolutely bounded by a constant, but going from L1 to L2 to L3 to RAM with anywhere between 0 and 5 TLB misses is far from constant.
Indeed, but I can choose a value "C" that is large enough to negate any of the differences between cache miss or hit.
Let's say "N" is the number of lines in one of our text files. Once we have put that data into a hashtable, the claim is then that lookup time is O(1). You counter, and state, no, the lookup time is potentially 30ms, or even 100ms (making up the numbers). For my claim that the lookup time of O(1) to be true, I can pick any value of 'C'. So I choose 1 million. I'm basically saying, lookup times will always be under 1 hour. Given our precondition that we have built this hashtable, no matter how we get the data, yes - it will be under 1 hour. If we used carrier pigeon with USB stick, we could just choose a larger value for C and still be correct.
The idea is basically, if you have something like N^2 + N^1, eventually when N is large enough, n^2 will become so dominant that you could multiple by it by a fixed value to wash away all the other terms in the expression.
Thus, while the actual lookup time can and will vary, it is still bounded. Keep in mind as well there are different functions for best case and average case performance. These notations do take into account that the per-instance lookup time can vary.
Wait, don't the inner nodes of the page table contain the _physical_ addresses of its child nodes? Wouldn't that make it a most one TLB miss per hash table lookup (assuming key and value are adjacent in the hash table bucket)?
If you have a 64-entry TLB and 4kB pages, then you can do random memory accesses (aka hash table accesses) up to 256 kB without any paging table reads; up to ~16 MB with one paging table read per operation; and up to ~1GB with two paging table reads per operation. (This, of course, is why large databases use superpages when possible; but while that pushes the limits back it doesn't eliminate them.)
In virtual machines there's further overhead since you have "virtual physical" addresses...
Let's say the runtime of some function is (x1n + x2n + x3n), where x1, x2, and x3 represent the L1,L2 l3 cache lookup times.
A function F is called big-oh of function G if there exists a value C such that CF is strictly greater for all sufficiently large values of N
For the above example, let's say I choose the value one billion for C. Is it true that 1 billion times n will be greater than the sum of (x1+x2+x3)n. The answer is yes, thus, f(n) = n is big-oh (x1+x2+x3)n. In other words, at a certain size of n, we can pick a constant multiple that dominates the other terms. This is in part why asymptotic functions are independent of hardware. Even if L3 cache were actually virtual and fetched over a network, I could still just choose a larger constant. If you can't choose such a constant, then chances are you need a faster growing function like n-squared
Id expect senior engineers to talk about how they will monitor this system, and to bring up things like customers we know we don't trust.
A senior engineer might tell you that running into TLB issues makes a suggestion that your approach is wrong and it's about time to move the solution to your data warehouse
Well yes, but that's not what this is about. It's about social pressure, not ability.
I could program this for you right now if I wanted to; most "optimisations" seemed the "obvious ones" to me, so I guess I would have passed. I could also program it in a hurry at ludicrous speed under pressure because all of production is down or whatever.
But ... I wouldn't be able to program this in an interview setting.
Last time I was asked a bunch of even easier things (in a timed interview, no less), where I literally have some exact code on my GitHub. I just couldn't finish it. Not because I can't "get" it, but because programming while two strangers are judging your every keystroke and commenting on what you're doing is just nerve-wrecking.
Or, basically this sketch: https://www.youtube.com/watch?v=kQa5NsdYSts
I think that rather, I would have done well because I know after doing hundreds of these both as the interviewer and the interviewee that using some sort of Map along with some vague rumblings of “space/time complexity tradeoff” is very often the solution for these types of questions. So I would have immediately gone there first by instinct.
Senior in a perfect world sure but the reality is that for decades ppl have been desperate for talent and so you don't have to do much to get by.
I knew a popular principle engineer at a fortune 50 company who was loved by execs. He would check in 5 or 10 of the same file. Opposite of the dry principle.
The coding exercise will involve writing tests, deisgn of classes, working with floating point arithmetic, working across thread barriers, some fairly standard maths, and so on.
I actually can't say we're hired a bad candidate yet and they all report that the interview is a positive experience.
In my fairly long career I've been through about 10-15 interview processes. A few of them were quite toxic and those were the "just cram leetcode for months" type. I never want to inflict that on someone else.
If a colleague came to me to discuss a question this basic, I'd want them PIPed out. This is miles from the complexity of problems that require collaboration. It's a shell pipeline that I'd write with sort/uniq in less than five minutes. I just did it to make sure my estimate wasn't wrong:
Maintainable? No. Done iteratively in less than five minutes? Yes.If your perspective is that it's unrealistic to ask anyone to come up with an answer to this question on the spot, you should take a long, hard look at yourself and the quality of your colleagues.
You didn't ask the question you were supposed to ask. :)
“Load to a relational store and use sql” would be a reasonable answer that, I’m sure, would be acceptable in most cases.
I only know how certain SQL engines implement queries because I was tasked at that point to increase the speed of the queries, and went deep into the debugging level detail to understand the exact cost of each action.
But I haven't done that in 7 years, and couldn't tell you much more than the tools used to figure it out.
I cannot remotely understand the requirements people make up for our jobs that have nothing to do with doing our jobs.
Any experienced engineer should have no trouble with it. There's no hiding here. - candidate just needs to deliver something working, something relatively clean, and be reasonably pleasant to pair with. No leetcode grinding necessary, though I have found that those who did well on this problem also generally got high scores from my colleagues who do ask LC questions.
It's really just a scenario with some mockup third-party API docs, where the applicant needs to write some paeudocode that checks different conditions, arranges the data, and ties together the different calls.
It might not be testing every possible skill the applicant has, but at least it's in-line with one of the tasks we actually expect them to perform regularly.
What if this is a one-off to produce a business report? Would it make sense to use programmer time to create an O(n) structure in memory, or just loop through the files line by line and let the CPU take a minute or five, or thirty? What is the programming language - something that has a library for this or something very low level where we’d read the file byte by byte?
If we’re dealing with the latter, a small amount of data, and a one off report, I don’t care at all in my work whether an engineer I’m managing somehow writes it in O(n^3).
It’s interesting how quick to judge the author is - ask this question for points, don’t even think about that, don’t mention arrays because they’re fixed size (despite implementations for dynamically allocated arrays totally existing and the candidate might be coming from that), and so on. Some humility would be nice.
Although I think what they wrote is very valuable, as this is how many interviews go. And I have to at least appreciate the author’s approach for trying to start a conversation, even if he still takes a rather reductive approach to evaluating candidates.
Unfortunately people don’t think about actual engineering cost of “optimal” solutions. Engineering costs are part of operational costs and need to be juxtaposed against compute.
You can get a lot more mileage out of running the largest EC2 instance for a year vs hiring a junior engineer.
The plural form was correct.
It's not just hiring one engineer, it's hiring a whole engineering department because that solution involves symbolic execution plus a few other things that I can not speak about without compromising my employment. The two solutions are in entirely different leagues in terms of engineering complexity.
The bruteforce solution is simple enough that can be maintained by junior engineers.
Add a few mid and senior engineers, and it can become significantly more efficient, without requiring the resources of the optimal solution while still being classified "brute-force".
It is yet another way the bitter lesson manifests [1].
The highest core count machine you can get on EC2 is like 45k per annum, which is peanuts compared to the cost of the team required to build the perfect solution.
[1] http://www.incompleteideas.net/IncIdeas/BitterLesson.html
A complete and efficient solution would take 2+ years plus a very senior, very specialized engineering team chasing a moonshot.
A brute-force approach that can leverage compute is far more efficient in engineering time, operational costs (eng time vs compute), and opportunity cost.
This isn't something that can be optimized in 10 minutes, and insinuating that while digging further suggests that haven't dealt with truly complex engineering problems.
> About 80% of the candidates go for the naive solution first. It’s easiest and most natural.
The “naive solution” will be easier to understand and maintain. Why make it harder if it doesn’t add value?
But even more importantly, with a slightly better solution I don’t get woken up in the night once a week because some buffoon left behind a hundred of these little performance landmines that worked great when the table had ten rows on their dev box but causes an outage in prod the second we hit some critical threshold of data.
This takes all sorts of forms from people using quadratic time or quadratic memory to my personal favorite: pulling entire database tables across the network to do basic analytics.
The authors always have the same excuse, that “it worked good enough for what was needed at the time”, ignoring the simple fact that the version which wouldn’t have caused an outage would have been just as easy from day one.
If you aren't doing better because you don't care, you're inflicting the costs your apathy on everyone else around you. If you aren't doing better because nested for loops is the most ergonomic solution for virtually every problem in your language of choice, you need to reevaluate your choices.
Everything doesn't have to be overengineered to death, but that's a far cry from being okay with regularly and intentionally choosing the actual worst solution that is all but guaranteed to blow up under any kind of growth.
I've worked with a lot of engineers that considered anything O(n^2) to be a red flag, and half the time the actual performance profiling favored the naive method simply because the compiler optimized it better.
That means that if you actually care about performance, you've got to spend 30 minutes profiling for most real world scenarios. Yeah, O(n^2) is obviously a crazy bad idea if you ever expect to scale to ten million records, but the vast majority of software being written is handing tiny 10K files, and a very large chunk of it doesn't care at all about performance because network latency eclipses any possible performance gain.
Luckily they’re typically easy to notice, and better approaches are often as easy as sorting your input first or caching items in a hash table.
An engineer should therefore catch these things when writing them or in code review and make sure a slightly better option is used in any situation where the size of input has a reasonable chance of growing.
The cost is nearly nothing and the benefit is not shipping code that will virtually guarantee slow response times and bloated scaling costs at best and humans being woken up at night for outages at worst.
I say very small because to me, n=10_000 sounds like a number that could easily and quickly grow higher since yoy are past a basic enumeration of a few choices.
No one said regularly or intentionally. Note that this thread stems from a comment talking about producing a one-off business report.
And yes, a really one-off business report is fine. As long as it runs and produces an anccurate answer, that is fine. Which is why I distinguished that if you find yourself regularly writing these kinds of algorithms and not having alarm bells going off in your head, that is almost certainly a problem.
I have never in 25 years encountered someone who spent noticeably too long optimizing running time for software that wasn’t performance critical. I have had to respond to at least two to four cases per year where somebody assumed a small case would remain small forever (or just didn’t think about it at all) and caused an outage, a severely bloated AWS bill (unbounded autoscaling + quadratic), or some other completely avoidable hell.
The problem is even if this is "known" upfront things always end up changing.
Unless the code is truly throw away code and not checked into source control.
I'm maybe guilty of being too harsh with this sometimes but the amount of times half-assed code has woken me up has trained me to be very critical of assumptions like this.
The attempts to circumstantially excuse away shitty answers goes against the desire to just not be shit.
The author here seemed able and willing to talk through constraints & issues. Their first paragraphs practically begged for it, as a sign of maturity. Rather than just excuse away shitty solutions, my hope is, even if you are not a super competent can-do coder, you at least can talk through and walk through problems with people that are trustable, to arrive at reasonably competent capable answers.
You can do a little better than that. Each item in your map has exactly 3 states:
- We’ve seen this customer visit one unique page with (xx) url on the first day
- We’ve seen this customer visit two unique pages - but only on the first day.
- We’ve seen the customer visit one unique page (xx) and they’ve visited on both days.
In the second state you don’t actually care what the URLs are. And I think the logic for the 3rd state is identical to the logic for the 1st state - since you only add them as a “loyal customer” by visiting them again on the second day. So I think you can get away with using an Option<Url> to store the state instead of a Set or a list. (Though I’d probably use a custom parametric enum for clarity).
It’s a great problem to model using a state machine.
"Let us hire this person because they dint solve the problem but were a great conversationalist problem solver" - said nobody at a standardized hiring committee!
> In theory you could write a pretty simple SQL query, and sure, Big Tech companies have giant data warehouses where you can easily do this sort of thing. But for the scope of a coding interview, you wouldn’t want to. Since this is not a distributed systems problem and the data fits in memory, why introduce the additional complexity and dependencies of a database for something that you can solve with 20 lines of simple code?
My first thought on an actual implementation was, if this is a one-off request, to import it into sqlite. No need to set up a big system, and I think it would be easier/faster than writing those 20 lines of code. Also a hell of a lot easier to iterate on minor spec tweaks like the unique pages overall vs per day clarification. And probably less likely to have off-by-one type of bugs, since the simple logic is handled by the database itself. Bonus, it does handle the case where the dataset is larger than memory!
The first answer that popped into my head was a shell pipeline, "cat file1 file2 | sort -k [pattern for customer ID] | awk -f ..." where the awk part just scans the sort output and checks for both dates and two pages within each customer-ID cluster. So maybe 10 lines of awk. It didn't occur to me to use hash tables. Overall it seems like a lame problem, given how big today's machines are: 10,000 page views per second for 2 days, crunching each record into 64 bits, means you can sort everything in memory. If 10 million views per second then maybe we can talk about a hadoop cluster. But 10k a second is an awfully busy site.
I actually had a real-life problem sort of like this a while back, with around 500 million records, and it took a few hours using the Unix command line sort utility on a single machine. That approach generally beat databases solidly.
That is basically how everything worked back when 1MB was a lot of memory. The temp files were even on magtape rather than disk. Old movie clips of computer rooms full of magtape drives jumping around, were probably running a sorting procedure of some type. E.g. if you had a telephone in the 1960s, they ran something like that once a month to generate your phone bill with itemized calls. A lot of Knuth volume 3 is still about how to do that.
These days you'd do very large sorting operations (say for a web search engine indexing 1000's of TB of data) with Hadoop or MapReduce or the like. Basically you split the data across 1000s of computers, let each computer do its own sorting operation so you can use all the CPU's and RAM at the same time, and then do the final merge stage between the computers over fast local networks.
I've used the Unix sort program on inputs as large as 500GB and it works fine with a few GB of memory. It does take a while, but so what.
But most jobs are not log file processing.
It's ridiculous to generalise this sort of thing:
"We are cooking soup here at Amazon Soup Kitchen. My favorite interview question is to ask candidates to bake a cake, that's the real test of any cook."
How is the author determining which candidates are great? Do "great" candidates answer the questions the best, or is the interviewer following up 1-2 years after hire and examining the impact of the person?
Great candidates aren't those who can answer DS & algorithms questions the best, but it seems that the author thinks that way.
> Since this is not a distributed systems problem and the data fits in memory, why introduce the additional complexity and dependencies of a database for something that you can solve with 20 lines of simple code?
Because this is a question about getting the right data, and SQL Databases are...extremely good for filtering, sorting and grouping... data. Besides, every page visit from every client is a unique observation, and the principle of...tidy data suggests that every observation use a database row.
Why solve this with 20 lines of code, when you can solve it in a 4 line SQL query?