This series contains review materials for software engineer interview questions. This guide provides a high-level overview of common concepts in computer science.
Recursion
Overview:
An algorithm that calls itself within its definition.
Recursive case a conditional statement that triggers the recursion.
Base case a conditional statement that breaks the recursion.
Stack level too deep and stack overflow.
Recursion places calls on the execution stack.
Typically limited by the runtime or operating system.
Must be aware of potential exploits (i.e. input data cannot be too large).
Often seen in algorithms such as depth-first search.
Dynamic Programming
Overview:
An algorithm that memoizes or caches intermediate results or return values from methods.
Problem must have two key attributes for dynamic programming to apply.
Optimal substructure.
Overlapping sub-problems.
Often seen in problems such as computing a fibonacci number.
Permutations
Overview:
A unique list of items where order matters
A given set of items has n! number of permutations.
If ordering a subset of the items, divide by the remaining permutations.
P(n,k) = n! / (n - k)!
Typical implementation requires swapping each item into each position in the list.
Combinations
Overview:
A unique group of items where order does not matter
e.g. Pick n items from a set
Computing the number of combinations starts with the number of permutations and divides by the number of redundancies.
C(n,k) = n! / (n - k)! k!
Sets and Subsets
Overview:
A collection of distinct objects (elements or members of the set)
A set has 2^n subsets (including the empty set)
Subsets may be generated by starting with the empty set
Add elements to each previous subset to generate new subsets
Bit Manipulation
Overview:
Commonly used to optimize base 2 calculations.
Operations:
Name
C Language
Result
Negation
~
Invert all bits
And
&
True when both input bits true
Or
|
True when either input bits are true
Exclusive Or
^
True when input bits differ
Left Shift
«
Shift bits left by specified amount and pad with zeroes
Right Shift
»
Shift bits right by specified amount and pad with zeroes