17 ms·

My favorite coding question to give candidates

• gpderetta 3y ago
  You do not need to sort for the preprocessing based solution, you only need a K-way partition, which if I'm not mistaken, it can be done in two linear passes. I don't remember if it can be done in place easily though.
• chiefalchemist 3y ago
  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.
  • acheron 3y ago
    Ugh yes, the interviewers who give ambiguous questions and expect you to read their mind are the worst. What’s the old xkcd: “communicating poorly then acting smug when you’re misunderstood is not cleverness.”
    • klodolph 3y ago
      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.
    • philwelch 3y ago
      He’s not expecting you to read his mind; he’s expecting you to notice the ambiguity and ask a clarifying question.
      • chiefalchemist 3y ago
        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.
        • gpderetta 3y ago
          Asking questions is a protocol violation???? What kind of interviews are you subjecting yourself to?
          • chiefalchemist 3y ago
            Apparently, you'd be surprised (the kind of crap interviewing experiences there are). That aside, the candidate definitely has to err to the side of caution. There's also typically a time limit, yes? That's protocol.
  • two_handfuls 3y ago
    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.
  • sneed_chucker 3y ago
    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?
    • davidw 3y ago
      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.
      • redditor98654 3y ago
        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. Source: Conducted 250+ interviews in Amazon.
        • davidw 3y ago
          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".
          • redditor98654 3y ago
            Yeah, I made my comment concise but in a real interview I do say something similar.
    • 3y ago
  • deleted 3y ago
    [deleted]
  • davidw 3y ago
    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.
    • chiefalchemist 3y ago
      It's certainly not transparency. 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.
  • phanimahesh 3y ago
    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.
• two_handfuls 3y ago
  Nice question. Reminds me of the famous saying: “never underestimate the power of sorting.”
• croes 3y ago
  Did any of the hired programmers for Amazon work at the Amazon search? 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".
  • stouset 3y ago
    Or JIRA, which is particularly inexcusable. 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.
  • SkyPuncher 3y ago
    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.
    • josephg 3y ago
      > 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.
• qsort 3y ago
  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 :)
  • dopidopHN 3y ago
    Thanks. My reasoning was indeed “alright, it’s a weird world without DB, what a DB do? Hash-join.
    • deleted 3y ago
      [deleted]
    • AstralStorm 3y ago
      A better db would keep an online running window in a bloom filter for it, though. (A good implementation of an index.) Not even mentioned in the post.
  • deleted 3y ago
    [deleted]
• CSMastermind 3y ago
  Reading that made me happy I'm not an IC anymore. 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.
  • SkyPuncher 3y ago
    I also cannot stand the context your given this in. It's setup as a one-off task. Who cares how fast it runs? Is it correct?
    • johnnyanmac 3y ago
      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.
• Niksko 3y ago
  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.
• zdw 3y ago
  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. For reference: http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/ http://www.leancrew.com/all-this/2011/12/more-shell-less-egg...
  • kristopolous 3y ago
    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
  • deleted 3y ago
    [deleted]
  • Izkata 3y ago
    Also possibly comm for combining two lists (one for criteria (a), another for criteria (b), then intersect them with comm).
• michaelteter 3y ago
  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.
  • optymizer 3y ago
    Because shell command injection and process spawning time are not always acceptable side-effects.
    • michaelteter 3y ago
      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”
  • gpderetta 3y ago
    You would definitely pass if I interviewed you, as long as your solution was reasonably efficient. I would love to interview a candidate that can show they can use command line tools effectively.
  • kasdi 3y ago
    Out of curiosity, how would you solve this particular problem with shell commands?
• deleted 3y ago
  [deleted]
• Archelaos 3y ago
  > 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.
  • deleted 3y ago
    [deleted]
  • 1_1xdev1 3y ago
    It’s obvious by the next few sentences that he means “others interpret this in an ambiguous way”, given how many people he says get it wrong
    • DangitBobby 3y ago
      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.
  • tkot 3y ago
    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).
• anotherpaulg 3y ago
  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. https://aider.chat/share/?mdurl=https://gist.github.com/paul-gauthier/6ae6feabe0b18decf6ee39c5377343ce https://aider.chat/share/?mdurl=https://gist.github.com/paul...
