Scala engineer coding interview questions

As asked

Implement a binary search function in Scala that takes a sorted IndexedSeq[Int] and a target Int and returns an Option[Int] with the index. Write it tail-recursively and explain why tail recursion matters on the JVM.

Sample answer outline

The candidate should write a @tailrec inner helper with lo and hi parameters, computing mid = lo + (hi - lo) / 2 to avoid overflow. If arr(mid) == target return Some(mid); if target < arr(mid) search left; else search right. Return None when lo > hi. Tail recursion matters because the JVM does not optimize general recursion; @tailrec tells the compiler to verify it can be converted to a loop, avoiding StackOverflowError.

Reference implementation (scala)

def binarySearch(arr: IndexedSeq[Int], target: Int): Option[Int] = {
  @annotation.tailrec
  def loop(lo: Int, hi: Int): Option[Int] = ???
  loop(0, arr.length - 1)
}

Expect these follow-ups

• What does the @tailrec annotation do at compile time?
• How would you generalize this to work on any Ordered type?

As asked

Write a Spark job in Scala using the Dataset API that reads a text file, splits each line by whitespace, counts word frequencies, and writes the top 10 most common words to Parquet. Explain where shuffles happen.

Sample answer outline

Read with spark.read.text, flatMap to split lines, use groupBy+count or countByValue, sort descending, take top 10, write to Parquet. The shuffle happens at the groupBy/count boundary. A strong candidate avoids collect before writing (which defeats the purpose of distributed processing) and uses ds.write.parquet instead. They also note that sorting for top-10 triggers another shuffle unless they use a take after sorting on the driver.

Reference implementation (scala)

import org.apache.spark.sql.SparkSession

object WordCount {
  def run(spark: SparkSession, inputPath: String, outputPath: String): Unit = {
    import spark.implicits._
    // Read, split, count, top-10, write
    ???
  }
}

Expect these follow-ups

• How would you avoid collecting all results to the driver before writing the top 10?
• How does this job scale if the input file is 10 TB?

As asked

Write a generic sum function in Scala that sums any collection of elements that have a Monoid instance, using either Cats or a hand-rolled Monoid type class. Demonstrate it with Int, String, and a custom type.

Sample answer outline

Define trait Monoid[A] { def empty: A; def combine(a: A, b: A): A }. Provide implicit instances for Int (sum) and String (concatenation). Write def sum[A](xs: List[A])(implicit m: Monoid[A]): A = xs.foldLeft(m.empty)(m.combine). The candidate should use context bound syntax [A: Monoid] and Monoid[A].empty. Bonus: show the Scala 3 using clause version. The custom type example shows they understand deriving instances.

Reference implementation (scala)

trait Monoid[A] {
  def empty: A
  def combine(a: A, b: A): A
}

def sum[A: Monoid](xs: List[A]): A = ???

// Instances
implicit val intMonoid: Monoid[Int] = ???
implicit val stringMonoid: Monoid[String] = ???

Expect these follow-ups

• What is the difference between Monoid and Semigroup in Cats?
• How would you derive a Monoid instance for a case class Product with two Monoid fields?

As asked

You are reviewing Scala code that processes millions of records with chained collection operations. What performance issues do you look for?

Sample answer outline

The candidate should look for accidental intermediate collections, strict versus lazy evaluation, poor choice of List for indexed access, and repeated groupBy or sortBy on large datasets. Iterator or View can avoid intermediate allocation, but they also move work later and can surprise readers if reused incorrectly. Vector is often a better general-purpose immutable sequence than List when indexed access or appends matter. For distributed data, the answer should separate local collection costs from Spark or Akka stream costs. Strong answers avoid premature optimisation but know where idiomatic code becomes expensive.

Reference implementation (scala)

val totalsByUser: Map[String, BigDecimal] =
  events.iterator
    .filter(_.status == "paid")
    .map(event => event.userId -> event.amount)
    .foldLeft(Map.empty[String, BigDecimal]) { case (acc, (userId, amount)) =>
      acc.updated(userId, acc.getOrElse(userId, BigDecimal(0)) + amount)
    }

