6 ms·

Great insight. But this is sadly not applicable to interviews. > It's easy to do in O(n^2) time, or if you are clever, you can do it in O(n). Or you could be n

• theflyinghorse 1y ago
  The point is to test whether or not you put in the time to sharpen common patterns and also to test your communication ability
  • ebiester 1y ago
    Super common patterns like dynamic programming?
    • tomas789 1y ago
      Yes. It is common on leetcode.
    • theflyinghorse 1y ago
      Yes. Common LC patterns such as 1D and 2D dynamic programming. I'm not defending leetcode style interviews, in fact I think they are actually bad, I'm simply stating their intent as observed by me. In my notes I have roughly 30 patterns to leetcode questions btw.
• corimaith 1y ago
  >The point of these problems is to test your cleverness. No it's just memorization of 12 or so specific patterns. The stakes are too high that virtually everyone going in will not be staking passing on their own inherent problem solving ability. LeetCode has been so thoroughly gamified that it has lost all utility of differentiability beyond willingness to prepare.
  • jkubicek 1y ago
    In defense of questions like this, “willingness to prepare” is a significant differentiator
    • erikerikson 1y ago
      But what is it differentiating? And is it really the best evidence of willingness to prepare? My MSc and BA on the topics, my open source contributions, two decades of industry experience... Those aren't evidence of not only willingness but execution of preparation?
      • lubujackson 1y ago
        It is a differentiator when you are hiring straight from college. The fact we use this beyond entry level roles is a sign the company has lost the thread and is cargo culting.
      • JonChesterfield 1y ago
        The papers and open source indicate that you can build stuff. That's not what it's testing for. Will you put up with very long hours of insane grindy nonsense in the spirit of being a team player for a team that doesn't really remember what game they're playing? Are you sufficiently in need of income to be fighting through this interview dance in preference to other things, such that once you join you'll be desperate to stay? Those are extremely important questions, and a willingness to have spent a thousand hours memorising leetcode correlates strongly with the attributes sought.
    • tjpnz 1y ago
      That willingness to prepare doesn't reconcile with the realities of parenthood and all of the other responsibilities someone in their thirties may have. Consistently finding that time will be a huge ask, especially if you haven't worked on those problems in a while.
      • LordDragonfang 1y ago
• chaboud 1y ago
  When I interview with problem solving problems, the point is to understand how the candidate thinks, communicates, and decomposes problems. Critically, problem solving questions should have ways to progressively increase and decrease difficulty/complexity, so every candidate "gets a win" and no candidate "dunks the ball". Interviewers learn nothing from an instant epiphany, and they learn next to nothing from someone being stumped. Unfortunately, this is why we can't have nice things. Problem solving questions in interviews can be immensely useful tools that, sadly, are rarely usefully used.
  • mjr00 1y ago
    > the point is to understand how the candidate thinks, communicates, and decomposes problems. 100% and it's a shame that over time this has become completely lost knowledge, on both sides of the interview table, and "leetcode" is now seen as an arbitrary rote memorization hurdle/hazing ritual that software engineers have to pass to enter a lucrative FAANG career. Interviewees grind problems until they've memorized every question in the FAANG interview bank, and FAANG interviewers will watch a candidate spit out regurgitated code on a whiteboard in silence, shrug, and say "yep, they used the optimal dynamic programming solution, they pass."
    • bluGill 1y ago
      If somebody writes the optimal algorithm that should be a negative unless their resume indicates they are writing that algorithm often. The only reason you should know any algorithm well enough to get it right is if your job is implementing the optimal version for every single language. Of course nobody maintains one algorithm in many different languages/libraries (say libc++, python, rust, ada, java - each has different maintainers), so I can safely safe the number is zero who should be able to implement your cleaver algorithm. Now if your cleaver algorithm is in the language standard library (or other library they often use) that should be able to call/use it, though even then I expect them to look up the syntax in most languages.
      • kragen 1y ago
        What if we just really enjoy clever algorithms? I've probably implemented first-order Markov-chain text generation more than a dozen times in different languages, and earlier this week I implemented Newton–Cotes adaptive quadrature just because it sounded awesome (although I missed a standard trick because I didn't know about Richardson extrapolation). I've also recently implemented the Fast Hadamard Transform, roman numerals, Wellons–NRK hash tries, a few different variants of Quicksort (which I was super excited to get down to 17 ARM instructions for the integer case), an arena allocator with an inlined fast path, etc. Recently I wrote a dumb constrained-search optimizer to see if I could get a simpler expression of a word-wrap problem. I learned about the range-minimum-query algorithm during a job interview many years ago and ad-libbed a logarithmic-time solution, and since then I've found a lot of fascinating variants on the problem. I've never had a job doing this kind of thing, and I don't expect to get one, just like I don't expect to get a job playing go, rendering fractals, reading science fiction, or playing video games. But I think there's a certain amount of transferable skill there. Even if what I need to do this week is figure out how to configure Apache to reverse proxy to the MediaWiki Docker container. (I know there are people who have jobs hacking out clever algorithms on different platforms. I even know some of them personally. But there are also people who play video games for a living.) I guess I'd fail your interview process?
