Free Handbook · Every example compiled & verified

Problem Solving

A repeatable way to crack coding problems in Scala: read it, break it down, test small cases, then apply one of eight patterns that cover most interviews.

0 / 142 lessons🔥 0 day streak

ShareX LinkedIn

Module 14 · what you'll be able to do

Turn a problem statement into inputs, outputs, constraints and edge cases before writing any code
Test a solution with a tiny hand-rolled check function instead of guessing
Estimate the Big-O a problem needs from its input limits, in plain English
Recognise and apply eight patterns in Scala: two pointers, sliding window, Map lookups, stack, backtracking, sorting, BFS/DFS and DP-lite
Choose between an idiomatic functional solution and a local mutable loop, and say why

Read the problem before touching the keyboard

Most failed coding rounds fail in the first two minutes: the candidate starts typing a solution to a problem they have not fully read. Slow down and write these five things down (in a comment, on the whiteboard, or out loud) before any code.

1
Restate it
One sentence, in your own words. "Given a list of prices, return the biggest profit from one buy followed by one later sell."
2
Inputs and outputs, with types
prices: Seq[Int] in, Int out. Can the sequence be empty? What is returned then? Should "no answer" be an Option?
3
Constraints
How big is n? Can values be negative? Duplicates? Already sorted? These decide the algorithm (see the Big-O lesson below).
4
Two examples by hand
One normal, one tricky. Work them out on paper. If you cannot do it by hand, you cannot code it.
5
Edge cases
Empty input, one element, all equal, already sorted, values big enough to overflow Int (Scala wraps silently, like Java; use Long or BigInt, see Module 01).

scalaMain.scala

// Restated: best profit from one buy then one later sell; 0 if prices only fall.
// Input: prices (may be empty). Output: Int >= 0.
def maxProfit(prices: Seq[Int]): Int =
  prices.foldLeft((Int.MaxValue, 0)) { case ((lowest, best), price) =>
    (lowest min price, best max (price - (lowest min price)))
  }._2

@main def run(): Unit =
  println(maxProfit(Seq(7, 1, 5, 3, 6, 4))) // normal: buy at 1, sell at 6
  println(maxProfit(Seq(7, 6, 4, 3, 1)))    // prices only fall
  println(maxProfit(Seq.empty))             // empty
  println(maxProfit(Seq(5)))                // one day

Outputcompiled & run with real Scala

The fold carries two values, the cheapest buy so far and the best profit so far, in a tuple. The four calls are the examples and edge cases from the reading step, written before the function body, not bolted on after.

Your turn

Change the contract to "return Option[(Int, Int)]: the buy day and sell day, or None if no profit is possible". Which of the four calls now needs a different expected answer?

Break it down and test with small cases

Break the problem into pieces you can test separately: a helper that checks one thing, a loop that applies it. Then test with the smallest inputs that could break it. In an interview, and in your own practice, a tiny check function is faster than setting up MUnit, and it shows the interviewer you verify your own code.

scalaMain.scala

def isPalindrome(s: String): Boolean =
  val clean = s.filter(_.isLetterOrDigit).map(_.toLower)
  clean == clean.reverse

@main def run(): Unit =
  val cases = List(
    "" -> true,                             // empty
    "a" -> true,                            // one character
    "ab" -> false,                          // smallest false case
    "Aba" -> true,                          // mixed case
    "A man, a plan, a canal: Panama" -> true,
    "race a car" -> false,
    ".," -> true,                           // only punctuation
  )
  val failures = cases.filterNot((input, expected) => isPalindrome(input) == expected)
  failures.foreach((input, expected) => println(s"FAIL '$input': expected $expected"))
  println(s"${cases.size - failures.size} passed, ${failures.size} failed")

Outputcompiled & run with real Scala

7 passed, 0 failed

The test cases are data: a list of input and expected-output pairs. Adding a case is one line, and the pure function under test needs no setup at all.

Your turn

Break isPalindrome on purpose (drop the .map(_.toLower)) and run it. Exactly two cases report FAIL. That is how a good small-case list pinpoints a bug.

The order to test in

