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.

Given that merge sort splits the array into 2, performs a recursive call on each of the 2 arrays, and repeats until the base case of 1 or less items in an array is reached, how many levels of recursion are there and why? Answer: log₂n levels. Each level results in a split of an array n into arrays of size n/2. The number of levels equals the number of times you split n/2 until you reach 1 or less. The definition of log₂n is the number of times n is divided by two (split) until it reaches a value of 1 or less.

Given the following, what is the pseudocode for the merge function? A = 1st sorted array. B = 2nd sorted array. C = Sorted output. i = 1, position of 1st sorted array. j = 1, position of 2nd sorted array. for k = 1 to n -if A[i] < B[j] --C[k] = A[i] --i++ -else (B[j] is < A[i]) --C[k] = B[j] --j++ end

What are the five variables required for the merge portion of merge sort? 1st sorted array of length n/2. 2nd sorted array of length n/2. Array containing the sorted output of the merge, length n. Variable to track position of 1st sorted array (i = 1). Variables to track position of 2nd sorted array (j = 1).

What three steps, in pseudocode, are required for merge sort? 1. Recursively sort 1st half of input array. 2. Recursively sort 2nd half of input array. 3. Merge two sorted subarrays into one.

What kind of running time do Selection, Insertion and Bubble sort have? Quadratic n²

What are the recursive steps of Karatsuba Multiplication? With the numbers x and y split into four numbers: a, b, c, d. 1) Recursively compute ac (a × c). 2) Recursively compute bd (b × d). 3) Recursively compute (a + b) × (c + d), which = ac + ad + bc + bd, then compute step 3 - step 1 - step 2 = ad + bc.

What are the non-recursive steps of Karatsuba Multiplication? With numbers x and y split into four numbers: a, b, c, d. 1) Compute a × c. 2) Computer b × d. 3) Computer step 3 - step 2 - step 1. 4) Add (step 1 × 10^n) + step 2 + (step 3 × 10^(n/2)).

What are two ways to enable rich text editing in your page? Answer: Embed an iframe containing a blank HTML page, set the "designMode" property of the iframe document object to "on". Apply the "contenteditable" attribute to an element on the page.

For a multiple select box that has multiple options selected, what does selectedIndex return? Answer: The index of the first option that was selected.

What are the six events related to the clipboard? Answer: before copy, copy, beforecut, cut, beforepaste, paste.

What "HTML5" textbox method can be used to select some of the text? Answer: setSelectionRange()

What "HTML5" textbox properties can be used to get the selected text? Answer: selectionStart, selectionEnd.

If multiple form controls share the same name, such as a set of radio buttons, what will the "elements" collection property of the form object return, using the common name as the index? Answer: An HTMLCollection containing all the elements with the name.

When a reset button is pressed, all of the form fields are set back to what value? Answer: The value they had when the page was first rendered.

What are three different ways to access a specific form element via JavaScript? Assigning the form an ID and accessing via document.getElementById(). Assigning the form a name and accessing via the property of the same name on the document object. Accessing the form from the document.forms collection by index or form name attribute.

What is the "data structure brainstorm" approach to solving a technical question? Answer: Run through a list of data structures and try to apply each one.

What is the "base case and build" approach to solving a technical question? 1. Solve the problem first for a base case (e.g. n = 1). 2. Solve the problem for the next case, assuming the answer for the previous (base) case is already known (e.g. n = 2). 3. Continue solving the problem for each next case (e.g. n = 3... 4... etc) until able to create a solution that uses previous cases to solve the current case.

What is the simplify and generalize approach to solving a technical question? Implement a multi-step approach. First, change a constraint such as the data type or amount of data (simplify the problem). Then, solve the new simplified version of the problem. Finally, using the algorithm for the simplified version of the problem, generalize the problem and adapt the algorithm for the simplified version to apply to the complex version.

What is the pattern matching approach to solving a technical question? Answer: Consider what problems the algorithm is similar to and try to modify the solution to the related problem to develop an algorithm for this problem.

What is the examplify approach to solving a technical question? Under exemplify, you write out specific examples of the problem and see if you can derive a general rule from there.

What are the five approaches you can use to solve a technical question? 1. Examplify 2. Pattern Matching 3. Simplify and Generalize 4. Base Case and Build 5. Data Structure Brainstorm

What are the five steps you should follow when solving a technical question? 1. Ask your interviewer questions to resolve ambiguity 2. Design an algorithm. 3. Write pseudocode first, but make sure to tell your interviewer that you'll eventually write "real" code. 4. Write your code at a moderate pace. 5. Test your code and carefully fix any mistakes.

What are the exact values of the following powers of 2? What are the approximate values? If unit is Bytes, what is the approximation of those bytes to MB, GB or other nearest unit? 2¹⁰ 2²⁰ 2³⁰ 2⁴⁰ Answer: 2¹⁰ = 1024 ≈ 1 thousand ≈ 1K 2²⁰ = 1,048,576 ≈ 1 million ≈ 1MB 2³⁰ = 1,073,741,824 ≈ 1 billion ≈ 1GB 2⁴⁰ = 1,099,511,627,776 ≈ 1 trillion ≈ 1TB

What are the exact values of the following powers of 2? If exact value is the number of bytes, what would be an approximation of those bytes to MB, GB, or other nearest unit? 2¹⁶ 2³² Answer: 2¹⁶ = 65,536 ≈ 64K 2³² = 4,294,967,296 ≈ 4GB

What are the exact values of the following powers of 2? 2⁷ 2⁸ Answer: 2⁷ = 128 2⁸ = 256

What concepts should you be familiar with? Bit Manipulation Singleton Design Pattern Factory Design Pattern Memory (Stack vs. Heap) Recursion Big-O Time

What algorithms should you be familiar with? Breadth First Search Depth First Search Binary Search Merge Sort Quick Sort Tree Methods (Insert/Find/etc.)

What data-structures should you be familiar with? Linked Lists Binary Trees Tries Stacks Queues Vectors/ArrayLists Hash Tables