Data structures

What is a linked list?
What is the structure like?
See my first post.

What is the complexity of finding a specific element in a linked list?
Hint: It's O(n).
• An excellent answer will discuss implementation, structure, operational complexity of common operations, and examples of usage.
• A good answer will discuss an example implementation or usage, but will fail to include internal details or complexity analysis.
• A poor answer would be not knowing about linked lists or confusing them with another data structure.

Compare a linked-list to a vector.
Hint: A vector is a single contiguous memory block containing all the elements whereas a linked list is made up of several memory blocks (elements) linked together through the "next" pointer. Access to an element of the array can be made directly in O(1) but in a list, to find the n^th element, you must iterate over the previous n elements, therefore the complexity is O(n). An array is fixed in size so to extend it you must reallocate a different memory block and copy all the existing data to the new allocated block; in a linked list you can simply add a new element which is linked to the last element, so it's much faster.
• An excellent answer will discuss the implementation differences, different pattern of memory usage and access, and mention some use cases where one is more appropriate than the other.
• A good answer will discuss the implementation differences and elaborate on some examples.
• An acceptable answer will merely mention the access time differences.
• A poor answer will make a technical mistake or not know one or both data structures.

What is a hash table? What is it used for?
Hint: The following description applies for all questions about maps. A hash table is a structure which uses hash functions to store and read items. When a key-value pair is inserted, the key is transformed through a hash function into an integer which represents the index in an array where the key-value pair will be stored. Because of this hash function, the insertion and deletions are O(1) in complexity. Therefore, most hash tables are implemented using an array. Hash tables are particularly efficient when the maximum number of entries can be predicted in advance, so that the array can be allocated once with the optimum size and never resized. If hash collisions occur, one usual solution is to store a list of items at each index in the array. This list will contains key-value pairs for which all the keys have the same hash value.
• An excellent answer will describe an O(1) read and write data structure with scaling memory usage and give several examples of where it is useful (e.g. caching, lookup tables with irregular keys).
• A good answer will describe an O(1) read and write data structure and give an example of where it is useful.
• An acceptable answer will mention constant-time access.
• A poor answer will give the access time as something other than constant-time, or confuse it with a tree or other structure.

How can a Map data structure be implemented? (By following the question regarding hash tables, this should be a gimme.)
• An excellent answer will cite at least the hash table-backed and the tree-backed implementations and note the different performance characteristics of each, possibly mentioning that the tree-backed implementation can provide some features not available in a hash-backed implementation (e.g. sorting).
• A good answer will cite both hash table and tree implementations.
• An acceptable answer will cite either the hash table or tree implementation.
• Being unable to answer this question is unacceptable.

What is a binary tree?(This question follows the Map question to allow people who forgot non-hash table solutions to realize and revise their omission. It is good for candidates who only mentioned the hash table implementation of a map to point out that a tree is also an alternative implementation after this question is asked.)
• An excellent answer will describe a binary tree as distinct from a ternary or general tree, and will note that a binary search tree or balanced tree are distinct sub-categories of the generic binary tree.
• A good answer will describe a generic tree where every node has no more than two children and will cite the O(log N) access time where N is the depth/height of the tree.
• An acceptable answer will describe a tree where every node has no more than two children.
• A poor answer will respond by describing a binary search tree or a non-binary tree, and will not respond to gentle hinting or prodding back to the specific question that was asked.

What is the operational complexity of inserting an element into a hash table?
• An excellent answer will correctly cite O(1) complexity and then consider details include about cases in which a collision occurs and common methodologies for resolving hash collisions (i.e. chaining, linear or quadratic probing, secondary hash functions, etc.) are needed.
• A good answer will cite O(1) complexity but will not include collision considerations.
• A poor answer will be incorrect.

