Fundamentals of the software engineering interview

Introduction

I’ve been interviewing software engineers professionally for almost a year now. I’ve thought a lot about why some people don’t pass interviews, why others do extremely well, and what makes a good coding/algorithm question. One thing that’s clear to me is that people who do not do well often do not understand fundamental data structures, algorithms, or coding skills. Conversely, people who do extremely well often have a much better than average grasp of the fundamental data structures, algorithms, and coding skills. This post is a non-exhaustive list of what I consider the fundamentals among these three categories. I find that virtually all coding questions require a composition of these skills and knowledge.

Data structures

• Arrays
• Linked lists (singly linked, doubly linked)
• Map/dictionary
• Priority queue / heap
• Trees
• Graphs
• Stacks
• Queues
• Sets

Algorithms

• Depth first search traversal
• Breath first search traversal
• pre-order/post-order/in-order tree traversal
• Greedy algorithm
• Binary search (and generalized binary search)
• Recursion
• Dynamic programming
• Quicksort
• Mergesort
• Backtracking
• Topological sort
• Union find
• Divide and conquer

Coding skills (python specific)

• Custom sort in one expression (sort with custom comparator)
• enums
• lexical scoping
• deep copy an object
• While loops
• for loops (forwards and reverse iteration)
• enumerate
• bitwise logic (&, |, shifting, etc.)
• array operations (index, append, extend, remove, find, slicing)
• Dict operations (iterate keys, iterate keys+values, iterate values, add, delete, union)
• set operations (add, remove, contains, union)
• Create an array with range of integers m through n
• Use every data structure with arbitrary objects
• Create a class
• Use class inheritance
• Polymorphism
• Use an abstract base class
• Overload operators (+, -, <, >, ==, etc.)
• Overload the __str__() function
• Get the memory location / unique id for an object
• Convert a string to int/double
• All constants (max number, min number, lowercase alphabet, uppercase alphabet, numeric digits, punctuation)
• String interpolation
• Map/filter/any/all
• List comprehension (in 1D, 2D, 3D, etc.)
• Lambda functions
• Adding type checking to function signature
• Type checking during runtime
• Caching utils
• All language keywords
• Reading from a file
• Writing to a file
• Convert a string to a file-like object (for testing)
• try/catch exception handing
• Built-in and custom exceptions
• bit operations (and, xor, or)
• String operations (to lowercase, is prefix, is suffix, find substring index, etc.)
• Convert char to ascii and vice versa (e.g. ‘a’ -> 97)
• Slicing an object (array / string)
• Reverse an array
• Iterate a container forward and reverse
• Define an iterator for a custom class
• Generate a random integer between a and b
• Generate a random float between a and b
• Datetime operations
• Math operations (exponentiation, logarithm, integer division, modulus, min/max/abs/floor/ceil)
• Swap two elements of a random access container
• Assert statements
• Debug logging
• Regexes
• Invert a min-heap to a max-heap and vice versa
• Read user input from the console
• Decorators
• Parallel programming
• Measuring time elapsed
• Sleeping for a specified amount of time
• Functors

Other

• clarifying requirements
• code quality
• manual testing
• creating good test cases
• time / space tradeoffs
• design patterns

FAANG

Interviewers are the most competitive companies often have a tendency for asking questions that I guess you would call Leetcode hard. Many Leetcode hard questions require prior knowledge of optimizations / techniques / patterns / etc. to solve in 40-45 minutes. In a sense it turns the interview into a mini competitive programming competition. The short version is that there’s an additional level of skills and knowledge beyond the fundamentals which deserves its own category and are usually discussed in guides to competitive programming.

• Interval trees
• Segment trees
• 2D prefix sums
• Sliding windows
• Monotonic queues/stack
• Rolling hashes
• string processing algorithms
• bucket sort / square root decomposition
• https://usaco.guide/general/