# The Google Interview Question Everyone Gets Wrong Channel: Veritasium Source: https://www.youtube.com/watch?v=dFVrncgIvos Recap page: https://rapidrecap.app/video/dFVrncgIvos Generated: 2025-07-07T05:10:27.335+00:00 --- ## Quick Overview **Key Takeaway:** The sum of handshakes at a party must always be an even number, making it impossible for the sum to be odd. **Key Points:** - Each handshake involves two people, adding 2 to the total sum of handshakes. - The handshaking lemma states that the sum of degrees in any finite graph is an even number. - The problem tests logical reasoning and basic graph theory, not complex math. - The correct answer is that it's impossible for the sum to be odd. ## Summary The Google interview question asks if the sum of handshakes reported by N people at a party can be an odd number. The definitive answer is no, it is impossible for the sum to be odd. This is because every single handshake involves two individuals. When two people shake hands, each person's individual handshake count increases by one, meaning that the total sum of all reported handshakes increases by two for every single handshake that occurs. This principle ensures that the total sum will always be an even number. This concept is a direct application of the handshaking lemma from graph theory, which states that the sum of the degrees of all vertices in any finite graph is always an even number, specifically twice the number of edges. The question serves as a test of logical reasoning and basic mathematical intuition, often leading candidates to overcomplicate a straightforward parity problem. **Key Points:** - The sum of handshakes will always be an even number because each handshake involves two participants. - Every handshake adds exactly two to the total sum of reported handshakes (one for each person involved). - This concept is formally known as the handshaking lemma in graph theory, where the sum of degrees (handshakes) in any graph is twice the number of edges (handshakes), thus always even. - The question is designed to test logical reasoning and fundamental mathematical understanding rather than complex calculations. - The common mistake is overthinking or failing to recognize the simple parity rule. - It is definitively impossible for the sum of handshakes to be an odd number. **Context:** The video presents a common Google interview question about the sum of handshakes at a party, where each person reports the number of hands they shook. The core of the question is whether the total sum of these reported numbers can be odd. This problem is a classic example of applying basic graph theory principles to a seemingly simple social scenario. ## Detailed Analysis The Google interview question about the sum of handshakes at a party has a definitive answer: it is impossible for the sum to be odd; it must always be an even number. The core reasoning is that every single handshake that occurs involves exactly two people. When two individuals shake hands, each of their personal handshake counts increases by one. Consequently, for every handshake, the total sum of all reported handshakes across the entire group increases by precisely two. Since the sum starts at zero (an even number) and only ever increases by even increments (two per handshake), the final sum will invariably remain an even number. This principle is formally established by the handshaking lemma in graph theory, which states that the sum of the degrees (number of connections/handshakes) of all vertices (people) in any finite graph is always equal to twice the number of edges (handshakes), thus guaranteeing an even sum. The question's difficulty lies not in complex mathematics but in recognizing this simple parity rule and avoiding common pitfalls like trying to construct a scenario where the sum is odd. The video emphasizes that the "everyone gets wrong" aspect stems from overcomplicating a straightforward logical problem. **Key Moments:** - **00:15**: Introduction of the Google interview question: "Is it possible that the sum of these N numbers is odd?" ![Screenshot at 00:15](https://ss.rapidrecap.app/screens/dFVrncgIvos/00-00-15.png) - **01:00**: Explanation of why each handshake adds 2 to the total sum. ![Screenshot at 01:00](https://ss.rapidrecap.app/screens/dFVrncgIvos/00-01-00.png) - **02:30**: Formal introduction of the Handshaking Lemma. ![Screenshot at 02:30](https://ss.rapidrecap.app/screens/dFVrncgIvos/00-02-30.png) - **03:45**: Conclusion that the sum must always be even. ![Screenshot at 03:45](https://ss.rapidrecap.app/screens/dFVrncgIvos/00-03-45.png) - **04:10**: Discussion on why people get it wrong (overthinking). ![Screenshot at 04:10](https://ss.rapidrecap.app/screens/dFVrncgIvos/00-04-10.png) **Insights:** - The problem is a direct application of the handshaking lemma, a foundational concept in graph theory. - The "trick" lies in the simplicity of the solution and the tendency to overcomplicate. - It assesses a candidate's ability to reason logically and identify fundamental constraints. - The parity (even/odd) of the sum is the key, not the specific number of people or handshakes. - Google interview questions often test foundational understanding and problem-solving approaches over rote memorization. **Action Items:** - When faced with similar parity-based problems, consider the impact of each individual action on the total sum. - Apply basic mathematical principles and graph theory concepts (like the handshaking lemma) to simplify complex-sounding questions. - Avoid overthinking and look for the simplest explanation or constraint that governs the problem. - Practice identifying underlying mathematical structures in seemingly non-mathematical problems.