Katkat
Back

Solve Three Algorithmic Tasks

SnapchatSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This set of three problems evaluates competencies in algorithm design and data structures, specifically efficient range counting on timestamped events, constrained selection/matching from double-sided cards, and merging multiple sorted lists.

You were asked three coding problems:

  1. Count events inside a time window
  • You are given an initial collection of event timestamps in HH:MM:SS format.
  • The timestamps may be unsorted and may contain duplicates.
  • Design a data structure that supports preprocessing and a query function:
  • build(events): preprocess the events.
  • query(start_time, end_time): return how many events fall within the inclusive range [start_time, end_time].
  • Example:
  • events = ["12:00:01", "01:02:02", "03:03:03"]
  • query("01:02:01", "01:02:03") -> 1
  • query("01:00:00", "04:00:00") -> 2
  1. Form a target string from double-sided cards
  • You are given cards where each card has one lowercase English letter on the front and one on the back.
  • Each card can be used at most once, and if used, you may choose only one side.
  • Determine whether the target string can be formed using the available cards.
  • Example:
  • cards = [["a", "b"], ["c", "d"]]
  • target = "ac" -> true
  • target = "ab" -> false because both a and b are on the same card.
  1. Merge multiple sorted lists
  • You are given N sorted lists of integers.
  • Merge them into one fully sorted output list.
  • The goal is to do better than concatenating everything and sorting again.