Get Biggest Lions
Reported by candidates from Optiver's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Optiver reported this one in March 2024, and the input size is the whole point. You get a stream of enter, exit and inspect events, and re-scanning every lion in the room on each INSPECT will blow up once the event count grows. The problem is a design question wearing a simulation costume. You need to track the tallest competitor live, match your own lions against a private schedule, and return names alphabetically. If you blank during the actual OA, StealthCoder sits invisibly on your screen and gives you a working structure when you need one.
The problem
As a lion trainer, you are taking part in an international lion exhibition. Lions from your team and competing teams enter and leave the showroom according to a schedule. You know the schedule for your lions, and during the show you observe every lion entering and leaving. At an inspection, return your lions currently in the room whose height is at least the height of the largest competing lion currently in the room. Return qualifying names in alphabetical order. If no competing lion is in the room, every one of your lions currently in the room qualifies. Original class behavior The constructor receives descriptions of your lions and their private schedule. LionEntered(currentTime, height) records one observed entry. LionLeft(currentTime, height) records one observed exit. getBiggestLions() returns the qualifying names for the current room state. Your schedule is followed exactly, so an event whose time and height match a pending scheduled entry or exit identifies one of your lions. Other events belong to competitors. When several events have the same timestamp, an inspection occurs either before all of them or after all of them, never between them. FastPrep Runner Adapter Implement LionCompetition(String[][] lions, String[][] schedule, String[] operations). Each row of lions is [name, height]. Each row of schedule is [name, enterTime, exitTime]. ENTER currentTime height calls LionEntered. EXIT currentTime height calls LionLeft. INSPECT currentTime calls getBiggestLions. Return one string-array row for every INSPECT command, in operation order. Function LionCompetition(lions: String[][], schedule: String[][], operations: String[]) → String[][] Examples Example 1 lions = [["marry","300"],["rob","250"]] schedule = [["marry","10","15"],["rob","13","20"]] operations = ["ENTER 8 200","ENTER 10 310","ENTER 10 300","INSPECT 11","ENTER 13 250","EXIT 13 310","INSPECT 13","EXIT 15 300","INSPECT 16","EXIT 16 200","EXIT 20 250"] return = [[],["marry","rob"],["rob"]] At time 11, the competing lion of height 310 is taller than both of our lions in the room, so the first row is empty. At time 13, that competitor has left and the remaining competing maximum is 200, so both marry and rob qualify. At time 16, marry has left and rob still qualifies against the competing lion of height 200. Constraints Subsequent invocations of LionLeft and LionEntered methods are always called in order, according to the currentTime parameter. The schedule is strictly followed - your lions enter and exit the room exactly at their specified times. The lion inspection (invocation of the getBiggestLions method) takes place either before or after all lions scheduled to enter or leave the room at a given minute did that - never in between. Lion names are unique. Times (currentTime, enterTime and exitTime) are always whole numbers (and multiple events can occur at the same time). A single lion enters the room only once during the show.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is two multisets. Keep a count map of competitor heights currently in the room, plus a way to get the max (a sorted map or a max-heap with lazy deletion). Keep your own lions in a sorted structure keyed by height, with names sorted alphabetically on output. For each ENTER or EXIT, check whether (time, height) matches a pending scheduled event for one of your lions. If it does, it's yours. Otherwise it's a competitor. The pitfall is ambiguity: a competitor can share a height with your lion at the same time, so consume the scheduled match once and treat extras as competitors. Another trap is the same-timestamp rule. Inspections never fall between events at one time, so process events in the given order. With no competitors present, return all your lions in the room. StealthCoder is the hedge if the matching logic tangles live.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Get Biggest Lions cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Optiver's OA.
Optiver reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Get Biggest Lions FAQ
What's the core trick in Get Biggest Lions?+
Maintain the current max competitor height incrementally instead of rescanning. A count map of competitor heights with a sorted key set or heap with lazy deletion gives you the max fast. Then filter your lions in the room by height at least that max and sort names.
How do I tell my lion from a competitor?+
Index your schedule by (time, height) for entries and exits. When an event arrives, if a pending scheduled entry or exit matches, consume it and mark that lion in or out. Anything unmatched is a competitor. Consume matches once so duplicates fall through to competitors.
How hard is this problem really?+
Medium. The logic isn't deep, but the parsing, matching and edge cases make it easy to slip. The example is small, so write your own tests with ties in height and empty rooms before trusting your solution.
What edge cases should I test?+
No competitors in the room, which means all your lions in the room qualify. A competitor with exactly your lion's height, which qualifies since the rule is at least. Multiple events at the same timestamp. An empty room returning an empty row. Alphabetical ordering of the output names.
How do I prepare for this in 48 hours?+
Practice design-style problems that track state across a stream of events, using sorted maps, heaps with lazy deletion and count maps. Write one full solution that parses string operations into method calls. Focus on clean state updates, not fancy algorithms.