What is Big-O notation, and how do you state the time and space complexity of your solution in a coding round?

Big O describes how an algorithm's running time or memory grows with the input size n, keeping only the fastest-growing term and dropping constants.

How does a Set or a Dictionary turn two-sum, duplicate detection or an anagram check from O(n²) into O(n) in Swift?

Instead of comparing every element with every other one, remember what you have already seen in a hash-based `Set` or `Dictionary`.

Live task: check that a string of brackets like "([]{})" is balanced. Which structure do you use, and which inputs break a naive solution?

A stack: push every opening bracket, and on a closing one pop and check that it is the matching opener.

How do Dictionary(grouping:by:), reduce(into:) and uniquingKeysWith: solve "group anagrams" and "count words", and why is plain reduce a trap here?

They replace the hand-written "look up, insert if missing, append" loop: `Dictionary(grouping:by:)` buckets elements by a key you compute, `reduce(into:)` folds into one dictionary that you mutate in place, and `uniquingKeysWith:` merges the values of repeated keys.

Find the bug: this palindrome check returns the right answer, but takes seconds on a 100,000-character string.

`s.index(s.startIndex, offsetBy: k)` walks the string from the start on every call, because a `Character` can span several bytes, so the loop is O(n²): billions of steps for 100,000 characters, about 9 seconds in a Release build on a Mac.

Which algorithm does Swift's sort() use, is it stable, and how do you sort users by score descending and then by name?

`sort()` is a modified timsort: O(n log n) in the worst case, near O(n) on mostly sorted input, and documented as stable, so equal elements keep their order.

This binary search crashes on some inputs and never returns on others. What is wrong with it, and which loop invariant makes it correct?

It mixes two conventions: `hi = a.count` is a half-open bound, but `lo <= hi` treats it as closed, so an empty array reads `a[0]` and traps; and when `a[mid]` is too small, `lo = mid` keeps `mid` in range, so once `mid == lo` nothing changes and the loop spins forever.

Live task: reverse a singly linked list in place. Follow-up: can freeing a million-node list overflow the stack in Swift, and what about a deep tree?

Walk the list once, saving `node.next` before pointing it back at `prev`: O(n) time, O(1) memory.

How do you traverse a binary tree depth-first and breadth-first in Swift, and which one fits "max depth" and which "level order"?

Depth-first goes down one branch before backing up, through recursion or an explicit stack; breadth-first visits the tree level by level.

Live task: implement an LRU cache with O(1) get and put. Which two structures do you combine, and why is a Dictionary alone not enough?

A `Dictionary` from key to node finds an entry in O(1), and a doubly linked list keeps the nodes in order of use, so moving a node to the front and dropping the last one are O(1) pointer updates.

Swift's standard library has no heap. How do you find the 100 most frequent words in a large text, and what does each approach cost?

Count the words into a dictionary in one O(n) pass, then pick the top k of the u distinct words: sort them all (O(u log u)), keep a min-heap of k entries (O(u log k)), or bucket them by count (O(n + u)).

Feature modules declare which modules they depend on. How do you compute a build order with a topological sort, and how does the same pass detect a cycle?

Treat the modules as a directed graph and run Kahn's algorithm: count each module's unbuilt dependencies, start with the modules at zero, and every time one is "built", decrement its dependents and add any that reach zero.

Irbisa · Cheatsheet

Live Coding Round in Swift

Q: How do you implement a stack and a queue in Swift, and why is Array.removeFirst() a poor way to dequeue?

An `Array` already is a stack: `append` pushes and `popLast()` pops, both O(1).

Q: Live task: write your own map and reduce as extensions on Sequence. What do generics and rethrows add to the signature?

Extend `Sequence`, loop with `for-in` and build the result.

Q: Live task: merge overlapping time slots like [1, 3], [2, 6], [8, 10]. Why sort first, and should touching slots such as [1, 3] and [3, 5] merge?

Sort the slots by start, then sweep once: if a slot starts before the last merged slot ends, extend that one to the later of the two ends, otherwise start a new slot.

Big O, hashing, stacks and queues, two pointers, sliding window, binary search, linked lists, trees, LRU cache, heaps and DP in Swift

Middle Developer · 18 questions

01
What is Big-O notation, and how do you state the time and space complexity of your solution in a coding round?
Big O describes how an algorithm's running time or memory grows with the input size n, keeping only the fastest-growing term and dropping constants.
02
How does a Set or a Dictionary turn two-sum, duplicate detection or an anagram check from O(n²) into O(n) in Swift?
Instead of comparing every element with every other one, remember what you have already seen in a hash-based Set or Dictionary.
```
func hasDuplicate(_ xs: [Int]) -> Bool {  var seen = Set<Int>()  for x in xs {    if !seen.insert(x).inserted { return true }   // inserted is false for a repeat  }  return false…
```

