Google Interview Hacks

What is the formal definition of Little-Oh notation? Answer: T(n) = o(f(n)) if and only if for all constants c > 0, ∃ a constant n₀ such that T(n) ≤ c × f(n) ∀n ≥ n₀.

What is the formal definition of Theta notation? Answer: T(n) = θ(f(n)) if and only if T(n) = O(f(n)) and T(n) = Omega(f(n)). ∃ constants c₁, c₂, n₀ such that c₁ × f(n) ≤ T(n) ≤ c₂ × f(n) for all n ≥ n₀.

What is the formal definition of Omega notation? Answer: T(n) = Omega(f(n)) if and only if ∃ constants c, n₀ such that T(n) ≥ c × f(n) ∀n ≥ n₀.

What is the formal definition of Big-Oh notation? T(n) = O(f(n)) if and only if there exist constants c, n₀ > 0 such that T(n) ≤ c × f(n) for all n ≥ n₀. n₀ is the crossing point. c, n₀ must be independent of n.

What is the high-level idea about asymptotic analysis? Asymptotic analysis suppresses constant factors and lower-order terms.

What are the three guiding principles for the course? 1) Worst-case analysis: the running time bound holds for every input of length n. 2) Ignore constant factors, lower-order terms: simplifies math, minimal loss of predictive power, architecture/compiler greater factor anyways. 3) Asymptotic analysis: focus on running time for large input sizes n.

If n = length of original array, j = current level, k = number of subproblems at that level and l = length of array in each subproblem, what are k and l in terms of j and n? Answer: Number of subproblems at level j is 2^j. Length of array in each subproblem at level j is n/j^2.