Expedia iOS Tech Screen: Pattern Drills

Solve 4 Expedia iOS interview problems in Swift using core algorithm patterns.

Introduction

30 Second Summary

You open a coding interview, read the problem, and the clock starts. The difference between senior engineers who pass and those who don't often comes down to one thing: recognizing which algorithm pattern fits the problem within the first 30 seconds.

In this project, you will build a Swift command-line tool that solves 4 LeetCode problems recently asked in Expedia's iOS Mobile Engineer III tech screen. Each solution trains a specific pattern-recognition reflex so you can identify the right approach before you write a single line of code.

What You'll Build

You run the project in Xcode and see all 4 problems solved with passing test cases printed to the console, each annotated with the pattern signal that tells you exactly when to reach for that algorithm.

By the end of this project, you'll have:

  • A runnable project where you press Cmd+R and see 4 optimally-solved problems with PASS results and complexity annotations printed to the console.
  • A documented Pattern Signal for each problem that trains you to identify the right algorithm (prefix sum, hash map grouping, interval merging, greedy + heap) in under 30 seconds.
  • A custom MaxHeap you built from scratch that you can drop into any future heap problem, since Swift has no built-in priority queue.
  • Secret Mission: Optimize Group Anagrams from O(n * k log k) to O(n * k) using a character frequency key.

Are there any prerequisites?

You should be comfortable with Swift syntax (arrays, dictionaries, loops, closures) and have basic knowledge of data structures and algorithms. You also need a Mac with Xcode installed.

Before We Start

Before We Start...

Before we dive in, let's lock in what you're about to build and why it matters for your Expedia prep. You are building a pattern-recognition toolkit in Swift. The goal is not to memorize solutions but to train the reflex: "I see signal X in the problem, so I reach for pattern Y."

Set Up the Xcode Project

Algorithm practice works best when you can iterate fast: write a function, run it, see output, fix a bug, repeat.

In this step, you'll create a minimal Xcode project that compiles and runs Swift code with console output. No UI, no frameworks. Just a file and a Run button.

In this step, get ready to:
  • Create a new macOS Command Line Tool project in Xcode.
  • Confirm the project compiles and prints output to the console.
Create a new Command Line Tool project

A Command Line Tool project gives you a single main.swift file that runs as a console application. No storyboards, no app lifecycle. Perfect for algorithm drills.

  • Press Cmd+Space to open Spotlight.
  • Type Xcode and press Enter to open it.
  • Click File in the menu bar.
  • Click New, then Project.
  • Select the macOS tab at the top of the template chooser.
  • Select Command Line Tool and click Next.
  • Enter ExpediaPatternDrills in the Product Name field.
  • Make sure Language is set to Swift.
  • Click Next, choose your Desktop as the save location, then click Create.

Xcode opens the project with main.swift visible in the left sidebar. This file is your program's entry point.

Why a Command Line Tool?

Playgrounds are tempting for quick experiments, but they have slow execution and flaky autocomplete. A Command Line Tool gives you the full Xcode debugger, fast compilation, and real project structure.

For algorithm practice where you need to iterate quickly, this is the best setup.

Replace the starter code and run

Xcode generated some default code in main.swift. You'll replace it with a simple print statement to confirm everything compiles and runs.

  • Click on main.swift in the left sidebar to open it in the editor.
  • Select all the existing code by pressing Cmd+A.
  • Replace it with the following code:
import Foundation

print("Pattern Drills Ready")

What does this code do?

  • import Foundation brings in Apple's base library. You'll need it for data structures later.
  • print("Pattern Drills Ready") writes text to the Xcode console, confirming your project is set up correctly.
  • Run the project by pressing Cmd+R.

Look at the console panel at the bottom of the Xcode window. You should see:

Pattern Drills Ready

Don't see the console output?

  • If the console panel is hidden, press Cmd+Shift+C to toggle it open.
  • If you see a build error, check that you selected Swift as the language when creating the project. Objective-C projects expect a different file structure.
  • Make sure you replaced ALL the default code in main.swift. Leftover lines from the template can cause conflicts.

Help me debug why my Xcode Command Line Tool isn't printing output to the console.

✔️ Awesome, I've got everything!

Great. Double check you've saved main.swift and the console shows the output.

ⓧ I'd like to double check the full code

Here is the complete main.swift for this step:

import Foundation

print("Pattern Drills Ready")