• hornban 3y ago
  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.
  • dnsco 3y ago
    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.
  • bfung 3y ago
    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.
    • sfn42 3y ago
      And now you know who the devs are who think LLMs will replace us. They're the ones who think this question is too much to ask.
  • corethree 3y ago
    This one is pretty easy though.
  • 3y ago
• missblit 3y ago
  The rationale for not wanting SQL solution feels a bit strained. If you don't want an SQL answer just say "Hey buster this is a C++ interview!"
  • krackers 3y ago
    Good thing SQLite is written in C.
• pjot 3y ago
  I think these kinds of problems cause interviewee’s (under stress) to overthink the solution. “Load to a relational store and use sql” would be a reasonable answer that, I’m sure, would be acceptable in most cases.
  • gpderetta 3y ago
    It would if I was the interviewer. But expect that the followup question would be how the SQL engine implements the query.
    • AndyNemmity 3y ago
      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.
• eachro 3y ago
  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.
  • Terr_ 3y ago
    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.
• clnq 3y ago
  > 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.
  • PartiallyTyped 3y ago
    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.
    • gpderetta 3y ago
      Why would only the non-bruteforce solution require hiring an engineer to maintain it? Does the brute force solution spontaneously manifest and maintains itself?
      • PartiallyTyped 3y ago
        > vs hiring engineers 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 http://www.incompleteideas.net/IncIdeas/BitterLesson.html
• josephg 3y ago
  > Map<CustomerId, Set<PageId>> will do 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.
  • gpderetta 3y ago
    It is mentioned later that you only need to list at most one URL .
• donatj 3y ago
  I mean in my book anyone doing this in anything other than a bash one liner leaning on Awk is overbuilding.
  • antisthenes 3y ago
    2 liner SQL query and forget about it.