How is a hash table implemented?
• An excellent answer will discuss selecting a hashing algorithm, dividing the address space into buckets and tuning the number of buckets to the use-case, hash collisions and bucket overflow/conflict resolution (possibly mentioning several strategies for dealing with collisions), dynamic resizing of the hash table, and might even discuss performance optimizations and interactions with hardware caching.
• A good answer will note the use of a hashing algorithm on the keys and an array or vector of buckets, and will identify hash collisions as a problem and may cite at least one method of dealing with them. The candidate will be able to answer a follow-up about dynamic resizing.
• An acceptable answer will mention an array of buckets and using a hashing function on the key to index into the array.
• A poor answer will be technically incorrect or impossible, or will be for a different data structure than a hash table.
What is the operational complexity of (various operations) on a binary tree?If the candidate already answered this as part of the first phone screen, this question may be skipped. It may also be asked to ensure the candidate is consistent in responding correctly.


What is operational complexity?
Hint: These notations describe different kinds of bounds on asymptotic growth rates. Search the web. You really should know what they all mean, if you want to work at GOOGLE.
• An excellent answer will distinguish between Big Oh, Big Omega, and Big Theta notations and describe each in detail, including how they relate to measures of run-time and space trade-offs.
• A good answer will describe Big Oh notation and how it relates to run-time of algorithms and common operations of abstract data types (ADTs).
• A poor answer will include vague or incorrect ideas regarding Big Oh notation and usage.

What is the operational complexity of inserting an element into a linked list? (Asking a clarifying question about singly-linked lists versus doubly-linked lists is unnecessary in this case, but clarifying requirements is always a good thing.)
• An excellent answer will correctly cite O(N) and note the edge cases such as empty lists and the beginning/ending of the list.
• An acceptable answer will correctly cite O(N).
• A poor answer will be incorrect.

Verbal communication tips

Why are you leaving your current position?
• A good answer will be generally positive, seeking better challenges or goals. Contract expirations and familial obligations are also common.
• A poor answer would be ranting against the current employer or generally being negative. Honesty is not necessarily negativity. The key is how they view their departure, whether they seek self-improvement whatever the situation.

Why do you want to work for GOOGLE?
• An excellent answer will be enthusiastic about GOOGLE and its business and problem space, demonstrating knowledge of our sites and familiarity with its use.
• A good answer will be enthusiastic about GOOGLE and show a desire to work in this environment and on our sorts of problems.
• A mediocre answer will demonstrate a lack of knowledge of our site and operations

Tell me about a recent project that you have worked on.
• An excellent answer will discuss an in-depth project involving a complicated problem, have a clear description of the problem that explains why it was difficult, describe the solution chosen, and reference how the candidate was involved in the entire process and implementation.
• A good answer may involve a small project that was well-executed, or a large project working on a simple problem, or a complex problem for which a sub-optimal solution was chosen.
• An acceptable answer will describe a project in detail from problem to implementation.
• A poor answer will not give a clear explanation of what the purpose of the project was, or will neglect to mention a solution at all, or will say the candidate was not actually involved in the project being described.

How to generate random numbers in [1...7] from random numbers in [1...5]

Well known as a Google/Microsoft interview question, the following problem is actually really complicated to solve correctly, although it looks easy:

Given a function which produces a random integer in the range 1 to 5, write another function which uses it and produces a random integer in the range 1 to 7.

I'm going to modify this a little and make it generic:
Given a function which produces a random integer in the range 1 to 5(M), write another function which uses it and produces a random integer in the range 0 to 7(N).

Of course it's easy to do it without generating a uniform distribution so I'm not going to spend time on that.
What needs to be done is generate a uniform distribution. But consider this example:
If we add random(5) + random(5), assuming random(5) generates numbers from 0 to 4, we have:

   1:  0+0

   2:  0+1, 1+0

   3:  0+2, 2+0, 1+1

   4:  0+3, 3+0, 1+2, 2+1

   5:  0+4, 4+0, 1+3, 3+1, 2+2

   6:  1+4, 4+1, 2+3, 3+2

   7:  2+3, 3+2, 3+3

   8:  3+4, 4+3

   9:  4+4

This obviously is not a uniform distribution because we have more chances of generating the number 4 than the number 8. So whatever algorithm is needed, it cannot simply use operations involving random(5). Or, actually it can, with some complicated math behind. Read about Box–Muller transformations and Rejection sampling.

