It’s an interesting question why we focus so much on algorithms that are mostly not used on a day to day basis, but the topic of persistence that’s everywhere and which is often only partially understood is far from being this prominent.
I remember a stint in research, about data analytic non the less, where rarely anyone had a good grasp of SQL or any other way to persist data for that matter. It really puzzles me to this day.
Might be me finding most ORMs to be harmful if used without understanding of the underlying technologies.
I recently had an A-ha moment when I realized that the problem I was trying to solve admitted a simple solution with dynamic programming, something I had never used outside programming competitions.
The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far your tweets were from 280 chars and where you divided them (e.g., dividing after a full stop is better than after a comma, which is better than between two works, which is way better than midword).
With a reasonable cost function, this really seems a textbook dynamic programming example (possibly much more credible than the entering-a-treasure-cave-with-a-rucksack story).
Yes, dynamic programming is how I implemented line wrapping for (the help text in) SingStar PS3 also.
Good spotting BTW, the line wrapping algorithm (where each tweet is a "line") is a perfect match for the post you are responding to.
When doing programming competitions, you're often trying to figure out what standard algorithm is similar to the problem and how you need to tweak it to match.
(Apologies to people on mobile for the following...)
One of the things I miss about Usenet was that
nearly everyone read it with a fixed with font
so that if you choose your phrasing well so as
to make your text come out naturally perfectly
justified, it would come out that way for them
too.
English has so many synonyms and near-synonyms
for every word, and so much flexibility in the
ordering of words that you can write like this
in near real time.
You get to the end of a line, find that you're
just a little long or short, and you backtrack
just a couple words or so most of the time and
you can usually find a way that works. In this
paragraph, for instance, I was one too long in
the first line, but contracting "you are" down
to "you're" fixed it. I was short in that last
sentence, but inserting "down" fixed it.
Perfect justification by inserting extra space
is for amateurs.
Now we've got all fancy and use variable width
fonts and automatic wrapping and posting isn't
quite as fun anymore.
Give it a try. Use an editor with a fixed font
to compose your next post and try to get it to
come out perfectly justified without having to
insert extra spaces. When you paste it into HN
that will get lost, but the composing can be a
fun little English puzzle.
I read at one point that the typesetters at the New Yorker would work with the copy editors to fix cases of bad justification (huge word space, awkward hyphen). It's rare to see that kind of care, but automatic algorithms are getting better.
On topic to the original post, I implemented Knuth-style line breaking in the Android text stack (working with Anish Athalye who was an intern at the time and did the first prototype). There were a bunch of nicely tuned implementations of advanced data structures and algorithms in there.
I still say it is a bad interview question, but there were lots of interesting examples I learned about.
- GCC splitting IA-64 instructions
- Trellis quantization in lossy video encoding
- Knuth-Plass line breaking algorithm (mentioned here too)
- Some algorithms I knew about, but which can be considered dynamic programming (I'm not sure how interesting this is): A* search, Dijikstra's shortest path, Myers common subsequence algorithm, transitive closure algorithm
I would say the GCC one is most interesting because there's a link to the actual code and comments by the developer.
Sorry I don't have the full context. It seems like some kind of pattern matching over instructions to put them in bundles.
I think it could be one of those cases where if you had a more obvious representation you wouldn't need a clever algorithm, but there is probably some other reason (good or not) that instructions are represented that way
CPUs have some number of individual units that do different things. You'll have a few ALUs that can do stuff like adding, subtracting, xor, and, etc. You'll have some number of units that do floating point math. You'll have a shift unit to do bitshifts. In ye olden days, the CPU would only do one thing at a time, while the rest of the CPU sat idle.
x86-64 (and most other architectures) can use multiple units at the same time using what's called a superscalar architecture. There's a hardware unit that figures out what units are in use and what instruction just arrived, and can either send the instruction to ALU0 if it's unused, or ALU1 if ALU0 is in use, etc.
But this hardware unit that does scheduling is complex, it takes up space that could be used by other stuff. IA64 aka Itanium, not to be confused with x86-64, is a VLIW (very long instruction word) architecture. The underlying assumption is that the compiler knows in advance what operations it's already emitted, and what operations are coming next, and the compiler can be considerably more complex than the hardware scheduler does. So a VLIW instruction isn't just "add eax,ebx" like x86, it's more like "ALU0: add r12,r48; ALU1: add r93,r42; SHIFT: r60,12; MEM: load r17,r32". (Itanium had 128 registers) The compiler had to do a bunch of stuff that modern CPUs do in hardware. I think it even had to deconflict instructions; like the compiler had to know that an addition takes 3 clock cycles or whatever, so if you used ALU0 on cycle 123772 and then tried to use ALU0 again on 123774 something bad would happen, but don't quote me on that.
So at some point the compiler is going to have a DAG of operations that need to get run in a block, and it needs to bundle up those individual operations into bundles of (I think) 4. Sounds dynamic programmy to me. At least I think that's what's going on.
It turns out that most code is pretty branchy, which means many lines of code will have multiple entry points. This invalidates the assumption that the compiler knows what operation it just executed. So in practice, VLIW architectures aren't able to achieve their theoretical performance, and superscalar architectures are better.
Would you rather be interviewed on algorithm questions or Ravens progressive matrices? They both test the same thing, but at least one you can study for, is somewhat relevant to the job (and is legal).
Only if you remember all the permutations. But I think Ravens progressive matrices are only good for finding people who have good visual acuity, not people who think deep.
I once coded a function to calculate edit distance. It was the algorithmic highlight of my career :)
But the general understanding of algorithms and complexity did help even in CRUD apps. It gives the bricks to form mental model of the underlying system. I don't need to code a b-tree but I may need to tweak its params.
I had a similar problem once and being an atypical programmer and did not know the term edit distance.
Some research gave me Levenshtein distance and from there I first used a naive perl implementation before finding that you could extend MySQL and found an example and implemented that.
Took me 1/2 a day to go from zero to working prototype
A good wood worker tends to know the tools of the trades and more importantly know when to not use a tool and when to invent a new one.. That said not every cabinet is a work of art some are just there to be functional for long enough to justify their creation.
I feel system interviews that dive deep about decisions and insights are far more useful than hitting a leetcode jackpot. Though it puts a high bar on the interviewer as well.
In the sense of going from rocks to iron to steel to finished tool, no, but otherwise, yes. Making specialised saws, scrapers, chisels, spokeshaves, planes and so forth are part of the luthier's, cabinetmaker's, and shipwright's existence. And that's just the tools, leaving workholding aside. Add in jigs and fixtures and there's a whole lot more. Not everything you need to do the job can be had off the shelf.
I have been tracking luthiers and it is fascinating how detailed and varied each builder is.. the likelihood that the instrument will sound good is well correlated to how much time the luthier puts into refining his process.
I don’t understand the rational for not wanting to learn DS/Algos this is just one part of it, there is also the whole business/customer side of writing code. There is a difference between never getting a demanding customer who understands the difference between a good instrument and something glued together and not wanting to know how to do something more than glueing it together is appalling. As a coder if you want to learn DS/Algos and you do not find a job the values that maybe there is more to learn so that find a job that values it. It will be competitive and you can fail but it is not wasted.
It leaves out framing carpenters, basically. I could have added patternmakers, timber fitters and so on, but there comes a time when adding to the list just for the sake of adding to the list becomes tedious. I, personally, have never been more than a hobbyist, but I've made my own tools both for woodworking and metalworking. This whole "get it at the store" thing is pretty new, and has mostly to do with building out of nothing but sheet goods using only power tools.
I've used Dijkstra algorithm for calculating distance in a graph once. It was a highlight of that month. Of course I had to look it up(despite learning it and implementing it at university). Who remembers this stuff exactly after years of glueing libraries together? And even if you remember - won't you check it anyway just to be sure?
It's OK to ask people general questions (what's algorithmic complexity, what kind of algorithms and data structures they know about, what are the tradeofs, etc).
But expecting people to remember the exact steps of an algorithm they last used 10 years ago at university is just stupid. It's like asking engineers to remember the tensile strength of a material they could use once a decade. That's what the documentation is for. It will take 3 minutes to look it up when I need it (if I need it at all).
Completely agree. The only thing that's important is knowing what to google for. i.e. being able to map from a real world problem to one or several algorithm/structure classes.
We always tell our candidates in advance what algorithms we'll be quizzing them on. And it's pretty much always:
+ fibbonacci
+ a sort
+ a linked list
I like having candidates write out these problems on paper because it shows that they know how to think about code. Fibbonacci allows us to see that they have basic recursion understanding, and basic iterative loop understanding. Linked lists shows us that they understand pointers. And a sort shows us that you can structure more complex code well.
If you truly want the job, you'll take 15 minutes the night before to remind yourself how all of these things work, none of them should be particularly foreign or confusing to an experienced programmer.
That covers the coding part of our interview. For the problem solving part of the interview, we may give you problems that require using heaps or skiplists or graph algorithms, but for this part of the interview we're happy to let you import imaginary libraries that do all the hard work.
I write on paper so infrequently that I actually find it pretty difficult to write more than a few words. I certainly wouldn't want to write something out longhand in an interview!
Edit: It seems to me it would be rather unfair of me to ask people to write out their thoughts in Org Mode in VS Code just because that's how I happen to like writing notes :-)
It's not a matter of writing speed, it's familiarity. I've been programming for 30 years and I don't think I've ever written code down on paper. Why ask an interview candidate to do something they've never done before and will never do again? You might as well ask them to type their code using only one hand.
I had to do a timed exercise to write code on paper IN PEN at a job interview. Talk about feeling like I had to get it correct the first time. Glad they didn't give me an offer because I would've had to consider accepting it.
It's a great showcase of how a flashy looking solution is the wrong approach. A good candidate will know it can be written in 2 lines recursively, but that the stack will explode with a fairly low term number, and that iterating with a for loop is more efficient.
Of course, recursion vs iteration is mostly an implementation detail. Here's a recursive version (expressed in Python) that works better than your loop:
def fib(n):
if n =< 0:
return (0, 1)
else:
a, b = f(n-1)
return (b, a + b)
(I say it works better, because it has the same asymptotic runtime, but fails better: When numbers get large, your C version will run into undefined behaviour that can cause arbitrary problems. The Python version will just crash with a well-defined exception.
A better language than Python can run this recursive version for arbitrarily big numbers.)
If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.)
Oh, your compiler doesn't have to be sufficiently smart. It merely has to avoid premature optimization: see this classic paper https://dspace.mit.edu/handle/1721.1/5753 by Guy Steele.
> I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC.
I guess that's the same overhead as in this imperative version:
> If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration.
The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.
I just tried it out, I didn't manage to get GHC to compile the equivalent of the code I've given into something that runs in constant memory. (I did the calculations modulo some number, to keep the numbers themselves bounded.)
GHC is sometimes able to do some of those transformations.
> The recursive Python version above didn't use tail calls.
Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.
> Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.
I was talking about this code:
def fib(n):
if n =< 0:
return (0, 1)
else:
a, b = f(n-1)
return (b, a + b)
Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.
Because after tuple packing returns (a C return) you still need to perform a Python return. The C tuple packing function cannot return directly from the Python function.
>(Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.)
This is not true. The recursive code will not compile with zero overhead even in haskell or lisp.
fib :: int -> int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
The code above will add layers to the call stack and has a speed complexity of O(N) and memory complexity of O(N).
To optimize in Haskell you need to deliberately restructure your code.
fib :: int -> int
fib n = let _fib 0 a b = a
_fib 1 a b = b
_fib n a b = fib (n - 1) b (a + b)
in _fib n 0 1
The above code will have O(N) speed complexity and constant memory in Haskell. In order for Haskell or any language with tail recursion optimization to work the recursive call must take up the entire return expression. In short the coder must deliberately make optimizations and write recursion in a way similar to the original iterative syntax in order for such tricks to work.
Though GHC is sometimes able to do some simple transformations on its own. But not in this case.
For anyone trying this at home: I suggest calculating your additions modulo some constant, so that the numbers involved stay within a fixed size. (Otherwise, you either hit the limits of Int and weird things can happen, or when calculating with the arbitrary precision type Integer, your numbers themselves will grow linearly in space.)
For the code above memory complexity is still O(N) even in a language that optimizes for tail calls. This occurs because you have an additional expression that occurs AFTER your recursive call that means the system must hold everything on the call stack for it to work.
Though if we allow programs like the C example that give wrong answers or have undefined behaviour, I can write an even faster version that takes no time at all.
The closed form solution is technically O(phi^N), so still exponential. It comes mostly from exponentiation not being constant time, see https://stackoverflow.com/questions/360748/computational-com.... It'll only be constant time if your values fit into a hardware register and you can leverage the exponentiation instructions of your CPU.
There is a O(log(N)) solution involving matrix exponentiation though, if you really need to get the big numbers.
Technically, Fib(n) at unbounded sizes is at least linear to compute. This is because the output of Fib(n) has O(n) bits in it. So even if the computation is free, it's still O(n) just to print the result.
That's not the type of thing I would ever expect a candidate to know in an interview, just something fun I've run across.
We've learnt on "discrete math" course at university how to derive closed form solutions to any similar recursive sequences using algebra and eigenvectors.
I remember that it's possible but I forgot all the required math :) Now that I googled it it's not THAT bad
While your formula is correct, it is not an actual implementation. How many digits of the square root do you need to compute exactly for being sure that the value of the power does not change?
Whether this is "fast" or not depends a lot on the concrete implementation of your arbitrary-precision real numbers.
As a nice thing, the second term (after the first minus sign) is smaller than 1, so you can omit it by rounding the result to the nearest integer; all the game happens in the first term.
You can implement the matrix exponentiation via repeated squaring recursively even in a language like Python that doesn't do tail call optimization, and it will still be fast: your recursion only goes to a logarithmic depth.
In any case, recursion vs iteration is an implementation detail. Especially if your language supports tail call optimization. Have a look at this example:
f(0) := (0, 1)
f(n) := let (a, b) = f(n-1) in (b, a + b)
f is recursive function over tuples of integers. And f is basically equivalent to the typically iterative algorithm for computing Fibonacci numbers.
I, for one, prefer recursion to explicit iteration in most cases. Anyway, if you were going to write the answer in Haskell, it's a three-liner and it's recursive.
For Fibonacci, recursion is not the best or most efficient way to approach the problem, but I like using it as a recursion problem (artificially constrain the candidate to using recursion) because Fibonacci is so simple that you get to spend most of your time talking about recursion itself rather than talking about Fibonacci as a problem.
At least for this part of the interview, I'm not worried about your problem solving skills I'm worried about your programming fundamentals. We'll test problem solving in a different session.
In my experience it's pretty necessary to do this. Probably depends on your local job market, but there are a shocking number of candidates that just don't know how to code.
The explanation I've heard is that good devs generally get hired after only a handful of interviews, whereas really bad devs are going to do a lot more interviews on average before they get hired, so you get a pretty skewed sampling even if there aren't that many really bad candidates around.
Yes, Joel Spolsky and IIRC Jeff Atwood have written somewhat extensively about it.
We are in a bubble, if we read programming blogs and think about programming in our free time, we are definitely not the kind that FizzBuzz exists to filter out. But from the perspective of companies, it makes sense if they really understood pointers or recursion or graph manipulation, because there are so many people lying on their resumes, not having sufficient analytical skills despite doing some resume driven cargo cult development etc.. And as an industry we don't really have an alternative to these algorithm interviews at scale, at the point we rely on non technical HR people to filter out resumes for us and they literally grep for framework/language experience.
Real jobs have certificates and degrees that mean something, where you can avoid the whole "do you know literal 101 things" phases of the interview process by just going "do you see the line on my resume that says M.Sc."
I don't know what your hiring experience with this is, but there is an entire market around "coding interviews" where people will learn how to pass these. I found algorithmic interviews completely useless to assess junior engineers because of how many just learn just to pass interviews, but then have very little experience with real problems.
If you want an example of this, check out r/cscareerquestions. The standard advice is not to practice any practical coding with projects, but to "grind leetcode" to get past interview filters.
If you want experience with real problems, they juniors should not be your thing. Juniors are supposed to be people with little experience that are able to work if given tasks by seniors.
A lot of candidates can't reason past the simple stuff so rarely do I have go beyond a simple coding problem. The FAANGs and unicorns maybe get lots of candidates so they can be very choosy.
Serious request, as a developer who would probably code a naive Fibonacci that doesn't meet your standard: Could you provide a code sample that does meet your standard? This looks like an important learning opportunity for me. Thanks.
True, but then the "worker" fib() method should be called fib_calculate() and should be wrapped by fib() which then returns a single integer. I believe that breaks the spirit of the question.
In my decades of programming I've never had to seriously consider these issues. I have used recursion and have written some pretty deep stuff like cryptography and writing my own interpreter (for a business - not a school project). I've even implemented recursion in a language that didn't support it. I have read about tail recursion several times. I still barely remember what it is. But I know a few books to reach for if I had to use recursion again. This is why the interview process is broken. I've written lots of production code and end up being seen as a lead programmer within weeks of a new job. And your questions would make me look like I don't know what I'm talking about.
I’ve worked with some interviewers who are out to prove they are smarter than the candidate because they remember a bit of something that the candidate does not.
Only when the interviewer finds someone “smarter” than himself does he approve of hiring the candidate.
There should be a fourth level where they use the closed form solution to get to the solution they want without any recursion or looping for reasonable values of N. Maybe even a fifth level using the O(log(N)) matrix exponentiation method.
I’m a bit puzzled at the idea of using recursion for an infinite sequence (did OP mean factorial?). Give me a LazyList / generator / IEnumerable instead any day for Fib.
This sounds like a reasonable approach and that is why software interviews remain broken. I'm sure it works for your organization, not saying you are bad at hiring or anything but it still smacks of the kind of hoop-jumping that turned me off so much from the process last time I was interviewing. This included on-the-spot coding exercises, massive take-home projects that required many hours of undifferentiated grunt work, totally useless whiteboard sketching and pseudo-code sessions, obscure Google-like quiz questions.
The interview process for the job I have now was a massive breath of fresh air.
The application asked for code samples and a cv. It was a small company and the CEO, CTO and direct co-workers all drove the interview process. The process was entirely conversational. First an intro phone call with the CTO and then a questionnaire via email in which I answered about 30 questions on various topics that were all very practical daily software development type stuff. It was painless to respond to each with about a paragraph in detail. Then a call with a direct co-worker about the questionnaire and this was my opportunity to ask questions of him about the company. Before getting the interview they actually read my code samples and reviewed my Github account. In the interview there was a ton of discussion about the company, its culture and all the of the above discussions. Following this was compensation negotiation with the CEO.
Everything about the hiring process said to me yes this is the place, they get it!
Many people would consider a 30 question take home project massive. You discuss your second experience as if it is some novel Utopian experience but when I read it sounds like an experience that was well suited to your strengths but wouldn't be suited to mine.
It definitely favored verbal skills, I am assuming that was a feature not a bug in the hiring process. The questions were not a project but a conversation in the context of my experience With a specific tech stack such as... “How do you keep a server from getting hacked”, “how do you handle conflicting dependencies”, “how do you know your code is ready to deploy to production”
What's wrong with a memoized recursive solution? Or a DP tail recursive solution? Tail recursive solutions are less buggy, easier to code, and easier to write than iterative ones. And they're much easier to prove the correctness of as well.
The memoized recursive solution is a good demonstration of how to use memoization to improve recursive function execution time. But it also seriously increases the memory requirements for many algorithms. If the question is "generate the first N numbers in the Fibonacci series", then memoization is a reasonable answer (though still not the fastest) since you actually need to generate and store every value anyways. If the question, instead, is "generate the Nth number in the series", then memoization will require an array of N values, when only 2 (at a time) are needed (which can still be generated recursively, but efficiently):
(defun fib (n &optional (a 0) (b 1))
(cond ((zerop n) a)
(t (fib (1- n) b (+ a b)))))
With tail recursion, that should be as fast as the iterative solution and uses as much memory to store the intermediate values.
Of course, the Fibonacci series also grows incredibly fast, so practically speaking, unless your language supports arbitrarily large integers, you'll never generate even 100 elements of the series.
If the question is "generate the Nth number in the series", I would be inclined to suggest a closed-form solution that returns in O(1) time (assuming regular size integers), no iteration required.
I think someone's ability to understand and explain recursion like am a child is very undervalued. It's not about testing whether you know the base case or the fact that you write less lines of code in recursion but the fact that there is a built-in stack for you to use without creating one.
What are the practical applications of recursion though ? Other than sorting and DFS ( well even DFS can be done iteratively with stacks ). I'll be curious to know.
I find testing for HashTable/HashMap knowledge to be far more practical than testing for LinkedLists simply because you can't escape HashTables in today's world.
> What are the practical applications of recursion though ?
Traversing and transforming nested data structures.
Just last month I had to write code that maps flat data from one system into a nested structure required by another system.
We wrote mappings as map literals and the code traverses them creating a new instance of the map filling the leaves with data from the input row and running some business logic on it.
I already don't want the job because of the interview process. Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal. You should be doing everything you can to put the candidate on their own turf and letting them shine. I have a lot of advice about interviews but one of the best I've heard over the years: whatever impression you have of the candidate try to prove yourself wrong. Using that advice, I've found a lot of great programmers that other companies skip over. Some people who are great at coding are bad at interviews and bad at live problem solving with an audience. If you really feel the need for a test, a paid take home coding assignment will give you the best signal.
I'd also like to add that because of this I adapted the traditional whiteboarding exercise at my current company to be about problem solving and design, and not about how many data structures you've memorized.
When a candidate comes in, I give them a fake-yet-realistic product requirement (like count elements in a real-time stream from field sensors) and let them run with it however they see fit. I put zero restrictions on the tech side of things in order to let the candidate shine (hopefully) in whatever tech they are most comfortable with.
I make sure to ask for feedback on the exercise and I've gotten all positive feedback from candidates.
It sounds like you're trying which is encouraging. I'll give you a few tips that I hope help.
> I adapted the traditional whiteboarding exercise
Lots of engineer types freeze when they have to make a presentation. I remember a meeting early in my career with literally three people in a conference room and I almost had a panic attack. No white board. People I already knew. All I had to to do is explain my ideas to three people. I did improve. I've given many public talks sometimes to hundreds of people and today I like public speaking. But I'll never forget where I started and that the person I'm interviewing might be very nervous. Putting them up on a whiteboard and into presentation mode only amplifies that nervousness. Just talk to people. Get them into that flow that comes from talking about something familiar that they are excited about. For most people a whiteboard test is not exciting. But if you give me a paid take home coding exercise, that's exciting. I like code, and I like to get paid for it. So if you really think you need a test, consider a very high signal test that is the exact work they will be doing.
> I make sure to ask for feedback on the exercise and I've gotten all positive feedback from candidates.
In an unequal relationship like that you are going to get a lot of false positives. If I really needed a job my response would be "loved the exercise, looking forward to talking to you more and discussing next steps if I'm the right candidate".
>Lots of engineer types freeze when they have to make a presentation. I remember a meeting early in my career with literally three people in a conference room and I almost had a panic attack.
That's definitely an unfortunate experience, but isn't giving presentations to explain your ideas - sometimes to people you don't really know - actually a significant part of the job? I'm an IC, and I present designs and project plans for feedback to groups of up to a couple dozen people, or to VPs, on a pretty regular basis. If I couldn't do that competently I would be failing at my job, because that kind of communication is just as important as actually writing the code. If I were conducting an interview and discovered that "public" speaking on the order of a few people in a conference room was extremely difficult for you, I'd probably consider that an important red flag.
> isn't giving presentations to explain your ideas - sometimes to people you don't really know - actually a significant part of the job?
For many engineering positions it is not. There are loads of shops where the developers, even senior developers, mostly just write code. I have hired many of them and put them to work successfully building stuff while I deal with the meetings.
> If I were conducting an interview and discovered that "public" speaking on the order of a few people in a conference room was extremely difficult for you
And yet I worked very successfully as a junior developer for a couple of years before I ever had to attend a meeting like that. Among the other 100 devs in the shop, I was considered a top talent at coding. That's not to brag but to point out that I was adding lots of value to the company without having to attend meetings with people from other departments. My manager did that. My manager did not code, although he could if he wanted to. In fact at that company they created a separate path for highly talented engineers who wanted to continue coding but wanted to avoid management and meetings. That was a couple of decades ago and less common, but I think it's a lot more common now.
And the fact that I can now publicly speak in front of hundreds of people should hopefully encourage you that it's something people can learn if they want to. Some people don't want to. There are roles for them too.
Isn't there just a bit of condescension in that title? It always sounds to me like something invented by a manager to be dismissive of someone who doesn't manage anyone.
I never got the vibe that "IC" was intended to be dismissive, or intended to be a pejorative or anything. I think it's more of an HR thing, because the distinction between IC vs Manager usually affects compensation and blah, etc. Whether or not that should be the case is a separate question.
I always assumed the term just leaked out of the HR world and into the general parlance.
If you're in a place where an IC can potentially make half a million or million dollars a year and drive some very interesting project work and be highly respected, no.
If you're in a place where not making it into manager track puts a very low ceiling on earning potential and respect, then yes it can be condescending.
Individual Contributor, used to contrast with "Manager". Point being, my main job is to design systems and write code, but I still have to do some of the organizational stuff sometimes.
>There are loads of shops where the developers, even senior developers, mostly just write code.
Okay, so your experience is different from mine. I'm surprised that there are places where this is really not a meaningful job requirement, and I've never worked at one, but I believe you.
>it's something people can learn if they want to
Sure... but so is coding. Part of the point of an interview is to see what skills and traits you already have. If you're missing some, that can be balanced against the ones you do have - it's not a dealbreaker, but it is still a negative.
>Some people don't want to. There are roles for them too.
Again, not where I work. Engineering, even at relatively junior levels, includes collaboration and explaining your work. You can't just say you don't want to do that - or rather, you can, but you'll have no upward mobility and be managed out pretty quickly.
You’re right. But what are you trying to prove with on the spot coding challenges? That the candidate can implement a hash table from scratch in 15 minutes with O(1) performance?
Is that something they’re going to do on the job? Very unlikely. So why are you not only testing for it but testing for it in a fake time-pressured stressful situation that also rarely exists on the job? (Yes , we all have deadlines but when are they ever 15 minutes on the spot?)
Perhaps you should have entered the education field where you could give such exams day after day to your heart’s content?
People giving on the spot coding exams, or worse whiteboard coding exams are just assholes. They're trying to haze interviewees and make themselves feel better. There's zero actual utility to such tasks in an interview.
> Lots of engineer types freeze when they have to make a presentation.
I've seen one place that wanted developers to do a full presentation with slides and all to a group of people.
The topic of the presentation was completely up to you, didn't even have to be a technical subject. You could do a presentation on baking if you wanted.
Was doing presentations a part of the job of the developer? No. They wouldn't have to do presentations in their day job...
I didn't go for the job and have never understood what they were looking for.
I do something similar: I ask the candidate to take 30 minutes or so to design a system like an online library. What are the objects in the system, how do they relate, can you design a REST or graphQL API for CRUD operations.
Then if it’s a front-end position we can move onto UI components for it; for back-end or full stack I focus on implement a couple of the CRUD operations.
You really get to see how people think and will work on the job with questions like this.
Implementing a sorting algorithm from scratch is a waste of time in many projects: use your libraries and get on with life. That’s why such interview questions are not important to me.
>> You really get to see how people think and will work on the job with questions like this.
Interviewing is hard and I applaud you for trying something newer and more realistic but I'd be cautious in thinking "spend 30 minutes designing a system and be prepared to defend your work with massive risk/reward hanging in the balance. Begin... NOW!!!!" is representative of how someone will work on the job. There are an awful lot of people who will solve the crux problems driving home after the interview or the next morning in the shower vs. on-demand.
I certainly don’t say BEGIN NOW! It’s a conversation. I continually ask questions during the design and ask the candidate to speak about the decisions being made.
In all honesty this process can easily last more than 30 minutes.
This is not a hard problem for someone with the experience I want, and there are many different correct answers.
Agree. Its far more valuable to see how a candidate approaches problems than some memorized recital show. I don't expect perfection, but if their reasoning is sound that becomes clear fairly quickly. I usually also include some imperfect questions purposely to see how they handle that. While we wish client projects were nice and clean with orderly data and tight requirements, the truth is that is rarely the case. It's useful to see how the candidate responds to those types of things. I had one gentleman argue with me about one of those questions claiming you would never see primary and foreign keys between tables not perectly match in the real world. Well when you are matching data from entirely disparate systems, you typically do. Anyway I digress.
I agree. I really dislike being asked to produce code of any complexity in an interview setting, although I do think it's important to see a candidate's code to understand how they solve problems for more senior roles.
Personally I'm way too anxious in interview settings to produce decent code. In interviews I find myself trying to get everything right first time, but in reality that's not how I work. I prefer to develop iteratively and debug as I go.
I'm also quite a slow and deep thinker. It's not uncommon for me to think about a problem for a good 15-20 minutes before writing any code. In this case I guess you would have some time to prep the night before, but I'd still be very nervous about coding on the day.
I prefer home assignments and that's typically what I'll do when interviewing people. I like to keep it simple and open ended. Simple because I don't want to waste their time and open ended to allow them some room for creativity because often we don't have explicit requirements in the real world. This has always worked quite well.
>I agree. I really dislike being asked to produce code of any complexity in an interview setting, although I do think it's important to see a candidate's code to understand how they solve problems for more senior roles.
I've never been a big fan of giving code interviews, however when I have to give them, I'm far more interested in the candidate's thought process around how they understand the problem and what needs to be considered in building the solution.
I agree, and I think this is where the value in these kinds of interview techniques lie. As the interviewee though, I have to say that the high-pressure situation makes me feel very... exposed(?) when I have to elucidate my thought process in real time.
I will say that one of the best "interviews" I've had included a portion where I worked with one of their engineers on a design problem they were actually having. It felt very collaborative, which allowed me to relax a bit, and I think we came up with a pretty good solution. I didn't mind doing "free work," because for me, it's fun to solve problems like these.
>I agree. I really dislike being asked to produce code of any complexity in an interview setting, although I do think it's important to see a candidate's code to understand how they solve problems for more senior roles.
I've been around the block a few times and I LOVE system design interviews, both as an interviewer and interviewee. They are much more collaborative and "fun" for me. The good news is that I've been managing for several years at this point, so those types of interviews are far more prevalent than coding.
Takehomes:
The minute you allow for them to ask for 2-3 hours of work. That's the moment that they'll ask for 40+hours of work for free (and call it 2-3 hours).
Also they'll try to claim copyright on your work (with pay) and reject you outright.
I agree you have to be careful. However the takehomes I have had were a few hours of work paid at 50% of the hiring rate and that was where it ended. Great experience. There are companies out there doing this to make a great interview process and companies out there who want free work. It should become obvious which is which very quickly.
How could I be mad if you are guaranteeing pay for this moonlighting? At that time it's freelance work. However, if you're going to limit to 4 hours: If I don't have doc building copy, and tests done on that 4 hour mark, you're not getting those extras.
> Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal.
Agreed. The best jobs I've taken had interviews like this, or paid assignments.
Talking about code that someone has already written is missing the element of productivity. Since we pay you by the week and only get so many hours a week out of you, we need some way before we hire you to understand what type of output we can expect.
The best way I know would be to work with someone for a week or two on a real problem, but that's way too expensive to trial a junior role.
At least for us, the system is more optimized around avoiding false positives than ensuring we don't pass over someone good.
Due to a lack of imagination and people who don't host interviews on a regular basis so they never put in the effort to get good at it. When I conduct a technical interview we are going to end up doing some stuff you do in your 9-5. And you probably won't even notice it. And if there is a budget available for it, I'm going to pay you to do a very small coding assignment. A few hours. Almost exactly your 9-5.
The fundamental difference is that a job is directly at stake based on your performance. For many people, this makes them more nervous than they would ever generally be during work. Due to the nature of interviews, I don't think there's really a way for it to be otherwise.
>> The best way I know would be to work with someone for a week or two on a real problem,
So if I get the job will we just touch base ever week or so? This sounds unlikely. Why can't you break work down to the point that you can pay me for 3-4 hours of real output and then use that to evaluate my quality?
All these tests around recursion and linked lists, etc are a feel-good proxy for actually measuring suitability, If someone is actually implementing them (IF!) it's not the junior, new-person; it's the senior architect who does it once every few years in a shared library. I can count the number of times I've used recursion in (a) a non-toy implementation and (b) not ripped it out and replaced with a faster, clearer iterative implementation on one hand.
> Talking to someone about code they have written and the decisions and thinking around their own code is so much more respectful and gives better signal
where have you been all my life? ;)
I'm an autodidact, zero formal bg in comp sci. I suck at timed tests and algo interviews. Fifteen years I've been at this and I've worked with several 'full stack' teams, none of which had a single engineer who was within a thousand miles of what I could do with CSS (and they're mostly utter slobs wrt HTML). And as to the endless javascript demands, I will never be of interest to google (and the feeling's mutual) but I always get the job done, and often the job is something FE that none of my esteemed colleagues would know the first thing about how to achieve, comp sci degrees and recursion expertise notwithstanding ... not to mention that every one of them has as many stack overflow tabs open as me.
I'll get back to my sorry little js projects now, maybe I'll get another job before I grow old and die ;)
Are you hiring for first year beginners? Or is this also a test for your senior software engineers?
Your question topics are completely useless to normal software engineering work. And this proves how immature your company is, in understanding the nature of the work.
Perhaps you should consider asking them instead, what their technique is to ensure reliability, throughout, and redundancy in their code? Can they make their code self-heal itself? Or to make some minor decisions to restart itself, if optimal conditions are not met.
Making people write code on paper is just ridiculous - way outside of testing and checking reality - and your reasoning of
>"because it shows that they know how to think about code"
means nothing at worst, and at best indicates you'll only be happy to work with people who are replicas of yourself.
Take home is the way to go, unless the position is some sort of public exhibitionist analogue developer position.
The least I think you can do is move from paper to machine, and inform them they should bring their own machine, or offer them use of one with many envs preconfigured.
This varies a lot. I had a take-home for a data engineer role which just asked to get and parse an xml and post a cleaned, limited json of the data. Took ~1hr. Perfect for an initial threshold.
The problem with take home interviews is that it could take one candidate an hour, and another every evening for a week.
Ideally the interviewer shouldn't be concerned about absolute code correctness, such as syntax or argument position, and should be interested more in how you're able to solve the problem, which should be a novel, yet simple task that doesn't require studying up on 200 level algorithms.
You want to hire developers (for permanent full time roles, at least) who have a good conceptual grasp of programming and logic, rather than their particular knowledge of a language or framework, or their ability to search on stackoverflow and run their code through a linter.
The worst interview problem I've been given was to write an AngularJS directive, I think literally to simply take an attribute and display it. I can't remember at the best of times the syntactical oddities of AngularJS, let alone when writing with pen and paper in an interview with no resources.
One of the better problems I was given was around parsing XML, from memory validating that opening tags matched closing tags, while allowing for self-closing tagsI remember the problem specifically didn't include any more complex facets of XML. Another was to reverse a string in-place ("hello world" -> "dlrow olleh"), and then to modify the algorithm to reverse the words but keep them in place ("hello world" -> "olleh dlrow"). Obviously in the real world you'd just use built in methods, but it's a problem that should be solvable without digging up your old lecture notes.
I've always felt comfortable writing code (or at least psuedocode) with a pen, but I think it's unfair to require a candidate to solve the problem on paper or whiteboard if they feel more comfortable typing on a computer instead, all that achieves is disadvantaging otherwise capable candidates who for one reason or another can't write code with a pen and paper. As long as they aren't googling "how to reverse a string in place", it immaterial what writing tool they use. If they feel more comfortable using a brush and papyrus, or carving a runestone, then that should be perfectly acceptable too (provided they bring their own writing material).
> Fibbonacci allows us to see that they have basic recursion understanding
I see no reason to use recursion when asked to calculate Fibonacci numbers. A loop looks like a more reasonable choice that also avoids typical pitfalls associated with recursion. Maybe that's because I did embedded programming for a while.
I suspect recursion is introduced in CS classes with this example, but people understand it as "you are supposed to use recursion to calculate Fibonacci numbers".
Recursion is often less efficient but looks more elegant and simpler. It breaks the problem down to is essence. Then you can trade some complexity for more run-time efficiency.
Beauty is in the eye of the beholder, but a loop is hard to beat as far as simplicity goes, and you don't depend on your compiler being clever enough to optimize tail recursion.
If you need to traverse a tree then sure, but with Fibonacci you don't even need the stack to begin with. You only need to keep a previous number.
You don't even need a loop. Binet's formula gives a closed-form expression for the Fibonacci sequence. (And of course I don't remember that formula off the top of my head, but I know it exists, so I'd be 90% of the way to solving a problem which required it.)
I think that your test if fairly easy and since it requires very little time before that, I dont understand the opposition of other people.
But, you are not seeing how people think about code. You are seeing presentation prepared before hand. That whole part abour seeing how people think, as much as it is repeated, is nonsense, so maybe it is not much of loss.
This sounds like an inspection of whether the person has had a class in basic algorithms rather than if they have ever coded anything in real life.
In school I played with sorting algorithms, in business if I ever found a developer manually writing a sorting algorithm, I would consider them inept (unless there were very specific reasons to do so).
If someone didn’t know how to sort a list using the built in or standard library of whatever language they are using, I would know very quickly that they have almost no experience writing anything useful.
In fact now that I think about it, it might be a good test to see if they are passionate enough to be a great problem solver:
When was the last time you wrote a sorting algorithm?
Acceptable answers:
- You mean sorting a list?
- In school
- Why would I write a sorting algorithm?
- Never
- (Glazing eyes and other body language that indicates frustration)
Red Flags:
- Anything that indicates they think writing a sorting algorithm is a perfectly logical thing to do during the course of software development.
(Note: The problem is sorting may seem like a well-understood problem, but it’s actually not. Only a person who studied the algorithms in school as an assignment would feel comfortable with that code.)
Acceptable answer: it depends on what I'm sorting. Is it a primitive like char strings, numbers, or a more complex data type? Could it have null values and type mismatches, am I using a strongly typed language? Does it need to be cleaned first?
I think the ability to come up with relevant and important questions to ask about the task given is more crucial than whether they can solve it. You can look up answers to questions from hundreds of good sources, but you need to be able to generate the right questions that need to be answered first.
If you're given a blank slate and asked to sort a list without using a library without any gotchas, complexity requirements, space requirements, expectations that the code is completely free of small bugs etc.; and you can't do that after some thinking even to a basic degree, then you're just not a good programmer.
As a programmer, your task is to find algorithms to solve problems. Sure, sorting numbers is a solved problem and in real life you should use a library. But you will not find a library for each problem you encounter, and sorting is a very simple problem to solve compared to anything you'll find in real life.
I agree, but how is applying pre-learned algorithms significantly better than using pre-build libraries? Both is about using an existing solution, instead of coming up with it on your own. The real approach would be to ask candidates to solve a problem that doesn't easily fit into any popular category, so that they have to come up with an original approach - but that is first hard to come up with, and 2nd it would require investing extra time on both sides, which usually neither candidates nor interviewer can afford.
Yes, that's a good point, and in our interviews we do try to take a slightly less well-known problem, at least one that doesn't have a dozen well-known named algorithms.
Still, even using a pre-learned algorithm demonstrates some level of confort with algorithms in general, and can be used as a stepping stone during the interview to shift the problem slightly to see how they adapt the algorithm.
For example, if a candidate is clearly taking their time and essentially working out the algorithm themselves, and succeeding, that demonstrates the skill and we can move to other problems. If the candidate just breezes through and finishes in 2 minutes, then we can change the problem ad-hoc to try to get them off the beaten track a bit (say, if they wrote quicksort, maybe ask about making it stable, or sorting even numbers differently from odd numbers, off the top of my head).
My point was that if testing for a skillset, using something that favors those who have toyed with a specific algorithm is the same as asking trivia questions.
Trivia does not provide evidence of skill, it demonstrates prior knowledge.
It would be better to introduce a unique situation that would place everyone at the same starting point.
If the expectation of the interviewer is to see if they know quicksort, then I fully agree with you. If the sorting problem is simply used as a (rather uninspired, granted) stepping stone to checking that the candidate has basic algorithm-finding skills, then I think it can serve this purpose (though less well-known but still relatively simple problems would be better). I gave an example in another thread as well, but in principle I would change the problem up a bit if the candidate is obviously producing a well-known algorithm; whereas, if the candidate is working out the solution themselves, I would be happy with that and move to other topics.
Even so, knowing very widely talked about programming trivia is still a signal for interest in the art. I'm not sure that sorting algorithms are a good example of what I'm thinking, but I always award extra mental points to candidates who seem knowledgeable about the field (e.g. they know the general consensus on manual memory management vs garbage collection). Still, I wouldn't consider these sorts of things dealbreakers by any stretch of the imagination.
I’ve been interviewing at a lot of places lately. I _never_ white board interviewed before this round of interviews I’ve done And at first I have to say that I hated it so much.
In a weird way though, I’ve at least grown to understand why it’s so popular, and I don’t think it’s just because FAANGS do it (though I think that’s how it came to prominence). It boils down to showing as an engineer your capable of being flexible and malleable your change and understanding. Some places definitely do this better than others, and I think it says a lot about company culture if they are Adversarial about it or not. In my experience rather unfortunately even good places to work can be adversarial about it.
The massive downside is and always will be it puts so much onerous on the candidate because you don’t really know what they are going to ask and freezing up or getting stumped is very frowned upon in these style interviews from what I experienced.
My tip to anyone though is just to practice, but I’ve yet to encounter places that don’t employ some technique to test algorithmic thinking and understanding of complex systems in some way.
Seems over-complicated, e.g. I probably wouldn't go for recursion for Fibbonacci, so I'd miss your expectations completely. Why not just ask a direct question on things that you're looking for? If you care about recursion, ask them to implement simple recursive tree walker or something. Equally linked lists are something that in modern languages almost no one will have to manage by hand. If you care about understanding the concept of pointers/refs, why just not asking directly about that.
Have you tried just having a conversation about pointers and recursion? Does that not work as well (or better)?
Kudos for letting candidates know what’s going to happen, it’s just that when I see problems that are clearly just a stand in for “do you know X?” I always wonder why interviewers don’t cut to the chase and just ask directly. “Are you comfortable with recursion? Can you describe it? When does it tend to be applicable?”
Some people (myself included) can bullshit through such questions pretty well even when we don't know the answers. It's a skill, a combination of reading body language for clues, being confidently vague in the right places and turning attention away from dangerous questions with charisma.
You learn it quickly when teachers do oral exams at university :)
Code doesn't lie, so I understand why people like to check candidates that way instead of relying on talk alone. I would just prefer if it wasn't a hit-or-miss test on what algorithms you memorized.
It does not matter how us think, I believe these detail-oriented algorithm interviews are intentionally designed for younger coders who can still do them out of memory, though in practice they're not very meaningful and if you really need them sometime you can always dive-in and get what you need.
I'm doing leetcode now, as a senior engineer there is no way to get a decent job without being tested like a college fresh-out as far as programmer positions are concerned, no complains, I will do them, it is the market picks me, not the other way around.
To me even though this is painful, but at least it is "merit-based", what I dislike the most is that you got a job based on other factors instead of how able you are.
IMHO all you need to know is to recognize a certain category of problems and remember that there is an appropriate algorithm for it - and if can you recall the name even better, will save you some time googling, but it's not that important. After consulting the documentation and if you previously learned it in a school/course, you'll be able to implement it in pretty much the same time as someone who knows how to draw it on a whiteboard from the top of their head.
Just using a graph was the highlight of that month for me. (The data wasn't already in a graph.) Reading the wiki, it may have been Dijkstra that I used under the hood. (I just wanted the sum of simple paths for all leaves to the root, for each leaf.)
How long did DFS take? In my experience, with Spark it's like factor of 100 slower than what one would expect on a single machine and a sizable dataset.
When I was at Microsoft, we used data structures quite often in our service that powered Azure Frontdoor / Azure CDN.
Some of the stuff I personally worked on was tries and nested tries for routing/cache purge, LRU & variants for the caching algorithm on a cache node, and I implemented consistent hashing for the distributed cache.
There were some algorithms stuff for load balancing, but I didn't work on that.
I know there was a few other things, but I can't remember them right now.
Quote: "... but I have come across everyday use cases of data structures and algorithms when working at Skype/Microsoft, Skyscanner and Uber"
Considering Skype is at best laughable compared to other IM applications, I'd not boast about working on it. I used Skype over 10 years and after it got bought by Microsoft it gradually started to be worse and worse, to the point I had to look at other IM in order to communicate with my clients.
I have a question, why is that Whatsapp and FB messenger can and will deliver notifications when you receive a message every single time, while for Skype this seems to be an unachievable feature?
I once thought it would be difficult for big tech company recruiting processes to tell the difference between:
a) A really good problem solver
b) Someone who has ran through all the example interview problems on leetcode or something similar
Then I thought that this might be similar to the Turing test. Once you’re that good at faking it that you can convince someone else - maybe the difference doesn’t matter at that point.
I sometimes suspect that everything is really just a sorting problem.
For example, here is a shell script that takes an input file consisting of lines of the form
X Y
where X and Y are integers representing the X and Y coordinates of live cells in a Conway's Life grid, and outputs the next generation in the same format. It runs in O(n log n) where n is the number of live cells, and it is really just sorting.
I have used graph algorithms a little bit at work. For example if you are generating code for a language like C where order of declaration matters, you can use a directed graph to represent dependencies between data types and then use a topological sort to order how you write structs to the header file.
I've done an awful lot of investment in booktime to learn various algos, simple to obscure, and frankly never used any of them. I do find that depressing.
What people seem to want is big-data or various tech stacks. I look forward to the time I can put even a bloom filter to work.
I implemented a bloom filter for the KeePass plugin [1] I wrote, using the data from HIBP. It was pretty fun and there were some challenges that you won't typically encounter in online guides.
Still, that was a hobby project, I've never had to implement anything similar at my regular job.
One algorithm I keep coming back to is Aho-Corasick, which locates all occurrences of a set of keywords in a string of text in linear time. (https://github.com/ahnick/ahocorasick) It's been useful anytime I needed to locate patterns in a group and I didn't want to be looping back over the group repeatedly.
I've used loads of algorithms to solve problems during work and memorised the mechanics of none of them. It seems memorising this stuff is the opposite of how to work effectively with computers.
I think it's nice knowing about analogous problems. If you know what you're trying to do is similar to NPC, one can quickly either dismiss the feature/problem, convert it to a problem with an existing solver, or maybe know that in general it's hard to solve but a relaxed variant is good enough.
I'd wish more of those problems showed up in my daily work, though.
Btw, a cool popsci book about algorithms occuring in day to day life is "Algorithms to live by".
Let's say someone can solve the algo problem, what's that show?
Mostly that they prepared for an algorithms question.
It may be a good filter for 3rd-wave do-as-you're told programmers who stay in their lanes, produce by the book expected code, and just consistently obediently build things.
They wan better cogs for the corporate software machine.
If people are asking me algo questions, the job probably isn't right for me because my answer is "it depends". Last time I took one I was thinking "there's like 4 answer to this, what the fuck do you want?" it might as well have been "I'm thinking of a color" ... they have something written down and called it the "right" answer.
I gave a parallelizable answer, they wanted single threaded. I gave a single threaded one, they wanted 2 passes. I gave them a 2 pass version, they wanted one that didn't use collections.deque, I mean it was nonsense. "Guess what's on my piece of paper!" Cool beans bro.
Some people would have given them that answer the first time, I'm sure of it. Not me though. Not during the interview, not during the day-to-day.
I don't know how. I really don't. I don't know the right answers, all I see are a bunch of possibilities. That's why I'm first-wave.
The writer of homebrew isn't what Google is looking for anymore. His time to get hired there closed around 15 years ago. After the revolutionaries comes the administrators, a far less interesting but necessary entourage.
The people like me have all already quit. I've actually got nothing to offer them.
If so, they're pushing "conformity" and "being a good cog in the machine" well past the point of cargo cult programming. That's what this algorithm-based interviewing is all about: a textbook cargo cult. And people wonder why they aren't seeing quality.
I'm not so sure. Maintaining and building an empire are dramatically different.
Companies that could build and not maintain: Lotus, Digital Research, Palm, Netscape, MySpace, Digg, Blackberry, Ashton Tate, it's a different set of skills. Heck, you can even toss the French Jacobins in there
They all shot themselves in the foot, I know, that's the point. Not having their eye on the ball and instead looking over the horizon is what built the empire, but then the ball hit their nose
Some people can do both (gates, zuck, bezos), but once you're at the Apple/Microsoft stage, you need the second group.
Whenever I interview engineers, my main priority, beyond grasping whether they understand the stack they’ll be working with, is gauging how well they can work in an organization of fellow engineers, designers, and product folks to deliver a product and support the larger engineering team.
If they can pass that hurdle, you can almost be certain they know how and when crack open an algorithms textbook or use Google-fu to apply the right algorithm to solve a given problem.
(Knowing which data structures to reach for is far more applicable than being able to apply algorithms from memory. The article is good evidence of that.)
I internally have something I call the "scramble score". If I hire someone to say, do some python backend and then a few weeks in I'm like "oh shit, actually this big deal we're doing needs us to get an iphone app together" and I can be like "hey, can you go from python backend to do an iphone app?" and a week or so later I'd have a basic app.
Those people do exist. Really, they think it's a thrilling joyride. Hard to find, but they're real. I look for those and run the team tight and small.
Not at all. it's a different kind of job for a different kind of person.
Fabrice Bellard, Ted Nelson, Theo de Raadt, Patrick Volkerding, Richard Stallman, Larry Wall, these people aren't off working at stable ibm-like firms. It's a different kind of thing. Look at Nelson's fiery career crash when he worked at Autodesk. Look at Woz and Paul Allen walking away or Bushnell getting rid of Atari. This isn't the grab-and-dash modern unicorn stuff, these people saw it wasn't right for them. The company outgrew them.
They couldn't do the job. That's not where they fit.
Chefs make terrible bus boys and bus boys make terrible chefs.
That's the big important lesson: The Chef is incapable of being a bus boy.
It's not "too easy for her" and she's not "too smart for it". The chef can't consistently, reliably, and efficiently do the tasks. The hierarchy is illusory, it's all about fit.
Drucker explains this better than I ever could. He's a good read
What does this have to do with the bulk of the article (which is about algorithms the author used at his jobs, and only tangentially (IMO) about the use of algorithmic questions in interviews)?
It has to do with the rest of the comments in this thread
at the time I posted it ... I was replying to that sentiment.
The vast majority of algorithms I use are for parallelizing complex workloads, failure detection, and scoring systems. I usually DIY after I find the OTS ones unsatisfactory.
I'm not "smarter", they're general solutions but all I seem to have in life are specific problems so specific solutions perform better.
I've used Sort method several types both in Java and JavaScript but they way it's used it as a library function, I don't need to write my own sorting algorithm. Same for Data Structure commons ones I've used are found in Java Collections - ArrayList, LinkedList, HashMap, Set etc. For Deep Learning have used several algorithms that are best practices and common data structures like Tensors and Vectors. I realize the value of knowing the theoretical underpinning but practically speaking these are only ever written one by library creators, no idea why companies insist everyone to know these and implement by heart, they can ask much more interesting practical problems.
Java is an interesting one; while you don't write the sorting algorithm, you do write the sorting conditions, a function that returns a number depending on the compared values. Likewise there's hash functions, although in practice those will be generated by your IDE or Lombok. (I haven't been into Java for a while so there may be better alternatives, iirc Scala and / or Kotlin solve it as well)
The point is, they should not actually require candidates to recall these things from memory. But there is certainly value in the non-memorization part of this knowledge and the ability to solve this kind of problems distinguish people who can think from those naive jobsworths. If nothing, they are better than back-of-the-newspaper if-you-have-seen-the-answer-you-know-the-answer kind of trick questions.
There's a huge distinction between "used" and "implemented myself".
I've used quite a lot of features from RDBMs, as well as topological sorting, LRU for caches, Unicode normalization, graph traversal, bloom filters, hash maps and so on.
I'm not payed to implement algorithms or data structures, but to solve problems. So for anything non-trivial I tend to use ready-made libraries.
I only implement stuff myself when it's faster and simpler to implement AND TEST it than to draw in another dependency, or if there isn't a well-made off-the-shelf component.
So what I've implemented myself at $work is pretty limited:
* depth-first tree traversal
* graph traversal
* parsers for various non-standard file formats
* maybe a topological sort once, not sure
Finally, many classical algorithms have lesser-known variants that optimize for some practical advantages (reduced memory usage, memory cache friendliness, sequential disk reads/writes etc.). So if I were to implement, say, a substring search, it might not be a by-the-book Boyer-Moore algorithm, but some subsequent paper that builds on it to add a few percent practical performance improvement.
You still have to understand how things are implemented by others (even at a high level view: ex: what is a RDBMS index) to be aware of their advantages and drawbacks to make the best use of algorithms available to achieve your goals (ex: performance of the solution, ease of evolution of the solution).
I agree. It's good to know a name of an algorithm/data structure, and rough characteristics (like bloom filter: O(1) lookup, super memory compact, statistical, can have false positives, no false negatives; perfect for caching lookups in "forbidden" lists).
There's not much point though in knowning the minutiae to the level that you can code one on the whiteboard without prior preparation -- which is probably the main point that the article relates to.
And this is the measure of a good engineer -- recognizing that it's most likely that battle tested libraries will have superior implementations of algorithms than whatever one can draw up oneself.
I use the STL daily. I know fairly well the complexity guarantees behind each data structure. That's one of the things I like about it versus other collections libraries. It forces you to be somewhat literate on data structures in order to make the right choices.
But no, I could not write you up a red-black tree from scratch without going away for a few days with my Knuth books and a few pots of coffee. Sorry.
For interviewing, I find it most useful if we ask a question that is an algorithmic problem to solve (but we don't tell them it is a graph problem and obviously it's not something as classic as Dijkstra). Then we observe if the candidate can formulate it as such, or can formulate it as anything useful (often there are several options, e.g. some find the problem to be dynamic programming). This gives much more information about the analytical skills of the candidate than about their algorithms knowledge. In terms of knowledge, what I find useful is just to ask what is a hashtable and how it works.
Of course, there are positions where this kind of skill is unnecessary and I cannot know everything about the false negatives. But failure in these areas also correlate with poor coding skills, at least in my experience of a free hundred interviews.
False negatives is right. You're skipping over a lot of good engineers with this approach and you'd have to interview fewer people if you could avoid that. How many times even without the pressure of an interview have I been stuck on what seems like a hard problem and then I go for a walk and end up running home because the lightbulb goes off and I can't believe how "stupid" I was and how simple the problem was.
Algorithms come up all the time. Sometimes standard algorithms to use, sometimes to implement or modify slightly, sometimes as something completely custom where some inspiration is drawn from the classics.
But does this mean you need to learn them by rote or be able to figure them out on a whiteboard? No. And although they appear regularly, I don‘t spend enough time on them that this would meaningfully affect my performance. So the time you spend thinking doesn‘t matter, very unlike a whiteboard situation.
I'm not at all opposed to companies like Google, Facebook, etc asking Algorithms, Data Structure and Big O related questions. Why? It's very applicable to problems at their scale. That being said, not all engineers there work on such problems.
If I'm asked to do a BFS/DFS, Tree traversal, etc for a small company.. I tend to share high level how I'll solve it then basically not actually code it up and say something like "This is pretty tricky...". Why? It's my way to exit the interview quickly because I question the ability of the company to hire talented engineers. Especially when I test your product out and see all sorts of inconsistencies.
Okay, so when do Data Structures matter to a company?
Are you building a product that needs to perform very efficiently at scale and the system is doing something outside the "norms" of what a data store can provide. Examples: Facebook's TAO system and their type ahead search.
Read the design paper for TAO and you'll see how they use very primitive data structured related to Graphs. Their typeahead system also makes use of some very basic data structures and some probabilistic data structures as well.
When do Algorithms matter to a company?
For most traditional companies, you're not going to do a BFS/DFS search, traverse a tree or a Dynamic Programming solution like Levenshtein distance. So unless these algorithms have a practical use case in your company, you're just creating a sort of monoculture.
Once again, Google and Facebook do apply these algorithms so I respect their interview process.
Big O has its place in such large companies. I think most people fail to understand the purpose of Big O; identify upfront if a solution will be sufficient from a time or space perspective as the data grows. Most people speak about Big O on interviews AFTER they code up the solution. You should do that before you code it up.
e.g, So the data for this problem is <100 items then this quadratic solution would work, but if we scale the data set up to say 10,000 items then it won't work. Then you can look at data structures or sorting algorithms for instance that'll help you get it down to say O(n) or O(n log n) etc
Look, I get the frustration a lot of people feel about this sort of interviewing process. I have a very non-traditional background and it could be very scary when you first start learning about this. My advice? Learn it for your own good. It'll make your a better programmer and it'll help you become more aware of so many things you weren't aware of before!
The moment when you realize why using an array for a Min Heap or why a Min Heap must be a complete tree... you'll step back and go "Now that's sexy!" Or when you realize even stupid stuff like "A balanced binary Tree has this weird reality that the leaf nodes account for 50% of all nodes in the tree" It's just fun if you see it in a positive way.
Let's call technical interviews that ask such questions when it doesn't represent the company "interviewer imposter syndrome". When a company tries to act and look like Google early on.. Google has a million+ candidates a year interviewing with them. They MUST allow good candidates slip through their process.
546 comments
[ 7.8 ms ] story [ 343 ms ] threadI remember a stint in research, about data analytic non the less, where rarely anyone had a good grasp of SQL or any other way to persist data for that matter. It really puzzles me to this day.
Might be me finding most ORMs to be harmful if used without understanding of the underlying technologies.
See eg https://en.wikipedia.org/wiki/Persistent_data_structure and immediately notice the warning 'Not to be confused with persistent storage.'
But immutable data structures are always trivially persistent.
The problem was to divide a text into a number of tweets to make it a thread, with the obvious constraint that no tweet should have more than 280 characters, but you still wanted to minimize some cost based on how far your tweets were from 280 chars and where you divided them (e.g., dividing after a full stop is better than after a comma, which is better than between two works, which is way better than midword).
With a reasonable cost function, this really seems a textbook dynamic programming example (possibly much more credible than the entering-a-treasure-cave-with-a-rucksack story).
That immediately brings Tex box badness to my mind. And the related line wrapping algorithm: http://www.tug.org/TUGboat/tb21-3/tb68fine.pdf
Good spotting BTW, the line wrapping algorithm (where each tweet is a "line") is a perfect match for the post you are responding to.
When doing programming competitions, you're often trying to figure out what standard algorithm is similar to the problem and how you need to tweak it to match.
Eric's mit video on this : https://www.youtube.com/watch?v=ENyox7kNKeY
leetcode https://leetcode.com/problems/text-justification/
On topic to the original post, I implemented Knuth-style line breaking in the Android text stack (working with Anish Athalye who was an intern at the time and did the first prototype). There were a bunch of nicely tuned implementations of advanced data structures and algorithms in there.
https://lobste.rs/s/n8tyip/data_structures_algorithms_i_actu...
I still say it is a bad interview question, but there were lots of interesting examples I learned about.
- GCC splitting IA-64 instructions
- Trellis quantization in lossy video encoding
- Knuth-Plass line breaking algorithm (mentioned here too)
- Some algorithms I knew about, but which can be considered dynamic programming (I'm not sure how interesting this is): A* search, Dijikstra's shortest path, Myers common subsequence algorithm, transitive closure algorithm
I would say the GCC one is most interesting because there's a link to the actual code and comments by the developer.
https://github.com/gcc-mirror/gcc/blob/master/gcc/config/ia6...
I think it could be one of those cases where if you had a more obvious representation you wouldn't need a clever algorithm, but there is probably some other reason (good or not) that instructions are represented that way
x86-64 (and most other architectures) can use multiple units at the same time using what's called a superscalar architecture. There's a hardware unit that figures out what units are in use and what instruction just arrived, and can either send the instruction to ALU0 if it's unused, or ALU1 if ALU0 is in use, etc.
But this hardware unit that does scheduling is complex, it takes up space that could be used by other stuff. IA64 aka Itanium, not to be confused with x86-64, is a VLIW (very long instruction word) architecture. The underlying assumption is that the compiler knows in advance what operations it's already emitted, and what operations are coming next, and the compiler can be considerably more complex than the hardware scheduler does. So a VLIW instruction isn't just "add eax,ebx" like x86, it's more like "ALU0: add r12,r48; ALU1: add r93,r42; SHIFT: r60,12; MEM: load r17,r32". (Itanium had 128 registers) The compiler had to do a bunch of stuff that modern CPUs do in hardware. I think it even had to deconflict instructions; like the compiler had to know that an addition takes 3 clock cycles or whatever, so if you used ALU0 on cycle 123772 and then tried to use ALU0 again on 123774 something bad would happen, but don't quote me on that.
So at some point the compiler is going to have a DAG of operations that need to get run in a block, and it needs to bundle up those individual operations into bundles of (I think) 4. Sounds dynamic programmy to me. At least I think that's what's going on.
It turns out that most code is pretty branchy, which means many lines of code will have multiple entry points. This invalidates the assumption that the compiler knows what operation it just executed. So in practice, VLIW architectures aren't able to achieve their theoretical performance, and superscalar architectures are better.
Unfortunately some old school teachers whet not keen on dyslexia diagnosis
But the general understanding of algorithms and complexity did help even in CRUD apps. It gives the bricks to form mental model of the underlying system. I don't need to code a b-tree but I may need to tweak its params.
Some research gave me Levenshtein distance and from there I first used a naive perl implementation before finding that you could extend MySQL and found an example and implemented that.
Took me 1/2 a day to go from zero to working prototype
I have been tracking luthiers and it is fascinating how detailed and varied each builder is.. the likelihood that the instrument will sound good is well correlated to how much time the luthier puts into refining his process. I don’t understand the rational for not wanting to learn DS/Algos this is just one part of it, there is also the whole business/customer side of writing code. There is a difference between never getting a demanding customer who understands the difference between a good instrument and something glued together and not wanting to know how to do something more than glueing it together is appalling. As a coder if you want to learn DS/Algos and you do not find a job the values that maybe there is more to learn so that find a job that values it. It will be competitive and you can fail but it is not wasted.
It's OK to ask people general questions (what's algorithmic complexity, what kind of algorithms and data structures they know about, what are the tradeofs, etc).
But expecting people to remember the exact steps of an algorithm they last used 10 years ago at university is just stupid. It's like asking engineers to remember the tensile strength of a material they could use once a decade. That's what the documentation is for. It will take 3 minutes to look it up when I need it (if I need it at all).
It's even more important to recognize when the solution found with google is subtly wrong.
+ fibbonacci
+ a sort
+ a linked list
I like having candidates write out these problems on paper because it shows that they know how to think about code. Fibbonacci allows us to see that they have basic recursion understanding, and basic iterative loop understanding. Linked lists shows us that they understand pointers. And a sort shows us that you can structure more complex code well.
If you truly want the job, you'll take 15 minutes the night before to remind yourself how all of these things work, none of them should be particularly foreign or confusing to an experienced programmer.
That covers the coding part of our interview. For the problem solving part of the interview, we may give you problems that require using heaps or skiplists or graph algorithms, but for this part of the interview we're happy to let you import imaginary libraries that do all the hard work.
I write on paper so infrequently that I actually find it pretty difficult to write more than a few words. I certainly wouldn't want to write something out longhand in an interview!
Edit: It seems to me it would be rather unfair of me to ask people to write out their thoughts in Org Mode in VS Code just because that's how I happen to like writing notes :-)
I did it once or twice when I was 8 years old and didn’t have a computer yet :)
Seriously though - how long ago was that - not recently I hope?
That's pretty neat.
I'm struggling to understand what you mean? This is a learning opportunity for me, if you wouldn't mind posting a code sample or elaborating further.
A better language than Python can run this recursive version for arbitrarily big numbers.)
But yes, I should have written "naive recursive solution". There are many ways to fix it. It just wasn't what the question was about.
If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.)
But, agreed with everything else you wrote!
And I instinctively distrust Sufficiently Smart Compilers ;)
> I can't be sure without measuring, but I strongly suspect the overhead will be mostly in tuple packing/unpacking and GC.
I guess that's the same overhead as in this imperative version:
The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.
GHC is sometimes able to do some of those transformations.
> The recursive Python version above didn't use tail calls.
Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.
I was talking about this code:
Not sure what you mean by tail calls here. I don't see Python-level tail calls. The interpreter will call C code for tuple packing, but those aren't in tail position with respect to the Python code either.Why wouldn't the tuple packing be in tail position in the Python code?
Looking at https://github.com/python/cpython/blob/master/Python/ceval.c, here is the code that needs to be executed after the tuple is constructed:
I guess you could duplicate all this code in a special "pack tuple and return from Python function" C function which you could then really tail call.Any specific implementation, and in this case cpython, could do arbitrary weird things after.
Thanks for looking up the code!
This is not true. The recursive code will not compile with zero overhead even in haskell or lisp.
The code above will add layers to the call stack and has a speed complexity of O(N) and memory complexity of O(N).To optimize in Haskell you need to deliberately restructure your code.
The above code will have O(N) speed complexity and constant memory in Haskell. In order for Haskell or any language with tail recursion optimization to work the recursive call must take up the entire return expression. In short the coder must deliberately make optimizations and write recursion in a way similar to the original iterative syntax in order for such tricks to work.Though GHC is sometimes able to do some simple transformations on its own. But not in this case.
For anyone trying this at home: I suggest calculating your additions modulo some constant, so that the numbers involved stay within a fixed size. (Otherwise, you either hit the limits of Int and weird things can happen, or when calculating with the arbitrary precision type Integer, your numbers themselves will grow linearly in space.)
Additionally you have a spelling error on line 5.
To be fair, while the asymptotic runtime may be the same, the C version is about 180 times faster.
Though if we allow programs like the C example that give wrong answers or have undefined behaviour, I can write an even faster version that takes no time at all.
There is a O(log(N)) solution involving matrix exponentiation though, if you really need to get the big numbers.
That's not the type of thing I would ever expect a candidate to know in an interview, just something fun I've run across.
(And you can also use recursion in the fastest implementations. You just wouldn't use the naive recursive solution.)
I remember that it's possible but I forgot all the required math :) Now that I googled it it's not THAT bad
https://medium.com/@andrew.chamberlain/the-linear-algebra-vi...
Of course the only use is to look smart once a decade when the subject comes up :)
Whether this is "fast" or not depends a lot on the concrete implementation of your arbitrary-precision real numbers.
As a nice thing, the second term (after the first minus sign) is smaller than 1, so you can omit it by rounding the result to the nearest integer; all the game happens in the first term.
If you can do arbitrary precision arithmetic (including powers and square roots) in unit time, this one is fastest.
In practice, this algorithm is not the fastest, because handling arbitrary precision floating point numbers is a pain.
Have a look at the matrix exponentiation algorithm for Fibonacci numbers in http://pages.cs.wisc.edu/~mhock/SSL/fibcalc.pdf
You can implement the matrix exponentiation via repeated squaring recursively even in a language like Python that doesn't do tail call optimization, and it will still be fast: your recursion only goes to a logarithmic depth.
In any case, recursion vs iteration is an implementation detail. Especially if your language supports tail call optimization. Have a look at this example:
f is recursive function over tuples of integers. And f is basically equivalent to the typically iterative algorithm for computing Fibonacci numbers.fib 1 = 1
fib n = fib (n-1) + fib (n-2)
At least for this part of the interview, I'm not worried about your problem solving skills I'm worried about your programming fundamentals. We'll test problem solving in a different session.
Is this really a useful exercise? Why not present them with an actual problem that is relevant to your field and see how they approach it?
These are considered pretty basic stuff that every programmer should know..
The explanation I've heard is that good devs generally get hired after only a handful of interviews, whereas really bad devs are going to do a lot more interviews on average before they get hired, so you get a pretty skewed sampling even if there aren't that many really bad candidates around.
We are in a bubble, if we read programming blogs and think about programming in our free time, we are definitely not the kind that FizzBuzz exists to filter out. But from the perspective of companies, it makes sense if they really understood pointers or recursion or graph manipulation, because there are so many people lying on their resumes, not having sufficient analytical skills despite doing some resume driven cargo cult development etc.. And as an industry we don't really have an alternative to these algorithm interviews at scale, at the point we rely on non technical HR people to filter out resumes for us and they literally grep for framework/language experience.
Second level is how they explain the simple recursion that’ll hit stack limits (i.e. without tail recursion)
Third level is using accumulator/tail recursion.
See how they can express these ideas and are they able to effectively communicate their intentions.
I'd still have you write the full thing out, but I'm guessing you'd do just fine.
Only when the interviewer finds someone “smarter” than himself does he approve of hiring the candidate.
It is an ego game.
Perhaps this describes OP.
The interview process for the job I have now was a massive breath of fresh air.
The application asked for code samples and a cv. It was a small company and the CEO, CTO and direct co-workers all drove the interview process. The process was entirely conversational. First an intro phone call with the CTO and then a questionnaire via email in which I answered about 30 questions on various topics that were all very practical daily software development type stuff. It was painless to respond to each with about a paragraph in detail. Then a call with a direct co-worker about the questionnaire and this was my opportunity to ask questions of him about the company. Before getting the interview they actually read my code samples and reviewed my Github account. In the interview there was a ton of discussion about the company, its culture and all the of the above discussions. Following this was compensation negotiation with the CEO.
Everything about the hiring process said to me yes this is the place, they get it!
Or
“You do not understand recursion nor Fibonacci”
FTFY
Of course, the Fibonacci series also grows incredibly fast, so practically speaking, unless your language supports arbitrarily large integers, you'll never generate even 100 elements of the series.
What are the practical applications of recursion though ? Other than sorting and DFS ( well even DFS can be done iteratively with stacks ). I'll be curious to know.
I find testing for HashTable/HashMap knowledge to be far more practical than testing for LinkedLists simply because you can't escape HashTables in today's world.
Traversing and transforming nested data structures.
Just last month I had to write code that maps flat data from one system into a nested structure required by another system.
We wrote mappings as map literals and the code traverses them creating a new instance of the map filling the leaves with data from the input row and running some business logic on it.
I'd also like to add that because of this I adapted the traditional whiteboarding exercise at my current company to be about problem solving and design, and not about how many data structures you've memorized.
When a candidate comes in, I give them a fake-yet-realistic product requirement (like count elements in a real-time stream from field sensors) and let them run with it however they see fit. I put zero restrictions on the tech side of things in order to let the candidate shine (hopefully) in whatever tech they are most comfortable with.
I make sure to ask for feedback on the exercise and I've gotten all positive feedback from candidates.
> I adapted the traditional whiteboarding exercise
Lots of engineer types freeze when they have to make a presentation. I remember a meeting early in my career with literally three people in a conference room and I almost had a panic attack. No white board. People I already knew. All I had to to do is explain my ideas to three people. I did improve. I've given many public talks sometimes to hundreds of people and today I like public speaking. But I'll never forget where I started and that the person I'm interviewing might be very nervous. Putting them up on a whiteboard and into presentation mode only amplifies that nervousness. Just talk to people. Get them into that flow that comes from talking about something familiar that they are excited about. For most people a whiteboard test is not exciting. But if you give me a paid take home coding exercise, that's exciting. I like code, and I like to get paid for it. So if you really think you need a test, consider a very high signal test that is the exact work they will be doing.
> I make sure to ask for feedback on the exercise and I've gotten all positive feedback from candidates.
In an unequal relationship like that you are going to get a lot of false positives. If I really needed a job my response would be "loved the exercise, looking forward to talking to you more and discussing next steps if I'm the right candidate".
That's definitely an unfortunate experience, but isn't giving presentations to explain your ideas - sometimes to people you don't really know - actually a significant part of the job? I'm an IC, and I present designs and project plans for feedback to groups of up to a couple dozen people, or to VPs, on a pretty regular basis. If I couldn't do that competently I would be failing at my job, because that kind of communication is just as important as actually writing the code. If I were conducting an interview and discovered that "public" speaking on the order of a few people in a conference room was extremely difficult for you, I'd probably consider that an important red flag.
> isn't giving presentations to explain your ideas - sometimes to people you don't really know - actually a significant part of the job?
For many engineering positions it is not. There are loads of shops where the developers, even senior developers, mostly just write code. I have hired many of them and put them to work successfully building stuff while I deal with the meetings.
> If I were conducting an interview and discovered that "public" speaking on the order of a few people in a conference room was extremely difficult for you
And yet I worked very successfully as a junior developer for a couple of years before I ever had to attend a meeting like that. Among the other 100 devs in the shop, I was considered a top talent at coding. That's not to brag but to point out that I was adding lots of value to the company without having to attend meetings with people from other departments. My manager did that. My manager did not code, although he could if he wanted to. In fact at that company they created a separate path for highly talented engineers who wanted to continue coding but wanted to avoid management and meetings. That was a couple of decades ago and less common, but I think it's a lot more common now.
And the fact that I can now publicly speak in front of hundreds of people should hopefully encourage you that it's something people can learn if they want to. Some people don't want to. There are roles for them too.
Believe op is using it as "individual contributor"
I've never heard of someone not liking the term "Individual Contributor" before
I always assumed the term just leaked out of the HR world and into the general parlance.
If you're in a place where an IC can potentially make half a million or million dollars a year and drive some very interesting project work and be highly respected, no.
If you're in a place where not making it into manager track puts a very low ceiling on earning potential and respect, then yes it can be condescending.
This varies a lot by country, industry, etc.
Individual Contributor, used to contrast with "Manager". Point being, my main job is to design systems and write code, but I still have to do some of the organizational stuff sometimes.
>There are loads of shops where the developers, even senior developers, mostly just write code.
Okay, so your experience is different from mine. I'm surprised that there are places where this is really not a meaningful job requirement, and I've never worked at one, but I believe you.
>it's something people can learn if they want to
Sure... but so is coding. Part of the point of an interview is to see what skills and traits you already have. If you're missing some, that can be balanced against the ones you do have - it's not a dealbreaker, but it is still a negative.
>Some people don't want to. There are roles for them too.
Again, not where I work. Engineering, even at relatively junior levels, includes collaboration and explaining your work. You can't just say you don't want to do that - or rather, you can, but you'll have no upward mobility and be managed out pretty quickly.
Is that something they’re going to do on the job? Very unlikely. So why are you not only testing for it but testing for it in a fake time-pressured stressful situation that also rarely exists on the job? (Yes , we all have deadlines but when are they ever 15 minutes on the spot?)
Perhaps you should have entered the education field where you could give such exams day after day to your heart’s content?
I've seen one place that wanted developers to do a full presentation with slides and all to a group of people.
The topic of the presentation was completely up to you, didn't even have to be a technical subject. You could do a presentation on baking if you wanted.
Was doing presentations a part of the job of the developer? No. They wouldn't have to do presentations in their day job...
I didn't go for the job and have never understood what they were looking for.
Then if it’s a front-end position we can move onto UI components for it; for back-end or full stack I focus on implement a couple of the CRUD operations.
You really get to see how people think and will work on the job with questions like this.
Implementing a sorting algorithm from scratch is a waste of time in many projects: use your libraries and get on with life. That’s why such interview questions are not important to me.
Interviewing is hard and I applaud you for trying something newer and more realistic but I'd be cautious in thinking "spend 30 minutes designing a system and be prepared to defend your work with massive risk/reward hanging in the balance. Begin... NOW!!!!" is representative of how someone will work on the job. There are an awful lot of people who will solve the crux problems driving home after the interview or the next morning in the shower vs. on-demand.
I certainly don’t say BEGIN NOW! It’s a conversation. I continually ask questions during the design and ask the candidate to speak about the decisions being made.
In all honesty this process can easily last more than 30 minutes.
This is not a hard problem for someone with the experience I want, and there are many different correct answers.
Personally I'm way too anxious in interview settings to produce decent code. In interviews I find myself trying to get everything right first time, but in reality that's not how I work. I prefer to develop iteratively and debug as I go.
I'm also quite a slow and deep thinker. It's not uncommon for me to think about a problem for a good 15-20 minutes before writing any code. In this case I guess you would have some time to prep the night before, but I'd still be very nervous about coding on the day.
I prefer home assignments and that's typically what I'll do when interviewing people. I like to keep it simple and open ended. Simple because I don't want to waste their time and open ended to allow them some room for creativity because often we don't have explicit requirements in the real world. This has always worked quite well.
I've never been a big fan of giving code interviews, however when I have to give them, I'm far more interested in the candidate's thought process around how they understand the problem and what needs to be considered in building the solution.
I will say that one of the best "interviews" I've had included a portion where I worked with one of their engineers on a design problem they were actually having. It felt very collaborative, which allowed me to relax a bit, and I think we came up with a pretty good solution. I didn't mind doing "free work," because for me, it's fun to solve problems like these.
I've been around the block a few times and I LOVE system design interviews, both as an interviewer and interviewee. They are much more collaborative and "fun" for me. The good news is that I've been managing for several years at this point, so those types of interviews are far more prevalent than coding.
Also they'll try to claim copyright on your work (with pay) and reject you outright.
Agreed. The best jobs I've taken had interviews like this, or paid assignments.
The best way I know would be to work with someone for a week or two on a real problem, but that's way too expensive to trial a junior role.
At least for us, the system is more optimized around avoiding false positives than ensuring we don't pass over someone good.
Since the denial rate in our industry is so high, you can see which one is more preferable.
So if I get the job will we just touch base ever week or so? This sounds unlikely. Why can't you break work down to the point that you can pay me for 3-4 hours of real output and then use that to evaluate my quality?
All these tests around recursion and linked lists, etc are a feel-good proxy for actually measuring suitability, If someone is actually implementing them (IF!) it's not the junior, new-person; it's the senior architect who does it once every few years in a shared library. I can count the number of times I've used recursion in (a) a non-toy implementation and (b) not ripped it out and replaced with a faster, clearer iterative implementation on one hand.
where have you been all my life? ;)
I'm an autodidact, zero formal bg in comp sci. I suck at timed tests and algo interviews. Fifteen years I've been at this and I've worked with several 'full stack' teams, none of which had a single engineer who was within a thousand miles of what I could do with CSS (and they're mostly utter slobs wrt HTML). And as to the endless javascript demands, I will never be of interest to google (and the feeling's mutual) but I always get the job done, and often the job is something FE that none of my esteemed colleagues would know the first thing about how to achieve, comp sci degrees and recursion expertise notwithstanding ... not to mention that every one of them has as many stack overflow tabs open as me.
I'll get back to my sorry little js projects now, maybe I'll get another job before I grow old and die ;)
Your question topics are completely useless to normal software engineering work. And this proves how immature your company is, in understanding the nature of the work.
Perhaps you should consider asking them instead, what their technique is to ensure reliability, throughout, and redundancy in their code? Can they make their code self-heal itself? Or to make some minor decisions to restart itself, if optimal conditions are not met.
You know.. basic software engineering stuff.
>"because it shows that they know how to think about code"
means nothing at worst, and at best indicates you'll only be happy to work with people who are replicas of yourself.
Take home is the way to go, unless the position is some sort of public exhibitionist analogue developer position.
The least I think you can do is move from paper to machine, and inform them they should bring their own machine, or offer them use of one with many envs preconfigured.
Ideally the interviewer shouldn't be concerned about absolute code correctness, such as syntax or argument position, and should be interested more in how you're able to solve the problem, which should be a novel, yet simple task that doesn't require studying up on 200 level algorithms.
You want to hire developers (for permanent full time roles, at least) who have a good conceptual grasp of programming and logic, rather than their particular knowledge of a language or framework, or their ability to search on stackoverflow and run their code through a linter.
The worst interview problem I've been given was to write an AngularJS directive, I think literally to simply take an attribute and display it. I can't remember at the best of times the syntactical oddities of AngularJS, let alone when writing with pen and paper in an interview with no resources.
One of the better problems I was given was around parsing XML, from memory validating that opening tags matched closing tags, while allowing for self-closing tagsI remember the problem specifically didn't include any more complex facets of XML. Another was to reverse a string in-place ("hello world" -> "dlrow olleh"), and then to modify the algorithm to reverse the words but keep them in place ("hello world" -> "olleh dlrow"). Obviously in the real world you'd just use built in methods, but it's a problem that should be solvable without digging up your old lecture notes.
I've always felt comfortable writing code (or at least psuedocode) with a pen, but I think it's unfair to require a candidate to solve the problem on paper or whiteboard if they feel more comfortable typing on a computer instead, all that achieves is disadvantaging otherwise capable candidates who for one reason or another can't write code with a pen and paper. As long as they aren't googling "how to reverse a string in place", it immaterial what writing tool they use. If they feel more comfortable using a brush and papyrus, or carving a runestone, then that should be perfectly acceptable too (provided they bring their own writing material).
* linked lists shouldn't be used anyway. and if they are used, you should use the standard implementation
* directly applying fibbonacci is trivial.
* sort: This is just a memorisation task, what's the point? (99% of the time, you shouldn't implement your own sort)
although, I agree with the open-book approach in the problem solving part.
Used recursion only once. Once.
(but that specific time recursion was really a life saver)
When programming in Clojure I use recursion a LOT.
I see no reason to use recursion when asked to calculate Fibonacci numbers. A loop looks like a more reasonable choice that also avoids typical pitfalls associated with recursion. Maybe that's because I did embedded programming for a while.
I suspect recursion is introduced in CS classes with this example, but people understand it as "you are supposed to use recursion to calculate Fibonacci numbers".
Beauty is in the eye of the beholder, but a loop is hard to beat as far as simplicity goes, and you don't depend on your compiler being clever enough to optimize tail recursion.
If you need to traverse a tree then sure, but with Fibonacci you don't even need the stack to begin with. You only need to keep a previous number.
But, you are not seeing how people think about code. You are seeing presentation prepared before hand. That whole part abour seeing how people think, as much as it is repeated, is nonsense, so maybe it is not much of loss.
In school I played with sorting algorithms, in business if I ever found a developer manually writing a sorting algorithm, I would consider them inept (unless there were very specific reasons to do so).
If someone didn’t know how to sort a list using the built in or standard library of whatever language they are using, I would know very quickly that they have almost no experience writing anything useful.
When was the last time you wrote a sorting algorithm?
Acceptable answers:
- You mean sorting a list? - In school - Why would I write a sorting algorithm? - Never - (Glazing eyes and other body language that indicates frustration)
Red Flags:
- Anything that indicates they think writing a sorting algorithm is a perfectly logical thing to do during the course of software development.
(Note: The problem is sorting may seem like a well-understood problem, but it’s actually not. Only a person who studied the algorithms in school as an assignment would feel comfortable with that code.)
I think the ability to come up with relevant and important questions to ask about the task given is more crucial than whether they can solve it. You can look up answers to questions from hundreds of good sources, but you need to be able to generate the right questions that need to be answered first.
Completely agree with this statement.
I would add that having the proper vocabulary is an important part of generating the right questions.
As a programmer, your task is to find algorithms to solve problems. Sure, sorting numbers is a solved problem and in real life you should use a library. But you will not find a library for each problem you encounter, and sorting is a very simple problem to solve compared to anything you'll find in real life.
Still, even using a pre-learned algorithm demonstrates some level of confort with algorithms in general, and can be used as a stepping stone during the interview to shift the problem slightly to see how they adapt the algorithm.
For example, if a candidate is clearly taking their time and essentially working out the algorithm themselves, and succeeding, that demonstrates the skill and we can move to other problems. If the candidate just breezes through and finishes in 2 minutes, then we can change the problem ad-hoc to try to get them off the beaten track a bit (say, if they wrote quicksort, maybe ask about making it stable, or sorting even numbers differently from odd numbers, off the top of my head).
Trivia does not provide evidence of skill, it demonstrates prior knowledge.
It would be better to introduce a unique situation that would place everyone at the same starting point.
Even so, knowing very widely talked about programming trivia is still a signal for interest in the art. I'm not sure that sorting algorithms are a good example of what I'm thinking, but I always award extra mental points to candidates who seem knowledgeable about the field (e.g. they know the general consensus on manual memory management vs garbage collection). Still, I wouldn't consider these sorts of things dealbreakers by any stretch of the imagination.
In a weird way though, I’ve at least grown to understand why it’s so popular, and I don’t think it’s just because FAANGS do it (though I think that’s how it came to prominence). It boils down to showing as an engineer your capable of being flexible and malleable your change and understanding. Some places definitely do this better than others, and I think it says a lot about company culture if they are Adversarial about it or not. In my experience rather unfortunately even good places to work can be adversarial about it.
The massive downside is and always will be it puts so much onerous on the candidate because you don’t really know what they are going to ask and freezing up or getting stumped is very frowned upon in these style interviews from what I experienced.
My tip to anyone though is just to practice, but I’ve yet to encounter places that don’t employ some technique to test algorithmic thinking and understanding of complex systems in some way.
...because you like working through problems on paper, and your interview process is designed to find people like you.
Kudos for letting candidates know what’s going to happen, it’s just that when I see problems that are clearly just a stand in for “do you know X?” I always wonder why interviewers don’t cut to the chase and just ask directly. “Are you comfortable with recursion? Can you describe it? When does it tend to be applicable?”
You learn it quickly when teachers do oral exams at university :)
Code doesn't lie, so I understand why people like to check candidates that way instead of relying on talk alone. I would just prefer if it wasn't a hit-or-miss test on what algorithms you memorized.
I'm doing leetcode now, as a senior engineer there is no way to get a decent job without being tested like a college fresh-out as far as programmer positions are concerned, no complains, I will do them, it is the market picks me, not the other way around.
To me even though this is painful, but at least it is "merit-based", what I dislike the most is that you got a job based on other factors instead of how able you are.
1. Dijkstra's 2. Kadane's 3. Bellman ford - negative edges
Just using a graph was the highlight of that month for me. (The data wasn't already in a graph.) Reading the wiki, it may have been Dijkstra that I used under the hood. (I just wanted the sum of simple paths for all leaves to the root, for each leaf.)
Cheers for us.
Some of the stuff I personally worked on was tries and nested tries for routing/cache purge, LRU & variants for the caching algorithm on a cache node, and I implemented consistent hashing for the distributed cache.
There were some algorithms stuff for load balancing, but I didn't work on that.
I know there was a few other things, but I can't remember them right now.
Considering Skype is at best laughable compared to other IM applications, I'd not boast about working on it. I used Skype over 10 years and after it got bought by Microsoft it gradually started to be worse and worse, to the point I had to look at other IM in order to communicate with my clients.
I have a question, why is that Whatsapp and FB messenger can and will deliver notifications when you receive a message every single time, while for Skype this seems to be an unachievable feature?
a) A really good problem solver
b) Someone who has ran through all the example interview problems on leetcode or something similar
Then I thought that this might be similar to the Turing test. Once you’re that good at faking it that you can convince someone else - maybe the difference doesn’t matter at that point.
I just don't think it makes sense to test people on this kind of questions and then make them write CRUD all day.
For example, here is a shell script that takes an input file consisting of lines of the form
where X and Y are integers representing the X and Y coordinates of live cells in a Conway's Life grid, and outputs the next generation in the same format. It runs in O(n log n) where n is the number of live cells, and it is really just sorting.What people seem to want is big-data or various tech stacks. I look forward to the time I can put even a bloom filter to work.
(edit: typo)
Still, that was a hobby project, I've never had to implement anything similar at my regular job.
[1]: https://github.com/mihaifm/HIBPOfflineCheck
I'd wish more of those problems showed up in my daily work, though.
Btw, a cool popsci book about algorithms occuring in day to day life is "Algorithms to live by".
Mostly that they prepared for an algorithms question.
It may be a good filter for 3rd-wave do-as-you're told programmers who stay in their lanes, produce by the book expected code, and just consistently obediently build things.
They wan better cogs for the corporate software machine.
If people are asking me algo questions, the job probably isn't right for me because my answer is "it depends". Last time I took one I was thinking "there's like 4 answer to this, what the fuck do you want?" it might as well have been "I'm thinking of a color" ... they have something written down and called it the "right" answer.
I gave a parallelizable answer, they wanted single threaded. I gave a single threaded one, they wanted 2 passes. I gave them a 2 pass version, they wanted one that didn't use collections.deque, I mean it was nonsense. "Guess what's on my piece of paper!" Cool beans bro.
Some people would have given them that answer the first time, I'm sure of it. Not me though. Not during the interview, not during the day-to-day.
I don't know how. I really don't. I don't know the right answers, all I see are a bunch of possibilities. That's why I'm first-wave.
The writer of homebrew isn't what Google is looking for anymore. His time to get hired there closed around 15 years ago. After the revolutionaries comes the administrators, a far less interesting but necessary entourage.
The people like me have all already quit. I've actually got nothing to offer them.
Companies that could build and not maintain: Lotus, Digital Research, Palm, Netscape, MySpace, Digg, Blackberry, Ashton Tate, it's a different set of skills. Heck, you can even toss the French Jacobins in there
They all shot themselves in the foot, I know, that's the point. Not having their eye on the ball and instead looking over the horizon is what built the empire, but then the ball hit their nose
Some people can do both (gates, zuck, bezos), but once you're at the Apple/Microsoft stage, you need the second group.
If they can pass that hurdle, you can almost be certain they know how and when crack open an algorithms textbook or use Google-fu to apply the right algorithm to solve a given problem.
(Knowing which data structures to reach for is far more applicable than being able to apply algorithms from memory. The article is good evidence of that.)
Those people do exist. Really, they think it's a thrilling joyride. Hard to find, but they're real. I look for those and run the team tight and small.
Fabrice Bellard, Ted Nelson, Theo de Raadt, Patrick Volkerding, Richard Stallman, Larry Wall, these people aren't off working at stable ibm-like firms. It's a different kind of thing. Look at Nelson's fiery career crash when he worked at Autodesk. Look at Woz and Paul Allen walking away or Bushnell getting rid of Atari. This isn't the grab-and-dash modern unicorn stuff, these people saw it wasn't right for them. The company outgrew them.
They couldn't do the job. That's not where they fit.
Chefs make terrible bus boys and bus boys make terrible chefs.
That's the big important lesson: The Chef is incapable of being a bus boy.
It's not "too easy for her" and she's not "too smart for it". The chef can't consistently, reliably, and efficiently do the tasks. The hierarchy is illusory, it's all about fit.
Drucker explains this better than I ever could. He's a good read
The vast majority of algorithms I use are for parallelizing complex workloads, failure detection, and scoring systems. I usually DIY after I find the OTS ones unsatisfactory.
I'm not "smarter", they're general solutions but all I seem to have in life are specific problems so specific solutions perform better.
No need to sort everything again after adding 1 element.
I've used quite a lot of features from RDBMs, as well as topological sorting, LRU for caches, Unicode normalization, graph traversal, bloom filters, hash maps and so on.
I'm not payed to implement algorithms or data structures, but to solve problems. So for anything non-trivial I tend to use ready-made libraries.
I only implement stuff myself when it's faster and simpler to implement AND TEST it than to draw in another dependency, or if there isn't a well-made off-the-shelf component.
So what I've implemented myself at $work is pretty limited:
* depth-first tree traversal
* graph traversal
* parsers for various non-standard file formats
* maybe a topological sort once, not sure
Finally, many classical algorithms have lesser-known variants that optimize for some practical advantages (reduced memory usage, memory cache friendliness, sequential disk reads/writes etc.). So if I were to implement, say, a substring search, it might not be a by-the-book Boyer-Moore algorithm, but some subsequent paper that builds on it to add a few percent practical performance improvement.
There's not much point though in knowning the minutiae to the level that you can code one on the whiteboard without prior preparation -- which is probably the main point that the article relates to.
I use the STL daily. I know fairly well the complexity guarantees behind each data structure. That's one of the things I like about it versus other collections libraries. It forces you to be somewhat literate on data structures in order to make the right choices.
But no, I could not write you up a red-black tree from scratch without going away for a few days with my Knuth books and a few pots of coffee. Sorry.
Of course, there are positions where this kind of skill is unnecessary and I cannot know everything about the false negatives. But failure in these areas also correlate with poor coding skills, at least in my experience of a free hundred interviews.
But does this mean you need to learn them by rote or be able to figure them out on a whiteboard? No. And although they appear regularly, I don‘t spend enough time on them that this would meaningfully affect my performance. So the time you spend thinking doesn‘t matter, very unlike a whiteboard situation.
If I'm asked to do a BFS/DFS, Tree traversal, etc for a small company.. I tend to share high level how I'll solve it then basically not actually code it up and say something like "This is pretty tricky...". Why? It's my way to exit the interview quickly because I question the ability of the company to hire talented engineers. Especially when I test your product out and see all sorts of inconsistencies.
Okay, so when do Data Structures matter to a company?
Are you building a product that needs to perform very efficiently at scale and the system is doing something outside the "norms" of what a data store can provide. Examples: Facebook's TAO system and their type ahead search.
Read the design paper for TAO and you'll see how they use very primitive data structured related to Graphs. Their typeahead system also makes use of some very basic data structures and some probabilistic data structures as well.
When do Algorithms matter to a company?
For most traditional companies, you're not going to do a BFS/DFS search, traverse a tree or a Dynamic Programming solution like Levenshtein distance. So unless these algorithms have a practical use case in your company, you're just creating a sort of monoculture.
Once again, Google and Facebook do apply these algorithms so I respect their interview process.
Big O has its place in such large companies. I think most people fail to understand the purpose of Big O; identify upfront if a solution will be sufficient from a time or space perspective as the data grows. Most people speak about Big O on interviews AFTER they code up the solution. You should do that before you code it up.
e.g, So the data for this problem is <100 items then this quadratic solution would work, but if we scale the data set up to say 10,000 items then it won't work. Then you can look at data structures or sorting algorithms for instance that'll help you get it down to say O(n) or O(n log n) etc
Look, I get the frustration a lot of people feel about this sort of interviewing process. I have a very non-traditional background and it could be very scary when you first start learning about this. My advice? Learn it for your own good. It'll make your a better programmer and it'll help you become more aware of so many things you weren't aware of before!
The moment when you realize why using an array for a Min Heap or why a Min Heap must be a complete tree... you'll step back and go "Now that's sexy!" Or when you realize even stupid stuff like "A balanced binary Tree has this weird reality that the leaf nodes account for 50% of all nodes in the tree" It's just fun if you see it in a positive way.
Let's call technical interviews that ask such questions when it doesn't represent the company "interviewer imposter syndrome". When a company tries to act and look like Google early on.. Google has a million+ candidates a year interviewing with them. They MUST allow good candidates slip through their process.
http://dimacs.rutgers.edu/~graham/pubs/papers/cmencyc.pdf