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.

Also they'll try to claim copyright on your work (with pay) and reject you outright.

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.

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.

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.

Believe op is using it as "individual contributor"

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.

I've never heard of someone not liking the term "Individual Contributor" before

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.

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 ;)

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!

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 :-)

Seriously though - how long ago was that - not recently I hope?

I did it once or twice when I was 8 years old and didn’t have a computer yet :)

...because you like working through problems on paper, and your interview process is designed to find people like you.

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.

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.

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.

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.

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.

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.

That's pretty neat.

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.

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.

    int fib(int n) {
       if (n<=2)
          return 1;
       int fibNMinus2= 1;
       int fibNMinus1 = 1;
       int tmp;
       for (int i=3; i<=n; i++) {
           tmp = fibNMinus2+ fibNMinus1 ;
           fibNMinus2 = fibNMinus1;
           fibNMinus1 = tmp;
       }
       return fibNMinus1;
    }

    int fib(int n) {
       if (i<=2)
          return 1;
       return fib(n-1)+fib(n-2);
    }

    def fib(n):
      if n =< 0:
        return (0, 1)
      else:
        a, b = f(n-1)
        return (b, a + b)

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!

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:

    def fib(n):
      if n =< 0:
        return (0, 1)
      else:
        a, b = f(n-1)
        return (b, a + b)

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:

        case TARGET(RETURN_VALUE): {
            retval = POP();
            assert(f->f_iblock == 0);
            assert(EMPTY());
            f->f_state = FRAME_RETURNED;
            f->f_stackdepth = 0;
            goto exiting;
        }

    // ...

    exiting:
    if (tstate->use_tracing) {
        if (tstate->c_tracefunc) {
            if (call_trace_protected(tstate->c_tracefunc, tstate->c_traceobj,
                                     tstate, f, PyTrace_RETURN, retval)) {
                Py_CLEAR(retval);
            }
        }
        if (tstate->c_profilefunc) {
            if (call_trace_protected(tstate->c_profilefunc, tstate->c_profileobj,
                                     tstate, f, PyTrace_RETURN, retval)) {
                Py_CLEAR(retval);
            }
        }
    }

    /* pop frame */
    exit_eval_frame:
    if (PyDTrace_FUNCTION_RETURN_ENABLED())
        dtrace_function_return(f);
    _Py_LeaveRecursiveCall(tstate);
    tstate->frame = f->f_back;

    return _Py_CheckFunctionResult(tstate, NULL, retval, __func__);

Any specific implementation, and in this case cpython, could do arbitrary weird things after.

Thanks for looking up the code!

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:

    a, b = 0, 1
    for _ in range(n):
      a, b = b, a + b

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)

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

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.)

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.

Additionally you have a spelling error on line 5.

    def f(n):
        if n<=2: return (1, 1)
        else:
            a, b = f(n-1)
            return (b, a+b)

    def fib(n):
        return f(n)[1]

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.

    fib = 1 : zipWith (+) (0 : fib) fib

fib 1 = 1

fib n = fib (n-1) + fib (n-2)

(And you can also use recursion in the fastest implementations. You just wouldn't use the naive recursive solution.)

    fib(n) = (((1 + sqrt(5)) / 2)^n - ((1 - sqrt(5)) / 2)^n) / sqrt(5)

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(0) := (0, 1)
    f(n) := let (a, b) = f(n-1) in (b, a + b)

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 :)

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.

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.

I'd still have you write the full thing out, but I'm guessing you'd do just fine.

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.

Used recursion only once. Once.

(but that specific time recursion was really a life saver)

When programming in Clojure I use recursion a LOT.

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.

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.

>"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).

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.

  (defun fib (n &optional (a 0) (b 1))
    (cond ((zerop n) a)
          (t (fib (1- n) b (+ a b)))))

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.

Or

“You do not understand recursion nor Fibonacci”

FTFY

* 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.