Common Techniques: Basic

There are some common problem-solving techniques that you should keep in your back pocket during technical interviews. They’ll come in handy for a lot of different questions, and interviewers really want to see that you know them! Three of the most common problem-solving techniques you’ll need to employ during interviews are:

  • Binary search: an efficient search algorithm for sorted arrays that divides the input in half on each pass;
  • Two pointers: a technique that uses two pointers to optimize naive solutions that involve using multiple loops;
  • Prefix sums: a technique for quickly finding the sum of any contiguous slice of an array;

Binary Search

Important Concepts

  • Binary search only works on sorted arrays.
Time complexity
  • Since you’re essentially halving your data input on each pass, the time complexity of this algorithm is O(log n).
  • Because it is very slow to perform insertions or deletions, binary search isn’t useful if the sorted array changes often.
Space Complexity
  • The algorithm takes only O(1) additional space. We have to allocate references to the lower bound, the upper bound, and the current element, regardless of how large the array is.

Generalized Algorithm

  1. Choose an element in the middle. Is that the one you’re looking for? Great! Otherwise, determine whether the element you chose is smaller or greater than the one you’re looking for.
  2. If the element you’re looking for is smaller than the one you chose, you know that you don’t need to worry about any elements to the right of your initial choice. Alternately, if the element you’re looking for is larger than the one you chose, you know that you don’t need to worry about any elements to the left of your initial choice. Either way, you’ve just halved the amount of elements that you need to look at.
  3. Do the same thing again and again, until you’ve found the element you’re looking for!
Pseudocode
def binary_search(l, value):
    # Set a min and a max (the 0th element and the n-1 element)
    min = 0
    max = len(l)-1
    # Check to see if guess is what you’re looking for. If so, stop! You’re done!
    while min <= max:
        # Set a guess as the median of min and max. If the answer isn’t an integer, round down.
        guess = (min + max)//2
        # If your guess was smaller than the target number, you’ll reset your max to guess - 1.
        if l[guess] > value:
            max = guess - 1
        # If your guess was larger than the target number, you’ll reset your min to guess + 1.     
        elif l[guess] < value:
            min = guess + 1
        # Compute a new guess, as in step 2, and start again!    
        else:
            return guess
    return -1

In Interviews, Expect to See Problems Like…

  • Implementing binary search from scratch.
  • Knowledge questions comparing binary search in an array to a binary search tree.
  • Using a binary search to count the number of occurrences of a number in a sorted array.
  • Using a binary search to count the number of occurrences larger than, or smaller than, a given number.
  • Using the binary search strategy to locate inputs of a function without an explicit array, e.g. if f(x) is monotonically increasing that takes integer arguments, binary search can be used to solve invert f(x), or show there is no solution (if f(x) takes floats as an argument, binary search can generally only approximate a monotone function to a given tolorance).
  • Doing multiple searches for an item in a large array.

Two Pointers

Two Pointers techniques come up frequently when manipulating singly-linked lists. Having pointers to two different nodes can be used to overcome the restriction that you can only traverse a singly-linked list in one direction.

Important Concepts

  • The two pointer technique can be used on any data structure that can be iterated through.

There are two main strategies for this technique:

  • Have a fast-runner pointer and a slow-runner pointer, where the fast-runner is ahead of the slow-runner.
  • Have one pointer start at the beginning of the data structure and one pointer start at the end, moving towards each other until they meet.
Time Complexity
  • O(n)

In Interviews, Expect to See Problems Like…

  • Remove duplicates from a sorted array
  • Reverse the characters in a string.
  • Reversing a linked list in place.
  • Detecting a cycle in a linked list.

Prefix Sums

Prefix sums are a method of pre-computation that will allow us to calculate the sum of any contiguous block of an array in O(1) time! The time to compute the prefix sum initial is O(n).

Generalized Algorithm

To create the prefix sum array

In general, prefix sum of an array x is an array y that can be calculated as:

yi = yi − 1 + xi-1 for i > 0, and y0 = 0 
The array y will have one more element than x.

To use the prefix sum array

To get the sum of the elements xa + xa+1 + ... + xb we would calculate yb+1 - ya.

Note: Some sources may not use the leading 0 at the beginning of the prefix sum array. The convention used here wastes a little bit of space, but simplifies some of the bounds checking when using the array.

Time Complexity
  • O(n) to create the prefix sum array.
  • O(1) to use the prefix sum array.
Space Complexity

Given a prefix sum array, it is possible to recover the original array by looking at the difference between neighboring elements. This means we can choose to overwrite the original array with the prefix array, or we can choose to make a separate array.

  • O(n) additional memory, if creating the prefix sum as a new array.
  • O(1) additional memory, if creating the prefix array in place.

In Interviews, Expect to See Problems Like…

  • Line of sight problems (calculating whether one point is visible from another, given an array of heights);
  • Find a cumulative distribution (for example, find what percentage of income the top 1% of earners make from an array of incomes);
  • Calculate the moving average on an array.
X