Google L4 onsite round Question | Give most optimised solution
Summary
I had an onsite round interview at Google for an L4 position where I was given a dynamic programming style problem related to electoral votes.
Full Experience
During my Google L4 onsite round, I was presented with a challenging problem involving electoral votes. The interviewer asked me to find the number of different combinations of states won by Party 1 that would lead to their candidate being elected.
Interview Questions (1)
Imagine that each state is assigned a number of votes as follows:
Alabama = 9 Alaska = 3 Arizona = 11 Arkansas = 6 .... Wyoming = 3 For the purpose of this question, assume that all states are "winner takes all." The winner of a state gets all the votes for that state.
To be elected, a candidate must win more than total_votes / 2. The candidate from Party 1 is running against the candidate from Party 2. candidate. How many different combinations of states won by Party 1 are there that will elect the Party 1 candidate?
For example, if Party 1 wins every state, the Party 1 candidate wins. If they win every state but lose Alabama, the candidate still wins.
Another example with three states:
StateA = 3 StateB = 4 StateC = 8 If Party 1 wins every state, their candidate will get elected. If they win StateA and StateC, their candidate will still get elected. If they win StateA and StateB but lose StateC, their candidate will not get elected.