Your environment is ready. Next up, you'll tackle your first algorithm problem using the prefix sum pattern.

Solve Find Pivot Index with Prefix Sum

Your project compiles and runs. Now it is time to solve the first problem: LeetCode 724, Find Pivot Index.

You will start with a brute-force approach to understand the problem, then optimize to O(n) using the prefix sum pattern. This teaches the key interview reflex: when you see a problem asking about balance points or cumulative ranges in an array, reach for prefix sum.

In this step, get ready to:
  • Write a brute-force O(n²) solution and confirm it passes all test cases.
  • Optimize to O(n) using the prefix sum pattern.
  • Document the pattern signal so you can recognize this pattern in 30 seconds.
Add the test helper function

Before writing any solution, you need a way to verify your answers. A small test helper will print PASS or FAIL for each case so you get instant feedback in the console.

  • In Xcode, open main.swift.
  • Select all the existing code and replace it with the following:
import Foundation

// MARK: - Test Helper

func assertEqual<T: Equatable>(_ result: T, _ expected: T, _ label: String) {
    if result == expected {
        print("  PASS: \(label)")
    } else {
        print("  FAIL: \(label) \u2014 got \(result), expected \(expected)")
    }
}

What does this code do?

  • assertEqual is a generic function that compares any Equatable result against an expected value.
  • If they match, it prints PASS with the label. If not, it prints FAIL with both values so you can debug immediately.
Write the brute-force solution

The problem asks: find the index where the sum of all elements to its left equals the sum of all elements to its right. The most intuitive approach is to check every index by summing both sides separately.

  • Add the following brute-force function and test calls below the assertEqual function:
// Brute-force: O(n^2)
func pivotIndex(_ nums: [Int]) -> Int {
    for i in 0..<nums.count {
        // Sum all elements to the left of i
        var leftSum = 0
        for j in 0..<i {
            leftSum += nums[j]
        }
        // Sum all elements to the right of i
        var rightSum = 0
        for j in (i + 1)..<nums.count {
            rightSum += nums[j]
        }
        if leftSum == rightSum {
            return i
        }
    }
    return -1
}
// Test Problem 1: Find Pivot Index
print("Problem 1: Find Pivot Index (#724)")
assertEqual(pivotIndex([1, 7, 3, 6, 5, 6]), 3, "[1,7,3,6,5,6] -> 3")
assertEqual(pivotIndex([1, 2, 3]), -1, "[1,2,3] -> -1")
assertEqual(pivotIndex([2, 1, -1]), 0, "[2,1,-1] -> 0")

What does this code do?

For each index i, two inner loops sum every element to the left and every element to the right. If both sums match, that index is the pivot.

The three test cases cover: a pivot in the middle (index 3), no pivot at all (-1), and a pivot at the very start (index 0).

Before you run this, do you think all 3 test cases will pass with this brute-force approach?

  • Press Cmd+R to build and run the project.

You should see all three lines print PASS in the Xcode console. The brute-force solution is correct.

Why is this O(n²)?

For every index (n iterations), two inner loops each scan up to n elements. That is n × n = O(n²) time. For small arrays this works fine, but in an interview with constraints up to 10,000 elements, an O(n) solution is expected.

Not seeing PASS for all three?

  • Check that you removed the old print("Pattern Drills Ready") line. The file should start with import Foundation.
  • Make sure the assertEqual function appears before pivotIndex in the file. Swift reads top to bottom.
  • Verify the test arrays match exactly: [1, 7, 3, 6, 5, 6], [1, 2, 3], and [2, 1, -1].

Why is my brute-force pivotIndex not passing all test cases?

Optimize with prefix sum

