8

How do you find edge cases in DSA problems for FAANG?

Profile picture
Senior Software Engineer at Taro Communitya year ago

How do I find edge cases in DSA problems?

Are there some common edge cases that everybody knows about?

Is there some sort of method or procedure to find those edge cases?

1.4K
2

Discussion

(2 comments)
  • 9
    Profile picture
    Tech Lead @ Robinhood, Meta, Course Hero
    a year ago

    Make things weird and try to break stuff.

    This really doesn't have to be taught - It's more about bringing out your inner survival instinct. Humans have evolved over millions of years to be careful:

    • Maybe these brightly colored berries I found are poisonous and I shouldn't eat them?
    • Maybe this dark cave I can't see into has a pack of hungry wolves so I shouldn't go in?
    • Maybe I should start this cooking fire further away from my hut so it doesn't accidentally catch on fire?

    Tap into that worry and apply it to your code. Leverage your fear to conquer your fear. This is where I've seen mediocre engineers fail time and time again. They are afraid to face their fear of their code being bad. They only think about the happy flow. They only run the happy flow. That works in the beginning, but the second anybody tries something weird against their code, the happiness is smashed to pieces.

    When you get a DSA problem or any problem really (it doesn't have to be FAANG or DSA), take the happy flow and mangle it as much as possible. In DSA, the interviewer will generally give you sample, neatly packaged test cases to illustrate the problem - Use those as a basis to turn everything on its head.

    The edge cases will vary for different problems (these companies are trying to gauge your on-the-spot creativity), so you naturally can't (and shouldn't) study your way out of this. But to help you out, here's some common edge cases:

    • Things are null
    • Thing are empty
    • Things are very big (e.g. 1 trillion integers in a list)
    • Things are very small (e.g. 1 integer in a list that needs to be sorted in some way)
    • Everything is the same (e.g. you are asked to run 2-sum on an array that is 1,000 1s)
    • Everything is different
    • Function parameters directly contradict each other (e.g. find the X biggest numbers in a list of Y ints, but X > Y)
    • Function parameters are impossible (e.g. find the X biggest numbers in a list, but X is negative)

    I want to make it clear that these are purely for inspiration. Your strategy for getting better at spotting edge cases shouldn't be just memorizing these (this doesn't scale). In the world of DSA and writing good code in general, there are far more ways things can break. Take a mental sledgehammer to any technical problem you work on, and your brain will naturally start building up the intuition and pattern recognition over time.

    Check these out for even more inspiration (they cover how I graded Meta interview candidates in DSA, which includes edge case coverage):

    For an extremely in-depth guide on how to become a better coder in general (not just DSA), check this out: "How to Learn/Practice Clean Code, particularly by oneself?"

  • 3
    Profile picture
    Tech Lead/Manager at Meta, Pinterest, Kosei
    a year ago

    I'd also embed this into your interview practice. Edbert talks about "Not Fixing Your Own Mistakes" in his talk about common mistakes among interviewees.

    Alex's list of common edge cases is great: start there and add other edge cases as you find them!