Design mindset

Often there is more than 1 solution to any problem. Knowing and weighting the pros and cons of each of the solutions is a sign that you have given serious thought about the problem and know how to choose the best one given any constraints. This is a valuable skill that can be leveraged to impress your interviewer during an interview.

A lot of interviewees believe that you should spit out the most optimized solution you know, as fast as possible. But it can also be a sign that you've simply memorized a bunch of solutions. The interviewer wants to see you think. But there is a superior approach, which shows your fluency in Computer Science.

  • Show that you see multiple solutions to this problem.
  • Compare the solutions with one another.
  • Select the one you choose and argument why.

Let's take a look into the famous 2-sum problem.

Having an array of integers, return any2elements that sum to a given number calledtarget.

Let's consider a few solutions in order to compare them.

Brute force

The easiest solution you can come up with is brute force.

Description

  • Consider all the pairs of numbers in the array
  • If any of them sum to the target, return the result

Code

def two_sum(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return (arr[i], arr[j])
    return None

Time and Space Complexity

This approach is taking us

  • O(n²) time because we have two loops iterating over an array
  • O(1) space - we didn't use anything extra

Why it works

This algorithm explicitly checks every single pair of numbers, so if there's a solution exists, it will be found.

Benefits

It is simple to understand, it doesn't require additional space.

Downside

Running time is pretty slow.

Should you mention it in the interview? Yes you should! No need to go into details, just summarize the approach and the time and space complexity. Most likely interviewer would ask if there is a better approach, but seeing the brute force gets you off on the right foot.

The previous algorithm solves the problem but it is slow because of the presence of a double loop which makes its time complexity be O(n^2). However, you can think of a faster solution if you're willing to use a larger amount of memory:

Hashtable

  • Save seen elements in the set because they could sum up to some future elements to form the target
  • For a new element considered, see if its complementary is already in the set
  • If it is, we have found the pair 🎉
  • If not, we will put current element in the set
def two_sum(arr, target):
    seen = set()
    for a in arr:
        need = target - a
        if need in seen:
            return (need, a)
        seen.add(a)
    return None

This approach is taking us

  • O(n) time - we went through the array exactly once
  • O(n) space for set which has no more elements, then the array

Why it works

We have considered all possibilities. Assuming there are two elements in the pair, we consider each second element while iterating on the array, and every first element while looking in the set.

Benefits

Intuitive and easy to understand. O(n) time is as good as it gets.

Downside

O(n) storage with the hash table.

The last approach is especially beneficial, if the array is already sorted / we want to save some space and still be quick.

Two pointers (if the array is sorted)

This can be portrayed as THE most efficient approach if we know that the array is already sorted. And it's also still an interesting and efficient approach if the array is not sorted: just slightly worse than the hash table but much better than brute force.

Description

  • Consider the pair of elements on the left and right
  • If pair sum is equal to target, return result
  • If the pair sum is smaller, increase it by considering next element on the left
  • If the pair sum is bigger, decrease it by considering next element from the right

Code

def two_sum(arr, target):
    arr.sort()
    start = 0
    end = len(arr) - 1
    while start < end:
        s = arr[start] + arr[end]
        if s == target:
            return (arr[start], arr[end])
        elif s < target:
            start += 1
        else:
            end -= 1
    return None

Time and Space Complexity for sorted array

  • O(n) time for the search
  • O(1) space

Really well! But what if array is not sorted?

Time and Space Complexity in general

  • O(n log n) time = O(n) for search and O(n log n) for sort
  • O(n) space - depending on the sort

Why it works

Though it's simple, it might not easy to see why some pairs could not be lost this way. This algorithm will at most compare 2n numbers, so how can we guarantee that we know a solution is found at all if there are n*(n-1)/2 pairs?

Actually, we ARE considering all the pairs. We just NOT considering them individually. We are smartly eliminating the pairs that would not fit.

Let's imagine the pairs on 2D plane.

  • On the horisontal is the index of the start element.
  • On the vertical is the index of the end element.
How two pointer method works
  • We should only consider the pair under the diagonal, because our start < end.
  • We also don't consider any pairs on the diagonal, cause start != end. If start == end it's not really a pair, it's the same element!

We start with start = 0 and end = n - 1

How two pointer method works

Knowing that the sum of start and end bigger than the target, eliminates not only pairs (0, n - 1) but also all the pairs where start > 0: (1, n - 1), (2, n - 1), (3, n - 1) and so on.

Visually, this corresponds to disregarding everything to the right of the current pair.

All right elements are eliminated

Similarly, if the element is less than target, we can discard all the elements above it. Because any element with end index smaller than current would give equally small sum:

All top elements are eliminated

This way we actually consider full 2D plane of the elements, eliminating not only the element which we consider on the route, but:

  • all pairs like (start + x, end) to the right if the pair is bigger than target
  • all pairs like (start, end - x) on top if the pair is smaller than target
How two pointer method works

Benefits

O(n log n) is not much more than O(n). If array is already sorted, we can take advantage of it. We use relatively small space - just for sorting. In some sorting algoritms, like heap sort, we would use no auxilary space at all.

Downside

To sort the array, we have two options: modify it in place or copy and sort. The first option may not use additional space if the correct sorting algorithm is used but has the possibly-unintended side effect of modifying the input array. The second option is to copy the array and then sort, which requires additional O(n) memory.

Conclusion

In the moment of the interview it's great to mention at least one alternative and compare your solution to it. Usually the easiest one to come up with is brute force approach. If you have stuck with ideas, you can start with simplest solution, and then observe it's patterns to see what you can optimize.

If you already know an optimal solution, still mention a different one, even if it's brute force. It shows the interviewer that you are considering options and capable of comparing them to make the best choice which gives you extra point as a candidate.

Remember, it not only about if you solve the problem, it's how you would solve it.