Empty, one element, two elements, the example from the problem, then one case aimed at each branch of your code. Small inputs make a wrong answer obvious by eye.

Big-O in plain English

Big-O answers one question: if the input gets ten times bigger, how much slower does this get? O(n) gets ten times slower. O(n²) gets a hundred times slower. O(log n) barely notices. Scala on the JVM does very roughly 10⁸ simple operations per second once the JIT has warmed up, which turns the constraints in a problem statement into a direct hint about which algorithm is expected.

Rules of thumb, not laws. They are good enough to rule out the wrong approach before you write it.
If n is up to…	You can afford	Typical approach
10 to 20	O(2ⁿ) or O(n!)	Backtracking: try every subset or ordering
~500	O(n³)	Three nested loops, small DP tables
~5,000	O(n²)	Two nested loops, 2-D DP
~10⁶	O(n log n)	Sort first, a heap, binary search inside a loop
~10⁸	O(n)	One pass: two pointers, sliding window, Map lookups
Anything larger	O(log n) or O(1)	Binary search on the answer, a formula

scalaMain.scala

// O(n^2): compare every pair
def nestedOps(a: IndexedSeq[Int]): Long =
  var ops = 0L
  var i = 0
  while i < a.length do
    var j = i + 1
    while j < a.length do
      ops += 1
      if a(i) == a(j) then return ops
      j += 1
    i += 1
  ops

// O(n): remember what we have seen
def setOps(a: IndexedSeq[Int]): Long =
  val seen = scala.collection.mutable.HashSet.empty[Int]
  var ops = 0L
  for x <- a do
    ops += 1
    if !seen.add(x) then return ops
  ops

@main def run(): Unit =
  for n <- List(1_000, 10_000) do
    val a = Vector.range(0, n) // no duplicates: the worst case
    println(s"n=$n  nested=${nestedOps(a)}  set=${setOps(a)}")

Outputcompiled & run with real Scala

n=1000  nested=499500  set=1000
n=10000  nested=49995000  set=10000

Ten times the input: the nested version does a hundred times the work, the set version ten times. (The functional one-liner a.distinct.size != a.size is also O(n).)

Your turn

Add a third function that sorts a copy and compares neighbours with sliding(2). What is its Big-O, including the sort?

Pattern 1: two pointers

Signal: a sorted array (or a string) and a question about pairs, or "do it in place". Put one index at each end and move them towards each other based on a comparison. Each step rules out a whole row of candidate pairs, so an O(n²) "try every pair" becomes O(n) with O(1) extra memory. In Scala it reads well as a tail-recursive loop over the two indexes.

scalaMain.scala

import scala.annotation.tailrec

// sorted input: indices of two numbers that add up to target
def pairSum(a: IndexedSeq[Int], target: Int): Option[(Int, Int)] =
  @tailrec def loop(i: Int, j: Int): Option[(Int, Int)] =
    if i >= j then None
    else
      val sum = a(i) + a(j)
      if sum == target then Some((i, j))
      else if sum < target then loop(i + 1, j) // need bigger: move left pointer up
      else loop(i, j - 1)                      // need smaller: move right pointer down
  loop(0, a.length - 1)

@main def run(): Unit =
  val a = Vector(1, 3, 4, 6, 8, 11)
  println(pairSum(a, 10))
  println(pairSum(a, 2))

Outputcompiled & run with real Scala

Some((2,3))
None

Your turn

Write sortedSquares(a: Vector[Int]): Vector[Int] for a sorted vector that may hold negatives: Vector(-4, -1, 0, 3, 10) gives Vector(0, 1, 9, 16, 100). Walk inwards from both ends, each time taking the larger absolute value, and prepend to the result.

VisualizepairSum(Vector(1, 3, 4, 6, 8, 11), 10)Step 1 / 7

1@tailrec def loop(i: Int, j: Int): Option[(Int, Int)] =
2  if i >= j then None
3  else
4    val sum = a(i) + a(j)
5    if sum == target then Some((i, j))
6    else if sum < target then loop(i + 1, j)
7    else loop(i, j - 1)

Line 1