• flashgordon 3y ago
  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!
  • sjducb 3y ago
    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.
    • tmtvl 3y ago
      Story of my life. I think people just take pity on me (it's better than sitting on the side of the road with my cap on the ground).
    • flashgordon 3y ago
      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.
• Izkata 3y ago
  > Can’t I just use a Database? > 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!
  • mplewis 3y ago
    Exactly. Use the right tool for the job here.
  • ReactiveJelly 3y ago
    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
  • Foobar8568 3y ago
    Excel and power query, bonus point, you can perform more advanced data analytics and industrialize for a folder easily
    • amluto 3y ago
      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.
• throwaway81523 3y ago
  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.
  • ghthor 3y ago
    How much memory does the sort command end up using; 2N?
    • throwaway81523 3y ago
      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.
• andrewstuart 3y ago
  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."
  • marssaxman 3y ago
    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.
    • sfn42 3y ago
      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.
• shepherdjerred 3y ago
  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.
• deleted 3y ago
  [deleted]
• antisthenes 3y ago
  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?
• AndyNemmity 3y ago
  Well, you're holding it in a log file. Either the data is important enough we'd like to keep it, so we should put it in a database or elasticsearch, or the data isn't important enough, and I'd like to get further clarity on what you're trying to achieve. ... I'm guessing I didn't get the job.
• corethree 3y ago
  Easy. 1. Find names appearing in both log files. From this create a Set of customers that appear in both. In python it's just creating a set from the first file, creating another set from the second file and unionizing them. O(N) 2. concatenate both files to treat as one. create a Map with key: Customer and value: Set[Page]. This is basically iterating through the log, when you see a customer append the customer_id to the map and add the page to the set if it already exists. O(N) 3. Filter the map for all customers with length(Set[Page]) > 1. To get the Set of all customers that visited more than one page. O(N) 4. Combine the sets of customers who visited multiple pages with customers that appeared in both log files into a new set. O(N). You can do this with, again the union operator in python. The irony is I'm more able to do this in python then I am in SQL. For SQL stuff at work I just look it up. I never remember the exact syntax. Total runtime O(N) total memory O(N) This is just your basic hashmap stuff for fast look up and aggregation. Usually fang questions are harder than this.
  • bvrmn 3y ago
    union -> intersection
    • corethree 3y ago
      Thanks for the correction.
• yardstick 3y ago
  How about a single map to a structure that contains a bitmap for days visited, and a bloom filter for pages visited. Very low memory and compute requirements. Map<CustomerId, Metadata> Where Metadata is a dateVisited bitset plus a bloom filter (32/64 bits depends on how accurate you need it to be).
• johnfn 3y ago
  OP's solution seems a little clunky to me. He does this thing where he loads the first day into a hashmap, and then he queries it as he loops over the second day. But why? That just overcomplicates your algorithm, and the memory used by O(2) days is roughly the same as O(1) days. It's also overly specialized to solving the very precise problem that's posed in the interview; what if tomorrow Big Boss wants you to aggregate over 3 days? A cleaner solution would be to load both days 1 and 2 into the same hashmap. Then you can iterate the map and count whatever condition you want.
  • deleted 3y ago
    [deleted]
  • tobiasSoftware 3y ago
    I agree. I hate how these interviews always focus so much on algorithmic time at the expense of flexibility of the code. I agree with the first part about avoiding the n^2 algorithm by using hash maps. However, making your algorithm use half the memory but hardcoding the requirement that a user visited on two days is bad design, especially when it's only halving the memory used. Also not only does it hardcode the requirements, it also makes it much more complex logic wise as you need that "if pages from day 1 >= 2 or first page from day 1 != page from day 2". My design was to create two hash maps, one for customer to a list of days and one for customer to list of pages, though after reading the article I realized my lists should really be sets. Then you can easily account for any change to the definition of a loyal customer, as all you need to do is use two O(1) lookups and then check the size of the lists. Easy, flexible, and little room for error.
    • Terr_ 3y ago
      > I agree. I hate how these interviews always focus so much on algorithmic time at the expense of flexibility of the code. Especially when the question scenario is generating "business metrics" which tend to see a lot of tweaking and iteration. Having engineers who make contextually appropriate designs and architectures is at least as important as having engineers who are math-whizzes.
• thaumasiotes 3y ago
  > I don’t mind getting the naive solution first, but I really want to see my candidate having that aha moment that O(n²) is probably never good in any problem. And I want that aha moment to come pretty quickly and without hints. No great engineer should ever settle for an O(n²) algorithm, unless bound by memory or some other unmovable constraint. But that is purely a cultural convention. O(n²) is great for many important problems. For example, parsing a sentence in natural language is Ω(n³); getting it in O(n²) would be evidence that the candidate was a deity. Why select for familiarity with the details and conventions of the interviewing process? How is that supposed to be helpful? > Candidates then switch it around to have CustomerId as the Key, and PageId as the Value of the Map. But that’s not particularly great either because it overlooks the fact that you can have many pages per customer, not just one. Some candidates have the intuition that they need a Collection of pages as the Value of the Map But this is wrong. You're completely fine having a map from CustomerId to a single PageId, because the problem statement specifies that you're collecting customers who have visited more than one page. If you process a record that says CustomerId = X, PageId = Y, and you look up CustomerId in your map, these are the possibilities: 1. map[CustomerId] has no entry. You write Y as the new entry for that CustomerId. 2. map[CustomerId] is already Y. You do nothing. 3. map[CustomerId] has an entry that is not Y. You now know that CustomerId represents one of the customers you're trying to find. At no point did you need the map values to represent more than one page. > The condition “customers that visited at least 2 unique pages” tends to be a little harder for candidates to get right, so if they’re stuck I throw a little hint: you have a Set of pages from Day1, and a single page from Day2… how can you determine that this is at least two unique pages? > Poor candidates will loop through the elements in the Set to check if the page from Day2 is in there. This turns your O(n) algorithm into O(n²) again. The number of candidates who have done this is surprising. > Better candidates will do a .contains() on the Set which is an O(1) operation on a hash set. But there is a catch with the logic. > The intuition to get this right is this: If you are inside that If loop and the customer visited at least two pages in Day1, and they visited any page in Day2, they’re loyal, regardless of which page they visit in Day2. Otherwise, they only visited only one page in Day1, so the question is: is this a different page? If so they’re loyal, else it’s a duplicate so you don’t know and should keep going. So your If statement has an Or: > [code sample involving the interviewer's terrible solution] > There’s a need for attention to detail, like using “>” instead of “>=” or missing the “!” in the second statement. I saw these fairly often. I didn’t worry. Great candidates spotted them quickly as they double-checked the algorithm when they were done. Good candidates spotted them after a little bit of hinting. That gave me a good signal on debugging skills. Why in the world is this presented as a desirable solution? You have a Set of visited pages from day 1 and a single visited page from day 2. You want to know whether the total number of visited pages is more than 1. Add the page from day 2 to the Set [O(1)], and then count the Set [also O(1)]. > What if you pre-processed the files and sorted them by CustomerId, then by PageId? > If the files are sorted, then the problem is easier and it’s just a two-pointer algorithm that you can execute in O(n) with O(1) of memory. > Since the second sort key is by PageId, you follow another two-pointer algorithm to determine that there are at least two unique pages. So it’s a 2-pointer algorithm within a 2-pointer algorithm. It’s kind of a fun problem! I’ll leave the actual implementation as an exercise for the viewer. > If you want to make the problem even more interesting, you can add a third file. I will leave that as an exercise for the reader as well! If you're preprocessing the files, why not concatenate them before (or while) sorting them? The asymptotic resource requirements are the same and you end up with one file that can be processed in O(n) time and O(1) space. (Though the result of the algorithm necessarily takes up O(n) space, so I'm not sure how much this should count as an improvement in terms of space requirements...) This additional preprocessing step makes the generalization to three files trivial. The algorithm is identical: concatenate the files, sort the monofile, and then walk through the sorted entries.