• roadside_picnic 1y ago
  > The point of these problems is to test your cleverness. Last round I did at Meta it was clearly to test that you grinded their specific set of problems, over and over again, until you could reproduce them without thinking. It's clear because the interviewers are always a bit surprised when you answer with whatever is not the text-book approach on both leetcode and on the interview guide they studied. Cleverness is definitely not high on the list of things they're looking for.
  • AlotOfReading 1y ago
    Cheekily using counting sort ended things the one and only time I agreed to interview with Meta. Definitely improved my inbox for a couple years though.
  • saagarjha 1y ago
    Interviewers are typically surprised when you do something new because they reuse questions with a lot of people and eventually you end up seeing most variations of a solution.
    • nitwit005 1y ago
      It's at times very clear people are following an interview guide, and just assume you're wrong if your approach isn't in the guide.
• viccis 1y ago
  >The point of these problems is to test your cleverness. In my experience, interviewers love going to the Leetcode "Top Interview 150" list and using problems in the "Array String" category. I'm not a fan of these problems for the kind of jobs I've interviewed for (backend Python mostly), as they are almost always a "give me a O(n) runtime O(1) memory algorithm over this array" type challenge that really doesn't resemble my day to day work at all. I do not regularly do in-place array algorithms in Python because those problems are almost always handled by other languages (C, Rust, etc.) where performance is critical. I wish interviewers would go to the "Hashmap" section for interviews in Python, JavaScript, etc., type of languages. They are much less about cleverness and more about whether you can demonstrate using the appropriate tools in your language to solve problems that actually do resemble ones I encounter regularly. There's also the problem of difficulty tuning on some of these. Problem 169 (Majority Element) being rated "Easy" for getting a O(n) runtime O(1) memory solution is hilarious to me. The algorithm first described in 1981 that does it (Boyer–Moore majority vote algorithm) has a Wikipedia page. It's not a difficult to implement or understand algorithm, but its correctness is not obvious until you think about it a bit, at which point you're at sufficient "cleverness" to get a Wikipedia page about an algorithm named after you. Seems excessive for an "Easy" problem.
  • Anon1096 1y ago
    Majority Element is rated easy because it can be trivially solved with a hashmap in O(N) space and that's enough to pass the question on Leetcode. The O(1) space answer is probably more like a medium.
    • viccis 1y ago
      Yeah it just depends on whether your interviewer considers that "solved". To test this out, I wrote a one liner in Python (after imports) that solves it with a hashmap (under the hood for Counter, which uses a heap queue to find the most common one): return Counter(nums).most_common(1)[0][0] And that's 50th percentile for runtime and memory usage. Doing it with another one liner that's 87% percentile for time because it uses builtin Python sorting but is 20th percentile for memory: return sorted(nums)[len(nums) // 2] But the interviewer might be looking for the best approach, which beats "100%" of other solutions in runtime per Leetcode's analysis: m, c = -1, 0 for x in nums: if not c: m = x c = 1 elif m == x: c += 1 else: c -= 1 return m If I were interviewing, I'd be happy with any of these except maybe the sorted() one, as it's only faster because of the native code doing the sort, which doesn't change that it's O(n log n) time and O(n) space. But I've had interviews where I gave answers that were "correct" to the assumptions and constraints I outlined but they didn't like them because they weren't the one from their rubric. I still remember a Google interview, in which we're supposed to "design to scale to big data", in which they wanted some fiddly array manipulation algorithm like this. I gave one that was O(n log n) but could be done in place with O(1) memory, and the interviewer said it was "incorrect" in favor of a much simpler O(n) one using dicts in Python that was O(n) memory. Had the interviewer specified O(n) memory was fine (not great for "big data" but ok) I would have given him the one liner that did it with dicts lol I guess my point is that interviewers should be flexible and view it as a dialogue rather than asking for the "right answer". I much prefer "identify the bug in this self contained code snippet and fix it" type problems that can be completed in <15-30 minutes personally, but Leetcode ones can be fine if you choose the right problems for the job.
• btilly 1y ago
  Bottom up dynamic programming algorithms require some cleverness. All of the ones listed can be solved with a top down dynamic programing algorithm. Which just means "write recursive solution, add caching to memoize it". For some of these, you can get cleverer. For example the coin change problem is better solved with an A* search. Still, very few programmers will actually need these algorithms. The top thing we need is to recognize when we accidentally wrote a quadratic algorithm. A quick scan of https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/ shows that even good people on prominent projects make that mistake on a constant basis. So apparently being able to produce an algorithm on the test, doesn't translate to catching an algorithmic mistake in the wild.
  • mcmoor 1y ago
    For the love of me I still can't consistently solve dynamic programming problems. Because "write a clever brute force solution that can be cached" is so broad that there are tons of variations out there, and a slight twist can bring you out of the loop fast.
    • zelphirkalt 1y ago
      Project Euler 18. I tried 3 heuristic approaches, before accepting, that to get the real answer without brute forcing it (because it comes back later in non-brute forcable version anyway), I need to find another way. I came up with an optimal solution, but it is still not dynamic programming, which I would also consider inferior to the bottom up solution I have found.
      • btilly 1y ago
        There is only one efficient solution that can be described as bottom up, and that one is in fact dynamic programming. A top-down solution in this case is in fact strictly worse. Why? Because while both take similar numbers of operations, in the bottom up solution you can throw away a row once you've processed the one above it. But in a top-down solution, you never know when you might call a particular recursive call again. This is very common. In a bottom up approach, we often know when we're done with data and can throw it away. This memory savings is the reason why people try to learn a bottom up approach. But it does come with the price of trying to figure out various kinds of "tricks". (That in complicated cases, may not be findable.)
• another_twist 1y ago
  No its not a measure of cleverness. Its about whether you can break down problems and apply common methods. Thats the entire job. Its a learnable skill and honestly resisting learning because of personal biases is a red flag in my book.
• deleted 1y ago
  [deleted]
• Eridrus 1y ago
  Constraint solvers are also often not applicable to the real world either. Many formulations scale in a way that is completely unusable in practice. Knowing how to get tools like Z3 or Gurobi to solve your problems is it's own skill and one that some companies will hire for, but it's not a general purpose technology you can throw at everything. This post is the unironic version of "FizzBuzz in TendorFlow", where just because you have a big hammer doesn't mean everything is a nail. And I say that as an enjoyer of bug hammers including SMT solvers.
• ReptileMan 1y ago
  I always prefer the "The Soviets used a pencil" type engineers. Simplicity is quite close to greatness.