Google Interview Questions

What Google interviews focus on

Common Google interview questions

• Given an array of integers, return indices of the two numbers such that they add up to a specific target. (Classic two-sum, but ask for multiple solutions and discuss complexity.)
  What a strong answer covers

  • Hash map for O(n) time and O(n) space
  • Sorting + two-pointer for O(n log n) time and O(1) space
  • Brute-force: O(n^2) time, O(1) space
  • Tradeoffs: memory vs. speed, handling duplicates
  • Follow-up: can solution scale to large arrays? Consider integer overflow

  View a sample answer

  The classic two-sum problem has several solutions. The most efficient is using a hash map to store complements as you iterate: for each number, check if target - num exists in the map, else add num with its index. This gives O(n) time and O(n) space. An alternative is to sort the array and use two pointers from both ends, achieving O(n log n) time and O(1) space (ignoring sort space), but you lose original indices unless you pair values with indices before sorting. The brute-force double loop is O(n^2) and only suitable for small inputs. A common pitfall is assuming the array is sorted or not handling duplicate values correctly. For follow-ups, consider integer overflow if target is large, or handling multiple pairs. The hash map solution is generally preferred for its linear time complexity.

• Design a URL shortener like bit.ly – discuss database schema, hashing, scaling, and handling redirects.
  What a strong answer covers

  • Database schema: id, short_key, original_url, created_at, expiration
  • Hashing: base62 encoding of auto-increment ID or hash of URL + salt
  • Scaling: read-heavy, use cache (Redis) for hot URLs, CDN for redirects
  • Redirection: HTTP 301/302, short key to long URL lookup
  • Bottlenecks: DB writes, hash collisions, key generation uniqueness

  View a sample answer

  A URL shortener like bit.ly needs to map short keys to original URLs. Database schema includes a unique auto-increment ID, a short key (e.g., 6-7 character base62 string), original URL, creation timestamp, and expiration. For hashing, we can either encode the auto-increment ID to base62 (ensuring uniqueness, no collisions) or hash the URL with a salt and truncate (risks collisions, requires check). The redirect flow: user hits short URL -> server looks up key (cache-first, then DB) -> returns 301 (permanent) or 302 (temporary) redirect to original URL. To scale, use read replicas, distribute across data centers, and cache frequent keys in Redis. Write scaling: batch inserts, use distributed ID generator (like Snowflake). A common pitfall is key collision when hashing; using ID-based encoding avoids that. Also consider monitoring cache hit rates and handling expired URLs.

• Tell me about a time you had a conflict with a colleague. How did you resolve it? (Behavioral – focus on collaboration and outcome.)
  What a strong answer covers

  • Situation: disagreement on technical approach for feature
  • Task: deliver a reliable payment module on time
  • Action: scheduled meeting to discuss pros/cons, listened to concerns, proposed compromise
  • Result: combined both approaches, delivered early with fewer bugs
  • Outcome: improved team relationship, now collaborate regularly

  View a sample answer

  In a previous project, my colleague and I disagreed on whether to use a monolithic or microservices architecture for a new payment module. I favored microservices for long-term scalability; he preferred a monolith for faster initial delivery. We scheduled a meeting where each presented a risk assessment: I highlighted deployment flexibility, he pointed out overhead. We agreed on a compromise: start with a modular monolith that can be split later. I contributed by designing clean module interfaces. The result was the project delivered two weeks early with significantly fewer bugs, and we later split the payment service without major refactoring. This experience taught me that active listening and focusing on shared goals (on-time delivery, quality) can turn conflict into collaboration.

• Implement a function to serialize and deserialize a binary tree. (Testing handling of nulls, recursion, and iteration.)
  What a strong answer covers

  • Serialization: pre-order traversal with marker for null nodes
  • Deserialization: recursive reconstruction using queue
  • Handling nulls: use sentinel (e.g., 'N') to preserve structure
  • Complexity: O(n) time and O(n) space for both
  • Alternative: level-order serialization with nulls

  View a sample answer

  Serialization converts a binary tree to a string so it can be stored/transmitted. A common approach is pre-order traversal storing node values and a special marker (e.g., 'N') for null children. Deserialization reads the string and rebuilds the tree recursively. Both operations take O(n) time and O(n) space. A pitfall is handling integer values that could be mistaken for markers; using a delimiter (like comma) and special character for null avoids ambiguity. Below is an implementation in Python.

  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  
  class Codec:
      def serialize(self, root):
          """Encodes a tree to a single string.
          :type root: TreeNode
          :rtype: str
          """
          def dfs(node):
              if not node:
                  return 'N,'
              return str(node.val) + ',' + dfs(node.left) + dfs(node.right)
          return dfs(root)
  
      def deserialize(self, data):
          """Decodes your encoded data to tree.
          :type data: str
          :rtype: TreeNode
          """
          nodes = data.split(',')
          self.i = 0
          def dfs():
              if nodes[self.i] == 'N':
                  self.i += 1
                  return None
              node = TreeNode(int(nodes[self.i]))
              self.i += 1
              node.left = dfs()
              node.right = dfs()
              return node
          return dfs()

