7 ms·

Funny, I just went through a pre-screen assessment for one of the big ones and it was not one but _two_ DP problems. I could have probably come up with a slow s

• glangdale 8y ago
  I feel your pain. I did exactly one dynamic programming algorithm (in the string matcher for Hyperscan) and was pretty inordinately pleased with myself for doing it, but we built dozens of algorithms in that project and that was the only case of DP that I recall. But I expect to go into interviews and have people demand a different rain dance, now that everyone is talking about DP. They like mugging people with 'so big it has to be out of core' stuff, which is a good way of finding out who went to the right grad school algorithms course. :-)
  • vkazanov 8y ago
    I think I only saw DP-based algorithms 3 times in 12 years of working and reading open source code. Two of them were boring textbook-based implementations. One algorithm was original, and came from 80s - it's from Emacs source code, with comments like "do not touch", "here be dragons", etc.
    • glangdale 8y ago
      Yes, the code involving the DP algorithm I put in had a bug in it - not from the DP algorithm itself but the assumptions that fed into it - which went undetected for some time because of how complex the DP algorithm was and how hard it was to evaluate. It only caused a minor performance quirk (not a actual semantic error) so was hard to find. A cautionary tale about being overly clever-clever I suppose.
• donw 8y ago
  I have yet to find an interview process that works better than RPI (Rob's Pairing Interview)[1] plus a day-in-the-life[2]. It gives both the employer and the candidate a chance to evaluate each other in context. As an employer, you get to see how the candidate performs on two different real-world tasks, as well as how they interact with existing employees. As an employee, you get to see what the company is really like to work with. No amount of whiteboarding can deliver that. And at the end of the day, if that relationship feels good, both parties can choose to continue onwards towards full employment. On the other hand, computer science trivia, by which I mean "implement Dijkstra or quicksort on a whiteboard", is a very poor means indeed by which to test for the ability to do real-world work in a real-world context. Sure, it's valuable to have a broad understanding of algorithms and data structures. But whiteboard interviews on those types of problems only tests how well you would do competing in an ACM (Association for Computing Machinery) challenge, not how well you can deal with "here is a totally new-to-you problem that lacks a precise solution, now work productively with a team to solve it under the constraints of an operating business" [1] https://builttoadapt.io/the-developer-hiring-process-is-broken-672bf273c183 https://builttoadapt.io/the-developer-hiring-process-is-brok... [2] https://blog.jonrshar.pe/2016/Dec/05/pivotal-interviews.html https://blog.jonrshar.pe/2016/Dec/05/pivotal-interviews.html
  • kyberias 8y ago
    This is absolutely horrible. "We believe coding is a social activity. In fact, we’re testing you to see how social you can be around coding."
    • Huggernaut 8y ago
      It's worth understanding that Pivotal are hiring for a work environment that is almost entirely pair-programming, with teams of 2 to 8 engineers that rotate pairs almost every day. With that in mind, it's absolutely critical that Pivotal consider the social side of candidates while pairing. That makes the process less suitable for other types of working environments.
      • amd121 8y ago
• nuna 8y ago
  I don't do well on on the spot programming interviews. studying doesn't help. I can identify what needs to be done almost always, but implementing it in front of someone in only 40 mins? I need to practice that I guess. In the end as you said, I am constantly wondering what being able to regurgitate a memorized problem tells them about me (nothing) and why they don't care about my past experience, projects, successes and ratings. However, this is what every software interview is now
  • metters 8y ago
    > I need to practice that I guess. You are right about that, at least according to that article here:https://news.ycombinator.com/item?id=18942572 https://news.ycombinator.com/item?id=18942572 That guy trained on a well known website to solving minor coding issues and then (that's the important part) practised solving them in mock interviews to real persons. Maybe that could help you.
  • joeax 8y ago
    Neither does this famous guy [1]. All these interviews do is waste a lot of time and generate a lot of false negatives. You can practice all you want to get better, but no one in the corporate world is saying "I need you to code bubble sort, and I need in the next 45 minutes" and then proceeds to stand over your shoulder the entire time. [1] https://twitter.com/dhh/status/834146806594433025 https://twitter.com/dhh/status/834146806594433025
    • bootlooped 8y ago
      For big companies that have a ton of applicants, the false-negative rate probably doesn't matter all that much. They need a quick way to narrow the field. As for wasting a lot of time, what more reliable method is there that takes less time than a leetcode-style problem? Surely there are more reliable methods, they probably don't take 30 minutes or less though.
• paulddraper 8y ago
  > Absolutely nothing, except that I can't solve DP problems on the spot It's an IQ test. It measures cognitive intelligence. Does it predict overall success? No.
  • viraptor 8y ago
    IQ tests themselves are a bad predictor for performance, and skewed by access to resources. So maybe it is similar? That's not a good thing though. For the dp problem, you need to have experience with dp problems, experience with general algorithm problems (from the acm-like programming challenge side specifically), and generally be good at applying those in new situations. Unless that's your actual previous work, it doesn't measure intelligence in any way.
    • theparanoid 8y ago
      IQ tests are one of the best-known predictors of performance in any occupation.
      • viraptor 8y ago
        > The validity of IQ as a predictor of job performance is above zero for all work studied to date, but varies with the type of job and across different studies, ranging from 0.2 to 0.6 Best know doesn't mean good. Any occupation also fails: > for minimally-skilled activities, athletic strength (manual strength, speed, stamina, and coordination) are more likely to influence performance. https://en.m.wikipedia.org/wiki/Intelligence_quotient https://en.m.wikipedia.org/wiki/Intelligence_quotient Also, that's a predictor for "any" job. You can do better if you know exactly what job you're interested in. Do a sample of work that's very close to the real one and you'll have a better prediction.
• echevil 8y ago
  > But DP? I've never needed it or used it. Why the emphasis in it then There are people who did only the multiple choice questions and moved on to the video conf interview. At least they can skip DP question for some people, so probably not an emphasis.
• repiret 8y ago
  Regardless of whether or not it’s a good measuring stick to see who to hire (it’s probably not), I feel like DP is something that ought to be in a professional programmer’s toolbox. I’m an embedded developer too, and I end up reaching for DP every year or two. I think I probably use it _more_ because I’m in embedded: if I was willing to accept harder to analyze memory requirements and runtime performance, which I almost always am outside of embedded, most things I’ve solved with DP I could have more swiftly solved by composing algorithms and data structures from the standard library.
  • sethammons 8y ago
    I agree, it is a tool box thing. I either did not know of or forgot the term "dynamic programming," but I use memoization regularly, and have used it as short cuts on recursive calls. Accidental dynamic programming. Heck, the first time I heard of the collatz conjecture, my toy playing around with it memoized the results.
• fakename11 8y ago
  Both of those have pretty easy recursive solutions. I don't think you are required to pass all the unit tests in order to move forward and doubt the most optimal DP solution was really required. I got similar (as in recursive with DP optimization possible) questions in my real interviews.
• abetusk 8y ago
  I completely agree with you that solving a DP problem for a job interview shows next to nothing about the candidate, that asking a DP problem as an interview problem is cargo culting/rain dancing/etc. On the other hand, I believe DP is fundamental algorithm that comes up again and again and is the equivalent in importance to the simplex method but for millennials and gen-[xyz]'ers. Among the problems it solves are: * Shortest path in a graph (aka Bellman-Ford's method) [1], A* path finding [2] * Approximate string matching [3] * Viterbi algorithm for hidden Markov models [4] * Earley parser [5] for context free grammar parsing * Dynamic time warping [6] * Finding the base of a strong generating set for permutation groups [7] I'm consistently surprised that DP crops up in so many places. While most people won't be required to implement the above list in their day-to-day programming life, it's quietly in the background as a fundamental algorithm. Dynamic programming is one of the few algorithms that, in a "natural" way, reduces a problem that is naively exponential to one that is polynomial. For example, try counting where 2^T random walkers lands in an array starting from the middle after T time steps. Naively, this would require 'simulation' of 2^T but with DP you can do this in O(T^2) (assuming addition of atomic integer types is "free" and there's no overflow on count) using DP (by summing a 'count' of random walkers at each time step, at each bucket in the array). [1] https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm [2] https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm [3] https://en.wikipedia.org/wiki/Approximate_string_matching https://en.wikipedia.org/wiki/Approximate_string_matching [4] https://en.wikipedia.org/wiki/Viterbi_algorithm https://en.wikipedia.org/wiki/Viterbi_algorithm [5] https://en.wikipedia.org/wiki/Earley_parser https://en.wikipedia.org/wiki/Earley_parser [6] https://en.wikipedia.org/wiki/Dynamic_time_warping https://en.wikipedia.org/wiki/Dynamic_time_warping [7] https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorith...
