How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Snapchat.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snapchat during technical interviews.

Solve Three Algorithmic Tasks | Snapchat Coding Question

Quick Overview

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.

Solve Three Algorithmic Tasks

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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` 2. **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. 3. **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.

Quick Answer: 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.

Part 1: Count Events Inside Inclusive Time Windows

You are given a list of event timestamps from a single day, each in 'HH:MM:SS' format. The timestamps may be unsorted and may contain duplicates. You are also given several query windows. For each query [start_time, end_time], return how many events fall inside the inclusive range. Your function should preprocess the events once and answer all queries efficiently.

Constraints

0 <= len(events), len(queries) <= 200000
Each timestamp is a valid time from '00:00:00' to '23:59:59'
Event timestamps may be unsorted and may contain duplicates
If a query has start_time > end_time, treat its answer as 0

Examples

Input: (['12:00:01', '01:02:02', '03:03:03'], [('01:02:01', '01:02:03'), ('01:00:00', '04:00:00')])

Expected Output: [1, 2]

Explanation: Only '01:02:02' is inside the first window. The second window includes '01:02:02' and '03:03:03'.

Loading coding console...

Part 2: Form a Target String from Double-Sided Cards

You are given double-sided cards. Each card contains one lowercase English letter on the front and one lowercase English letter on the back. You may use each card at most once, and if you use a card you may choose only one of its two letters. Determine whether it is possible to form the target string exactly.

Constraints

0 <= len(cards) <= 500
0 <= len(target) <= 500
Each letter is a lowercase English letter
A card like ['a', 'a'] can still be used at most once, so it contributes only one 'a'

Examples

Input: ([['a', 'b'], ['c', 'd']], 'ac')

Expected Output: True

Explanation: Use 'a' from the first card and 'c' from the second card.

Input: ([['a', 'b'], ['c', 'd']], 'ab')

Expected Output: False

Explanation: Both 'a' and 'b' are on the same card, but a card can be used only once.

Input: ([['a', 'a'], ['a', 'b'], ['c', 'd']], 'aac')

Expected Output: True

Explanation: Use the first card for one 'a', the second card for the other 'a', and the third card for 'c'.

Input: ([], '')

Expected Output: True

Explanation: An empty target needs no cards.

Input: ([], 'a')

Expected Output: False

Explanation: There are no cards available to supply any letter.

Hints

Think of each needed target character as needing to be assigned to a distinct card that contains that letter.
This can be solved as a bipartite matching problem between target positions and cards.

Part 3: Merge Multiple Sorted Lists

You are given N sorted lists of integers. Merge them into one fully sorted list. The goal is to do better than concatenating all numbers and sorting again.

Constraints

0 <= len(lists) <= 100000
0 <= total number of integers across all lists <= 200000
Each individual list is already sorted in non-decreasing order
Values may be negative and duplicates are allowed

Examples

Input: ([[1, 4, 5], [1, 3, 4], [2, 6]])

Expected Output: [1, 1, 2, 3, 4, 4, 5, 6]

Explanation: Repeatedly taking the smallest front element across the lists produces the fully merged order.

Input: ([[], [0], [], [0, 2]])

Expected Output: [0, 0, 2]

Explanation: Empty inner lists should be ignored.

Input: ([])

Expected Output: []

Explanation: No lists means the merged result is empty.

Input: ([[-3, -1, 2], [-2, 2, 2], [5]])

Expected Output: [-3, -2, -1, 2, 2, 2, 5]

Explanation: Negative values and duplicates must remain in sorted order.

Input: ([[1]])

Expected Output: [1]

Explanation: A single one-element list is already merged.

Hints

Keep track of the current smallest unused element from each list.
A min-heap lets you repeatedly extract the next smallest value efficiently.