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

Facts and Tricks:

And Or Xor
x & 0s = 0 x | 0s = x x ^ 0s = x
x & 1s = x x | 1s = 1s x ^ 1s = ~x
x & x = x x | x = x x ^ x = 0

Powers Of 2:

2^N Exact Value Approx. Value Human Readable
7 128    
8 256    
10 1024 1 thousand 1K  
16 65536 64K  
20 1048576 1 million 1MB
30 1073741824 1 billion 1GB
32 4294967296 1 trillion 4GB
40 1099511627776 1TB  

Sources