What I think is a simpler algorithm is the following: since every number can be represented in X bits, generate X numbers from 1 to 5, and depending on the generated number, set bit X to 1 or 0. Number from 0 to 7 can be represented with 3 bits. Let me know what you think.

   1:  int genRandom1to5() {

   2:      return (rand() % 5) + 1;

   3:  }

   4:   

   5:  int genRandom1to7() {

   6:      int rand17 = 0;

   7:      for (int i = 0; i < 3; i++) {

   8:          int rand15 = 3;

   9:          while (rand15 == 3) {

  10:              rand15 = genRandom1to5();

  11:          }

  12:          if (rand15 < 3)

  13:              rand17 |= (1 << i);

  14:      }

  15:      return rand17;

  16:  }

How to do integer partitioning

The problem statement: given a number N, for example 5, print all the partitions of this number, meaning: the sum of all possible number that add up to N. In this example:

   1:          1+1+1+1+1

   2:          1+1+1+2

   3:          1+1+2+1

   4:          1+1+3

   5:          1+2+1+1

   6:          1+2+2

   7:          1+3+1

   8:          1+4

   9:          2+1+1+1

  10:          2+1+2

  11:          2+2+1

  12:          2+3

  13:          3+1+1

  14:          3+2

  15:          4+1

  16:          5

The answer is obviously recursive, and the complexity is, of course O(2^{n - 1}), exponential.

   1:  void doPartitions(int n, vector<int>* partition) {

   2:      if (n <= 0) { //the number cannot be partitioned further, so print

   3:          for (int i = 0; i < partition->size() - 1; i++)

   4:              cout << partition->at(i) << "+";

   5:          cout << partition->at(partition->size() - 1) << endl;

   6:          return;

   7:      }

   8:      int size = partition->size();

   9:      for (int i = 1; i <= n; i++) {

  10:          //add the current no to the partitions

  11:          //and generate partitions from the leftover number

  12:          partition->push_back(i);

  13:          doPartitions(n - i, partition);

  14:          while (partition->size() > size)

  15:              partition->pop_back(); //reset the partitions each iteration

  16:      }

  17:  }

What's left here is to find a way to print only the distinct solutions, but this is a simple exercise.

How to find all possible words from a phone number

The problem statement: Most phone numbers these days are like 1-800-COOLSTUFF, which means you have to type 1-800-266578833 on your phone to dial. Given an array of numbers like "266578833" above, find all the words which could be formed from them. The problem is obviously exponential in complexity. Assuming each phone key holds 3 letters and having the array "266578833", there are 3*3*3*3*3*3*3*3*3 possible combinations, which means 3⁹. So any algorithm has to be at least O(3ⁿ), where n is the size of the array of numbers.

The problem is easily solved in a recursive way: take each number and see which letters are assigned to it. Take each letter in turn, and each turn generate all possible combinations with the other letters:

   1:  //keep here the vector of letters

   2:  //like on position 5, the letters "jkl", which are on key 5 of a phone

   3:  vector<string> words;

   4:   

   5:  void generateWords(int* vec, int size, int index, vector<char>* currentWord) {

   6:      if (index == size) {//print if we reached the end

   7:          for (int i = 0; i < size; i++)

   8:              cout << currentWord->at(i);

   9:          cout << endl;

  10:          return;

  11:      }

  12:      //otherwise take each letter from the current key and add it to the stack

  13:      //then generate combinations with the other keys

  14:      for (int i = 0; i < words[vec[index]].size(); i++) {

  15:          currentWord->push_back(words[vec[index]][i]);

  16:          generateWords(vec, size, index + 1, currentWord);

  17:          currentWord->pop_back();

  18:      }

  19:  }

To call this, "words" needs to be initialized, like this:

   1:      words.push_back("");    //0

   2:      words.push_back(".,'"); //1

   3:      words.push_back("abc"); //2

   4:      words.push_back("def"); //3

   5:      words.push_back("ghi"); //4

   6:      words.push_back("jkl"); //5

   7:      words.push_back("mno"); //6

   8:      words.push_back("pqrs");//7

   9:      words.push_back("tuv"); //8

  10:      words.push_back("wxyz");//9

  11:      int size = 3;

  12:      int vec[] = { 2, 5, 8 };

  13:      vector<char> currentWord;

  14:      generateWords(vec, size, 0, &currentWord);

