Back to Dashboard

Intro to Data Structures and Algorithm Interviews

Master the systematic approach to acing coding interviews with this comprehensive step-by-step framework.

The 7-Step Interview Process

These are the steps you should follow when in a data structures and algorithm interview:

1. Read the Question / Understand the Question

  • • Read outloud or silently

2. Clarifying Questions

Ask questions to ensure you understand the constraints and requirements.

3. Identifying Edge Cases

Consider boundary conditions and special scenarios.

4. Come Up With Algorithm

4a. Discuss Tradeoffs

4b. Write It Out (Pseudocode, Scratch Notes)

Purposes:

  • • Reminder for yourself - it's so you don't forget your approach halfway through implementation
  • • This is going to help talk outloud
  • • Reference notes for the interview committee
  • • Align on the approach with the interviewer (the more time spent here the less likely you will go off the rails in implementation step)

5. Implement

5a. Talk Out Loud

Explain your thought process as you code.

6. Test Your Code

Custom test cases / walking through your code before clicking run (it is ok to test during development!)

Responsibility (like proofreading a paper)

The interviewer doesn't know if you're a responsible programmer or not who looks at code before submitting PR or kicking off expensive builds. The interview is where you show them.

7. Time and Space Complexity Analysis

(can be done in clarifying questions, but not recommended to commit upfront in case you can't think of an approach to align with that)

Sample Question

Problem Statement

Given an array of 0s, 1s, and 2s, return a sorted array.

# input -> [2, 0, 2, 1, 1, 0]
# output -> [0, 0, 1, 1, 2, 2]

Brute Force Approach

This brute force approach would fail unless you were going for an internship at not a top tier tech company (i.e. not Meta, Google, OpenAI but instead Target, CVS, Capital One)

def sort_colors_brute_force(arr:list[int]) -> list[int]:
    """
    Brute-force method to sort array of 0s, 1s, and 2s.
    Not in-place: builds and returns a new sorted list.
    """
    # Step 1: Count occurrences of 0s, 1s, and 2s
    count_0 =count_1 =count_2 =0
    for numin arr:
        if num== 0:
            count_0 +=1
        elif num== 1:
            count_1 +=1
        elif num== 2:
            count_2 +=1

    # Step 2: Reconstruct sorted list
    return [0]* count_0+ [1]* count_1+ [2]* count_2

Time and Space Complexity

Time Complexity: O(n)

  • • One pass to count (O(n))
  • • One pass to build a new list (O(n))

Space Complexity: O(n)

  • • Because it creates a new list with the sorted result
  • • Uses only 3 integers (count_0, count_1, count_2) otherwise

Optimal Solution (Jr, Mid-level, Senior)

This is what you need to produce to pass as jr, mid-level and senior:

Example of Pseudocode Notes You Should Take

low -> 0
mid -> 0
high -> len(input) - 1

traversing the array using mid

if arr[mid] === 0 swap arr[mid] with arr[low], increment mid and low
if arr[mid] == 1: just move mid forward
if arr[mid] == 2: swap arr[mid] with arr[high], decrement high. not increment mid in this case
def sort_colors(arr):
   # Initialize three pointers
   low =0# For placing 0s
   mid =0# Current element under consideration
   high =len(arr)- 1# For placing 2s

   # Traverse the array with mid pointer
   while mid<= high:
       if arr[mid] ==0:
           # Swap current element with the element at low
           arr[low],arr[mid]= arr[mid], arr[low]
           low +=1
           mid +=1
       elif arr[mid] ==1:
           # 1s are in the middle, just move forward
           mid +=1
       else:
           # Swap current element with the element at high
           arr[mid],arr[high]= arr[high], arr[mid]
           high -=1# Move high pointer left
           # Do not increment mid here because we need to check the swapped value

   return arr

⏱️ Time Complexity

➤ O(n) – Linear Time

Why?

You only traverse the array once, using a while loop with a mid pointer.

At every step, you do one of three operations:

  • • Move mid forward,
  • • Swap and move low and mid,
  • • Swap and move high backward.

Although high might get moved many times, each index in the array is looked at only once by mid. Even when we swap with high, we are bringing in a new element to inspect — but that new element has not been processed yet. So we never reprocess an element.

Conclusion:

Each element is processed at most once. Therefore, the total number of operations is proportional to the number of elements, i.e., O(n), where n is the length of the array.

🧠 Space Complexity

➤ O(1) – Constant Space

Why?

  • • The algorithm sorts the array in-place.
  • • It uses only a fixed number of pointers (low, mid, high) and no extra data structures like lists or dictionaries.
  • • You are not allocating space that scales with the input size — just 3 integers and some temporary variables for swapping.

Conclusion:

The space usage does not increase with input size. So the algorithm has constant space complexity, or O(1).

Advanced Solution (Staff/Principal Engineer)

Truly General k-Partition Version (In-place)

This version generalizes the Dutch National Flag algorithm to handle any number of distinct known values (e.g., 0–k), assuming:

  • • The set of values is known ahead of time and bounded
  • • You want to sort them in-place and group them by category

It works by maintaining a boundary pointer for each value.

General k-Partition Algorithm Explanation:

  1. 1. Initialize a pointer map for each value: value → index
  2. 2. Traverse the array and for each value:
  3. • Shift larger values right to make room
  4. • Insert current value at the right spot (its partition's boundary)
  5. • Update boundaries for that value and all greater values
def k_partition_sort(nums:list[int], value_order:list[int]):
    """
    In-place sorting of known k distinct values using generalized Dutch National Flag logic.
    
    Args:
    nums: list[int] - input list containing only values from value_order.
    value_order: list[int] - the ordered list of distinct values (e.g., [0,1,2] or [0,1,2,3,4])
    """
    from collectionsimport defaultdict

    # Step 1: Create boundary map
    boundaries =defaultdict(int)# Maps each value to where its region ends
    n =len(nums)
    
    i =0
    while i< n:
        val =nums[i]
        # Find where to insert this value
        insert_pos =0
        for vin value_order:
            if v== val:
                break
            insert_pos +=boundaries[v]

        # If insert position < current index, we need to shift the middle block
        if insert_pos!= i:
            # Save current value
            temp =nums[i]
            # Shift elements right
            for jin reversed(range(insert_pos, i)):
                nums[j +1]= nums[j]
            # Insert the value at correct boundary
            nums[insert_pos]= temp

        # Update boundaries for current and all greater values
        found =False
        for vin value_order:
            if v== val:
                found =True
            if found:
                boundaries[v]+= 1

        i +=1


# Example with 3 values
nums1 =[2, 0, 2, 1, 1, 0]
k_partition_sort(nums1,[0, 1, 2])
print("Sorted (3-value):", nums1)# Output: [0, 0, 1, 1, 2, 2]

# Example with 5 values
nums2 =[4, 2, 0, 1, 3, 2, 4, 0, 1, 3]
k_partition_sort(nums2,[0, 1, 2, 3, 4])
print("Sorted (5-value):", nums2)# Output: [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

Time and Space Complexity of k_partition_sort

Time Complexity: Worst-case O(n * k)

For each of the n elements, shifting may require O(k) operations (up to k boundaries checked + shifting range).

Space Complexity: O(k)

Uses O(k) space for the boundaries map. No auxiliary array used.