Expect these follow-ups

• When is List the wrong default?
• How do View and Iterator differ?
• How would you prove a collection change actually helped?

As asked

Implement a traverse function in Scala that takes a List[A] and a function A => Option[B] and returns an Option[List[B]], short-circuiting on None. Then generalize it to work with any Applicative effect F[_] from Cats.

Sample answer outline

The Option-specific version uses foldRight with a combining function, short-circuiting when the function returns None because Option is a monad and flatMap returns None immediately on the first failure. The generic Applicative version replaces Option with F[_]: Applicative and uses Applicative.pure for the empty list case and mapN or ap to combine. Important distinction: the generic Applicative version does not short-circuit on failure because Applicative has no flatMap; all effects are combined. If short-circuiting is needed in the generic version, the constraint must be upgraded to Monad. This shows understanding of why traverse is the generalisation of sequence and map. The candidate should also mention that Cats provides traverse for all Traverse instances and that parTraverse replaces Applicative with a parallel version.

Reference implementation (scala)

// Specific version
def traverse[A, B](list: List[A])(f: A => Option[B]): Option[List[B]] = ???

// Generic version using Cats
import cats.Applicative
def traverseG[F[_]: Applicative, A, B](list: List[A])(f: A => F[B]): F[List[B]] = ???

Expect these follow-ups

• What is the difference between traverse and sequence in Cats?
• How does parTraverse differ from traverse and when would you use it?

As asked

Implement a thread-safe fixed-capacity LRU cache in Scala with O(1) get and put. Explain your concurrency strategy and how you would make this functional using ZIO Ref or Cats Effect Ref.

Sample answer outline

Core data structure is a LinkedHashMap with access-order mode (or a doubly-linked list plus HashMap). Thread safety with java.util.concurrent or wrapping the whole thing in a Ref[F, State] where State is immutable. The functional approach wraps all mutations in Ref.modify so they are atomic. A strong candidate knows that LinkedHashMap.removeEldestEntry gives the eviction hook. They also discuss the trade-off between wrapping a mutable structure in a Ref versus a fully immutable implementation.

Reference implementation (scala)

// Functional skeleton using Cats Effect
import cats.effect.Ref
case class CacheState[K, V](map: Map[K, V], order: List[K])

class LRUCache[F[_], K, V](capacity: Int, state: Ref[F, CacheState[K, V]]) {
  def get(key: K): F[Option[V]] = ???
  def put(key: K, value: V): F[Unit] = ???
}

Expect these follow-ups

• What is the time complexity of your eviction strategy?
• How would you extend this cache to expire entries after a TTL using Cats Effect or ZIO?

As asked

Using ZIO's Schedule API, implement a retry policy that retries up to 5 times with exponential backoff starting at 100ms and capped at 30 seconds, and only retries on specific error types.

Sample answer outline

Use Schedule.recurs(5) combined with Schedule.exponential(100.millis) and capped with andThen(Schedule.stop) or .upTo. Filter on error type using Schedule.recurWhile or retryWhile. The candidate should show how to compose schedules with && and + operators and know that Schedule.exponential doubles the delay each retry. Bonus for adding jitter with Schedule.jittered to avoid thundering herd.

Reference implementation (scala)

import zio._
import zio.Schedule

val retryPolicy: Schedule[Any, Throwable, Long] = ???

def callWithRetry(effect: ZIO[Any, Throwable, String]): ZIO[Any, Throwable, String] =
  effect.retry(retryPolicy)

Expect these follow-ups

• What is the difference between ZIO retry and ZIO repeat?
• How would you add jitter to prevent multiple services from retrying simultaneously?

As asked

Using Akka Streams, implement a flow that rate-limits a Source[Message, _] to at most 100 messages per second without dropping messages. Show the code and explain the buffering behaviour.

Sample answer outline

