Google Interview Hacks

Top 10 algorithms for linked lists? 1. Insertion of a node in Linked List (On the basis of some constraints) 2. Delete a given node in Linked List (under given constraints) 3. Compare two strings represented as linked lists 4. Add Two Numbers Represented By Linked Lists 5. Merge A Linked List Into Another Linked List At Alternate Positions 6. Reverse A List In Groups Of Given Size 7. Union And Intersection Of 2 Linked Lists 8. Detect And Remove Loop In A Linked List 9. Merge Sort For Linked Lists 10. Select A Random Node from A Singly Linked List 1. Insertion of a node in Linked List (On the basis of some constraints) If Linked list is empty then make the node as head and return it. 2) If value of the node to be inserted is smaller than value of head node, then insert the node at start and make it head. 3) In a loop, find the appropriate node after which the input node (let 9) is to be inserted. To find the appropriate node start from head, keep moving until y...

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)).

The ultimate goal is to design systems with good generalization capacity, that is, systems that correctly identify patterns in data instances not seen before. The generalization performance of a learning system strongly depends on the complexity of the model assumed. If the model is too simple, the system can only capture the actual data regularities in a rough manner. In this case, the system has poor generalization properties and is said to suffer from underfitting By contrast, when the model is too complex, the system can identify accidental patterns in the training data that need not be present in the test set. These spurious patterns can be the result of random fluctuations or of measurement errors during the data collection process. In this case, the generalization capacity of the learning system is also poor. The learning system is said to be affected by overfitting. Spurious patterns, which are only present by accident in the data, tend to have complex forms. This is the...