• mxcrossb 8y ago
  When I went to graduate school, I took two algorithms classes. The first was general, and the second more targeted. For both classes, dynamic programming regularly was needed. I think they ask about it on interviews because it’s basucally a proxy for “did you get good grades in graduate level courses”. At a top school, undergrad courses should be close enough. Of course, they could just look at your transcript, but maybe you cheated.
  • chestervonwinch 8y ago
    Which is sort of silly if you didn't PhD in CS, but rather say, mathematics, where your courses hit you with numerical methods for PDEs, linear algebra, optimization, etc.
  • badfrog 8y ago
    But then they use the same interview questions for somebody who finished school 10 years ago and hasn't touched DP since then.
    • mxcrossb 8y ago
      This also makes them convenient tools for age discrimination
• jarsin 8y ago
  I see a disturbing trend every time one of these articles comes up. It seems all these companies are doubling down on these absurd interviews. Making them harder and harder to get in. DP is the epitome of how absurd these interviews have become and now people are getting asked 2 of these questions in pre-assestment stage.
  • drharby 8y ago
    I view it as industry moving the marker higher and higher for cult and loyalty marks and seeing if they get a steady manpower influx inline with their needs. Jokes on them when they stop getting good devs and start getting good shortterm greedy puzzle solvers. Hyuck hyuck hyuck
• msluyter 8y ago
  I have a theory that dynamic programming problems have become more popular in part because the lower hanging fruit — reverse a linked list, is this a palindrome? — have become widely known and practiced via books and sites like hackerrank. DP problems represent the next rung of the ladder, are somewhat less familiar. And most importantly, satisfy an interviewer’s possibly sadistic impulses by presenting a problem that has an easy 2^n solution. ;) Sarcasm aside, I think this is just the inevitable result of the systemisation and gaming of the whiteboard interview.
• _hardwaregeek 8y ago
  It's especially horrifying when you see all the people who devote their time to learning the rain dance instead of actually useful skills. People on /r/csMajors or /r/cscareerquestions who will say with a straight face, (well, as much as one can virtually) "you only need a data structures and algorithms class" or the generic "just grind leetcode" as a response for any perceived inadequacy. I wonder how many of these people make their job only to realize they have no experience and no interest in the actual content of their job.