Snowflake·Software Engineer·Technical Phone Screen·Intermediate

IntermediateRejected

Apr 2026Remote

Summary

Snowflake software engineer phone screen, one hour, pretty much the entire session was a single hard DP problem and its followup. Brain fog hit at the worst possible time and I couldn't close it out.

Questions Asked (1)

Given a list of events each with a start day, end day, and value, and a maximum number of events you can attend, find the maximum total value you can collect. You can only attend one event at a time, must attend it in full, and two events cannot share a boundary day.

Algorithms & Data Structures

Author's notes

My brain just was not there.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort events by end day, then use dynamic programming where dp[i][k] represents the maximum value using the first i events and attending at most k events. For each event, either skip it or attend it and combine with the best previous non-overlapping event (found via binary search) using one fewer event. The answer is dp[n][K].

Pro tip: Clarify the boundary condition: 'two events cannot share a boundary day' means if one event ends on day d, the next must start on day d+2 or later. Also, mention that if K is large enough, the problem reduces to weighted interval scheduling without the cardinality constraint.

1. Clarify and Define

Restate the problem to confirm understanding: events have start, end, value; attend at most K events; no overlapping and no shared boundary days. Ask about constraints (e.g., number of events, value ranges) to guide algorithm choice.

2. Sort and Preprocess

Sort events by end day. For each event, compute the index of the latest non-conflicting event using binary search on end days, ensuring the next event starts after the current event's end day plus one (i.e., start > end + 1).

3. Define DP State and Recurrence

Let dp[i][k] be the max value using first i events with at most k events attended. Recurrence: dp[i][k] = max(dp[i-1][k], value[i] + dp[p(i)][k-1]) where p(i) is the latest non-conflicting event index.

4. Optimize Space and Iterate

Iterate k from 1 to K and i from 1 to n, filling the DP table. Optimize space by using two 1D arrays (previous and current) since dp[i][k] depends only on dp[i-1][k] and dp[p(i)][k-1].

5. Return and Analyze Complexity

Return dp[n][K]. Time complexity O(n log n + nK) due to sorting, binary search, and DP. Space complexity O(n) with optimization. Discuss potential improvements if K is large.

Key Points to Mention

Sorting events by end day to enable efficient non-overlap checks.
Binary search to find the latest non-conflicting event (start > end + 1).
Dynamic programming state: dp[i][k] = max value using first i events and at most k events.
Recurrence relation: skip event i or take it plus dp[p(i)][k-1].
Boundary condition: events cannot share a boundary day, so next start must be at least end + 2.
Time and space complexity: O(n log n + nK) time, O(n) space with optimization.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.