How do you implement a stack and a queue in Swift, and why is `Array.removeFirst()` a poor way to dequeue?

An Array already is a stack: append pushes and popLast() pops, both O(1).

struct Stack<Element> {  private var items: [Element] = []  mutating func push(_ x: Element) { items.append(x) }   // amortized O(1)  mutating func pop() -> Element? { items.popLast() }     // O(1), nil when empty  var top: Element? { items.last }  var isEmpty: Bool { items.isEmpty }…

04
Live task: check that a string of brackets like "([]{})" is balanced. Which structure do you use, and which inputs break a naive solution?
A stack: push every opening bracket, and on a closing one pop and check that it is the matching opener.
```
func isBalanced(_ s: String) -> Bool {  let openerFor: [Character: Character] = [")": "(", "]": "[", "}": "{"]  var stack: [Character] = []  for c in s {    if "([{".contains(c) {      stack.append(c)…
```

Live task: merge two sorted arrays into one sorted array in O(n + m) without calling `sorted()`. What are the edge cases?

Walk both arrays with two indices, append the smaller of the two current elements and advance that index; when one array runs out, append the rest of the other.

func merge<T: Comparable>(_ a: [T], _ b: [T]) -> [T] {  var result: [T] = []  result.reserveCapacity(a.count + b.count)     // one allocation  var i = 0, j = 0  while i < a.count && j < b.count {    if a[i] <= b[j] {                           // <= takes a's element first on a tie: stable…

Live task: write your own `map` and `reduce` as extensions on `Sequence`. What do generics and `rethrows` add to the signature?

Extend Sequence, loop with for-in and build the result.

extension Sequence {  func myMap<T>(_ transform: (Element) throws -> T) rethrows -> [T] {    var result: [T] = []    result.reserveCapacity(underestimatedCount)   // a lower bound, often 0: only a hint    for element in self {      result.append(try transform(element))…

07
How do Dictionary(grouping:by:), reduce(into:) and uniquingKeysWith: solve "group anagrams" and "count words", and why is plain reduce a trap here?
They replace the hand-written "look up, insert if missing, append" loop: Dictionary(grouping:by:) buckets elements by a key you compute, reduce(into:) folds into one dictionary that you mutate in place, and uniquingKeysWith: merges the values of repeated keys.
```
let words = ["eat", "tea", "tan", "ate", "nat", "bat"] // Group anagrams: the sorted letters are the shared keylet groups = Dictionary(grouping: words) { String($0.sorted()) }// ["aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]]…
```
08
Find the bug: this palindrome check returns the right answer, but takes seconds on a 100,000-character string.
```
func isPalindrome(_ s: String) -> Bool {  var left = 0  var right = s.count - 1  while left < right {    let l = s[s.index(s.startIndex, offsetBy: left)]    let r = s[s.index(s.startIndex, offsetBy: right)]    if l != r { return false }    left += 1    right -= 1  }  return true}
```
s.index(s.startIndex, offsetBy: k) walks the string from the start on every call, because a Character can span several bytes, so the loop is O(n²): billions of steps for 100,000 characters, about 9 seconds in a Release build on a Mac.
09
Which algorithm does Swift's sort() use, is it stable, and how do you sort users by score descending and then by name?
sort() is a modified timsort: O(n log n) in the worst case, near O(n) on mostly sorted input, and documented as stable, so equal elements keep their order.
```
import Foundation struct User {  let name: String  let score: Int}…
```

Live task: merge overlapping time slots like `[1, 3], [2, 6], [8, 10]`. Why sort first, and should touching slots such as `[1, 3]` and `[3, 5]` merge?

Sort the slots by start, then sweep once: if a slot starts before the last merged slot ends, extend that one to the later of the two ends, otherwise start a new slot.

func merge(_ slots: [ClosedRange<Int>]) -> [ClosedRange<Int>] {  let sorted = slots.sorted { $0.lowerBound < $1.lowerBound }   // O(n log n)  var result: [ClosedRange<Int>] = []  for slot in sorted {    if let last = result.last, slot.lowerBound <= last.upperBound {      // overlaps or touches the last merged slot: extend it, keeping the later end…

How do the two-pointer and sliding-window techniques turn an O(n²) scan into O(n)? Show it on the longest substring without repeating characters.

Both replace the nested loop with indices that only move forward.

// Two pointers on a sorted array: indices of a pair with the given sum, O(n)func pair(in sorted: [Int], sum target: Int) -> (Int, Int)? {  var l = 0, r = sorted.count - 1  while l < r {    let sum = sorted[l] + sorted[r]    if sum == target { return (l, r) }…

12
This binary search crashes on some inputs and never returns on others. What is wrong with it, and which loop invariant makes it correct?
```
func indexOf(_ target: Int, in a: [Int]) -> Int? {  var lo = 0  var hi = a.count  while lo <= hi {    let mid = (lo + hi) / 2    if a[mid] == target { return mid }    if a[mid] < target {      lo = mid    } else {      hi = mid - 1    }  }  return nil}
```
It mixes two conventions: hi = a.count is a half-open bound, but lo <= hi treats it as closed, so an empty array reads a[0] and traps; and when a[mid] is too small, lo = mid keeps mid in range, so once mid == lo nothing changes and the loop spins forever.
13
Live task: reverse a singly linked list in place. Follow-up: can freeing a million-node list overflow the stack in Swift, and what about a deep tree?
Walk the list once, saving node.next before pointing it back at prev: O(n) time, O(1) memory.
```
final class Node<T> {  var value: T  var next: Node?  init(_ value: T, next: Node? = nil) {    self.value = value    self.next = next…
```
14
How do you traverse a binary tree depth-first and breadth-first in Swift, and which one fits "max depth" and which "level order"?
Depth-first goes down one branch before backing up, through recursion or an explicit stack; breadth-first visits the tree level by level.
```
final class TreeNode {  let val: Int  var left: TreeNode?  var right: TreeNode?  init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {    self.val = val…
```
15
Live task: implement an LRU cache with O(1) get and put. Which two structures do you combine, and why is a Dictionary alone not enough?
A Dictionary from key to node finds an entry in O(1), and a doubly linked list keeps the nodes in order of use, so moving a node to the front and dropping the last one are O(1) pointer updates.
```
final class LRUCache<Key: Hashable, Value> {  private final class Node {    let key: Key?                       // nil only in the two sentinels    var value: Value?    var next: Node?    weak var prev: Node?                // weak: neighbours must not retain each other…
```

How do you recognise a dynamic programming problem, and how do you go from plain recursion to memoization to a bottom-up table in Swift?

It is DP when the answer is built from answers to smaller versions of the same problem, and a plain recursion would solve the same subproblem many times.

// House robber: the most money from houses 0...i without robbing two neighbours.// best(i) = max(best(i - 1), best(i - 2) + nums[i]): skip house i, or rob it // 1. Plain recursion: O(2^n), the same i is solved again and againfunc robNaive(_ nums: [Int], _ i: Int) -> Int {  if i < 0 { return 0 }…

17
Swift's standard library has no heap. How do you find the 100 most frequent words in a large text, and what does each approach cost?
Count the words into a dictionary in one O(n) pass, then pick the top k of the u distinct words: sort them all (O(u log u)), keep a min-heap of k entries (O(u log k)), or bucket them by count (O(n + u)).
```
typealias Entry = (word: Substring, count: Int) // A min-heap by count in a plain array: the children of i sit at 2i + 1 and 2i + 2func siftDown(_ heap: inout [Entry], from start: Int) {  var i = start  while true {…
```
18
Feature modules declare which modules they depend on. How do you compute a build order with a topological sort, and how does the same pass detect a cycle?
Treat the modules as a directed graph and run Kahn's algorithm: count each module's unbuilt dependencies, start with the modules at zero, and every time one is "built", decrement its dependents and add any that reach zero.
```
struct CycleError: Error { let stuck: [String] } /// deps[module] lists the modules that must be built before it.func buildOrder(_ deps: [String: [String]]) -> Result<[String], CycleError> {  var waitingOn: [String: Int] = [:]          // module -> dependencies not built yet  var dependents: [String: [String]] = [:]    // dependency -> modules waiting for it…
```

Live Coding Round in Swift

What is Big-O notation, and how do you state the time and space complexity of your solution in a coding round?

How does a `Set` or a `Dictionary` turn two-sum, duplicate detection or an anagram check from O(n²) into O(n) in Swift?

How do you implement a stack and a queue in Swift, and why is `Array.removeFirst()` a poor way to dequeue?

Live task: check that a string of brackets like `"([]{})"` is balanced. Which structure do you use, and which inputs break a naive solution?

Live task: merge two sorted arrays into one sorted array in O(n + m) without calling `sorted()`. What are the edge cases?

Live task: write your own `map` and `reduce` as extensions on `Sequence`. What do generics and `rethrows` add to the signature?

How do `Dictionary(grouping:by:)`, `reduce(into:)` and `uniquingKeysWith:` solve "group anagrams" and "count words", and why is plain `reduce` a trap here?

Find the bug: this palindrome check returns the right answer, but takes seconds on a 100,000-character string.

Which algorithm does Swift's `sort()` use, is it stable, and how do you sort users by score descending and then by name?

Live task: merge overlapping time slots like `[1, 3], [2, 6], [8, 10]`. Why sort first, and should touching slots such as `[1, 3]` and `[3, 5]` merge?

How do the two-pointer and sliding-window techniques turn an O(n²) scan into O(n)? Show it on the longest substring without repeating characters.

This binary search crashes on some inputs and never returns on others. What is wrong with it, and which loop invariant makes it correct?

Live task: reverse a singly linked list in place. Follow-up: can freeing a million-node list overflow the stack in Swift, and what about a deep tree?

How do you traverse a binary tree depth-first and breadth-first in Swift, and which one fits "max depth" and which "level order"?

Live task: implement an LRU cache with O(1) `get` and `put`. Which two structures do you combine, and why is a `Dictionary` alone not enough?

How do you recognise a dynamic programming problem, and how do you go from plain recursion to memoization to a bottom-up table in Swift?

Swift's standard library has no heap. How do you find the 100 most frequent words in a large text, and what does each approach cost?

Feature modules declare which modules they depend on. How do you compute a build order with a topological sort, and how does the same pass detect a cycle?

What is Big-O notation, and how do you state the time and space complexity of your solution in a coding round?

How does a Set or a Dictionary turn two-sum, duplicate detection or an anagram check from O(n²) into O(n) in Swift?

How do you implement a stack and a queue in Swift, and why is Array.removeFirst() a poor way to dequeue?

Live task: check that a string of brackets like "([]{})" is balanced. Which structure do you use, and which inputs break a naive solution?

Live task: merge two sorted arrays into one sorted array in O(n + m) without calling sorted(). What are the edge cases?

Live task: write your own map and reduce as extensions on Sequence. What do generics and rethrows add to the signature?

How do Dictionary(grouping:by:), reduce(into:) and uniquingKeysWith: solve "group anagrams" and "count words", and why is plain reduce a trap here?

Find the bug: this palindrome check returns the right answer, but takes seconds on a 100,000-character string.

Which algorithm does Swift's sort() use, is it stable, and how do you sort users by score descending and then by name?

Live task: merge overlapping time slots like [1, 3], [2, 6], [8, 10]. Why sort first, and should touching slots such as [1, 3] and [3, 5] merge?

How do the two-pointer and sliding-window techniques turn an O(n²) scan into O(n)? Show it on the longest substring without repeating characters.

This binary search crashes on some inputs and never returns on others. What is wrong with it, and which loop invariant makes it correct?

Live task: reverse a singly linked list in place. Follow-up: can freeing a million-node list overflow the stack in Swift, and what about a deep tree?

How do you traverse a binary tree depth-first and breadth-first in Swift, and which one fits "max depth" and which "level order"?

Live task: implement an LRU cache with O(1) get and put. Which two structures do you combine, and why is a Dictionary alone not enough?

How do you recognise a dynamic programming problem, and how do you go from plain recursion to memoization to a bottom-up table in Swift?

Swift's standard library has no heap. How do you find the 100 most frequent words in a large text, and what does each approach cost?

Feature modules declare which modules they depend on. How do you compute a build order with a topological sort, and how does the same pass detect a cycle?

How does a `Set` or a `Dictionary` turn two-sum, duplicate detection or an anagram check from O(n²) into O(n) in Swift?

How do you implement a stack and a queue in Swift, and why is `Array.removeFirst()` a poor way to dequeue?

Live task: check that a string of brackets like `"([]{})"` is balanced. Which structure do you use, and which inputs break a naive solution?

Live task: merge two sorted arrays into one sorted array in O(n + m) without calling `sorted()`. What are the edge cases?

Live task: write your own `map` and `reduce` as extensions on `Sequence`. What do generics and `rethrows` add to the signature?

How do `Dictionary(grouping:by:)`, `reduce(into:)` and `uniquingKeysWith:` solve "group anagrams" and "count words", and why is plain `reduce` a trap here?

Which algorithm does Swift's `sort()` use, is it stable, and how do you sort users by score descending and then by name?

Live task: merge overlapping time slots like `[1, 3], [2, 6], [8, 10]`. Why sort first, and should touching slots such as `[1, 3]` and `[3, 5]` merge?

Live task: implement an LRU cache with O(1) `get` and `put`. Which two structures do you combine, and why is a `Dictionary` alone not enough?