• Design Google Maps’ real-time traffic feature – how would you collect data, update routes, and handle millions of users?
  What a strong answer covers

  • Data collection: GPS from mobile devices, road sensors, traffic cameras, third-party feeds
  • Data aggregation: anonymized location pings aggregated per road segment
  • Route update: real-time calculation using Dijkstra/A* with congestion weights
  • Scalability: shard by geographical region, use stream processing (Apache Kafka, Flink)
  • Bottlenecks: data volume, latency, privacy concerns

  View a sample answer

  Real-time traffic for Google Maps requires massive data ingestion and processing. Data sources include GPS pings from users with location sharing enabled, road sensors, and government traffic feeds. Each ping contains anonymized lat/long, timestamp, and speed. These are aggregated per road segment (using map-matching algorithms) to compute average speed and congestion level. Route updates use a weighted graph where edge weights reflect real-time travel times, computed via Dijkstra or A* with heuristics. To handle millions of users, the system is sharded by geographic tiles; each shard processes its region's data. Stream processing engines (e.g., Apache Flink) aggregate data in near-real-time. CDNs cache static tiles, while dynamic route calculations happen on backend servers. A major challenge is ensuring low latency (sub-second updates) while handling privacy: data must be anonymized and aggregated. Another bottleneck is map-matching accuracy for noisy GPS data. The system also uses historical patterns to predict future traffic (e.g., rush hour).

• Explain a project you’re most proud of. What was your role, challenges, and impact? (Behavioral – evaluate ownership and influence.)
  What a strong answer covers

  • Situation: complex migration of legacy system to cloud
  • Task: lead a team of 5 engineers to migrate with zero downtime
  • Action: created phased plan, set up CI/CD, automated testing, communicated risks
  • Result: migration completed on time, 30% cost reduction, 99.99% uptime
  • Outcome: recognized by management, mentored junior engineers

  View a sample answer

  My proudest project was migrating a monolithic on-premise CRM to a cloud-native microservices architecture. As the lead engineer, I was responsible for technical design and coordination. The challenge was ensuring zero downtime during a six-month migration. I broke the project into phases: first, containerize the monolith; second, extract individual services (user auth, billing, reporting) with feature flags; third, cut over incrementally. I set up CI/CD pipelines with automated integration tests and rollback mechanisms. We also held weekly stakeholder demos to manage expectations. The result was a seamless migration with no downtime, a 30% reduction in infrastructure costs, and improved system reliability (99.99% uptime). Personally, I grew in system design and team leadership, and I mentored two junior engineers who later led their own migrations. The key takeaway was that careful planning and communication are critical for large-scale changes.

• Given a stream of integers, find the median at any point. (Use two heaps – max-heap and min-heap.)
  What a strong answer covers

  • Two heaps: max-heap for lower half, min-heap for upper half
  • Invariant: size difference ≤ 1, max-heap all ≤ min-heap
  • Median: if equal size, average of tops; else top of larger heap
  • O(log n) insertion, O(1) median retrieval
  • Pitfall: handling duplicates correctly

  View a sample answer

  To find the median from a stream, maintain a max-heap for the smaller half of numbers and a min-heap for the larger half. On each insertion, add to one heap, then rebalance to keep sizes differing by at most 1, and ensure all values in max-heap ≤ all in min-heap. The median is the top of the larger heap (if odd count) or the average of both tops (if even). This yields O(log n) insertion and O(1) median query. A common pitfall is forgetting to check the invariant after each addition, leading to incorrect order. Below is a Python implementation.

  import heapq
  
  class MedianFinder:
      def __init__(self):
          self.small = []  # max-heap (store negatives)
          self.large = []  # min-heap
  
      def addNum(self, num: int) -> None:
          # Add to appropriate heap
          if not self.small or num <= -self.small[0]:
              heapq.heappush(self.small, -num)
          else:
              heapq.heappush(self.large, num)
          # Balance sizes
          if len(self.small) > len(self.large) + 1:
              heapq.heappush(self.large, -heapq.heappop(self.small))
          elif len(self.large) > len(self.small):
              heapq.heappush(self.small, -heapq.heappop(self.large))
  
      def findMedian(self) -> float:
          if len(self.small) == len(self.large):
              return (-self.small[0] + self.large[0]) / 2.0
          else:
              return -self.small[0]

• Why Google? What makes you a good fit for our culture? (Behavioral – connect personal values to Google’s mission.)
  What a strong answer covers

  • Mission: organize world's information and make it universally accessible
  • Culture: innovation, collaboration, intellectual curiosity, impact
  • Personal fit: passion for solving hard problems, user focus, data-driven decisions
  • Examples: previous open-source contributions, side projects, leadership
  • Growth: desire to learn from Googlers and contribute to large-scale systems

  View a sample answer

  Google's mission to organize the world's information deeply resonates with me. I've always been driven by creating products that have a positive global impact. At my previous job, I led an initiative to improve search relevance for a niche dataset, which increased user engagement by 15%. This experience aligned with Google's data-driven approach. I also admire Google's culture of intellectual curiosity—I often attend tech talks and contribute to open-source projects like [specific project]. I believe my ability to work collaboratively across teams and my persistence in tackling complex problems (like the traffic system we discussed) makes me a good fit. I'm eager to learn from the brilliant engineers at Google and contribute to solving large-scale challenges that affect billions of users. My values of transparency, innovation, and user focus match Google's principles.

Tips to prepare

• Practice coding on a whiteboard or without an IDE: Google interviews often require writing code by hand, so get comfortable thinking and writing on a flat surface.
• Always think aloud: Interviewers want to see your problem-solving process, so narrate your approach, trade-offs, and debugging steps.
• Master core data structures: Focus on arrays, strings, trees, graphs, and hash tables – they appear in most coding problems. Be ready to discuss time and space complexity.
• Prepare for system design by studying scalability: Understand caching, load balancing, sharding, and CAP theorem. Practice designing systems like YouTube, Twitter, or a chat service.
• Review behavioral stories with the STAR method: Structure your answers around Situation, Task, Action, Result, and tailor them to Google’s leadership principles (e.g., 'Have a backbone, disagree and commit').

Frequently asked