The brute-force works but recalculates sums from scratch at every index. The prefix sum insight: compute the total once, then maintain a running left sum as you iterate. The right sum is always total - leftSum - nums[i].

  • In main.swift, find the entire brute-force pivotIndex function (including the // Brute-force: O(n^2) comment above it).
  • Replace it with this optimal implementation:
func pivotIndex(_ nums: [Int]) -> Int {
    // Compute total sum once
    let total = nums.reduce(0, +)
    var leftSum = 0
    for i in 0..<nums.count {
        // Right sum is everything except left side and current element
        let rightSum = total - leftSum - nums[i]
        if leftSum == rightSum {
            return i
        }
        // Grow left sum as we move right
        leftSum += nums[i]
    }
    return -1
}

What does this code do?

  • nums.reduce(0, +) computes the total sum in a single pass.
  • As you iterate, leftSum tracks the running sum of everything to the left of index i.
  • rightSum = total - leftSum - nums[i] gives you the right side without a second loop. One pass, O(n) time, O(1) space.

The function signature and return values are identical. Do you think the same 3 test cases will still pass?

  • Press Cmd+R to run.

All three PASS lines appear again. Same correct results, but now in O(n) instead of O(n²).

Seeing FAIL on one of the tests?

  • Double check that leftSum += nums[i] comes AFTER the comparison, not before. Adding before you compare shifts the balance.
  • Make sure you fully deleted the old brute-force function. Two functions with the same name will cause a compile error.

Help me fix my prefix sum pivotIndex implementation.

Document the pattern signal

The pattern signal is the most valuable part of this exercise. It is the one-line reflex that tells you which algorithm to reach for within 30 seconds of reading a problem.

  • Directly above the func pivotIndex line, add the following comment block:
// MARK: - Problem 1: Find Pivot Index (#724)
// Pattern: Prefix Sum
// Signal: Problem asks about a balance point, cumulative range, or splitting
// an array into equal-sum halves. Reach for prefix sum.
// Time: O(n), Space: O(1)

Why document the signal?

In an interview, you have maybe 30 seconds to read the problem and decide on an approach. The signal comment captures the keywords (balance point, cumulative range, equal-sum halves) that should trigger this pattern. When you review this file before your interview, these signals train your pattern recognition reflex.

  • Also update the test section. Find the line that says:
// Test Problem 1: Find Pivot Index
print("Problem 1: Find Pivot Index (#724)")
  • Replace those two lines with the following to add the section header and a trailing blank line:
// MARK: - Run All Tests

print("=== Expedia iOS Tech Screen: Pattern Drills ===\n")

// Test Problem 1: Find Pivot Index
print("Problem 1: Find Pivot Index (#724) \u2014 Prefix Sum")
assertEqual(pivotIndex([1, 7, 3, 6, 5, 6]), 3, "[1,7,3,6,5,6] -> 3")
assertEqual(pivotIndex([1, 2, 3]), -1, "[1,2,3] -> -1")
assertEqual(pivotIndex([2, 1, -1]), 0, "[2,1,-1] -> 0")
print("")

What changed in the test section?

  • The // MARK: - Run All Tests comment creates a navigation landmark in Xcode's jump bar. As you add more problems, you can quickly jump to the test section.
  • The header print line gives your console output a clear title.
  • The trailing print("") adds a blank line after this problem's output, keeping things readable when more problems follow.
  • Save main.swift with Cmd+S.
  • Press Cmd+R to build and run.

You should see this output in the Xcode console:

=== Expedia iOS Tech Screen: Pattern Drills ===

Problem 1: Find Pivot Index (#724) — Prefix Sum
  PASS: [1,7,3,6,5,6] -> 3
  PASS: [1,2,3] -> -1
  PASS: [2,1,-1] -> 0

Seeing a compile error?

  • If Xcode shows a "cannot find 'assertEqual' in scope" error, make sure the assertEqual function is defined above pivotIndex in the file. Order matters in main.swift.
  • If you see a duplicate function error, confirm you fully removed the old brute-force pivotIndex function.

Help me fix my compile error in main.swift.

✔️ Awesome, I've got everything!

Great. Double check you have saved main.swift and all 3 PASS lines appear when you run.

ⓧ I'd like to double check the full code

Your main.swift should contain these sections in order. Scroll through your file and confirm each is present:

  • import Foundation at the top.
  • // MARK: - Test Helper followed by the assertEqual function.
  • The Pattern Signal comment block (MARK, Pattern, Signal, Time/Space lines).
  • The optimized pivotIndex function using total, leftSum, and rightSum.
  • // MARK: - Run All Tests followed by the header print, 3 assertEqual calls, and a trailing print("").

Your first pattern is locked in. You can now recognize and implement prefix sum in under a minute. Next up, you will tackle Group Anagrams and learn the hash map with canonical key pattern.

Solve Group Anagrams with Hash Map Canonical Key

Your pivot index solution proved you can spot a prefix sum problem in seconds. Now you are moving to a pattern that shows up even more often in interviews: grouping items by equivalence.

Group Anagrams asks you to cluster strings that are rearrangements of each other. The key insight is that every anagram shares the same set of characters. If you sort each string's characters, all anagrams collapse to the same sorted key. That sorted key becomes your canonical form, and a dictionary groups everything that shares one.

In this step, get ready to:
  • Implement the Group Anagrams solution using a sorted-character canonical key and a dictionary.
  • Add test cases that verify all 3 expected groups print PASS.
  • Document the Pattern Signal comment for hash map canonical key recognition.
Implement the groupAnagrams function

The algorithm is straightforward: iterate over every string, sort its characters to produce a key, and append the original string to the dictionary bucket for that key.

  • In main.swift, find the line that says // MARK: - Run All Tests.
  • Add the following function directly above that line:
// MARK: - Problem 2: Group Anagrams (#49)

func groupAnagrams(_ strs: [String]) -> [[String]] {
    var dict = [String: [String]]()
    for s in strs {
        let key = String(s.sorted())
        dict[key, default: []].append(s)
    }
    return Array(dict.values)
}

What does this code do?

For each string s, s.sorted() rearranges its characters alphabetically. "eat", "tea", and "ate" all sort to "aet".

The dict[key, default: []] pattern creates an empty array if the key does not exist yet, then appends the original string. After one pass, every bucket contains all the anagrams for that sorted key.

Add test cases and run

The standard LeetCode example uses 6 strings that should split into 3 groups. You will also verify the exact contents of each group.

  • In main.swift, scroll down to the // MARK: - Run All Tests section.
  • Find the line print("") after the Problem 1 tests.
  • Add the following test code below that line:
// Test Problem 2: Group Anagrams
print("Problem 2: Group Anagrams (#49) \u{2014} Hash Map with Canonical Key")
let anagramResult = groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
let anagramGroupCount = anagramResult.count
assertEqual(anagramGroupCount, 3, "6 strings -> 3 groups")
let sortedGroups = anagramResult.map { $0.sorted() }.sorted { $0[0] < $1[0] }
assertEqual(sortedGroups[0], ["ate", "eat", "tea"], "Group 1: ate/eat/tea")
assertEqual(sortedGroups[1], ["bat"], "Group 2: bat")
assertEqual(sortedGroups[2], ["nat", "tan"], "Group 3: nat/tan")
print("")

Why sort the groups before asserting?

Dictionary order is not guaranteed in Swift. The sortedGroups line sorts each inner array alphabetically, then sorts the outer array by each group's first element. This gives you a deterministic order so your assertions always pass.

Before you run this, do you think all 4 test assertions will pass on the first try?

  • Press Cmd+R to build and run.

You should see all 4 Group Anagrams tests print PASS in the Xcode console, alongside your existing Pivot Index results.

Seeing FAIL on the group assertions?

  • Make sure you copied the sortedGroups line exactly. If you skip the outer .sorted { $0[0] < $1[0] }, the groups may arrive in a different order each run.
  • Check that your groupAnagrams function returns Array(dict.values), not dict.keys.

Help me debug my Group Anagrams test failures.

Add the Pattern Signal comment

The solution works. Now step back and document the interview reflex: when should you reach for this pattern?

  • In main.swift, find this line above your groupAnagrams function:
// MARK: - Problem 2: Group Anagrams (#49)
  • Add these comment lines between the MARK line and the func groupAnagrams line, so the block looks like this:
// MARK: - Problem 2: Group Anagrams (#49)
// Pattern: Hash Map with Canonical Key
// Signal: Problem asks to group, deduplicate, or find equivalences among items.
// Transform each item into a canonical key and use a hash map.
// Time: O(n * k log k), Space: O(n * k)

What is a Pattern Signal?

A Pattern Signal is the cue you look for in the first 30 seconds of reading a problem. For this pattern, the signal is any problem that asks you to group, deduplicate, or find equivalences among items.

The canonical key can take different forms depending on the problem: sorted characters (anagrams), frequency counts, prime products, or normalized representations. The dictionary does the heavy lifting of grouping.

  • Save main.swift.
  • Press Cmd+R to confirm the project still builds and all tests pass.

✔️ Awesome, I've got everything!

Great. Double check you have saved main.swift and see all PASS lines in the console.

ⓧ I'd like to double check the full code

Your main.swift should now contain these sections in order. Scroll up and confirm each is present:

  • The assertEqual test helper function.
  • Problem 1: pivotIndex with Pattern Signal and complexity comments.
  • Problem 2: groupAnagrams with Pattern Signal (Hash Map with Canonical Key) and complexity comments.
  • The // MARK: - Run All Tests section with Pivot Index tests followed by Group Anagrams tests (4 assertions: group count, group 1, group 2, group 3).

Two patterns down. Next up, you will tackle Merge Intervals, where sorting by start time unlocks a clean linear scan through overlapping ranges.

Solve Merge Intervals with Sort and Linear Scan

Your hash map grouping solution handles anagrams cleanly. Now you'll tackle a pattern that shows up constantly in interval-related questions at Expedia.

Merge Intervals asks you to combine overlapping ranges into a single list. The key challenge: overlapping intervals might not be adjacent in the input. Sorting by start time guarantees that any overlapping intervals end up as neighbors, letting you merge in a single linear pass.

In this step, get ready to:
  • Implement the merge function using sort + linear scan.
  • Add test cases covering standard, touching, and unsorted intervals.
  • Document the Pattern Signal for recognizing interval problems.
Implement the merge function

The algorithm has two phases. First, sort the intervals by their start value so overlapping intervals become adjacent. Second, scan through the sorted list and merge any interval whose start is less than or equal to the previous interval's end.

  • In main.swift, find the line that says // MARK: - Run All Tests.
  • Add the following function above that line:
func merge(_ intervals: [[Int]]) -> [[Int]] {
    guard !intervals.isEmpty else { return [] }
    let sorted = intervals.sorted { $0[0] < $1[0] }
    var output: [[Int]] = [sorted[0]]

    for i in 1..<sorted.count {
        let start = sorted[i][0]
        let end = sorted[i][1]
        let lastEnd = output[output.count - 1][1]

        if start <= lastEnd {
            output[output.count - 1][1] = max(lastEnd, end)
        } else {
            output.append([start, end])
        }
    }
    return output
}

What does this code do?

  • guard !intervals.isEmpty handles the edge case of an empty input immediately.
  • sorted { $0[0] < $1[0] } sorts intervals by start value, guaranteeing overlapping ranges are adjacent.
  • The if start <= lastEnd check detects overlap. Using <= (not <) is critical. Intervals [1,4] and [4,5] are considered overlapping.
  • max(lastEnd, end) extends the merged interval to cover both ranges fully.
  • Build the project by pressing Cmd+B.
  • Verify you see Build Succeeded in the Xcode status bar with no errors.

Seeing a build error?

  • Check that the function is placed before the // MARK: - Run All Tests line. Calling the function before it's defined causes a compile error.
  • Make sure the closing brace } for the function matches the opening brace on the func merge line.

Help me fix my merge function build error.

Add test cases and verify

Three test cases cover the important scenarios: a standard overlapping set, two intervals that touch at exactly one point, and an unsorted input that proves sorting works correctly.

  • Find the last print("") at the end of the Group Anagrams test section.
  • Add the following test block below it:
// Test Problem 3: Merge Intervals
print("Problem 3: Merge Intervals (#56) \u{2014} Sort + Linear Scan")
assertEqual(merge([[1,3],[2,6],[8,10],[15,18]]), [[1,6],[8,10],[15,18]], "Standard case")
assertEqual(merge([[1,4],[4,5]]), [[1,5]], "Touching intervals merge")
assertEqual(merge([[1,4],[0,4]]), [[0,4]], "Unsorted input")
print("")

What do these test cases prove?

  • Standard case: multiple overlapping intervals get merged while non-overlapping ones stay separate.
  • Touching intervals: [1,4] and [4,5] share an endpoint and MUST merge. This catches the common bug of using < instead of <=.
  • Unsorted input: [1,4],[0,4] arrives out of order. The sort step handles it correctly.

Before you run this, what do you expect to see? Will all three test cases pass, or will any fail?

  • Run the project by pressing Cmd+R.

You should see all three Merge Intervals test cases print PASS in the console, alongside the passing tests from Steps 2 and 3.

Seeing a FAIL on the touching intervals test?

  • Check that your overlap condition uses <= (less than or equal), not < (strict less than). Intervals that share an endpoint must merge.
  • If the unsorted test fails, make sure you're iterating over sorted (the sorted copy), not the original intervals parameter.

Help me debug my merge intervals implementation.

Document the Pattern Signal

The Pattern Signal is a comment you write above each solution that captures the 30-second recognition reflex. When you see a problem in an interview, these signals help you identify the right approach before you write any code.

  • In main.swift, find the line that says func merge(_ intervals: [[Int]]) -> [[Int]] {.
  • Add the following MARK comment block directly above it:
// MARK: - Problem 3: Merge Intervals (#56)
// Pattern: Sort + Linear Scan
// Signal: Problem involves ranges, intervals, or time spans that may overlap.
// Sort by start, then linear scan comparing each to the last merged result.
// Time: O(n log n), Space: O(n)

Why this signal works

Any time a problem mentions ranges, time spans, schedules, or intervals that may overlap, the approach is the same. Sort by start value to make overlaps adjacent, then merge in one pass.

The O(n log n) time comes from the sort. The linear scan itself is O(n). Space is O(n) for the output array in the worst case where no intervals overlap.

  • Save main.swift.

✔️ Awesome, I've got everything!

Great. Make sure you've saved your file and all three Merge Intervals tests still print PASS.

ⓧ I'd like to double check the full code

Your main.swift should now contain these sections in order. Scroll through and confirm each is present:

  • import Foundation and the assertEqual test helper.
  • Problem 1: pivotIndex function with MARK header and Pattern Signal.
  • Problem 2: groupAnagrams function with MARK header and Pattern Signal.
  • Problem 3: merge function with MARK header and Pattern Signal (the code you added in this step).
  • Run All Tests section with tests for all three problems (3 for pivotIndex, 4 for groupAnagrams, 3 for merge).

Three patterns down. Your next challenge is the toughest one in the set: Remove Stones requires a greedy approach with a max heap, and Swift's standard library won't help you. You'll build the heap from scratch.

Solve Remove Stones with Greedy and Max Heap

Your first three problems each had a clean, well-known pattern. This final problem introduces a twist: you need to repeatedly modify the largest element in a collection.

The obvious approach is to sort the array each time. You will try that first, confirm it works, and then discover why it falls short at scale. That gap is exactly what forces you to build a data structure Swift does not ship: a max heap.

In this step, get ready to:
  • Attempt a naive sort-each-time solution and analyze why it is too slow.
  • Build a custom MaxHeap struct from scratch in Swift.
  • Implement the optimal greedy + heap solution and verify it passes all test cases.
Attempt the naive sort-each-time approach

LeetCode 1962 asks you to minimize the total sum of a pile array by repeatedly removing half the stones from the largest pile, k times. The first instinct is simple: sort the array, grab the biggest, halve it, re-sort, repeat.

  • In main.swift, find the // MARK: - Run All Tests line. Add this naive function directly above it:
// Naive approach: sort, pick max, halve, re-sort each time
func minStoneSumNaive(_ piles: [Int], _ k: Int) -> Int {
    var arr = piles
    for _ in 0..<k {
        arr.sort()
        let largest = arr[arr.count - 1]
        arr[arr.count - 1] = largest - largest / 2
    }
    return arr.reduce(0, +)
}

What does this code do?

Each iteration sorts the full array to find the maximum, removes half its stones (using integer division for floor), then moves on. It produces correct results for small inputs.

  • Now add a quick test case at the bottom of your file (after the last print("") line) to confirm it works:
// Quick naive test
print("Naive approach test:")
assertEqual(minStoneSumNaive([5, 4, 9], 2), 12, "Naive: piles=[5,4,9], k=2 -> 12")

Before you run this, do you think the naive approach will produce the correct answer for this small input?

  • Run the project with Cmd+R.

You see PASS for the naive test. The solution is correct. But correctness is not the only requirement in an interview.

Why is sorting each time too slow?

Each sort costs O(n log n), and you do it k times. That gives O(n * k log n) total. LeetCode's constraints allow n and k up to 10^5. Multiplied together with the log factor, that is roughly 10^11 operations. Far too slow to pass within the time limit.

What you really need is O(log n) access to the maximum element each time, which drops the total to O(n + k log n). That is exactly what a max heap provides.

  • Delete the entire minStoneSumNaive function and the 3-line naive test you just added. You will replace them with the optimal solution next.
Build a custom MaxHeap struct

Swift has no built-in priority queue or heap in its standard library. In an interview, you need to implement one from scratch. This is an array-based binary heap where the parent lives at index (i-1)/2 and children at 2i+1 and 2i+2.

  • In main.swift, find the // MARK: - Run All Tests line. Add the following code directly above it to start your MaxHeap struct:
// MARK: - Problem 4: Remove Stones to Minimize the Total (#1962)
// Pattern: Greedy + Max Heap
// Signal: Problem requires repeatedly picking the maximum (or minimum) element
// and modifying it. You need a heap. In Swift, implement a custom one.
// Time: O(n + k log n), Space: O(n)

struct MaxHeap {
    private var elements: [Int] = []

    var isEmpty: Bool { elements.isEmpty }
    var count: Int { elements.count }

    init(from array: [Int]) {
        elements = array
        // Build heap: sift down from last non-leaf to root
        for i in stride(from: (elements.count / 2) - 1, through: 0, by: -1) {
            siftDown(i)
        }
    }

    mutating func insert(_ value: Int) {
        elements.append(value)
        siftUp(elements.count - 1)
    }

What does this code do?

The init(from:) takes a raw array and converts it into a valid heap in O(n) time by calling siftDown from the last non-leaf node up to the root. insert appends a value and bubbles it up to maintain the heap property.

  • Try building with Cmd+B. You will see compiler errors about siftDown and siftUp not being found. That is expected. You are about to add them.
  • Directly below the insert method (still inside the struct), add the poll and sum methods, then the two private helpers:
    mutating func poll() -> Int? {
        guard !elements.isEmpty else { return nil }
        let top = elements[0]
        elements[0] = elements[elements.count - 1]
        elements.removeLast()
        if !elements.isEmpty {
            siftDown(0)
        }
        return top
    }

    func sum() -> Int {
        return elements.reduce(0, +)
    }

    private mutating func siftUp(_ index: Int) {
        var i = index
        while i > 0 {
            let parent = (i - 1) / 2
            if elements[i] > elements[parent] {
                elements.swapAt(i, parent)
                i = parent
            } else {
                break
            }
        }
    }

What does this code do?

poll() removes and returns the maximum element. It swaps the root with the last element, removes the last, then sifts down to restore the heap property. sum() returns the total of all remaining elements for the final answer.

siftUp walks a node upward by comparing it to its parent. If the child is larger, they swap. This restores the max-heap property after an insertion.

  • Directly below siftUp, add the final private helper and the struct's closing brace:
    private mutating func siftDown(_ index: Int) {
        var i = index
        while 2 * i + 1 < elements.count {
            let left = 2 * i + 1
            let right = 2 * i + 2
            var largest = i
            if left < elements.count && elements[left] > elements[largest] {
                largest = left
            }
            if right < elements.count && elements[right] > elements[largest] {
                largest = right
            }
            if largest == i { break }
            elements.swapAt(i, largest)
            i = largest
        }
    }
}

What does siftDown do?

siftDown walks a node downward by comparing it to its two children. It swaps with the larger child until the node is bigger than both children or reaches a leaf. This is used by both poll and the build-heap initializer.

  • Save main.swift and build with Cmd+B.
  • You should see Build Succeeded in Xcode's status bar. The compiler errors from earlier are gone.

Still seeing build errors?

  • Make sure the closing brace } after siftDown closes the struct. You should have one brace closing the method and one closing struct MaxHeap.
  • Confirm that siftUp and siftDown are spelled exactly as referenced in init and insert. Swift method names are case-sensitive.
  • Check that all methods are inside the struct's braces. If a method appears after the closing } of the struct, it cannot access elements.

Help me fix my MaxHeap build errors in Xcode

Implement minStoneSum and run the final tests

With the heap in place, the algorithm is simple: build a heap from the piles, poll the max k times, push back the reduced value each time, then sum what remains.

  • Directly below the closing brace of struct MaxHeap (and still above // MARK: - Run All Tests), add the solution function:
func minStoneSum(_ piles: [Int], _ k: Int) -> Int {
    var heap = MaxHeap(from: piles)
    for _ in 0..<k {
        guard let max = heap.poll() else { break }
        let removed = max / 2
        heap.insert(max - removed)
    }
    return heap.sum()
}

What does this code do?

It builds the heap in O(n), then k times: polls the max in O(log n), computes the remainder after removing half the stones, and inserts it back in O(log n). Total: O(n + k log n). Compare that to the naive O(n * k log n).

max / 2 uses Swift's integer division, which automatically floors. So max - removed gives the pile size after removing floor(max/2) stones.

  • Now scroll down to the bottom of the file, after the last print("") line following the Merge Intervals tests. Add the test cases and the closing banner:
// Test Problem 4: Remove Stones
print("Problem 4: Remove Stones to Minimize Total (#1962) — Greedy + Max Heap")
assertEqual(minStoneSum([5, 4, 9], 2), 12, "piles=[5,4,9], k=2 -> 12")
assertEqual(minStoneSum([4, 3, 6, 7], 3), 12, "piles=[4,3,6,7], k=3 -> 12")
print("")

print("=== All Pattern Drills Complete ===")

What do these test cases verify?

  • piles=[5,4,9], k=2: First pick 9, remove 4 (floor(9/2)), leaving 5. Then pick 5 (either one), remove 2, leaving 3. Total: 5+4+3 = 12.
  • piles=[4,3,6,7], k=3: Greedily halving the largest 3 times yields a sum of 12.

Before you run, predict: will both test cases pass on the first try, or do you expect an off-by-one error somewhere?

  • Save main.swift and run with Cmd+R.

Both Remove Stones test cases print PASS, and the final line reads === All Pattern Drills Complete ===. Your heap-based solution is working correctly.

Seeing FAIL or a crash?

  • If the result is off by a small amount, check that your insert pushes back max - removed (not removed itself). You keep the remaining stones, not the removed ones.
  • If you see an index-out-of-range crash, check that poll() guards against an empty array before accessing elements[0].
  • If siftDown seems broken, verify the while condition is 2 * i + 1 < elements.count (checks if a left child exists).

Help me debug my MaxHeap implementation for Remove Stones

✔️ Awesome, I've got everything!

Great. Double check you have saved main.swift and all 4 problems print PASS in the console.

ⓧ I'd like to double check the full code

Your file is long now. Scroll through and confirm these sections appear in order:

  • assertEqual helper function at the top.
  • MARK: Problem 1 with pivotIndex.
  • MARK: Problem 2 with groupAnagrams.
  • MARK: Problem 3 with merge.
  • MARK: Problem 4 with MaxHeap struct and minStoneSum function.
  • MARK: Run All Tests section with tests for all 4 problems, ending with print("=== All Pattern Drills Complete ===").

You now have all four Expedia tech screen patterns implemented and tested. Each one has a documented signal that tells you when to reach for it. That is the reflex you are training: see the signal, grab the pattern, implement with confidence.

Secret mission

Frequency Key Optimization for Group Anagrams

In a real interview, after you present the sorted-key solution, the interviewer will ask: "Can you do better than O(k log k) per string?" Your mission: eliminate the sort entirely by replacing it with a character frequency array key, dropping the per-string cost from O(k log k) to O(k).

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources for interview review, or delete them entirely.

Resources you used:

  • The ExpediaPatternDrills Xcode project folder on your machine.

Keep everything running

No action needed. Choose this if you want to keep the project as an interview reference sheet.

  • Your ExpediaPatternDrills project stays in place, ready for you to review pattern signals before your Expedia screen.
  • You can reopen it any time in Xcode by double-clicking the ExpediaPatternDrills.xcodeproj file.

Pause - I'll come back to this later

Since this is a local project with no running processes, there is nothing to pause. Your project files sit on disk and consume no memory or CPU when Xcode is closed.

  • Close the project in Xcode by pressing Cmd+W.
  • Quit Xcode by pressing Cmd+Q.

Delete - I don't want to use this again

Remove the project folder entirely to free up disk space.

  • Close the project in Xcode if it is still open.
  • Open Terminal and navigate to the folder where you saved your project.
  • Delete the project folder by running:
rm -rf ExpediaPatternDrills
  • Confirm deletion by running ls and verifying ExpediaPatternDrills no longer appears.

Nice Work!

Nice Work!

You just built a complete pattern-recognition toolkit in Swift, solving 4 real Expedia tech screen problems with optimal implementations and passing test cases.

You've learned how to:

  • Solve 4 Expedia iOS tech screen problems optimally in Swift, covering prefix sum, hash map grouping, interval merging, and greedy + heap patterns.
  • Build a reusable MaxHeap from scratch in Swift, a critical skill since Swift has no built-in priority queue in its standard library.
  • Document Pattern Signal comments that tell you which algorithm to reach for within 30 seconds of reading a new problem.
  • Secret Mission: Optimize Group Anagrams from O(n * k log k) to O(n * k) using a frequency array key instead of sorting.

Ready to quiz yourself?