Databricks Coding Interview: Ordered Set Operations

The interviewer opens

Welcome, and thanks for joining this interview for the software engineer role at Databricks. We'll work through a coding problem together, and I'd like you to think out loud as you code. If you need to step out or take a break, you can pause the interview any time with the Pause button at the top right of your screen.

The problem is about maintaining a collection of integers that stays in sorted order while you answer queries against it, the kind of ordered-data thinking that comes up a lot in database and query-engine work. It's up in the Problem tab now, so please read it through, take your time, and ask me any questions before you start.

The problem

Build an integer set that keeps its elements in sorted order, and run a sequence of operations on it.

• ops: list of {op, value} records, where op is "add", "remove", "contains" or "ceiling".

The set starts empty. Each operation appends one string to the result. add inserts value and outputs "true", or outputs "false" if it was already present. remove deletes value and outputs "true", or outputs "false" if it was absent. contains outputs "true" or "false". ceiling outputs the smallest element >= value as a decimal string, or "null" if there is none.

Example: add 5, add 1, add 5, contains 1, remove 1, ceiling 2, ceiling 6 → ["true","true","false","true","true","5","null"]

Up to 10^5 operations; values may be negative.