UK Big Tech Interview Guide: FAANG-Level Preparation Strategies

def two_sum(nums, target):
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
return []
. Valid Palindrome
Question: Given a string, determine if it is a palindrome, considering only
alphanumeric characters and ignoring cases.
Solution:
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
. Longest Substring Without Repeating Characters
Question: Given a string s, find the length of the longest substring without repeating
characters.
Solution:
def length_of_longest_substring(s):
char_map = {}
start = 0
max_length = 0
for end, char in enumerate(s):
if char in char_map and char_map[char] >= start:
start = char_map[char] + 1
char_map[char] = end
max_length = max(max_length, end - start + 1)
return max_length
. Product of Array Except Self
Question: Given an integer array nums, return an array answer such that answer[i]
is equal to the product of all the elements of nums except nums[i].
Solution:
def product_except_self(nums):
n = len(nums)
answer = [1] * n
left_product = 1
for i in range(n):
answer[i] = left_product
left_product *= nums[i]
right_product = 1
for i in range(n - 1, -1, -1):
answer[i] *= right_product
right_product *= nums[i]
return answer
Linked Lists
. Reverse Linked List
Question: Given the head of a singly linked list, reverse the list, and return the
reversed list.
Solution:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
. Merge Two Sorted Lists
Question: You are given the heads of two sorted linked lists list1 and list2 . Merge
the two lists into one sorted list.
Solution:
def merge_two_lists(list1, list2):
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
elif list2:
tail.next = list2
return dummy.next
. Linked List Cycle
Question: Given head, the head of a linked list, determine if the linked list has a cycle
in it.
Solution:
def has_cycle(head):
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
. Copy List with Random Pointer
Question: A linked list of length n is given such that each node contains an additional
random pointer, which could point to any node in the list, or null. Construct a deep
copy of the list.
Solution:
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
def copy_random_list(head):
if not head:
return None
curr = head
while curr:
new_node = Node(curr.val, curr.next)
curr.next = new_node
curr = new_node.next
curr = head
while curr:
if curr.random:
curr.next.random = curr.random.next
curr = curr.next.next
old_head = head
new_head = head.next
curr_old = old_head
curr_new = new_head
while curr_old:
curr_old.next = curr_old.next.next
curr_new.next = curr_new.next.next if curr_new.next else None
curr_old = curr_old.next
curr_new = curr_new.next
return new_head
Trees and Graphs
. Maximum Depth of Binary Tree
Question: Given the root of a binary tree, return its maximum depth.
Solution:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
. Invert Binary Tree
Question: Given the root of a binary tree, invert the tree, and return its root.
Solution:
def invert_tree(root):
if not root:
return None
root.left, root.right = root.right, root.left
invert_tree(root.left)
invert_tree(root.right)
return root
. Number of Islands
Question: Given an m x n D binary grid grid which represents a map of \\'1\\'s
(land) and\‘\’s (water), return the number of islands.
Solution:
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
num_islands = 0
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
num_islands += 1
dfs(r, c)
return num_islands
. Course Schedule
Question: There are a total of numCourses courses you have to take, labeled from 0
to numCourses - 1 . You are given an array prerequisites where prerequisites[i]
= [ai, bi] indicates that you must take course bi first if you want to take course
ai . Return true if you can finish all courses. Otherwise, return false .
Solution:
def can_finish(numCourses, prerequisites):
adj = {i: [] for i in range(numCourses)}
for crs, pre in prerequisites:
adj[crs].append(pre)
visiting = set()
def dfs(crs):
if crs in visiting:
return False
if adj[crs] == []:
return True
visiting.add(crs)
for pre in adj[crs]:
if not dfs(pre):
return False
visiting.remove(crs)
adj[crs] = []
return True
for crs in range(numCourses):
if not dfs(crs):
return False
return True
. Validate Binary Search Tree
Question: Given the root of a binary tree, determine if it is a valid binary search tree
(BST).
Solution:
def is_valid_bst(root):
def is_valid(node, min_val, max_val):
if not node:
return True
if not (min_val < node.val < max_val):
return False
return is_valid(node.left, min_val, node.val) and
is_valid(node.right, node.val, max_val)
return is_valid(root, float('-inf'), float('inf'))
. Lowest Common Ancestor of a Binary Search Tree
Question: Given a binary search tree (BST), find the lowest common ancestor (LCA) of
two given nodes in the BST.
Solution:
def lowest_common_ancestor(root, p, q):
curr = root
while curr:
if p.val > curr.val and q.val > curr.val:
curr = curr.right
elif p.val < curr.val and q.val < curr.val:
curr = curr.left
else:
return curr
Heaps and Priority Queues
. Kth Largest Element in an Array
Question: Given an integer array nums and an integer k, return the kth largest
element in the array.
Solution:
import heapq
def find_kth_largest(nums, k):
min_heap = []
for num in nums:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif num > min_heap[0]:
heapq.heapreplace(min_heap, num)
return min_heap[0]
. Merge k Sorted Lists
Question: You are given an array of k linked-lists lists , each linked-list is sorted in
ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Solution:
import heapq
def merge_k_lists(lists):
min_heap = []
for i, l in enumerate(lists):
if l:
heapq.heappush(min_heap, (l.val, i, l))
dummy = ListNode()
tail = dummy
while min_heap:
val, i, node = heapq.heappop(min_heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(min_heap, (node.next.val, i, node.next))
return dummy.next
. Find Median from Data Stream
Question: Design a data structure that supports adding new numbers and finding the
median of all numbers added so far.
Solution:
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max-heap
self.large = [] # min-heap
def addNum(self, num):
heapq.heappush(self.small, -1 * num)
if (self.small and self.large and (-1 * self.small[0]) >
self.large[0]):
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.small) > len(self.large) + 1:
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -1 * val)
def findMedian(self):
if len(self.small) > len(self.large):
return -1 * self.small[0]
if len(self.large) > len(self.small):
return self.large[0]
return (-1 * self.small[0] + self.large[0]) / 2.0
Dynamic Programming
. Climbing Stairs
Question: You are climbing a staircase. It takes n steps to reach the top. Each time
you can either climb  or  steps. In how many distinct ways can you climb to the top?
Solution:
def climb_stairs(n):
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
. Coin Change
Question: You are given an integer array coins and an integer amount . Return the
fewest number of coins that you need to make up that amount.
Solution:
def coin_change(coins, amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if a - c >= 0:
dp[a] = min(dp[a], 1 + dp[a - c])
return dp[amount] if dp[amount] != amount + 1 else -1
. Longest Increasing Subsequence
Question: Given an integer array nums, return the length of the longest strictly
increasing subsequence.
Solution:
def length_of_lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], 1 + dp[j])
return max(dp)
. Word Break
Question: Given a string s and a dictionary of strings wordDict , return true if s
can be segmented into a space-separated sequence of one or more dictionary words.
Solution:
def word_break(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
Sorting and Searching
. Merge Intervals
Question: Given an array of intervals , merge all overlapping intervals.
Solution:
def merge(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for i in range(1, len(intervals)):
last_merged = merged[-1]
current = intervals[i]
if current[0] <= last_merged[1]:
last_merged[1] = max(last_merged[1], current[1])
else:
merged.append(current)
return merged
. Search in Rotated Sorted Array
Question: Given a rotated sorted array, search for a target value.
Solution:
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if target > nums[mid] or target < nums[left]:
left = mid + 1
else:
right = mid - 1
else:
if target < nums[mid] or target > nums[right]:
right = mid - 1
else:
left = mid + 1
return -1
. Find First and Last Position of Element in Sorted Array
Question: Given a sorted array, find the starting and ending position of a given
target value.
Solution:
def search_range(nums, target):
def find_bound(is_first):
left, right = 0, len(nums) - 1
bound = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
bound = mid
if is_first:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return bound
left_bound = find_bound(True)
if left_bound == -1:
return [-1, -1]
right_bound = find_bound(False)
return [left_bound, right_bound]
System Design
. Design a URL Shortener (like TinyURL)
Question: Design a service that takes a long URL and returns a short, unique URL.
Solution: See detailed explanation in the previous turn.
. Design a News Feed System (like Facebook or Twitter)
Question: Design the backend for a news feed system.
Solution: See detailed explanation in the previous turn.
. Design a Typeahead Suggestion Service (like Google Search)
Question: Design a service that provides typeahead suggestions.
Solution: See detailed explanation in the previous turn.
. Design a Distributed Key-Value Store (like DynamoDB)
Question: Design a distributed key-value store.
Solution: See detailed explanation in the previous turn.
Behavioral Questions
. Tell me about a time you had a conflict with a coworker.
Question: This question assesses your ability to handle interpersonal conflicts and
work effectively in a team.
Solution: Use the STAR method to structure your answer.
. Tell me about a time you failed.
Question: This question is designed to assess your self-awareness, resilience, and
ability to learn from your mistakes.
Solution: Use the STAR method to structure your answer.