Binary Search

Three problems from Snowflake's online assessment use the same method. Each asks for the smallest or largest number that meets a condition, where checking one guess is cheap but computing the number directly is hard. A Premium question wants the fewest operations that finish every job. String Search wants the most deletions that still leave a target findable. The barrier problem wants the tallest cut that keeps enough total energy. In each one, if a value works then every value on one side of it works too, and that's all binary search needs.

The prompts don't make it obvious. A Premium question reads like a scheduling simulation, and a max-heap that keeps boosting the longest job passes the small cases before timing out on the large ones. String Search reads like repeated deletion with a rescan after each step. The barrier problem looks like arithmetic with a closed-form answer. The constraint lines are the clue, with values up to a billion and strings of 10^5 characters, and the hidden tests use those sizes.

The Snowflake angle

Write the check before the search. On a hidden-test assessment, halving the range is the easy part, and the check function is where points get lost. Say what a guess k means, write feasible(k) as its own function, and test it by hand on one value that passes and one that fails. Then pick bounds you can explain out loud. A bound that's off by one fails the hidden case at the edge of the range, and the samples rarely test there.

SnowflakePremium lesson · Coding round

The 3 Snowflake problems are below.

1. 1A Premium questionCoding · Medium · Frequently asked
2. 2A Premium questionCoding · Medium
3. 3A Premium questionCoding · Medium

Each with hints, the follow-up and a tested solution.

Get the Snowflake questions

$49 a year · all 100 companies · cancel anytime

From 111 Snowflake reports, forum threads behind logins and write-ups in Chinese.

Read a free Snowflake lesson firstAlready a member? Sign in