Pointers at both ends.

Variables now

`i`	`0`
`j`	`5`

All 7 steps as a table

Step	Line	What happened	Variables now
1	1	Pointers at both ends.	`i = 0` `j = 5`
2	4	1 + 11 = 12, too big.	`sum = 12`
3	7	Nothing can pair with 11 any more (1 is the smallest partner), so drop it.	`j = 4`
4	4	1 + 8 = 9, too small.	`sum = 9`
5	6	Nothing can pair with 1 (8 is now the largest partner), so drop it.	`i = 1`
6	4	3 + 8 = 11, too big: drop 8. Then 3 + 6 = 9, too small: drop 3.	`i = 2` `j = 3`
7	5	4 + 6 = 10: found, after 5 checks instead of up to 15 pairs.

Pattern 2: sliding window

Signal: "longest / shortest / best contiguous subarray or substring such that…". Grow a window by moving its right edge; when the window breaks the rule, shrink it from the left. Each index enters and leaves the window at most once, so the whole scan is O(n). A fixed-size window is even simpler, and sliding(k) expresses it directly (at O(n·k)); the running-sum version below is O(n).

scalaMain.scala

// length of the longest substring with no repeated character
def longestUnique(s: String): Int =
  s.indices.foldLeft((0, 0, Map.empty[Char, Int])) { case ((best, left, lastSeen), right) =>
    val c = s(right)
    val newLeft = lastSeen.get(c).filter(_ >= left).map(_ + 1).getOrElse(left)
    (best max (right - newLeft + 1), newLeft, lastSeen.updated(c, right))
  }._1

// fixed-size window: biggest sum of any k consecutive numbers
def maxSumK(a: IndexedSeq[Int], k: Int): Int =
  val first = a.take(k).sum
  (k until a.length).foldLeft((first, first)) { case ((sum, best), i) =>
    val next = sum + a(i) - a(i - k) // slide: add the new, drop the old
    (next, best max next)
  }._2

@main def run(): Unit =
  println(s"${longestUnique("abcabcbb")} ${longestUnique("bbbb")} ${longestUnique("pwwkew")}")
  println(maxSumK(Vector(2, 1, 5, 1, 3, 2), 3))
  println(Vector(2, 1, 5, 1, 3, 2).sliding(3).map(_.sum).max)

Outputcompiled & run with real Scala

3 1 3
9
9

The filter(_ >= left) matters: a character last seen before the window started is not a repeat inside it. The last line is the readable O(n·k) version, fine when k is small.

Your turn

Write minLengthAtLeast(a: Vector[Int], target: Int): Int: the shortest contiguous run of positive numbers whose sum is at least target (0 if none). Vector(2, 3, 1, 2, 4, 3) with target 7 gives 2.

Pattern 3: Map and Set lookups

Signal: "find two that…", "count how many…", "group by…", "first duplicate". Trade memory for time: remember what you have seen in a Map keyed by the thing you will look up later. groupBy, groupMapReduce and foldLeft over a Map make most of these one-liners.

scalaMain.scala

import scala.annotation.tailrec

// unsorted input: indices of two numbers that add up to target
def twoSum(nums: Vector[Int], target: Int): Option[(Int, Int)] =
  @tailrec def loop(i: Int, indexOf: Map[Int, Int]): Option[(Int, Int)] =
    if i == nums.length then None
    else indexOf.get(target - nums(i)) match
      case Some(j) => Some((j, i))
      case None => loop(i + 1, indexOf.updated(nums(i), i))
  loop(0, Map.empty)

// group words that are anagrams of each other, in first-seen order
def groupAnagrams(words: List[String]): List[List[String]] =
  val groups = words.groupBy(_.sorted)
  words.map(_.sorted).distinct.map(groups)

@main def run(): Unit =
  println(twoSum(Vector(2, 7, 11, 15), 9))
  println(twoSum(Vector(3, 2, 4), 6))
  groupAnagrams(List("eat", "tea", "tan", "ate", "nat", "bat")).foreach(g => println(g.mkString(",")))

Outputcompiled & run with real Scala