How to find subsets of an array

The problem statement: given an array of integers, for example (2, 5, 8, 10), how do you print all the subsets of this array. By all the subsets, I mean:

   1:  empty set

   2:  10

   3:  8

   4:  8 10

   5:  5

   6:  5 10

   7:  5 8

   8:  5 8 10

   9:  2

  10:  2 10

  11:  2 8

  12:  2 8 10

  13:  2 5

  14:  2 5 10

  15:  2 5 8

  16:  2 5 8 10

Well the answer is simple recursively: for each number in the array, compute recursively all the subsets without including it. Then include it and compute again all the subsets.

   1:  void subsets_recursive(int* vec, int size, int index, vector<int>* subset) {

   2:      if (index == size) { //print if we reached the end

   3:          if (subset->size() == 0)

   4:              cout << "empty set";

   5:          for (int i = 0; i < subset->size(); i++)

   6:              cout << subset->at(i) << " ";

   7:          cout << endl;

   8:          return;

   9:      }

  10:      int n = subset->size();

  11:      //first print all the subsets without including the number

  12:      subsets_recursive(vec, size, index + 1, subset);

  13:      //clear the numbers that we added in the previous subsets

  14:      while (subset->size() != n)

  15:          subset->pop_back();

  16:      //add the number to the subset and print all subsets including it

  17:      subset->push_back(vec[index]);

  18:      subsets_recursive(vec, size, index + 1, subset);

  19:  }

Iteratively it's a different story. Complexity for this (both recursively and iteratively) is O(2ⁿ), where "n" is the size of the array. This means we have to iterate 2ⁿ times. As it turns out, there's a trick involved: take each number i from 0 to 2ⁿ and check each bit. If bit k from number i is 1, then consider array_k to be in the current subset. Too bad I didn't think of this during the interview. Here it is:

   1:  void subsets_iterative(int* vec, int size) {

   2:      int n = pow((double)2, (double)size);

   3:      vector<int> currentSubset;

   4:      for (int i = 0; i < n; i++) {

   5:          currentSubset.clear();

   6:          for (int j = 0; j < size; j++)

   7:              if (((i >> j) & 1) != 0)

   8:                  currentSubset.push_back(vec[j]);

   9:          if (currentSubset.empty())

  10:              cout << "empty set";

  11:          for (int i = 0; i < currentSubset.size(); i++)

  12:              cout << currentSubset.at(i) << " ";

  13:          cout << endl;

  14:      }

  15:  }

How to do the product trick on a array

The problem is: given an array of numbers, replace each number with the product of all numbers except itself, without using the divide operator "/".
Quite tricky. Of course the goal is to make the program as fast as possible.

First solution: O(n²) - having a temporary array, iterate through the array. At each iteration, iterate again through the array, skipping the current number and keeping the rest of the product in the temporary array. Kids stuff.

Second solution: O(n) - having two temporary arrays, iterate once through the array and keep the product of all numbers smaller (in index) than the current number. Iterate again in reverse and keep a product of all the numbers bigger (in index) than the current number. At the end, the answer is the product of these two vectors. Example:

   1:  array :  1  2  3  4

   2:  left  :  1  1  2  6 <--at each index is the product of all the previous numbers

   3:  rights: 24 12  4  1 <--at each index is the product of all the next numbers

   4:  final : 24 12  8  6 <--left[0]*right[0], left[1]*right[1]... etc.