Use Flow[Message].throttle(100, 1.second, 100, ThrottleMode.Shaping). ThrottleMode.Shaping delays elements to achieve the rate; ThrottleMode.Enforcing drops or fails. The third parameter is the burst size (leaky bucket). A strong candidate explains that the upstream is backpressured rather than messages being dropped in Shaping mode, and that the buffer fills up to the burst size before backpressure kicks in. Also mention conflate as an alternative when you want to drop and merge.

Reference implementation (scala)

import akka.stream.scaladsl._
import akka.stream.ThrottleMode
import scala.concurrent.duration._

case class Message(id: Int)

val rateLimited: Flow[Message, Message, _] =
  Flow[Message].throttle(100, 1.second, 100, ThrottleMode.Shaping)

Expect these follow-ups

• What is the difference between ThrottleMode.Shaping and ThrottleMode.Enforcing?
• How would you implement per-user rate limiting where different users have different quotas?

As asked

Given a sealed binary tree ADT in Scala, implement a fold function that reduces the tree to a single value, then use it to implement sum and depth without writing recursive functions for each.

Sample answer outline

Define sealed trait Tree[A]; case class Leaf[A](value: A); case class Branch[A](left: Tree[A], right: Tree[A]). fold takes an initial value for Leaf and a combining function for Branch. sum = fold(identity)(_ + _). depth = fold(_ => 1)((l, r) => 1 + math.max(l, r)). Strong candidates note that this fold is catamorphism and that all structural recursion over an ADT can be expressed as a fold, separating the traversal from the computation.

Reference implementation (scala)

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

def fold[A, B](tree: Tree[A])(leaf: A => B)(branch: (B, B) => B): B = ???

def sum(tree: Tree[Int]): Int = ???
def depth[A](tree: Tree[A]): Int = ???

Expect these follow-ups

• How would you make the fold stack-safe for very deep trees?
• What is a catamorphism and how does it relate to recursion schemes?

As asked

Given k sorted Source[Int, _] in Akka Streams (or Stream[IO, Int] in fs2), implement a function that merges them into a single sorted stream in O(n log k) time where n is the total number of elements.

Sample answer outline

Use a min-heap (priority queue) of size k. Pull the first element from each stream and add to the heap. On each step, pop the minimum and emit it, then pull the next element from that stream. In Akka Streams, this requires a custom GraphStage because there is no built-in sorted merge junction. MergeLatest is for non-ordered merging of the most recent values from concurrent sources and is not suitable here. In fs2, pull-based composition works naturally with a priority queue. The candidate should recognize this is the standard k-way merge problem and explain the O(n log k) complexity of heap operations.

Reference implementation (scala)

import akka.stream.scaladsl._
import scala.collection.mutable

// Merge k sorted sources into one sorted source
def mergeSorted(sources: List[Source[Int, _]]): Source[Int, _] = {
  // Implement using a priority queue or Akka's MergeLatest
  ???
}

Expect these follow-ups

• How would you implement a custom GraphStage in Akka Streams that pulls from exactly two sorted sources and emits the smaller element each time?
• How do you test a streaming merge without a real data source?

As asked

Implement a simple stack machine (push, pop, peek) using the Cats State monad so that the state threads automatically and the computation is pure. Show how you sequence multiple operations.

Sample answer outline

State[S, A] wraps a function S => (S, A). Define push(x: Int): State[List[Int], Unit] = State.modify(x :: _). pop: State[List[Int], Option[Int]] uses State(s => s match { case h :: t => (t, Some(h)); case Nil => (Nil, None) }). Chain operations with flatMap or for-comprehension. Run with .run(initialState).value. Strong candidates note this is purely functional with no mutation and that the same stack can be used from multiple threads safely.

Reference implementation (scala)

import cats.data.State

type Stack = List[Int]

def push(x: Int): State[Stack, Unit] = State.modify(x :: _)
def pop: State[Stack, Option[Int]] = ???
def peek: State[Stack, Option[Int]] = ???

// Sequence: push 1, push 2, pop, peek
val program: State[Stack, Option[Int]] = ???

Expect these follow-ups

• When would you choose State monad over passing state explicitly as a function parameter?
• How does StateT generalize the State monad to work inside another effect like IO?