Some((0,1))
Some((1,2))
eat,tea,ate
tan,nat
bat

groupBy returns a hash Map whose iteration order is not guaranteed, so the result is re-ordered by first appearance. A Map is also a function from key to value, which is why .map(groups) works.

Your turn

Write firstUniqueChar(s: String): Int: the index of the first character that appears exactly once, or -1. Count with groupMapReduce, then indexWhere. "leetcode" gives 0, "aabb" gives -1.

Pattern 4: stack

Signal: nesting (brackets, tags, paths), "undo", or "the next greater / smaller element". A monotonic stack keeps indexes whose values are still waiting for an answer; each new value pops every waiting index it answers. Every index is pushed and popped once: O(n). An immutable List is a perfect stack.

scalaMain.scala

// for each day, how many days until a warmer temperature (0 if never)
def daysUntilWarmer(temps: Vector[Int]): Vector[Int] =
  val answer = Array.fill(temps.length)(0)
  temps.indices.foldLeft(List.empty[Int]) { (waiting, i) =>
    val (answered, still) = waiting.span(j => temps(j) < temps(i))
    answered.foreach(j => answer(j) = i - j)
    i :: still
  }
  answer.toVector

// simplify a Unix path: /a/./b/../../c/ -> /c
def simplifyPath(path: String): String =
  val stack = path.split("/").foldLeft(List.empty[String]) {
    case (st, "" | ".") => st
    case (st, "..") => st.drop(1)
    case (st, part) => part :: st
  }
  "/" + stack.reverse.mkString("/")

@main def run(): Unit =
  println(daysUntilWarmer(Vector(73, 74, 75, 71, 69, 72, 76, 73)).mkString(" "))
  println(simplifyPath("/a/./b/../../c/"))
  println(simplifyPath("/../"))

Outputcompiled & run with real Scala

1 1 4 2 1 1 0 0
/c
/

The waiting list is kept with the most recent index on top, and temperatures on it never increase from top to bottom, so span pops exactly the days the new temperature answers.

Your turn

Evaluate Reverse Polish Notation: evalRpn(List("2", "1", "+", "3", "*")) is 9. Fold over the tokens with a List[Int] stack, and pattern match b :: a :: rest on an operator.

Pattern 5: recursion and backtracking

Signal: "all combinations", "all permutations", "every way to…", and small n (under about 20). Build a candidate one choice at a time and recurse. With immutable lists there is no explicit "undo" step: each recursive call gets its own extended list, and the caller's list is untouched.

scalaMain.scala

def subsets[A](items: List[A]): List[List[A]] = items match
  case Nil => List(Nil)
  case head :: tail =>
    val rest = subsets(tail)
    rest.map(head :: _) ++ rest

def permutations[A](items: List[A]): List[List[A]] = items match
  case Nil => List(Nil)
  case _ =>
    for
      x <- items
      p <- permutations(items.filterNot(_ == x))
    yield x :: p

def combinationSum(candidates: List[Int], target: Int): List[List[Int]] = candidates match
  case _ if target == 0 => List(Nil)
  case Nil => Nil
  case c :: rest if c > target => combinationSum(rest, target)
  case c :: rest => combinationSum(candidates, target - c).map(c :: _) ++ combinationSum(rest, target)

@main def run(): Unit =
  println(subsets(List("a", "b", "c")).map(_.mkString("[", ",", "]")).mkString(" "))
  println(permutations(List(1, 2, 3)).map(_.mkString).mkString(" "))
  println(combinationSum(List(2, 3, 6, 7), 7))

Outputcompiled & run with real Scala

[a,b,c] [a,b] [a,c] [a] [b,c] [b] [c] []
123 132 213 231 312 321
List(List(2, 2, 3), List(7))

Each function is its recursive definition written down: the subsets of head :: tail are the subsets of tail, with and without head. (The library also has items.permutations and items.combinations(k).)

Your turn

Write nQueens(n: Int): Int, the number of ways to place n queens on an n×n board so none attack each other. Place one queen per row, recursing with the list of columns used so far. nQueens(6) is 4 and nQueens(8) is 92.

