Google Interview Hacks

What is Array Slicing? Answer: Taking a subset from an array and allocating a new array with those elements. Takes O(n) time and O(n) space, where n is the number of elements in the resulting array. var slice = new int[endIndex - startIndex]; Array.Copy(sourceArray, startIndex, slice, 0, slice.Length);

The main thing we use logarithms for is what? Answer: Solving for x when x is an exponent.

A Logarithm is really asking what? Answer: "What power must we raise the base to, in order to get this answer?"

For C# variables allocated to the heap, when is allocation handled? Answer: At Run Time

For C# variables allocated to the stack, when is allocation handled? Answer: At Compile Time

Unlike the Stack, variables created on the heap are...? Answer: Accessible by any function, anywhere in your program. Heap variables are essentially global in scope.

Why is Heap memory slightly slower to read from and write to, compared to stack memory? Answer: Because you have to use Pointers to access memory on the Heap.

Unlike the Stack, the Heap does not have size restrictions on what? Answer: Variable size (apart from the obvious physical limitations of your computer.)

What is the Heap memory? A region of your computer's memory that is NOT automatically managed for you, and is not as tightly managed by the CPU. It is a more free-floating region of memory (and larger). To allocate memory on the Heap (in C), you must use function calls such as malloc( ) or calloc( ), which are built-in C functions. Once you have allocated memory on the heap, you are responsible for using free( ) to deallocate that memory once you don't need it anymore. If you fail to do this, your program will have a memory leak, which means memory will still be set aside and unavailable for your other processes.

Why do variables called in functions have limited scope and referred to as "local variables"? These variables are pushed onto the stack when they are created and popped off the stack when the function exits/completes.

What is the advantage of using Stack to store variables? Memory is managed for you. You don't have to allocate memory by hand, or free it once you don't need it anymore. What's more, because the CPU organizes stack memory so efficiently, reading from and writing to stack variables is very fast.

What is the Stack? A special region of your computer's memory that store temporary variables created by each function (including Main( ) ). It is managed and optimized by the CPU quite closely. Everytime a function declares a new variable, it is pushed where? Everytime that function exits, what happens to all of the variables? Onto the Stack. They are freed / deleted. Once a stack variable is freed, that region of memory becomes available for other stack variables.

What are the steps to answering an interview problem? 1. Make sure you understand. 2. ASK clarifying questions. (They WANT you to do this.) 3. Talk out your thought process to the interviewer.

What are some ways to approach designing an algorithm for a new problem? 1. Frame your problem in terms of another, more general problem to use an already existing algorithm. 2. Start with a Brute Force application to give yourself a base. Then optimize it. 3. Divide and Conquer - a way of dealing with a large problem by breaking it down into bits and pieces and working your way up towards the solution. Instead of seeing the whole problem as a single, huge and complex task you divide the problem in relatively smaller problems that are easier to understand and deal with. You solve smaller problems and aggregate the solution until you are left with the solution only. At each step the problem at hand shrinks and the solution gets mature until you have the final correct solution. Solving the smaller task and applying the same solution repetitively ( or often times recursively) to other chunks give you the result in less time.

What is the time and space complexity of heapsort? O(n lg n) time O(1) space What is the time and space complexity of merge sort? O(n lg n) time O(n) space How would you split up a data set in order to choose from multiple models? In such a situation, you should split the data into three parts: a training set for building models, a validation set for choosing among trained models (called the cross-validation set), and a test set for judging the final model. What is a Type 1 error? A false positive What is a Type 2 error? A false negative In statistics, how would you calculate precision? true_pos / (true_pos + false_pos) In statistics, how would you calculate recall? true_pos / (true_pos + false_neg) In statistics, what does precision measure? Precision measures how accurate our positive predictions are. In statistics, what does recall measure? Recall measures what fraction of the positives our model identified. How would you calculate the F1 score? ...

What is L-BFGS? Answer: Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm using a limited amount of computer memory. It is a popular algorithm for parameter estimation in machine learning.

What does BFGS stand for? Answer: Broyden-Fletcher-Goldfarb-Shanno algorithm

What is the trade-off between precision and recall? Answer: A model that predicts "yes" when it's even a little bit confident will probably have a high recall but a low precision; a model that predicts "yes" only when it's extremely confident is likely to have a low recall and a high precision. Alternatively, you can think of this as a trade-off between false positives and false negatives. Saying "yes" too often (high recall) will give you lots of false positives; saying "no" too often will give you lots of false negatives (high precision).

How would you divide up a data set for training and testing? Answer: Split your data set, so that two-thirds of it is used to train the model, after which we test/measure the model's performance on the remaining third.

Machine learning: What tends to happen with the training error in a linear model as the degree of polynomial increases? Answer: The error decreases, but too high a degree of polynomial will cause overfitting.