I was invited for an Amazon online assessment (OA) earlier this month. It wasn’t the first time I tried approaching Big Tech, but the first time it did not reject my CV.

This OA invitation was very surprising to me, but made me happy. It had a week deadline, and I wanted to give it my best try to see how it goes. So I started preparing for it (a.k.a grinding DSA and leetcode). I was surprised by the sheer amount of stuff you need to know in order have a chance to pass it. And a week ended up not being enough to prepare for it. I managed to pass the first task, and the second one was too hard (2D-DP I barely scratched)

Anyway, at the end I got rejected, but it did not discourage me. I keep learning, and I’m posting this to share what I struggled with the most so far, and how I approached various DSA topics.

You can find exhaustive explanation of those algorithms scattered across the internet. I’d rather discourage you from relying solely on this post for preparation as it’s just my opinionated thoughts on the stuff you need to learn. It makes a nice addition to your study materials to get different point of view, but shouldn’t really be treated as a base of it.

The Patterns Link to heading

There are multiple so-called “patterns” you need to memorize and embody within your brain cells in order to be able to recognize and apply them either in OA or in-office face to face interview.

Those patterns are:

  • Two Pointers
  • Binary Search
  • Heap / Priority Queue
  • DFS (a.k.a Depth-First Search)
  • BFS (a.k.a Breath-First Search)
  • Backtracking
  • DP (a.k.a Dynamic Programming)
  • Trie
  • Greedy
  • Graph

Two Pointers Link to heading

Two pointers is a pattern used on arrays when you need to iterate it while maintaining two distinct indicies. You can move those pointers in the same direction, opposite direction, or in a sliding window of fixed width (which is itself a sub-pattern of two pointers).

Same Direction Link to heading

There is a slow pointer, and a fast pointer. When a fast pointer reaches the end of array then algorithm returns calculated result. This result will vary on a problem-by-problem basis. One of the basic (Leetcode easy) problems that can be solved using same direction pointers is 26. Remove Duplicates from Sorted Array

Solution
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0

        for fast in range(1, len(nums)):
            if nums[fast] > nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
        
        return slow + 1

Slow pointer is maintaining the last index of non-duplicated subset of nums. It only moves when non-duplicate number is matched (if condition). After it moves it also replaces list value with a non-repeating number to fulfill remove the duplicates in-place requirement. Previous value at slow index is lost but you don’t need it - it was a duplicate.

Since slow is the last index of non-repeating subset of nums, the result we are looking for (count of non-repeating numbers) is slow + 1

The problem can be solved this way because nums are sorted in **non-decreasing order** (stated in description) so consequent number is either the same or greater than the current one.

Opposite Direction Link to heading

There is a left pointer, and a right pointer. The left starts at the leftmost index (0), the right start at the rightmost index (len(numbers) - 1).

In order to proceed you need to determine which pointer should be moved. It can be either left, or right. Once you pinpoint it and move it, the next step is to check whether left and right indices fulfill stated problem. If they do then return result, otherwise proceed with another iteration.

One of the problems which can be solved with this pattern is 167. Two Sum II - Input Array Is Sorted

Solution
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while left < right:
            candidate = numbers[left] + numbers[right]

            if candidate == target:
                return [left + 1, right + 1]
            elif candidate < target:
                left += 1
            else:
                right -= 1

Input array is sorted in non-decreasing order, so each consecutive n_i is either the same or greater than the previous one. We need to find a target sum of two numbers at distinct indices. Since array is sorted we can start from the leftmost value (smallest), and the rightmost value (largest), and iterate over a list checking whether sum is equal to target.

The condition is fairly straightforward.

If sum is equal to target, then we found our solution.

If sum is less than target it means that we need to increase it. The array is sorted in ascending order, so to increase it we need to move left pointer closer to the right.

Reversed condition apply for the right pointer. If sum is less than target, we need to decrease it. The array is sorted in ascending order, so to decrease it we need to move right pointer closer to the left.

Sliding Window Link to heading

Sliding window is a Same Direction variant but instead of pointers pointing to two distinct indices they point to starting and ending index of a subarray. When moved, window either shrinks, enlarges, or stay the same but moves left or right.

Sliding window can be used when

Sign up for the newsletter