Pattern 6: sort first

Signal: intervals, "closest", "meeting rooms", "can these be scheduled", or any problem that gets easy once things are in order. Paying O(n log n) for sortBy often turns the rest into a single O(n) fold.

scalaMain.scala

def mergeIntervals(intervals: List[(Int, Int)]): List[(Int, Int)] =
  intervals.sortBy(_._1).foldLeft(List.empty[(Int, Int)]) {
    case ((lastStart, lastEnd) :: done, (start, end)) if start <= lastEnd =>
      (lastStart, lastEnd max end) :: done   // overlap: extend the last interval
    case (done, interval) =>
      interval :: done                       // gap: start a new interval
  }.reverse

@main def run(): Unit =
  println(mergeIntervals(List((8, 10), (1, 3), (2, 6), (15, 18), (17, 20))))
  println(mergeIntervals(List((1, 4), (4, 5))))

Outputcompiled & run with real Scala

List((1,6), (8,10), (15,20))
List((1,5))

The fold builds the result backwards so that "the last interval" is always the head of the list, a cheap O(1) pattern match. One reverse at the end restores the order.

Your turn

Meeting rooms: given meetings as (start, end), return the fewest rooms needed. Sort the starts and the ends separately, then walk both with two pointers.

Pattern 7: BFS and DFS on a grid

Signal: a grid or map ("islands", "rooms", "shortest path in a maze"), or anything described as connections. Treat each cell as a node with up to four neighbours. DFS answers "which cells connect?"; BFS answers "how many steps at minimum?".

scalaMain.scala

import scala.annotation.tailrec
import scala.collection.immutable.Queue

type Cell = (Int, Int)
val dirs = List((1, 0), (-1, 0), (0, 1), (0, -1))

def neighbours(grid: Vector[String], cell: Cell, open: Char): List[Cell] =
  val (r, c) = cell
  for
    (dr, dc) <- dirs
    (nr, nc) = (r + dr, c + dc)
    if nr >= 0 && nc >= 0 && nr < grid.length && nc < grid(0).length && grid(nr)(nc) == open
  yield (nr, nc)

def countIslands(grid: Vector[String]): Int =
  def sink(start: Cell, seen: Set[Cell]): Set[Cell] =
    neighbours(grid, start, '#').foldLeft(seen + start) { (s, n) =>
      if s(n) then s else sink(n, s)
    }
  val land = for r <- grid.indices; c <- grid(r).indices if grid(r)(c) == '#' yield (r, c)
  land.foldLeft((0, Set.empty[Cell])) { case ((islands, seen), cell) =>
    if seen(cell) then (islands, seen) else (islands + 1, sink(cell, seen))
  }._1

def shortestSteps(maze: Vector[String]): Int =
  val goal = (maze.length - 1, maze(0).length - 1)
  @tailrec def loop(queue: Queue[(Cell, Int)], seen: Set[Cell]): Int =
    queue.dequeueOption match
      case None => -1
      case Some(((cell, d), _)) if cell == goal => d
      case Some(((cell, d), rest)) =>
        val next = neighbours(maze, cell, '.').filterNot(seen)
        loop(rest.enqueueAll(next.map(_ -> (d + 1))), seen ++ next)
  loop(Queue(((0, 0), 0)), Set((0, 0)))

@main def run(): Unit =
  println(countIslands(Vector("##..#", "#...#", "..#..", ".....", "##.##")))
  println(shortestSteps(Vector("..#.", "#...", "..#.", ".#..")))

Outputcompiled & run with real Scala

5
6

A Set is also a function from element to Boolean, so seen(cell) asks "have we been here?" and filterNot(seen) drops visited cells.

Your turn

Change countIslands to return the size of the biggest island instead: compare the size of the seen set before and after each sink.

Pattern 8: DP-lite

Signal: "how many ways", "minimum cost", "maximum value", where the answer for n depends on the answers for smaller n. Write the one-sentence meaning of dp(i), the base case, and the step from smaller answers. Often you only need the last one or two values, which is a foldLeft over a tuple.

scalaMain.scala

