Upgrade to Pro — share decks privately, control downloads, hide ads and more …

On the job interview... Composition

On the job interview... Composition

In this talk, we’re going to pretend we’re on a job interview, and have been given a single starting function. Using only this function, we have to build up many more functions. Can we pass the interview and get the job!?

Kyle Simpson

June 15, 2022
Tweet

More Decks by Kyle Simpson

Other Decks in Programming

Transcript

  1. Hello, welcome to Inter-Dot Web Solutions! I’m Maria, and I’ll

    be conducting your technical screen interview today.
  2. Let’s jump right in, then. I’m going to give you

    a single function, and we’ll use that function throughout the interview.
  3. Can you tell me what this function does? Can you

    write some code that uses it?
  4. Fantastic, well done! Now, what if we wanted to compose

    more than two functions, like this?
  5. Indeed, nice. “f”, “g”, and “h” functions all produce the

    same output. But are they the same kind or shape?
  6. What do we know about the differences between how “f”

    would execute compared to either “g” or “h”?
  7. “f” will have a call-stack depth of just 2, but

    both “g” and “h” will have call-stack depth of 3.
  8. Seems like it’s going to become very cumbersome to keep

    nesting calls to “composeTwo” as we add more steps to the composition.
  9. Any ideas on how we could define a “compose” function

    using “composeTwo”, but which can compose as many functions as we need?
  10. Looping through the function arguments in reverse, and for each

    iteration defining a new “f” that is the composition of the previous “f” and the preceding function argument.
  11. But now the call-stack depth is 4 for both “g”

    and “h”, whereas it’s still just 2 for your “f”.
  12. These loops you’ve written, they look like reductions to me.

    Can you express them with reduce utilities?
  13. Huh. Usually linear loop-based algorithms end up with lower call-stack

    depth than recursive algorithms, but not here.
  14. Any idea how we could make a definition for the

    general “compose” that doesn’t have the higher call-stack depth?
  15. I think the problem is that by using the “composeTwo”

    function, we’re lazily deferring the actual function calls.
  16. Instead, if we eagerly compute each intermediate composition result, and

    then pass that onto the next, it should keep the max call-stack depth at 2.
  17. The loop and reduction implementations are now call-stack depth of

    2. But the recursion one is still call-stack depth of 4.
  18. Perfect. Well, I have to say, you breezed through this

    technical screen interview. We’ll be in touch!