# Interviews: Concepts

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 |