Quick Overview

This multi-part question evaluates set and multiset operations, frequency counting, top-K computation over time windows, sliding-window and streaming data structures, and character-multiset matching for string construction within the coding & algorithms domain.

Solve set equality and ad log top‑K

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

### Problem Set (Coding) #### 1) Check whether two sets are equal You are given two integer arrays `A` and `B` that represent **sets**, except they may contain duplicates and are not sorted. Return `true` if they represent the same mathematical set (same unique elements), otherwise return `false`. **Example** - `A = [1,2,2,3]`, `B = [3,1,2]` → `true` - `A = [1,2]`, `B = [1,2,4]` → `false` **Constraints** - `0 <= len(A), len(B) <= 2e5` - Values fit in 32-bit signed integer. --- #### 2) Top-K ads from impression logs + sliding window ingestion You are given an impression log as a list of events: - `events[i] = (timestamp_ms, ad_id)` - `events` is sorted by `timestamp_ms` ascending. **Part 1 (batch):** Given `events`, a window size `W_ms`, and an end time `T_end`, return the **top K ad IDs by number of impressions** whose timestamps fall in `[T_end - W_ms, T_end]`. Break ties by smaller `ad_id` (or specify a deterministic rule). **Part 2 (streaming):** Implement a data structure with two operations: - `ingestImpression(timestamp_ms, ad_id)` - `getTopK(T_end, W_ms, K)` such that it efficiently supports a sliding window query over recent impressions. Assume `ingestImpression` timestamps are non-decreasing. --- #### 3) Can a target string be formed from a source string? Given two strings `source` and `target`, determine if you can form `target` using characters from `source`. - Each character in `source` can be used **at most once**. - Return `true` if possible, else `false`. **Example** - `source = "aab"`, `target = "aba"` → `true` - `source = "ab"`, `target = "abb"` → `false` **Constraints** - Strings consist of ASCII letters (you may assume lowercase `a-z` if you want to simplify). - Length up to `2e5`.

Quick Answer: This multi-part question evaluates set and multiset operations, frequency counting, top-K computation over time windows, sliding-window and streaming data structures, and character-multiset matching for string construction within the coding & algorithms domain.

Part 1: Set Equality Ignoring Duplicates

Given two integer arrays A and B, determine whether they represent the same mathematical set. The arrays may be unsorted and may contain duplicates, but duplicates should be ignored. Return True if both arrays contain exactly the same unique elements, otherwise return False.

Constraints

  • 0 <= len(A), len(B) <= 200000
  • Array values fit in 32-bit signed integer
  • Duplicates may appear any number of times
  • The arrays are not guaranteed to be sorted

Examples

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

Expected Output: True

Explanation: Both arrays represent the set {1, 2, 3}.

Input: ([1, 2], [1, 2, 4])

Expected Output: False

Explanation: The second array contains 4, so the sets differ.

Hints

  1. Duplicates do not matter, so focus on unique elements only.
  2. A hash-based container can compare the unique contents of both arrays in linear time.

Part 2: Top-K Ads in a Time Window (Batch)

You are given a list of impression events sorted by timestamp in ascending order. Each event is represented as [timestamp_ms, ad_id]. Given a window size W_ms, an end time T_end, and an integer K, return the top K ad IDs by number of impressions whose timestamps fall inside the inclusive window [T_end - W_ms, T_end]. If two ads have the same number of impressions, the smaller ad_id must come first. If fewer than K unique ads appear in the window, return all of them.

Constraints

  • 0 <= len(events) <= 200000
  • 0 <= W_ms, T_end <= 10^9
  • 0 <= K <= 200000
  • Each event is [timestamp_ms, ad_id]
  • events is sorted by timestamp_ms ascending
  • ad_id fits in 32-bit signed integer

Examples

Input: ([[100, 1], [150, 2], [180, 1], [220, 3], [300, 2]], 100, 220, 2)

Expected Output: [1, 2]

Explanation: The window is [120, 220]. Ads 2, 1, and 3 each appear once, so tie-breaking by smaller ad_id gives [1, 2, 3]. The top 2 are [1, 2].

Input: ([[10, 5], [20, 5], [25, 3], [40, 3], [50, 3]], 30, 50, 2)

Expected Output: [3, 5]

Explanation: The window is [20, 50]. Ad 3 appears 3 times and ad 5 appears once.

Hints

  1. Since events are sorted by time, first find the left and right boundaries of the window.
  2. After counting frequencies inside the window, sort by (-count, ad_id) for deterministic output.

Part 3: Streaming Top-K Ads with Sliding Window Queries

Implement a stream processor for ad impressions. You will receive a sequence of operations encoded as integer lists. An ingest operation has the form [1, timestamp_ms, ad_id], meaning a new impression arrived. A query operation has the form [2, T_end, W_ms, K], meaning you must return the top K ad IDs by impression count among all ingested impressions whose timestamps lie in the inclusive window [T_end - W_ms, T_end]. Break ties by smaller ad_id. Ingest timestamps are non-decreasing. Return one answer list for each query operation, in order.

Constraints

  • 0 <= len(operations) <= 200000
  • Ingest operations are of the form [1, timestamp_ms, ad_id]
  • Query operations are of the form [2, T_end, W_ms, K]
  • Timestamps in ingest operations are non-decreasing
  • 0 <= timestamp_ms, T_end, W_ms <= 10^9
  • 0 <= K <= 200000
  • ad_id fits in 32-bit signed integer

Examples

Input: ([[1, 100, 7], [1, 120, 5], [1, 150, 7], [2, 150, 60, 2]],)

Expected Output: [[7, 5]]

Explanation: The query window is [90, 150]. Ad 7 appears twice and ad 5 appears once.

Input: ([[2, 50, 10, 3], [1, 10, 1], [1, 20, 2], [1, 20, 1], [2, 20, 15, 2], [2, 15, 10, 2]],)

Expected Output: [[], [1, 2], [1]]

Explanation: The first query happens before any ingest, so it returns []. The second query sees timestamps in [5, 20], giving counts {1: 2, 2: 1}. The last query only includes timestamp 10.

Hints

  1. Because ingested timestamps are non-decreasing, you can store them in a simple array and binary search query boundaries.
  2. For each query, only count impressions whose indices fall inside the time window.

Part 4: Can Target Be Formed from Source Characters?

Given two strings source and target, determine whether target can be formed using characters from source. Each character in source can be used at most once. Return True if it is possible, otherwise return False.

Constraints

  • 0 <= len(source), len(target) <= 200000
  • Both strings contain lowercase English letters a-z
  • Each character from source can be used at most once

Examples

Input: ("aab", "aba")

Expected Output: True

Explanation: source contains two a characters and one b, which is enough to build target.

Input: ("ab", "abb")

Expected Output: False

Explanation: target needs two b characters but source only has one.

Hints

  1. Count how many times each character is needed in target.
  2. If any character is required more often than it appears in source, the answer is False.

Loading coding console...