The Phone Screen

LinkedIn's technical phone screen runs about an hour, and it often has two problems. One of them is usually a short warm-up next to a heavier problem. Bulb Switcher, Can Place Flowers set up as theater seating, and Valid Parentheses set up as a config validator keep turning up in that slot.

Interviewers expect the same clean code and hand trace on the warm-up as on the heavier problem, and candidates have been turned down after solving both. In the three problems below, the bugs sit at the edges, like the end seats of the theater row or a close paren that arrives before any opener.

The LinkedIn angle

Finish fast, then trace anyway. The time you save on the warm-up goes to the heavier problem, but spend a little of it first. Say the brute force in one sentence, write the clean version, and walk the edge input through it out loud before you call it done. Write complete code that compiles and dry-run it, since some interviewers will run it.

One idea per problem

None of these needs a clever data structure. Each needs one observation that replaces a simulation with a count. Bulb Switcher reduces to counting perfect squares, because each bulb flips once per divisor. The seating row needs one greedy pass that takes the first legal empty seat. With a single bracket type, the validator's stack holds nothing beyond its height, so a counter can replace it. The follow-up usually asks you to defend that observation or extend it.

Asked at LinkedIn

Three warm-ups, in rough order of how often they come up. Each test case is the function's arguments as a JSON array and the expected return. Give each one a timed pass in the editor, dry-run it, and then read the walkthrough for the follow-up.

1

Can Place Flowers: Seating Strangers in a Theater

EasyFrequently asked

Problem

You're an usher seating guests in one row of a theater. The row is an array seats where 1 marks an occupied seat and 0 an empty one. Nobody wants to sit next to another person, so a new guest may only take an empty seat whose left and right neighbors (where they exist) are both empty, and every guest you seat counts as a neighbor for the guests after them. Given an integer people, return true if you can seat that many new guests and false otherwise.

The row as given may already have guests sitting side by side; the rule binds only the people you seat. seats holds at least one seat, and people is at least 0.

Input encoding. Each test case is a JSON array [seats, people]. The function returns a boolean.

Inputseats = [1,0,0,0,1]people = 1Outputtrue

Seat 2 is the only empty seat with both neighbors empty, so exactly one guest fits.

Inputseats = [0,0,1,0,0]people = 2Outputtrue

Seats 0 and 4 sit at the ends of the row, so each needs only its one inner neighbor empty.

How this uses the pattern

Scan left to right and seat a guest at the first empty seat whose neighbors are both free. Remember the index of the nearest occupied seat to the left, original or new, so the input never changes, and stop as soon as the count reaches people.

Can Place Flowers: Seating Strangers in a Theater

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (11)

Need a hint? (3 available)

The LinkedIn angle

LinkedIn rarely asks this one as flowers. On the technical phone screen it shows up as an usher seating guests in a theater row where nobody will sit next to anyone, sometimes with the bare stub boolean canSeatPeople(List seats, int numberOfPlace). The return type tells you the answer is yes or no against a target, so the scan can stop once the count reaches it. Explain out loud why the greedy works: the first legal seat in an empty run never fits fewer guests than a later pick would. The bugs are usually at seat 0 and the last seat, so dry-run both ends. Candidates with working solutions have still been rejected here, so tidy boundary code counts as much as the answer.

Take it further

A natural bend on that stub, since a List could just as well be an iterator, has the seats stream in one at a time with no index access and asks for the most guests the row can take. Peeking at seats[i + 1] is gone, so count empty runs in closed form. A run of L empty seats boxed in by occupied seats holds (L - 1) / 2, a run touching one end holds L / 2, and a phantom empty seat past each end folds every case into the first formula. The walkthrough carries the streaming version through.

Show solution & walkthrough

2

Bulb Switcher: The Perfect-Squares Tell

MediumCommonly asked

Problem

