General Topics Flashcards
First Six Chapters
What are the core tools for solving coding interview problems?
Data Structures and Algorithms
Questions to keep in mind when reading a coding interview problem:
- What is the input?
- What is the output?
- What is the ask?
- What transformation is needed?
What is a Data Structure (General Definition)?
A way to organize and manage data
What is a Data Structure (Precise Definition)?
The collection of 1) data values, 2) the relationships among those values and 3) the operations/functions that can be performed on those values.
What is Complexity Analysis
The process of determining how efficient and algorithm is.
What are the two types of complexity?
Time and Space.
What do we use Complexity Analysis for?
It is how we can measure how “good” an algorithm is compared to other algorithms.
What is Time Complexity?
A measure of how fast and algorithm runs.
What is Space Complexity?
A measure of how much auxilliary memory and algorithm takes up.
What is Big O notation?
Notation for describing time complexity and space complexity of algorithms.
Bit
Binary Digit
What is the fundamental unit of information in Computer Science?
Bit. Any data store in a computer is composed of bits.
What values can a bit be?
Either 0 or 1.
Byte
A grouping of 8 bits.
How many bits (or data values) can a byte represent?
If unsigned, 0 to 255 or 2^8 (staring at 0). If signed, -128 to 127 or -2^7 to (2^7 - 1)
Fixed-width Integer
An integer represented by a fixed number of bits, regardless of the value of the integer.
What does “O” stand for in “Big O notation?”
Order. It represents the order (i.e. rate) of growth of an algorithm’s running time and/or space requirements in relation to the size of the input.
What scenario of algorithm performance does Big O notation aim to emulate.
Worst-case or upper-bound performance.
What does “n^2” stand for in “O(n^2)?”
The running time (and/or space depending on what kind of complexity we are analyzing for) of the algorithm grows proportionally to the square of the input size.
How many complexities am I responsible for knowing for my coding interviews?
8
How many categories of complexities am I responsible for know in my coding interviews?
4
What are the categories of complexities I am responsible for knowing in my coding interviews?
Linear, Logarithmic, Exponential, Factorial
What are the Linear Complexities?
Constant and Linear
What are the Logarithmic Complexities?
Logarithmic and Log-Linear
What are the Exponential Complexities?
Quadratic, Cubic and Exponential
What complexity is the sole member of the Factorial category?
Factorial
What is the Big O notation for Constant complexity?
O(1)
What
What is the Big O notation for Linear complexity?
O(n)
What is the Big O notation for Logarithmic complexity?
O(log(n))
What is the Big O notation for Log-Linear complexity?
O(nlog(n))
What is the Big O notation for Quadratic complexity?
O(n^2)
What is the Big O notation for Cubic complexity?
O(n^3)
What is the Big O notation for Exponential complexity?
O(2^n)
What is the Big O notation for Factorial complexity?
O(n!)
What do the variables (usually n) in Big O notation represent?
The size of the inputs into algorithms
What are the adjacent complexities of Constant
O(1) is the fasted of the set that I’m responsible knowing:
O(log(n)) -> O(1)
What are the adjacent complexities of Logarithmic
O(n) -> O(log(n)) -> O(1)
What are the adjacent complexities of Linear
O(nlog(n)) -> O(n) -> O(log(n))
What are the adjacent complexities of Log-Linear
O(n^2) -> O(nlog(n)) -> O(n)
What are the adjacent complexities of Quadratic
O(n^3) -> O(n^2) -> O(nlog(n))
What are the adjacent complexities of Cubic
O(2^n) -> O(n^3) -> O(n^2)
What are the adjacent complexities of Exponential
O(n!) -> O(2^n) -> O(n^3)
What are the adjacent complexities of Constant
O(n!) is the slowest algorithm that I’m responsible for knowing:
O(n!) -> O(2^n)
In coding interviews, what is the implied base of the logarithm?
2
Explain O(log(n)) in plain English.
Every time the log input doubles, the number of operations need to process that input one increases by one unit.
What are the two rules of thumb that indicate a complexity of O(log(n))
1) You are removing half of your inputs for every step or 2) Doubling the inputs only results in one extra step in the algorithm.
