Robinhood·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Technical screen for a Data Scientist role at Robinhood, focused on interval-based algorithm problems tied to fraud detection use cases. The problem felt more like a software engineering question than a data science one, which threw me off a bit.

Questions Asked (1)

Given a list of user login sessions as [start_time, end_time] pairs, first determine whether any sessions overlap, then return the minimal set of session IDs to remove so the remaining sessions are non-overlapping and maximize total time covered.

Algorithms & Data Structures

Author's notes

I recognized the overlap-detection part pretty fast, sort and scan, easy.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, sort sessions by start time and scan for overlaps using a sweep-line approach. Then, to find the minimal removals that maximize total covered time, model it as a weighted interval scheduling problem where each session's weight is its duration, and use dynamic programming to select the optimal non-overlapping subset; the removed set is the complement.

Pro tip: Clarify the objective: 'minimal set to remove' and 'maximize total time covered' can conflict—if multiple minimal removal sets exist, you must choose the one maximizing coverage. Explicitly state this tie-breaking rule and justify your DP formulation.

1. Clarify requirements and edge cases

Confirm definitions: whether overlapping includes touching endpoints (e.g., [1,2] and [2,3]), whether session IDs are unique, and how to handle zero-length sessions. Discuss assumptions about input size and time complexity expectations.

2. Detect overlaps efficiently

Sort sessions by start time and iterate, comparing each session's start with the previous end. If any start < previous end (or <= depending on definition), an overlap exists; report it and optionally list overlapping pairs.

3. Formulate as weighted interval scheduling

Treat each session as an interval with weight equal to its duration. The goal is to select a maximum-weight non-overlapping subset; the sessions not selected are removed. This directly maximizes total covered time while minimizing removals (since maximizing kept sessions is equivalent to minimizing removals when weights are positive).

4. Solve with dynamic programming

Sort intervals by end time. Define DP[i] as the maximum total duration using intervals up to i. For each interval, either skip it (DP[i-1]) or take it plus the best compatible earlier interval (duration + DP[p(i)]), where p(i) is the latest non-overlapping index found via binary search. Reconstruct the chosen set by backtracking.

5. Return removals and validate

Compute the removed set as all sessions minus the chosen optimal set. Verify that the remaining sessions are non-overlapping and that total covered time is maximal. Discuss complexity: O(n log n) time and O(n) space.

Key Points to Mention

Sorting by start time for overlap detection and by end time for DP
Weighted interval scheduling with dynamic programming and binary search for predecessor
Tie-breaking: when multiple minimal removal sets exist, choose the one maximizing total covered time
Handling edge cases: touching intervals, zero-length sessions, duplicate IDs
Time and space complexity analysis (O(n log n) time, O(n) space)
Reconstruction of the optimal set via backtracking to identify removed session IDs

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