• ozim 3y ago
  Love how he goes, he does not like tricky questions and first thing he describes is a trick hidden in the question designed specifically to fool candidates. Yet he still thinks it is not a tricky question. But great article and I learned something from it.
  • twelve40 3y ago
    but this "trick" tests for something very real: many times i've seen people around me mindlessly jump to coding a PM-written ticket without clarifying important details or even doing a basic sanity check on the feature. The end result is often a disaster for both parties, and should be avoided with a bit of thought upfront. It's not like anyone is lying or misleading here, such details get omitted all the time in real life but you need to collect them for a proper implementation.
    • ozim 3y ago
      I don't think solution for that is dropping perfectly capable people on the interview. There should be process for clarifying tickets with the team because you don't just drop tickets on developers "out of nowhere" and expect them to ask questions especially if company culture is "drop the ticket on dev let him figure this out". Someone has to either make ticket written in detail so you can drop it on dev without dev needing to ask questions OR make refinement where you get team to ask questions to have input from multiple people because single person is not able to understand all the details of the system.
• pharmakom 3y ago
  Just chuck it in SQLite and move onto the next business problem. 20 mins, tops.
• j-pb 3y ago
  Sorting the files can be a logarithmic operation with constant memory. A great candidate would know that this is a log-linear operation O(n*log(n)), not a logarithmic one O(log(n).
• bvrmn 3y ago
  Awful solutions TBH. They are quite hard to implement (requirements are coupled and could not be composed, logic heavy details) very specific and non-extendable for requirements changes in any way. You don't want this kind of code in a real life.
• zzyzxd 3y ago
  > After a candidate puts forth the O(n²), I smile politely and I wait. I am really hoping the next words that come out of their mouth are “…but the complexity of this is O(n²) so can I do better?” > Occasionally, a candidate will think they’re done at this point. 90% of the times that a candidate was done without questioning the quadratic nature of that solution, the final outcome of the loop was No Hire. So that’s another signal for me. I would have been one of such candidates. The author said they didn't like tricky questions and wanted to get a signal on how the candidate may approach real world problems. Well this is indeed tricky -- unless you drop a bunch of constraints in the beginning, for a real world project, I would just use all the resources I can access to finish it. I am not going to go the extra miles to optimize it in all possible ways. Premature optimization can be evil. I provided the solution, it works and meets all your requirements, then I am done. Want me to make it fast/memory efficient? You have to say it. Forgot to mention it in the first iteration? No problem, cut me a ticket and I will see if I can sneak it into my next sprint.
  • nemetroid 3y ago
    This is how we end up with https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/.
  • hoseja 3y ago
    You shouldn't be using O(n^2) algos at all, ever, unless the problem is well-constrained to be very small or there is no other possible solution. They fester and/or blow up regularly otherwise.
    • professoretc 3y ago
      I've heard O(n²) described as the most dangerous asymptotic complexity, because it seems fine for small testing inputs but falls down when you throw real-world -sized data at it.
    • nsxwolf 3y ago
      This will never matter in, say, a site configuration dashboard where a set of options is generated quadratically from a couple small sets of data. There are some features that will never be used at any significant scale.
• ZoomZoomZoom 3y ago
  The question looks more or less OK, except the ambiguity part. Hower, perhaps after "25 years in Big Tech" one shouldn't invent a process that discriminates against "loyal" customers living in timezones unaligned with the logging server. As usual, users come last.
  • dooglius 3y ago
    I think unaligned customers are discriminated in favor of--more likely to be browsing around the server's midnight and get marked as visiting two days.
    • ZoomZoomZoom 3y ago
      I don't think you can decide if it's a net positive/negative discrimination with any degree of certainty without knowing the date-stamping machine's location and the demographics of the userbase. However, there most certainly will be a non-zero amount of users discriminated against (browsing during a span around their local midnight that falls onto a single date on the servers), and that's what matters most in my opinion.
      • thaumasiotes 3y ago
        At the end of the article he elaborates the problem in a way he seems to feel is too complex to mention in the interview itself: what if there's a third day? If there are three server days of logs and a loyal customer continues to be defined as one who visits on two different days, the timezone problem essentially goes away. More fully: - if a loyal customer is one who visits regularly; - and we sample several days of visits; - then loyal customers will be detected regardless of their timezone. If you want the concept of a "loyal customer" to match the detection threshold, the weirdness related to timezones will still exist, but if you think of the detection threshold as a tool that's good enough to detect loyal customers, then it won't.
• rf15 3y ago
  > I don’t like hard or tricky questions. ... > I’ve actually expressed the problem in an ambiguous way. So when other people do it, hard and tricky questions are bad, but when you deliberately set your candidate up for failure by withholding concrete information, that's clever and insightful. Got it. Or more productively put: The author obviously enjoys tearing down simple questions with complex implications (one often does in the sw field) and reflects over their candidates, but seemingly lacks the self-reflection to understand what makes questions hard or tricky and why interviewers like to pick them.
  • hoseja 3y ago
    I don't see it. Usually the bad tricks are CS puzzle gotchas, not a designed-in, well-spottable, management underspecification, which is actually testing for an everyday-used skill in the actual job.
    • arp242 3y ago
      Except it's not a "actual job" setting. It's an interview. Especially for more junior people it's selecting on confidence, because especially in a hiring setting they don't want to "seem stupid" by asking questions. I guess this is also a problem for more senior people. It's just a different setting than "actual job". If you want to ask if anything could be clarified then ask.
      • dwaltrip 3y ago
        In the beginning of the interview, tell them that it’s completely fine and expected to ask clarifying questions.
        • arp242 3y ago
          That has only limited effect, as this kind of thing is more of an emotional thing.
          • 3y ago
• animal531 3y ago
  Data structure questions heavily favors previous use. For example in the past I've used a multi-dictionary for certain problems, so it would have been an easy reach for me; but maybe not for someone from a different coding history. Personally I prefer something like fizzbuzz which is a pure code question, it applies to candidates of all levels and tells you if they can reason through problems.
  • gpderetta 3y ago
    In this specific case it heavily favor anybody that has spent more than 5 minutes with a programming language and used a dictionary.
    • deleted 3y ago
      [deleted]
• Mawr 3y ago
  Here we see the most classic interviewing error: not understanding that there's a difference between a test and what's being tested. Will the data fit in memory? Well, of course it will, it's an interview... oh you expected me to ask you anyway? I should obviously load both files into the hashmap, that way it works for an arbitrary amount of files instead of just two... oh, you expected me to write a solution for literally the exact problem you stated without considering its practicality? Even though before you wanted the opposite, when you asked about the algorithmic complexity? Guess I'm failing.
  • gpderetta 3y ago
    An interview could reasonably ask for an out-of-core solution. But you are right that optimizing specifically for two files seems wrong, especially as the data contains a timestamp, so you could simplify the problem and ignore the number of files completely.
    • xoranth 3y ago
      You can generalize to > Now, given two N log files we want to generate a list of ‘loyal customers’ that meet the criteria of: (a) they came on ALL days, and (b) they visited at least L unique pages. while keeping linear time complexity and O(num records in first file * L) memory complexity. It is not too different from the solution given in the article (just use 3 maps instead of two). That means that multiple files doesn't need out-of-core if the maps for one file at a time fit memory.
• laurent_du 3y ago
  I am baffled that several contributors to this thread seem to find this question difficult, some even calling it "dehumanizing". This is a very easy and basic question and I wouldn't want to work with someone who couldn't solve it efficiently in a few minutes.
  • tobiasSoftware 3y ago
    I agree that "throw everything in a hashmap" should be straightforward and is a good interview test. However, his further steps to "optimize" it by saying "Poor candidates load the contents of both files into memory." are terrible. Yes, that might optimize resources, but first it hardcodes the requirement that there are exactly two days breaking the solution if the requirement changes, and second it adds a bunch of finicky fragile code about "if there are two pages or more from day one or if the first page from day one is different from the page from day two". Great candidates treat software like a business with changing requirements and code that is read by multiple people, poor candidates treat software like a math challenge where the only goal is to use as few resources as possible.
• RagnarD 3y ago
  What if a candidate notes that web hits can come from all parts of the planet and every timezone and therefore "same day" for a particular end user does NOT overlap with the "same day" of the log files and thus immediately throws into question the meaning of '(a) they came on both days'. Many users could visit the site multiple times in one of their days, but recorded as two separate days in two separate log files. This certainly adds some complexity to the question and might not even be something the interviewer considered in the first place.
  • ZoomZoomZoom 3y ago
    Great to see I'm not the only one here who isn't fixated on 'how' so strongly that they've stopped asking 'why'!
  • bjornlouser 3y ago
    Exactly. It's a trick interview question since the minute you deliver this report on 'Loyal Customers' someone will want to increase the complexity of the 'unique' page visitation constraint to include information that will never be available in the log file.
  • deleted 3y ago
    [deleted]
• traverseda 3y ago
  >Poor candidates load the contents of both files into memory. I suppose this is the step where I become a "poor candidate". I think it's important to acknowledge changing client requirements at this point. Sure, loading both files in to memory is less memory efficient, but it's much easier to tweak this algorithm later if you do it. You can change to to count over 3 different days, or 2 days in a 5 day time period, or any number of other things. You can save some memory if you don't, but you'll arrive at a solution that is much less flexible. I mean the real solution is to load all the data into a database of course, but even given the constraints of the problem I'd still argue for loading each entire file in to memory as the more general and flexible solutions, when our pretend clients inevitably change their pretend minds. >you don’t need to actually keep every single page from Day 1 in the Map, just two, since the problem is “at least two pages” so a Set of size 2 or even an array of size 2 will use less memory than an unbounded Set. And with this I think we've crossed over from the practical to leetcode. At this point you're asking the candidate to add a bunch of new code paths (each one should be tested) and make their solution a lot less general. Going from a pretty general algorithm that can be tweaked pretty easily to something super specific with a bunch of new sources of bugs. >Or, if you’ve already determined that a customer is loyal, you don’t need to waste CPU cycles going thru the logic again next time you encounter that customer in Day 2. No, please load it all in to your data structures properly, even if you "waste" a bit of time. All these weird little conditionals sprinkled throughout your code when you're ingesting the data are going to be sources of problems later. They might save a bit of memory, a few cycles, but they significantly increase the complexity of the code, and make a refactor of tweaks much much harder. If this developer started doing stuff like that in an interview with me, well it would raise some red flags. >If you want to make the problem even more interesting, you can add a third file. I will leave that as an exercise for the reader as well! See, our imaginary customers imaginary minds did end up changing. Bet you wish you had loaded both files into memory now.
• leephillips 3y ago
  The best answer to the interview question is not mentioned in the article. It’s something like “I’m not interested in working here because I don’t want to use my art to spy on people.”
• greatgib 3y ago
  What is very is funny is that, in all big and small companies I have worked in or with, no one ever use or discussed BigO. It only shows up in interviews technical tests. Lots of good software engineers will have the instinctive knowledge of good or costly solutions without mapping it to BigO. Also, what is funny is that, in my opinion, BigO is used and required by people that want to look smart but are not necessarily so. Because what we do with bigO is really limited. Almost nowhere the discussion will go further than O(1), O(logn), O(n), O(n2). Because after it becomes hard to understand maths. But in my opinion, algorithm complexity goes way beyond that when you use it in real life.
  • rf15 3y ago
    I kind of agree, the track record of people obsessed with BigO is not good in my book. The last person that valued it would still get the smallest element in a collection by... sorting it and then selecting the first element.
  • PH95VuimJjqBqy 3y ago
    > What is very is funny is that, in all big and small companies I have worked in or with, no one ever use or discussed BigO. Maybe you don't work in the right places then.
  • sfn42 3y ago
    Sounds like you don't understand it and are doing the usual mental gymnastics to justify your ignorance. People always say this about math. If you understand it you'll use it all the time because you'll recognize situations where you can leverage it. If you don't understand it you'll blissfully make do, unaware that you could have done things a better way. And then you'll proudly proclaim "math is pointless, I've never needed to use math after I graduated!". Fact is you did need it, you need it all the time. You just don't realize because you can't use it.
• hoarf 3y ago
  Here's a better interview question: What is the problem of using later job interview stages as validation for early stages and what would be a better metric for validation.
• michael_leachim 3y ago
  that looks like I am a good candidate for Amazon, lol. but on a serious note, the good solution is sort of obvious and in general you encounter much more interesting problems on a daily basis, but than again I am working in Clojure where working with data structures is much easier and straightforward than in Java.
  • michael_leachim 3y ago
    I am sorry if that sounds condescending, in reality I question my engineering ability almost every day. There is a lot of things that I know horribly less than any engineer worth their salt.
• say_it_as_it_is 3y ago
  What are your favorite interview questions for people who assume management roles as these?
• effnorwood 3y ago
  [dead]
• mattkenefick 3y ago
  Job interviews like this are terrible. It's a shame he's put so many people through it.
• avmich 3y ago
  Yeah, I'm disagreeing with some approaches. For example, in real life the engineer usually knows the constraints of the problem, and can add them himself. More, asking clarifying questions regarding memory versus speed will quite often draw blanks from less-technical consumer. Some aspects of the problem seem artificial - do we need exactly two days visits to be loyal? Exactly two unique pages? What one's going to do tomorrow, when these requirements change? And that would affect the design chosen. I feel that author filtered out lots of great candidates over this problem, which might be something to pause about. On the other hand, interviewing to get a good signal is indeed a tricky business, so I can sympathize.
• svilen_dobrev 3y ago
  i have a ~~similar task in my python course.. given 2 text files with similar format, one holding persons and cds they have each, another holding songs and which cds they are on, to answer which songs particular person has, and which persons has particular song. Yeah, a join. Nothing about O(blah) though, these are way-too specialized / optimizing lands. that said, coding != thinking.. Some people cannot think of a solution at all, 50% go for 3 loops one-in-another.. copy-pasted 2x2 times, few do the ~~simplest 2 maps with 2-3 funcs.. and once a "master" invented a class with quite a few methods contaning copy-paste inside :/ Probably one can do some analysis over who goes which way and why but i never bothered. It is also a good ground to show the different ways to add key-value to a map if it's not there - and their pros/cons (one can hook some O(blah) stuff here. i don't. There's just simpler vs faster, with variants). And yes, having an (subtly) unclear requirement (that should be identified and asked about), is important part of the learning - that's 90% of cases in life.
• phendrenad2 3y ago
  The venn diagram of people who blog about their coding interview questions and the people I want to interview with does not overlap. Nothing personal, but they always come across as "here's how I make monkeys dance for my amusement" or "here's a clever question and the more people ask me about it in the interview (despite it being perfectly clear to begin with) the more it strokes my ego and the more I am likely to interview them"
• interactivecode 3y ago
  You know since this assignment is basically a boss asking for a single report once about "loyal customers" complexity doesn't matter. let's say worst case scenario it takes 30min to run. who cares about complexity the business value is in the answers from the data. If you're consistently getting reliable answers and finally decide to build a system for these types of reports, clearly this guy's real world experience at Amazon's Clickstream product is going to be far more valuable than what ever anyone who is brand new to the problem can come up with, even if they choose the "correct" algorithm from the start. Because I bet you that for most real world products that create more than a single fixed format report you actually want your data setup in a completely different way than what you initially thought. You'll probably learn for example that you want to aggregrate data per week instead of per day. or perhaps you want to link this data to an internal users database, or perhaps your boss wants a notification when new data is added. Or perhaps you'll learn that loading it into a single 1GB SQLite DB solves your problem without even needing to think about any algos.
  • extragood 3y ago
    I have a similar feeling. My team builds out a lot of one-off projects for customers, and a lot of them don't need to be especially performant. That has always been the case for reporting/analytical projects. You know what does make a difference though? Amount of development effort spent on the solution. The most performant solution can very easily cost the company much more in terms of development time spent. So in that sense, it's sub-optimal
• deleted 3y ago
  [deleted]
• deleted 3y ago
  [deleted]
• coolThingsFirst 3y ago
  The problem is that once you start asking algorithm questions for top tech companies people will optimize for knowing them deeply instead of exploring other fields of CS. This is what happens with Codedorces/ACM-ICPC. Suddenly everyone is hyper driven to crank them out day after day under pressure and much more interesting fields databases or turning a business idea into a usable app get neglected. Lets not fool ourselves no one is going to solve hard medium LC under time pressure in 30 minutes unless they’ve seen a similar problem before which leads to hiring worse engineers who pass interviews. Once a metric becomes the goal it ceases to be a good metric.
  • seanmcdirmid 3y ago
    https://en.m.wikipedia.org/wiki/Goodhart%27s_law https://en.m.wikipedia.org/wiki/Goodhart%27s_law
• amluto 3y ago
  > For example, you don’t need to actually keep every single page from Day 1 in the Map, just two, since the problem is “at least two pages” so a Set of size 2 or even an array of size 2 will use less memory than an unbounded Set. That seems overcomplicated. For each customer on day 1, you either have multiple pages or you have a single page. If you see them on day 2 and they had multiple pages on day 1, then they are loyal. Or if they had a different page on day 1 than day 2, they’re loyal. (Or two different pages on day 2, but this comes along for free.) So the data structure can be: map<customerid, (MultiplePages | pageid)> Where MultiplePages is choice in a sum type that doesn’t store any associated data. Or you can do: map<customerid, optional<pageid>> Where the none state of the optional means there are multiple pages, but this is a bit of an odd use of an optional.
• happytiger 3y ago
  This is a great way to hire people who all meet a homogenous standard of behavior. It’s absolutely efficient from an engineering standpoint to eliminate weak links who can’t solve basic engineering problems. It creates a team of people who are good at tests, and good in testing environments. However, there are so many things that make an engineer great that have nothing to do with how they solve problems but who they are, how dedicated to improvement they are, etc. But they may not be someone who: -thinks quickly on their feet - finds this type of situation tolerable - may have disabilities one can’t see that would make this kind of interview difficult for them - have personality challenges or anxiety in social situations that make interviews like this impossibly difficult The list of reasons that “whiteboard testing interviews” don’t work well is long. I don’t think there’s anything wrong with this approach if that’s the kind of organization you want to build. But it does tend to create homogeny and act as a gatekeeper for “those who do not fit in.” Some of the very best engineers I have ever hired would never make it though this interview. But they were amazing engineers who did world class work.
• rakoo 3y ago
  Hot take: The optimal solution is the most obvious one for people who are more used to UNIX commands than programming languages, because the primitives in UNIX are more powerful (they give you a beautiful solution if you can make your problem fit in them; if not, the shell becomes atrocious). Here's my reasoning for the problem: we have 2 files, one for each day, and we want to see who came both days on different pages. That's a job for join, with some sort|uniq in the middle. - for each page, we want unique CustomerId -> PageId "mappings", but in UNIX land that's just 2 columns on the same row: cat dayX | awk '{print $3 $2}' | sort | uniq - now I have two lists, I join them join day1_uniq day2_uniq this gives me, for each customer, its id, then all its pages, on the same line. Customers who came only on one day are not in the output. - now I want to see if there are at least 2 pages and those 2 pages are different. There's no easy UNIX way to do this because it's all on a single line, so we'll use awk to build a hashmap. We don't need to build a map of all pages, we only need to see if there are at least 2 different pages cat both_days | awk '{for (i = 1; i < NF; i++) {pages[$i] = 1; if (length(pages) == 2) {print; next}} }' (Note: length() is not posix but gawk) Result: a list of all customers having visited at least 2 different pages on both days. Everything is dominated by the initial sort. I haven't ran this, it's a rough draft.