Online Election

Online Election

What is this problem about?

The Online Election problem gives you a sequence of votes (indexed by time) and a series of queries asking "who was leading at time t?" You must efficiently answer each query. This coding problem precomputes the leader at each vote time, then uses binary search to answer queries in O(log n). The array, hash table, design, and binary search interview pattern is directly demonstrated.

Why is this asked in interviews?

Atlassian and Google ask this because it tests preprocessing for query optimization — a common pattern in time-series data analysis. Precomputing the leader at every vote and then binary-searching for each query gives O(n log n) setup and O(log n) per query. The alternative (linear scan per query) is too slow.

Algorithmic pattern used

Precomputation + binary search. Scan through all votes once, maintaining a frequency map and current leader. Build an array leaders[] where leaders[i] = leader after the i-th vote. For each query time t: binary search for the largest index i where times[i] ≤ t. Return leaders[i].

Example explanation

times=[0,1,1,0,0,1], votes=[0,1,0,0,0,0]. (person 0 and 1 competing). After vote 0: freq={0:1}. Leader=0. After vote 1: freq={0:1,1:1}. Tie → current vote goes to 1. Leader=1. After vote 2: freq={0:2,1:1}. Leader=0. leaders=[0,1,0,0,0,0] at times=[0,1,1,0...] — wait, need to be careful about tied votes. Query t=4: binary search in times → largest ≤ 4. Leaders at that point.

Common mistakes candidates make

• Not handling ties correctly (the most recent vote breaks ties).
• Linear scan per query (O(n) per query instead of O(log n) with binary search).
• Off-by-one in binary search for "largest time ≤ t."
• Not precomputing leaders during the preprocessing phase.

Interview preparation tip

"Query at time t" design problems always precompute state at each event, then binary-search for queries. This is the standard pattern for snapshot queries, version queries, and temporal data queries. Practice bisect_right (Python) or upper_bound (C++) for "find last index where condition holds." This binary search pattern appears across many real-time data system design questions.