// ways to climb n stairs taking 1 or 2 steps: ways(n) = ways(n-1) + ways(n-2)
def climbStairs(n: Int): Long =
  (2 to n).foldLeft((1L, 1L)) { case ((a, b), _) => (b, a + b) }._2

// house robber: max sum with no two adjacent houses
def rob(houses: List[Int]): Int =
  val (take, skip) = houses.foldLeft((0, 0)) { case ((take, skip), h) =>
    (skip + h, take max skip)
  }
  take max skip

// unique paths moving only right or down through a rows x cols grid
def uniquePaths(rows: Int, cols: Int): Long =
  (1 until rows).foldLeft(Vector.fill(cols)(1L)) { (above, _) =>
    above.tail.scanLeft(1L)(_ + _)
  }.last

@main def run(): Unit =
  println(s"${climbStairs(5)} ${climbStairs(10)}")
  println(s"${rob(List(2, 7, 9, 3, 1))} ${rob(List(2, 1, 1, 2))}")
  println(uniquePaths(3, 7))

Outputcompiled & run with real Scala

8 89
12 4
28

scanLeft is a fold that keeps every intermediate result, which is exactly "each cell is the cell above plus the cell to the left" for one row of the grid.

Your turn

Write longestIncreasing(xs: Vector[Int]): Int, the length of the longest strictly increasing subsequence, with dp(i) = the longest one ending at i. Vector(10, 9, 2, 5, 3, 7, 101, 18) gives 4.

Choosing the pattern

The problem says…	Try	Typical cost
sorted array, pairs, "in place"	Two pointers	O(n)
contiguous subarray / substring, "longest", "at most k"	Sliding window	O(n)
"find two", "count", "group", "seen before"	Map / Set lookups	O(n)
nesting, "next greater", undo	Stack (a List)	O(n)
"all combinations / permutations", n ≤ 20	Backtracking	O(2ⁿ) or O(n!)
intervals, schedules, "closest"	Sort first	O(n log n)
grid, maze, connections, "minimum steps"	BFS / DFS	O(rows × cols)
"how many ways", "min cost", "max value"	DP	O(n) to O(n²)

Functional or imperative in the interview?

Scala interviewers usually like to see idiomatic code: folds, pattern matching, immutable collections, Option for "no answer". But a clear while loop over an Array inside one function is perfectly acceptable Scala, and sometimes the honest choice for performance. Say which you chose and why. Whatever you write, name the pattern and its cost out loud before coding it.

Two pointers: Two indexes moving towards each other (or in the same direction) to avoid checking every pair.
Sliding window: A contiguous range grown from the right and shrunk from the left, so each element is visited at most twice.
Monotonic stack: A stack kept in increasing or decreasing order, used for "next greater / smaller element" questions.
Backtracking: Building candidates one choice at a time and recursing; with immutable lists the "undo" is automatic.
DP state: The one-sentence meaning of dp(i): what sub-problem each table cell answers.

Quick check

The problem: "Given up to 100,000 integers, return the length of the longest contiguous subarray whose sum is at most k." All numbers are positive. Which approach fits?

← Module 13Data Structures & Algorithms Module 15 →Interview Questions

Frequently asked questions

Can I use Scala for coding interviews?

Yes. LeetCode, HackerRank and CoderPad support Scala, and Scala-focused teams prefer it. Its collections make many problems short (groupBy, foldLeft, sliding, sortBy), and pattern matching makes recursive solutions read like their definitions. Know the costs: List append and indexing are O(n), so use Vector or Array when you need them.

Should I write functional or imperative code in a Scala interview?

Prefer idiomatic functional code, immutable collections, folds, pattern matching and Option, because that is what Scala teams write. But a local mutable loop over an Array is acceptable when it is clearer or faster; say why you chose it. Correctness, a stated complexity and tested edge cases matter more than style.

What are the most common coding interview patterns?

Eight patterns cover most problems: two pointers, sliding window, hash map lookups, stack, recursion and backtracking, sorting first, BFS and DFS, and simple dynamic programming. Recognising the signal words for each one matters more than memorising individual problems.

Finish the Scala handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.