Capital Group Technical

Question 1

What is a tree?

Answer 1

A hierarchical data structure made of nodes, with one root and child nodes.

Question 2

What does each node have?

Answer 2

a value and references to children

Question 3

What is a binary tree?

Answer 3

A tree where each node has at most two children: left and right.

Question 4

What is a root?

Answer 4

top node

Question 5

What is a leaf?

Answer 5

node with no children

Question 6

What is depth/height?

Answer 6

distance from root

Question 7

What is a subtree?

Answer 7

a node + its descendants

Question 8

What is DFS?

Answer 8

depth first search - go as deep as possible before backing up

Question 9

What is DFS used for?

Answer 9

searching, counting nodes, checking properties recursively

Question 10

What is preorder?

Answer 10

node -> left -> right

Question 11

What is inorder?

Answer 11

left -> node -> right

Question 12

What is postorder?

Answer 12

left -> right -> node

Question 13

What is the usual DFS skeleton?

Answer 13

def dfs(node):
if not node:
return

dfs(node.left)
dfs(node.right)

Question 14

What is BFS?

Answer 14

breadth first search - visit nodes level by level

Question 15

What is BFS used for?

Answer 15

shortest path, level order traversal, nearest/minimum depth problems

Question 16

What is the skeleton for BFS?

Answer 16

from collections import deque

queue = deque([root])

while queue:
node = queue.popleft()

 if node.left:
        queue.append(node.left)
 if node.right:
        queue.append(node.right)

Question 17

How do you explain the difference between DFS vs BFS?

Answer 17

DFS goes deep first using recursion or a stack, while BFS explores level by level using a queue

Question 18

What is a heap?

Answer 18

a special data structure where you can quickly get the min or max element

Question 19

What is a min heap?

Answer 19

smallest value on top

Question 20

What is a max heap?

Answer 20

largest value on top

Question 21

When are heaps used?

Answer 21

you need the top K elements, you need fast access to min/max repeatedly

Question 22

What is the syntax for heap in python?

Answer 22

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)

smallest = heapq.heappop(heap)

Question 23

What is the time complexity for heaps?

Answer 23

O(log n) insert and remove

Question 24

What are arrays usually used for?

Answer 24

scan once, track min/max, sliding window, two pointers

Question 25

What is an example skeleton for arrays?

Answer 25

max_val = float('-inf') for num in nums: max_val = max(max_val, num)

Question 26

What is the basic idea around DFS?

Answer 26

Process node, then recursively visit left and right children.

Question 27

What is the basic idea of BFS?

Answer 27

Visit node, add children to a queue, process in order.

Question 28

What is the maximum depth of binary tree leetcode problem?

Answer 28

def maxDepth(root): if not root: return 0 return 1 + max(maxDepth(root.left), maxDepth(root.right))

Question 29

What is the invert binary tree leetcode problem?

Answer 29

def invertTree(root): if not root: return None root.left, root.right = root.right, root.left invertTree(root.left) invertTree(root.right) return root

Question 30

What is the leetcode problem from binary tree level order traversal?

Answer 30

from collections import deque def levelOrder(root): if not root: return [] result = [] queue = deque([root]) while queue: level = [] for _ in range(len(queue)): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result

Question 31

What is the leetcode problem for same tree?

Answer 31

check if two binary trees are identical def isSameTree(p, q): if not p and not q: return True if not p or not q: return False if p.val != q.val: return False return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Question 32

What is the leetcode problem for validate binary search tree?

Answer 32

def isValidBST(root): def helper(node, low, high): if not node: return True if not (low < node.val < high): return False return helper(node.left, low, node.val) and helper(node.right, node.val, high) return helper(root, float('-inf'), float('inf'))

Question 33

What is the leetcode problem for kth largest element in an array?

Answer 33

import heapq def findKthLargest(nums, k): heap = [] for num in nums: heapq.heappush(heap, num) if len(heap) > k: heapq.heappop(heap) return heap[0]

Question 34

What is the leetcode problem for top k frequent elements

Answer 34

import heapq from collections import Counter def topKFrequent(nums, k): count = Counter(nums) heap = [] for num, freq in count.items(): heapq.heappush(heap, (freq, num)) if len(heap) > k: heapq.heappop(heap) return [num for freq, num in heap]

Question 35

What is the leetcode problem for two sum?

Answer 35

def twoSum(nums, target): seen = {} for i, num in enumerate(nums): diff = target - num if diff in seen: return [seen[diff], i] seen[num] = i

Question 36

What is the leetcode problem for maximum subarray?

Answer 36

def maxSubArray(nums): current = best = nums[0] for num in nums[1:]: current = max(num, current + num) best = max(best, current) return best

Question 37

What is the leetcode problem for best time to buy and sell stock?

Answer 37

def maxProfit(prices): min_price = float('inf') max_profit = 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit

Question 38

What is the leetcode problem for contains duplicate?

Answer 38

def containsDuplicate(nums): return len(nums) != len(set(nums))

Question 39

What is the leetcode problem for product of an array except self?

Answer 39

def productExceptSelf(nums): res = [1] * len(nums) prefix = 1 for i in range(len(nums)): res[i] = prefix prefix *= nums[i] suffix = 1 for i in range(len(nums) - 1, -1, -1): res[i] *= suffix suffix *= nums[i] return res