Google is known for its challenging interview process, especially when it comes to software engineering and algorithmic roles. While the exact questions asked can vary and evolve over time, here are some example questions that might be representative of the type of problems you could encounter:
1. Array and Strings
Question 1: Given an array of integers, find two numbers such that they add up to a specific target number.
Answer:
def two_sum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hashmap:
return [hashmap[complement], i]
hashmap[num] = i
Explanation: This solution uses a hash map to store numbers and their indices. For each number, it checks if the complement (target – current number) exists in the hash map. If it does, we have our two numbers.
Question 2: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
Answer:
def has_unique_chars(s):
return len(s) == len(set(s))
Explanation: This solution uses a set to keep track of unique characters. If the length of the string and the set are the same, all characters are unique.
2. Linked Lists
Question 1: Detect a cycle in a linked list.
Answer:
def has_cycle(head):
slow, fast = head, head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast:
return True
return False
Explanation: This solution uses the “two-pointer” or “hare and tortoise” approach. If there’s a cycle, the fast and slow pointers will eventually meet.
Question 2: Merge two sorted linked lists:
Answer:
def merge_two_lists(l1, l2):
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next, l1 = l1, l1.next
else:
current.next, l2 = l2, l2.next
current = current.next
current.next = l1 or l2
return dummy.next
Explanation: We iterate through the lists, adding the smaller current node to the merged list, and advancing the pointer of the list from which we took the node.
3. Trees and Graphs
Question 1: Check if a binary tree is balanced:
Answer:
def is_balanced(root):
def height(node):
if not node:
return 0
left, right = height(node.left), height(node.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return height(root) != -1
Explanation: A helper function computes the height of the tree. If the left or right subtree is unbalanced or the difference in their heights is more than 1, the tree is unbalanced
Question 2: Implement a function to check if a tree is a subtree of another tree.
Answer:
def is_subtree(s, t):
if not s:
return False
if is_same_tree(s, t):
return True
return is_subtree(s.left, t) or is_subtree(s.right, t)
def is_same_tree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return p.val == q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
Explanation: The main function checks if two trees are the same or if one tree is a subtree of the left or right subtree of the other.
4. Recursion and Dynamic Programming
Question 1: Write a method to generate the nth Fibonacci number.
Answer:
def fibonacci(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
Explanation: This iterative solution uses two variables to keep track of the two most recent Fibonacci numbers.
Question 2: Implement the “coin change” problem: Given an infinite number of quarters, dimes, nickels, and pennies, write code to calculate the number of ways of representing n cents.
Answer:
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Explanation: This dynamic programming solution initializes a dp array to represent the minimum coins needed for each amount. It updates the dp array for each coin and each amount.
5. Sorting and Searching
Question 1: Implement a binary search for a sorted array.
Answer:
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Question 2: Sort an array of strings so that all anagrams are next to each other.
Answer:
def group_anagrams(strs):
d = {}
for s in strs:
key = tuple(sorted(s))
d[key] = d.get(key, []) + [s]
return list(d.values())
6. Design Problems:
Question 1: Design a cache system.
Question 2: Design a system like Twitter with basic functionalities like posting tweets, following/unfollowing users, etc.
7. System Related:
Question 1: How would you design a distributed system?
Question 2: Explain the concept of sharding and its importance in large-scale applications.
