0

DSA Question for Big O Notation and Structure of Technical Interview

Profile picture
Senior Software Engineer at Taro Community2 months ago

It's been a while since I actually was in college and had to remember all the basic fundamental stuff like Big O and every algorithm, leetcode question abstractions etc. (I'm very very rusty).

What is more important to talk about / be most prepared for when interviews asking technical questions during tech screeners regarding Big O Notation? Will we be expected to memorize both runtime and memory for each data structure, algorithm, and design pattern

For example, will I have to whiteboard in pseudocode with a whiteboard marker, show how an infinite loop would function, report the runtime (example Bubblesort, runtime: average O(n^2) worse: O(n^2) and memory: O(1), and need to memorize concept like this? And is this most important to know than writing out the code in a code editor with test cases?

Many people have been interviewing differently during the pandemic in lieu of coming in-person so have had to use leetcode, things like Code Signal and actual IDEs more than before with coming in-person with a physical whiteboard to write pseudocode on. Are we expected to do both (write pseudocode on a physical whiteboard with a whiteboard marker on a particular algorithm in-person and also answer a leetcode question remotely as a part of a screener before that) or is it in the reverse order? Do we typically have to write out pseudocode on a whiteboard after passing a leetcode question as a screener then do systems design afterward? What's the typical sequence for technical interviews for FAANGMULA companies?

34
2

Discussion

(2 comments)
  • 3
    Profile picture
    Staff Eng @ Google, Ex-Meta SWE, Ex-Amazon SDM/SDE
    2 months ago

    How would the ordering of the interviews change your preparation?

    Whether the interview is in-person or over VC, assume all of these skills will be tested. Whether you’re writing on a whiteboard or you’re typing in a dumb shared text editor or you’re using an IDE, you should be able to express your intentions with near-compilable code. If you skip a method implementation for time, still write the signature. If you’re abbreviating variables, still just note that. I don’t consider the medium very important when evaluating outcomes. I expect a little more shorthand/abbreviation on a whiteboard but not without clear explanation.

    From there, algorithmic complexity is definitely something you need to be able to discuss fluently. I definitely review a lot of common algorithms, and also be sure i know examples of common complexities just to have it on hand (O(1), O(logn), O(n), O(nlogn), O(n^2), maybe a few more exotic things like O(nlognlogn), then some graph things for O(m*n), etc).

    More important than memorization, IMO, is analysis. When you’ve written something, as you’re going you should know the complexity, and how it would change if you made certain tweaks. If you’re using library functions, you should know their complexities. Being able to discuss this, and time versus memory tradeoffs, is pretty critical.

    For system design I actually am least psyched about the all-online version, because they often throw whatever their digital whiteboarding tool of choice is at you, and you have to adapt. I hate fighting the tool in real time. Like do the shapes have built in labels, or do I create my own text label for each? Do the shapes have “snap points” for connecting arrows or do I just get close enough? None of this is an issue on a whiteboard. I don’t have much advice here other that trying a variety of these tools and at least expressing a simple-ish system in each.

    From an order perspective, while I’m still not sure the impact, I normally see an online coding screen first (rarely the screen is live coding with a person, but it happens), and once that’s cleared the loop is setup with some coding and design and behavioral rounds, but I don’t normally see an order, and don’t normally see you being disqualified in the middle of this. I’m sure if you made really offensive comments they might, but based on performance they normally look at it as a whole.

  • 1
    Profile picture
    Tech Lead @ Robinhood, Meta, Course Hero
    a month ago

    Knowing Big(O) for both runtime and space complexity is table-stakes for a DSA interview, especially at FAANG.

    I recommend not just memorizing it but being able to do the analysis and actually understand the complexity values as well. This part of the DSA interview is pretty intense as you'll need to thoroughly explain why the Big(O) is a certain way. I failed a lot of Meta candidates as it was clear to me they had only memorized the Big(O) value and didn't understand the why.