← Snowflake Interview Insights

Snowflake·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Snowflake software engineer interview with a classic scheduling DP problem. Nothing too surprising but the problem has enough moving parts that it's easy to fumble if you haven't seen interval scheduling before.

Questions Asked (1)

Q1

Given a list of jobs each with a start time, end time, and profit value, find the maximum profit you can earn by picking a non-overlapping subset of jobs. Jobs that share an endpoint (one ends exactly when another starts) are considered compatible.

Algorithms & Data Structures
Author's notes

This is basically the weighted job scheduling problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

This is the classic weighted interval scheduling problem. Sort jobs by end time, then use dynamic programming where dp[i] is the max profit considering jobs up to i. For each job, either skip it (dp[i-1]) or take it plus the best profit from jobs that end before its start (found via binary search).

Pro tip: Clarify the compatibility rule upfront: jobs that share an endpoint are compatible, so when finding the previous compatible job, use the largest end time <= current start time. Also, mention that sorting by end time is crucial for the DP to work correctly.

1. Understand the problem

Restate the problem: given jobs with start, end, profit, find max profit from non-overlapping jobs. Confirm that sharing endpoints is allowed.

2. Sort jobs by end time

Sort the jobs in ascending order of their end times. This ordering ensures that when considering a job, all compatible jobs appear earlier in the list.

3. Define DP state and recurrence

Let dp[i] be the maximum profit using jobs from 0 to i. For job i, find the latest job j < i such that end[j] <= start[i] (using binary search). Then dp[i] = max(dp[i-1], profit[i] + dp[j]).

4. Implement and handle base cases

Initialize dp[0] = profit[0]. Iterate i from 1 to n-1, compute dp[i] using the recurrence. Return dp[n-1] as the answer.

5. Analyze complexity and edge cases

Time complexity: O(n log n) due to sorting and binary search. Space: O(n) for DP array. Discuss edge cases like empty input or single job.

Key Points to Mention

  • Sorting by end time is essential for the DP to consider jobs in the correct order.
  • Binary search (or linear scan) to find the latest compatible job efficiently.
  • DP recurrence: dp[i] = max(dp[i-1], profit[i] + dp[p(i)]) where p(i) is the index of the latest compatible job.
  • Time complexity O(n log n) and space complexity O(n).
  • Compatibility rule: jobs sharing an endpoint are compatible, so use <= when comparing end and start times.
  • Alternative approaches: greedy doesn't work due to varying profits; can also use memoization or segment tree for optimization.

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