The program is equally simple:

   1:  void product(int* vec, int size) {

   2:      int* left = new int[size]; //left products

   3:      int* right = new int[size]; //right products

   4:      int product = 1;

   5:      left[0] = 1;

   6:      right[size - 1] = 1;

   7:      for (int i = 1; i < size; i++) {

   8:          left[i] = product * vec[i - 1];//keep the product of prev numbers

   9:          product = left[i];

  10:      }

  11:      product = 1;

  12:      for (int i = size - 2; i >= 0; i--) {

  13:          right[i] = product * vec[i + 1];//keep the product of next numbers

  14:          product = right[i];

  15:      }

  16:      for (int i = 0; i < size; i++)

  17:          vec[i] = left[i] * right[i]; // compute the final results

  18:      delete[] left;

  19:      delete[] right;

  20:  }

How to generate permutations of an array or string

I've been asked this on interviews a number of times, so I think it counts as "common questions". The answer is simple.

It can be done recursively in a logical way: having a function which takes an array, swap the first element with all the others, in turn, and at each turn, call the function again for the rest of the array (skipping the first position):

   1:  //head is the original array, unchanged between functions calls

   2:  //this is so that we can print the full array

   3:  //first is the "partial" array, which is being permuted now

   4:  void permutations(int* head, int totalLen, int* first, int len) {

   5:      if (len == 1) {//we reached the end of the array

   6:          for (int i = 0; i < totalLen; i++)

   7:              cout << head[i] << " ";

   8:          cout << endl;

   9:          return;

  10:      }

  11:      //first do all the permutations

  12:      //without swaping the first element with all the others

  13:      permutations(head, totalLen, first + 1, len - 1);

  14:      int temp = first[0];

  15:      for (int i = 1; i < len; i++) {

  16:          first[0] = first[i]; //swap the first element

  17:          first[i] = temp; //with all the others, in turn

  18:          permutations(head, totalLen, first + 1, len - 1);

  19:          first[i] = first[0]; //each turn generate permutations for

  20:          first[0] = temp;// the rest of the array, then swap back the first elem

  21:      }

  22:  }

The function is called like this:

   1:      int size = 4;

   2:      int vec[] = { 1, 2, 3, 4 };

   3:      permutations(vec, size, vec, size);

How to find the longest continuous increasing sequence

How to find the longest continuous increasing sequence in a array of numbers is one of the questions I was asked in a interview at Microsoft, Copenhagen. The solution I provided then was not the best one, since I wasn't so well prepared (I gave a O(n*log₂n) solution which is better than the basic O(n²) solution, but still not the optimum one). This can be done with O(n) time complexity. Hopefully writing these things here will help me in my future interviews.

The idea for the O(n) solution is to keep track of the start of the longest continuous increasing sequence and it's length. At each item, if it's bigger than the previous, then we have a sequence. If it's longer then the current maximum length, then we have a new longest increasing sequence, longer than the previous one.

The same principle can be applied to similar problem which I'll post later. Until then, here's the algorithm:

   1:  void longestContinuousIncrSeq(int* a, int size) {

   2:      int maxstart = 0;

   3:      int max = 1;

   4:      int start = 0;

   5:      for (int i = 1; i < size; i++) {

   6:          if (a[i] > a[i - 1]) {

   7:              if (i - start + 1 > max) {

   8:                  max = i - start + 1;

   9:                  maxstart = start;

  10:              }

  11:          } else {

  12:              start = i;

  13:          }

  14:      }

  15:      cout << "Longest sequence starts at " << maxstart << " and is " << max << " numbers long." << endl;

  16:      for (int i = 0; i < max; i++) {

  17:          cout << a[maxstart + i] << " ";

  18:      }

  19:      cout << endl;

  20:  }

How to check if a number is a power of 2 (Google phone screening)

This is actually one of the questions I was asked in my Google first phone screening, and it's really easy, because there's a trick for that: given a number N, you can check if it's a power of two if N & (N-1) == 0.

   1:  int n = 1024;

   2:  cout << n << " is " 

   3:      << ((n & (n-1)) ? "NOT " : "" )

   4:      << "power of 2" << endl;

You could also do the iterative version, where you repeatedly check the first byte (N & 1), then shift to the right (N >> 1), and again, for all 32 bits (assuming it's a 32bit integer). If the total number of bits with value 1 is just one, it means it's a power of two. I gave this as an alternative to the trick above and everything was fine.