There are n bulbs in a row, numbered 1 to n, and all of them start off. The first round switches every bulb on. Round 2 then toggles every second bulb (2, 4, 6, ...). From there, round i toggles every i-th bulb, so round n touches only bulb n. Return how many bulbs are on after all n rounds.

n ranges from 0 to 2^31 - 1, so simulating the rounds will not finish in time.

Input encoding. Each test case is a JSON array [n]. The function returns the count as an integer.

Inputn = 3Output1

Round 1 turns all three on, round 2 turns bulb 2 off, round 3 turns bulb 3 off. Only bulb 1 is left on.

Inputn = 25Output5

Bulbs 1, 4, 9, 16 and 25 stay on. Every other bulb is toggled an even number of times.

How this uses the pattern

Track one bulb across all rounds. Bulb i is toggled once for each divisor of i, so it ends on exactly when i has an odd number of divisors, which only perfect squares do. Count the squares up to n.

Bulb Switcher: The Perfect-Squares Tell

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (9)

Need a hint? (3 available)

The LinkedIn angle

Bulb Switcher shows up on LinkedIn's technical phone screen as the quick half of a two-problem round, usually ahead of the phone-number words problem or Nested List Weight Sum. It can also come as 100 lockers toggled pass by pass, or as a short story. Either way, the question is which positions flip an odd number of times. Bulb i flips once per divisor, divisors pair up as d and i / d, and only a perfect square has a divisor paired with itself. Say the brute force out loud, then the square-root idea. A reported version wanted the bulbs themselves (1, 4, 9, 16, 25), so keep a loop that can list them.

Take it further

A reported LinkedIn version asks for the bulbs themselves: return every bulb left on, in increasing order, so n = 30 gives [1, 4, 9, 16, 25]. Filtering 1..n for squares costs O(n). Stepping root upward and emitting root * root costs O(sqrt n) and reuses the counting loop line for line. (Worked in the solution.)

Show solution & walkthrough

3

Valid Parentheses: The Config Validator, in O(1) Space

EasyCommonly asked

Problem

A config validator checks a changed JSON, YAML or HOCON file before it ships. One piece of that validator decides whether the parentheses in a value are properly matched.

Given a string s of letters, digits and other characters with ( and ) mixed in, return true if every ) closes an earlier unmatched ( and every ( is eventually closed. Every character other than ( and ) is ignored. A string with no parentheses at all is balanced.

Input encoding. Each test case is a JSON array [s]. The function returns a boolean.

Inputs = "((45+)*a3)"Outputtrue

Skip the digits, the operators and the letter. The inner ( closes after "45+", the outer one closes at the end.

Inputs = "()(NFJDH)(()"Outputfalse

The first two pairs close cleanly, but the ( at index 9 is never closed, so one paren is left open when the string ends.

How this uses the pattern

With a single bracket type, a stack of open parens tells you nothing beyond its height. Track that height as an integer that rises on (, falls on ), never dips below zero and finishes at exactly zero.

Valid Parentheses: The Config Validator, in O(1) Space

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (9)

Need a hint? (3 available)

The LinkedIn angle

Valid Parentheses turns up on the LinkedIn phone screen as the warm-up, often skinned as a config validator. LinkedIn configures its services with JSON, YAML and HOCON files, and a validator that waves through a malformed one can take down several services at once. The reported example, "((45+)*a3)", carries digits and operators between the brackets, so everything except ( and ) gets skipped. Most candidates can write the stack, and the reported follow-up asks for O(1) space. With one bracket type, the stack only ever holds copies of (, so its depth is all the information it carries and a single counter replaces it, provided you fail the moment it dips below zero.

Take it further

The reported follow-up on the screen is to redo it in O(1) space. Since only ( and ) count, the stack never holds anything but open parens, so an integer depth can stand in for it. Add one on (, subtract one on ), return false the instant the depth goes negative, and require zero at the end. (Worked in the solution.)

Show solution & walkthrough