Google Python Developer Interview Questions & Answers

I use a write pointer to track the next position for a nonzero value. I scan the array from left to right. When I find a nonzero value, I copy it to the write position and move the pointer forward. After the scan, I fill every remaining position with zero. This keeps the nonzero values in their original order. The time complexity is O(n), and the auxiliary space complexity is O(1).

The task is to move every zero to the end of the array while keeping the nonzero values in the same relative order. I use an in-place write-pointer method. A read index checks each value. The write pointer marks where the next nonzero value should go. After all nonzero values are placed, the remaining positions are filled with zeros.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is an array of integers. In the example, the input is [0, 1, 0, 3, 12, 0, 5, 0].

The required output is [1, 3, 12, 5, 0, 0, 0, 0].

The nonzero values must remain in their original relative order. The array is modified in place, and the function returns that modified array.

I use a variable named write. It stores the index where the next nonzero value should be placed.

The central invariant is that every position before write contains the nonzero values seen so far, in their original order.

This method fits the problem because it preserves order and uses only constant extra memory.

I start with write = 0.

This means that no nonzero values have been placed yet. The first nonzero value should be written at index 0.

I then scan the array from left to right using index i.

Start with nums = [0, 1, 0, 3, 12, 0, 5, 0] and write = 0.

At i = 0, nums[i] is 0. I skip it. The array stays [0, 1, 0, 3, 12, 0, 5, 0], and write stays 0.

At i = 1, nums[i] is 1. It is nonzero. I write 1 at nums[0]. The array becomes [1, 1, 0, 3, 12, 0, 5, 0]. Then write becomes 1.

At i = 2, nums[i] is 0. I skip it. The array stays [1, 1, 0, 3, 12, 0, 5, 0], and write stays 1.

At i = 3, nums[i] is 3. It is nonzero. I write 3 at nums[1]. The array becomes [1, 3, 0, 3, 12, 0, 5, 0]. Then write becomes 2.

At i = 4, nums[i] is 12. It is nonzero. I write 12 at nums[2]. The array becomes [1, 3, 12, 3, 12, 0, 5, 0]. Then write becomes 3.

At i = 5, nums[i] is 0. I skip it. The array stays [1, 3, 12, 3, 12, 0, 5, 0], and write stays 3.

At i = 6, nums[i] is 5. It is nonzero. I write 5 at nums[3]. The array becomes [1, 3, 12, 5, 12, 0, 5, 0]. Then write becomes 4.

At i = 7, nums[i] is 0. I skip it. The array stays [1, 3, 12, 5, 12, 0, 5, 0], and write stays 4.

The first scan is complete. I fill indices 4 through 7 with zero. The final array is [1, 3, 12, 5, 0, 0, 0, 0].

Every nonzero value is copied in the same order in which it appears in the input.

The write pointer always marks the next free position for a nonzero value. Therefore, the positions before write contain exactly the nonzero values seen so far, in stable order.

After the scan, every remaining position is filled with zero. This places all zeros at the end without changing the relative order of the nonzero values.

The first loop reads each element. When the current value is nonzero, the code copies it to nums[write] and increases write.

The second loop starts at write and sets every remaining position to zero.

Finally, the function returns the modified array.

The first loop scans n elements. The second loop fills at most n remaining positions. The total time complexity is O(n).

The algorithm uses only a few variables, so the auxiliary space complexity is O(1).

Important edge cases include an array containing only zeros, an array containing no zeros, a single zero, a single nonzero value, and zeros already grouped at the end.

The key idea is to separate reading from writing. The read index examines every element from left to right. The write index marks the next position where a nonzero value belongs. When a nonzero value is found, it is copied to nums[write], and write moves forward. The invariant is that every position before write contains all nonzero values seen so far in their original order. After the scan, every position from write to the end is set to zero. This preserves stable nonzero ordering and modifies the array in place.

Let n be the length of the array. The algorithm takes O(n) time. The first loop reads each array element once. The second loop fills the remaining positions with zeros. Together, the work is still linear. The auxiliary space is O(1). Auxiliary space means extra memory used by the algorithm. Only the write index, loop variables, and the array length are stored. No extra array grows with the input.

A common mistake is swapping zeros with later values in a way that changes the relative order of the nonzero values. Another mistake is increasing write when the current value is zero. Some candidates forget the second loop, so old values remain after the nonzero section. Another mistake is creating a second array and then claiming O(1) auxiliary space. Candidates may also use pointer updates in the wrong order and overwrite a value before it has been read.

State the invariant before coding: every index before write already contains the nonzero values seen so far in their original order.

I would use a min heap that stores one current value from each sorted list. Each heap entry contains the value, the list index, and the value’s position in that list. I also track the largest active value. The heap minimum and that largest value form a range covering every list. I update the best range, then advance only the list that supplied the minimum. I stop when that list is exhausted. The time is O(N log k), with O(k) auxiliary space.

The input contains k sorted integer lists. We must return the inclusive range with the smallest width that contains at least one value from every list. If two ranges have the same width, we choose the one with the smaller start. A min heap fits this problem because it gives us the smallest active value while current_max tracks the largest active value.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a list of sorted integer lists. The output is a two-value list, [start, end].

The returned range must contain at least one value from every input list.

For the example:

L0 = [4, 10, 15, 24, 26] L1 = [0, 9, 12, 20] L2 = [5, 18, 22, 30]

The answer is [20, 24]. It contains 24 from L0, 20 from L1, and 22 from L2. Its width is 24 - 20 = 4.

I use a min heap. Python heapq implements a min heap, so the smallest stored value is available at the top.

Each heap entry stores:

(value, list_index, element_index)

The heap contains one current candidate from each list. I also keep current_max, which is the largest value among those current candidates.

The central invariant is: while the heap contains one value from every list, [heap_min, current_max] is a valid range covering all lists.

Push the first value from each list into the heap:

(4, L0, i0) (0, L1, i0) (5, L2, i0)

The smallest value is 0. The largest active value is 5, so current_max = 5.

The initial best range is [0, 5]. Its width is 5.

Step 1 pops (0, L1, i0). The current range is [0, 5]. We push 9 from L1. current_max becomes 9. The best range remains [0, 5].

Step 2 pops (4, L0, i0). The current range is [4, 9]. We push 10 from L0. current_max becomes 10. The best range remains [0, 5].

Step 3 pops (5, L2, i0). The current range is [5, 10]. We push 18 from L2. current_max becomes 18. The best range remains [0, 5].

Step 4 pops (9, L1, i1). The current range is [9, 18]. We push 12 from L1. current_max stays 18. The best range remains [0, 5].

Step 5 pops (10, L0, i1). The current range is [10, 18]. We push 15 from L0. current_max stays 18. The best range remains [0, 5].

Step 6 pops (12, L1, i2). The current range is [12, 18]. We push 20 from L1. current_max becomes 20. The best range remains [0, 5].

Step 7 pops (15, L0, i2). The current range is [15, 20]. We push 24 from L0. current_max becomes 24. The best range remains [0, 5].

Step 8 pops (18, L2, i1). The current range is [18, 24]. We push 22 from L2. current_max stays 24. The best range remains [0, 5].

Step 9 pops (20, L1, i3). The current range is [20, 24]. Its width is 4, which is smaller than the previous best width of 5. We update the best range to [20, 24].

L1 has no next value after 20. We stop because a later range could not contain a value from every list.

At every active step, the heap contains one current value from each list. Therefore, the smallest heap value and current_max define a range covering every list.

The smallest value controls the left boundary. Advancing a different list would leave that same minimum in the heap. It could not improve the left boundary. Therefore, advancing only the list that supplied the minimum is the correct move.

When that list is exhausted, complete coverage is no longer possible. The best range already found must be the answer.

The code first pushes the first value from every list into the min heap. It updates current_max during this initialization.

It sets the initial best range to [min_heap[0][0], current_max].

In each loop, it pops the smallest active value. It checks whether the current range is narrower than the best range. If the widths are equal, it chooses the smaller start.

It then moves to the next value in the same list. If that list has no next value, the loop stops. Otherwise, the code pushes the next value and updates current_max.

The function returns [best_left, best_right].

Let N be the total number of values across all lists. Let k be the number of lists.

Each value can be pushed into and popped from a heap whose size is at most k. Each heap operation takes O(log k) time. The total time is O(N log k).

The heap stores at most one current value from each list, so the auxiliary space is O(k).

Relevant edge cases include duplicate values across lists, negative numbers, lists with different lengths, a list containing only one element, and equal-width ranges that require the smaller-start tie-break.

The key insight is to keep one active value from every sorted list. A min heap exposes the smallest active value, while current_max stores the largest active value. Together, they define a valid covering range. The invariant is that the heap contains one current candidate from each list until one list is exhausted. After checking the current range, we advance only the list that supplied the minimum because that is the only move that can improve the left boundary while keeping the other current candidates.

Let N be the total number of values in all lists, and let k be the number of lists. Each value may be pushed into and popped from a heap of size at most k. Each push or pop costs O(log k), so the total time is O(N log k). The heap stores one active value from each list, so the auxiliary space is O(k). Auxiliary space means the extra memory used by the algorithm.

Common mistakes are advancing every list instead of only the list that supplied the minimum, checking exhaustion before updating the best range, forgetting to track current_max, and omitting the smaller-start tie-break. Another mistake is storing only values in the heap without the list index and element index needed to advance the correct list. Candidates may also claim O(N) time even though each heap operation costs O(log k).

State the invariant before writing code: the heap contains one active value from every list, so the heap minimum and current_max always define a valid covering range.

I would first traverse the tree and store each node’s parent. Then I would run breadth-first search from the target node. For every node, I check its left child, right child, and parent. A visited set prevents the search from moving back and forth between the same nodes. BFS processes the tree one distance level at a time, so when the distance reaches K, the queue contains the answer. The solution takes O(n) time and O(n) auxiliary space.

The problem asks us to return the values of all nodes exactly K edges from a given target node. A normal binary-tree node only points to its children, but a valid path may also move through its parent. I first build parent links for every node. I then run level-order BFS from the target, treating children and the parent as neighboring nodes.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The inputs are the tree root, a reference to the target node, and an integer k.

The output is a list of node values. Every returned node must be exactly k edges from the target.

In the example, the target node has value 5 and k is 2. One valid result is [7, 4, 1]. The output order is not required to be unique.

Tree nodes already point to their left and right children. They do not normally point to their parents.

I traverse the tree once with DFS. For each node, I store a mapping from that node reference to its parent reference.

For example, node 5 maps to parent 3. Node 2 maps to parent 5. Nodes 7 and 4 map to parent 2.

After this step, each node can have up to three neighbors: its left child, its right child, and its parent.

The initial queue is [5]. The initial visited set is {5}. The current distance is 0.

The visited set stores node references, not node values. This matters because different nodes may contain the same value.

The main invariant is: at the start of each BFS level, every node in the queue is exactly the current distance from the target.

At distance 0, the queue is [5].

We process node 5. Its unvisited neighbors are node 6, node 2, and parent node 3. We add them to the queue and visited set.

The next queue is [6, 2, 3]. These nodes are one edge from the target.

At distance 1, we process nodes 6, 2, and 3.

Node 6 adds nothing because node 5 is already visited.

Node 2 adds nodes 7 and 4. Its parent, node 5, is already visited.

Node 3 adds node 1. Node 5 is already visited.

The next queue is [7, 4, 1]. These nodes are two edges from the target.

Now distance equals k, so these nodes are not processed further. We return their values: [7, 4, 1].

The paths are 5 to 2 to 7, 5 to 2 to 4, and 5 to 3 to 1. Each path has exactly two edges.

The parent map lets the search move through every valid tree connection. The visited set prevents a node from being discovered more than once.

BFS processes nodes in increasing distance order. The first queue contains nodes at distance

1. The next queue contains nodes at distance
2. The following queue contains nodes at distance 2.

Therefore, when the current distance equals k, the queue contains exactly the nodes that are k edges from the target.

The build_parents function performs DFS and stores each node’s parent.

The deque stores the current BFS frontier. The visited set stores nodes that have already been discovered.

At the start of every BFS level, the code checks whether distance equals k. If it does, it returns the values currently in the queue.

Otherwise, the code processes exactly len(queue) nodes. This keeps the current BFS level separate from the next level.

For each node, it examines the left child, right child, and parent. It marks an unvisited neighbor before adding it to the queue.

Building the parent map takes O(n) time. BFS also visits each node at most once, so the total time is O(n).

The parent map, visited set, and queue can each use O(n) memory. The recursive DFS call stack uses O(h), where h is the tree height. The total auxiliary space is O(n).

If k is 0, the result is [target.val]. The target may be the root. A skewed tree still works. If no node exists at distance k, the function returns an empty list.

The key idea is to make upward movement possible. I first build a map from each node reference to its parent reference. This makes the tree behave like an undirected graph. I then run BFS from the target. The queue processes nodes one distance level at a time. The central invariant is that every node in the queue at the start of a level is exactly the current distance from the target. Therefore, when the distance reaches k, the queue contains the complete answer.

Let n be the number of nodes and h be the tree height. Building the parent map visits every node once, which takes O(n) time. BFS also visits each node at most once, so it takes O(n) time. The parent map, visited set, and BFS queue can use O(n) extra memory. The recursive DFS call stack uses O(h) memory. Because h can be as large as n, the total auxiliary space is O(n).

A common mistake is searching only through left and right children. This misses paths that move through a parent. Another mistake is forgetting the visited set, which can make the search move repeatedly between a child and its parent. Candidates may also increase the distance after each node instead of after one full BFS level. Marking nodes visited only after removing them from the queue can add duplicates. Using node values instead of node references in the visited set is also unsafe when duplicate values exist. Finally, the auxiliary space is O(n), not O(1).

Before writing code, say this invariant clearly: at the start of each BFS level, every node in the queue is exactly the current distance from the target. This makes the stopping condition and level updates easy to explain.

I assign each node a row and column. The root starts at row 0, column 0. I use BFS with a queue, so I visit nodes level by level. For each node, I store its pair of row and value in a map keyed by column. After traversal, I process columns from left to right and sort each column by row, then by value for ties. The time complexity is O(n log n), and the auxiliary space complexity is O(n).

The problem asks us to group tree nodes by their horizontal position. Each vertical column becomes one list in the result. Inside a column, nodes are ordered from top to bottom. When two nodes have the same row and column, the smaller value comes first. The diagram uses BFS, a queue, and a map from column to a list of row and value pairs.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The root starts at row 0 and column 0.

For a node at row r and column c:

• Its left child is at row r + 1 and column c - 1.
• Its right child is at row r + 1 and column c + 1.

The row tells us the vertical level. The column tells us the horizontal position.

I use a queue for BFS. BFS means breadth-first search. It processes the tree level by level.

Each queue item stores three values:

• the node reference
• its row
• its column

I also use a map called col_table. Its key is a column number. Its value is a list of pairs in the form row and node value.

The main invariant is that every visited node is stored in the list for its correct column with its correct row.

The queue starts with the root:

[(3, 0, 0)]

The column map starts empty.

The minimum and maximum columns both start at 0.

These bounds help us later read the columns from left to right.

The tree is:

• Root 3 at row 0, column 0.
• Left child 9 at row 1, column -1.
• Right child 20 at row 1, column 1.
• Node 20 has left child 15 at row 2, column 0.
• Node 20 has right child 7 at row 2, column 2.

Step 1:

The queue contains node 3 at row 0, column 0.

We remove 3 from the queue. We add the pair (0, 3) to column 0.

Then we add its children:

• 9 with row 1 and column -1
• 20 with row 1 and column 1

The queue becomes [(9, 1, -1), (20, 1, 1)].

Step 2:

We remove 9. We add (1, 9) to column -1.

Node 9 has no children.

The queue becomes [(20, 1, 1)].

Step 3:

We remove 20. We add (1, 20) to column 1.

Then we add its children:

• 15 with row 2 and column 0
• 7 with row 2 and column 2

The queue becomes [(15, 2, 0), (7, 2, 2)].

Step 4:

We remove 15. We add (2, 15) to column 0.

Node 15 has no children.

The queue becomes [(7, 2, 2)].

Step 5:

We remove 7. We add (2, 7) to column 2.

Node 7 has no children.

The queue becomes empty, so traversal stops.

The final map is:

• column -1: [(1, 9)]
• column 0: [(0, 3), (2, 15)]
• column 1: [(1, 20)]
• column 2: [(2, 7)]

We process columns from -1 to 2. Inside each column, we sort by row first and value second.

The final result is [[9], [3, 15], [20], [7]].

Every node receives a row and column based on its position from the root.

Every node is stored under its exact column.

Columns are read from the smallest column to the largest column, so the result goes from left to right.

Inside each column, sorting by row places higher nodes before lower nodes. Sorting by value after row resolves ties when two nodes share the same row and column.

Therefore, the output follows the required vertical traversal order.

The code uses deque so removing an item from the front is efficient.

The col_table dictionary groups nodes by column.

The BFS loop removes one node at a time, records it, and adds its children with updated row and column values.

After BFS, the code loops from min_col to max_col. It sorts each column list using row first and value second. It then keeps only the node values.

BFS visits each of the n nodes once, so traversal takes O(n) time.

Sorting all stored row and value pairs takes O(n log n) time in the worst case.

The total time complexity is O(n log n).

The queue and column map together store O(n) items, so the auxiliary space complexity is O(n).

Important edge cases are an empty tree, a single node, a skewed tree, and multiple nodes that share the same row and column.

The key idea is to give every node a coordinate. The row measures depth. The column measures horizontal position. BFS visits the tree level by level and stores each node as a pair of row and value inside a map keyed by column. The invariant is that every visited node is placed in the list for its exact column with its exact row. Reading columns from left to right and sorting each column by row, then value, produces the required order.

Let n be the number of nodes. BFS visits every node once, which takes O(n) time. The algorithm then sorts the stored row and value pairs. In the worst case, this sorting takes O(n log n) time. Therefore, the total time complexity is O(n log n). The queue and the column map can together hold O(n) items, so the auxiliary space complexity is O(n).

A common mistake is grouping by row instead of column. Another mistake is changing the left and right column updates. The left child must use column minus one, and the right child must use column plus one. Some candidates sort only by row and forget the value tie-breaker. Others return row and value pairs instead of returning only values. Using list.pop(0) as a queue is also slower than using deque.popleft(). Finally, claiming O(n) total time is incorrect because sorting can take O(n log n).

State the coordinate rule first: left means column minus one, right means column plus one, and every child moves to the next row. Then explain that the final sort uses the exact key (row, value).

I would use a stack because Reverse Polish notation gives the operands before each operator. I read the tokens from left to right. I push each integer onto the stack. For an operator, I pop the right operand first and then the left operand, calculate the result, and push it back. Division truncates toward zero. At the end, exactly one value must remain. The solution takes O(n) time and O(n) auxiliary space.

The input is a list of tokens containing integers and the operators "+", "-", "*", and "/". We must evaluate the expression and return one integer. A stack fits this problem because every operator uses the two most recent unfinished values. The stack keeps those values in the correct order.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The function receives a list of string tokens. A token is either an integer or a binary operator.

For the example, the input is ["4", "13", "5", "/", "+"]. The expected result is 6.

Division must truncate toward zero. For example, 13 divided by 5 becomes 2, and -13 divided by 5 becomes -2.

The expression is invalid when an operator does not have two operands, when an unsupported token appears, when division uses zero as the right operand, or when more than one value remains after processing.

A stack stores intermediate integer results. The top of the stack is the rightmost item.

The main invariant is this: after each valid token is processed, the stack contains exactly the intermediate results for that prefix of the expression, in evaluation order.

An integer creates a new intermediate result, so we push it. An operator combines the two most recent results, so we pop two values, calculate, and push one result.

Start with an empty stack.

Read the tokens from left to right. If a token is not one of the four operators, convert it to an integer and push it.

If the token is an operator, first check that the stack contains at least two values. Pop the right operand first. Then pop the left operand. This order matters for subtraction and division.

Start with stack [].

Token "4" is an integer. Push 4. The stack becomes [4].

Token "13" is an integer. Push 13. The stack becomes [4, 13].

Token "5" is an integer. Push 5. The stack becomes [4, 13, 5].

Token "/" is an operator. The stack has enough operands. Pop right = 5, then left = 13. Compute 13 divided by 5 with truncation toward zero. The result is 2. Push 2. The stack becomes [4, 2].

Token "+" is an operator. Pop right = 2, then left = 4. Compute 4 + 2 = 6. Push 6. The stack becomes [6].

All five tokens have been processed. Exactly one value remains, so the returned result is 6.

Python's // operator rounds negative results down, not toward zero. To avoid that problem, divide the absolute values first. Then restore the sign.

For example, abs(-13) // abs(5) is 2. Because the operands have different signs, the final value becomes -2.

Before division, reject a zero right operand. Before every operator, reject a stack with fewer than two values. After the loop, reject a stack whose size is not exactly one.

The invariant is true at the start because the empty stack represents an empty token prefix.

When an integer is read, pushing it adds the correct new intermediate value.

When an operator is read, the two top values are the two most recent unfinished results. Popping the right operand before the left operand preserves operand order. Replacing those two values with their calculated result keeps the invariant true.

Therefore, after all tokens are processed, the single remaining stack value is the value of the full expression.

Each token is processed once. Each push and pop takes constant time. The total time is O(n), where n is the number of tokens.

The stack can hold up to O(n) values, so the auxiliary space is O(n).

Important cases are negative numbers, truncating division toward zero, insufficient operands, leftover operands, unsupported tokens, and division by zero.

The key insight is that Reverse Polish notation always places an operator after its two operands. A stack keeps the unfinished values in exactly the order needed. Each stack entry represents one intermediate integer result. The central invariant is that after processing any valid prefix, the stack contains exactly the intermediate results for that prefix in evaluation order. Integers are pushed. Operators replace the top two values with one calculated value. Popping right before left preserves subtraction and division order.

Let n be the number of tokens. We read every token once. Each stack push and pop takes O(1) time, so the total time is O(n). The stack may contain many integers before operators reduce it. In the worst case, it can grow with the input size, so the auxiliary space is O(n). Auxiliary space means the extra memory used by the algorithm.

A common mistake is popping the left operand before the right operand. That gives the wrong result for subtraction and division. Another mistake is using left // right directly, because Python rounds negative division down instead of truncating toward zero. Candidates may also forget to check for division by zero, insufficient operands, unsupported tokens, or leftover operands. Another error is returning the top value without checking that it is the only remaining value.

State the stack invariant before coding: after each token, the stack contains the correct intermediate results for the processed prefix. Then clearly say that you pop the right operand first and the left operand second.

I scan the grid in row-major order. When I find a land cell that is not visited, I count one new island and start BFS from that cell. A deque stores cells that still need processing, and a visited set prevents the same land cell from being counted twice. Each completed BFS visits one whole four-directionally connected component. The solution takes O(rows × cols) expected time in Python and O(rows × cols) auxiliary space.

The input is a two-dimensional grid containing "1" for land and "0" for water. The output is the number of separate islands. Land cells belong to the same island only when they connect horizontally or vertically. Breadth-first search works well because it can visit one complete connected component before the main grid scan continues.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The input is a grid of strings.

A cell containing "1" is land. A cell containing "0" is water.

The function returns one integer. This integer is the number of connected islands.

Only four directions create a connection:

• Up: (-1, 0)
• Down: (1, 0)
• Left: (0, -1)
• Right: (0, 1)

Diagonal cells do not connect.

I scan the grid from left to right and from top to bottom. This is called row-major order.

When I find a land cell that is not visited, I have found the start of a new island. I increase the island count and start breadth-first search.

A deque works as the BFS queue. It stores land cells that still need to be processed.

The visited set stores coordinate pairs such as (1, 4). Each pair identifies one grid cell that has already been assigned to an island.

The central invariant is that every coordinate in visited is a land cell belonging to a discovered island.

If the grid is empty, the function returns 0.

Otherwise, I store the number of rows and columns.

I create an empty visited set.

I define the four direction changes.

I set islands to 0.

The grid scan begins at position (0, 0).

The example grid is:

[ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "1"], ["0", "0", "1", "0", "1"], ["0", "0", "0", "1", "1"] ]

The expected result is 3.

At (0, 0), the value is "1" and the cell is not visited. I increase islands from 0 to 1. I add (0, 0) to visited and place it in the queue.

I remove (0, 0) from the queue. Its new valid land neighbors are (1, 0) and (0, 1). I mark both visited and enqueue them.

I remove (1, 0). It discovers (1, 1), so I mark (1, 1) visited and enqueue it.

I remove (0, 1). It has no new unvisited land neighbor.

I remove (1, 1). It also has no new unvisited land neighbor. The queue becomes empty. The top-left 2 by 2 block is the first island.

The row-major scan continues until (1, 4). This cell contains unvisited land. I increase islands from 1 to 2, mark (1, 4) visited, and start another BFS.

The second BFS visits (1, 4), (2, 4), (3, 4), and (3, 3). These cells connect through horizontal or vertical edges. When the queue becomes empty, the second island is complete.

The scan later reaches (2, 2). It contains unvisited land. I increase islands from 2 to 3 and start the third BFS.

The third BFS visits only (2, 2). It has no four-directional land neighbor.

All remaining cells are water or already visited. The function returns 3.

Every unvisited land cell starts exactly one BFS.

That BFS reaches every land cell connected to its starting cell through the four allowed directions.

A cell is marked visited before it is added to the queue. This prevents duplicate queue entries and prevents the same land cell from starting another island search.

Therefore, each BFS counts exactly one island, and every island is counted exactly once.

The empty-grid check handles an input with no cells.

The nested loops scan every coordinate in row-major order.

The code skips water cells and land cells already in visited.

For each new land cell, it increases islands, creates a deque, and marks the starting cell visited.

The while loop removes one cell from the queue. It calculates the four neighboring coordinates. A neighbor is added only when it is inside the grid, contains "1", and is not visited.

After the full grid scan finishes, the function returns islands.

Let rows be the number of rows and cols be the number of columns.

The expected time complexity in Python is O(rows × cols). The main scan checks every grid position. Each discovered land cell also checks four neighbors. Set membership and insertion are O(1) on average.

The auxiliary space complexity is O(rows × cols). The visited set can contain every land cell, and the queue can also contain many cells in the worst case.

Relevant edge cases include an empty grid, all water, one land cell, one large island, and land cells that touch only diagonally.

Treat the grid as an unweighted graph. Each land cell is a node, and four-directional neighboring land cells have edges between them. Scan the grid in row-major order. Each unvisited land cell starts a new connected component, so increase the island count and run BFS from that cell. The deque stores cells that still need exploration. The visited set stores exact (row, column) coordinates already assigned to an island. The invariant is that visited contains only land cells belonging to discovered components. BFS visits all and only the cells in one island, so each completed BFS adds exactly one to the answer.

Let rows be the number of grid rows and cols be the number of columns. The solution takes O(rows × cols) expected time in Python. The outer loops check every cell. Each discovered land cell checks at most four neighbors. Membership checks and insertions in the Python set are O(1) on average. The auxiliary space is O(rows × cols). In the worst case, the visited set and BFS queue can both grow with the number of cells.

One mistake is treating diagonal land cells as connected, even though only four directions are allowed. Another is marking a cell visited after removing it from the queue, which may enqueue the same cell more than once. Candidates may also forget the empty-grid check, skip the boundary checks, or mix up row and column coordinates. Using list.pop(0) instead of deque.popleft() makes queue removal slower. It is also incorrect to claim constant auxiliary space because the visited set and queue can grow with the grid.

Before coding, state the invariant clearly: every coordinate in visited is land that has already been assigned to a discovered island. Then explain that each new unvisited land cell starts one BFS and increases the answer exactly once.

I would store every created path in a Python dictionary. The dictionary starts with the root path "/" mapped to None. For createPath, I reject an empty path, the root path, and duplicate paths. I then find the immediate parent and insert the new path only when that parent exists. The get method performs a direct lookup and returns -1 when the path is missing. createPath takes O(|path|) expected time, get takes O(1) average lookup time after hashing, and space grows with the stored path characters.

The problem asks us to build a small in-memory file system. We must create a path only when its immediate parent already exists. We must also return the integer stored for a path, or -1 when the path is missing. A Python dictionary is a good fit because it stores each complete path and supports fast lookup.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The class supports two operations.

createPath(path, value) tries to add a new path. It returns True when the path is created. It returns False when the path is empty, is the root path, already exists, or has a missing parent.

get(path) returns the stored integer value. It returns -1 when the path is not present.

The dictionary stores full path -> value.

I start with:

paths = {"/": None}

The root path already exists. It is a sentinel entry. A sentinel is a special starting value. Normal created paths store integers.

The invariant is that the dictionary contains exactly the paths that were created successfully.

Before finding the parent, createPath rejects three cases:

• The path is empty.
• The path is the root path "/".
• The path already exists.

Each case returns False without changing the dictionary.

Next, I use rfind("/") to locate the final slash.

For "/docs", the final slash is at index 0, so the parent is "/".

For "/docs/api", the parent is the substring before the final slash, which is "/docs".

If the parent is missing, createPath returns False. Otherwise, it stores the new path and returns True.

The initial state is:

{"/": None}

First, createPath("/docs", 5) checks parent "/". The parent exists, and "/docs" does not exist. We insert "/docs": 5. The result is True.

The state becomes:

{"/": None, "/docs": 5}

Next, createPath("/docs/api", 9) checks parent "/docs". The parent exists, and "/docs/api" does not exist. We insert "/docs/api": 9. The result is True.

The state becomes:

{"/": None, "/docs": 5, "/docs/api": 9}

Next, createPath("/tmp/logs", 7) checks parent "/tmp". That parent is missing. We do not insert anything. The result is False, and the state stays unchanged.

Then, get("/docs/api") finds the path and returns 9.

Finally, get("/tmp") does not find the path and returns -1.

The exact outputs are:

[True, True, False, 9, -1]

The final stored paths are "/docs" -> 5 and "/docs/api" -> 9. The path "/tmp/logs" was never created.

The dictionary starts with the sentinel root path.

A new non-root path is inserted only when the path does not already exist and its immediate parent is already stored. Therefore, every stored non-root path has a valid parent chain.

A failed createPath call leaves the dictionary unchanged.

The get method reads the same dictionary. It returns the exact stored integer for an existing path and -1 for a missing path.

The constructor creates the dictionary with the root entry.

createPath validates the path, finds the immediate parent, checks that parent, and inserts only after every check passes.

get uses self.paths.get(path, -1).

Finding the last slash and creating the parent substring take O(|path|) time. Python dictionary lookup and insertion are O(1) on average after hashing. Therefore, createPath takes O(|path|) expected time. get performs an O(1) average dictionary lookup after the path is hashed. Auxiliary space is O(total stored path characters).

Use a Python dictionary where each key is a complete path string and each value is the integer stored for that path. Add the root path "/" first as a sentinel mapped to None. Before inserting a new path, reject invalid or duplicate paths, extract the immediate parent, and verify that the parent already exists. The central invariant is that the dictionary contains exactly the paths that were created successfully. This is simpler than building a tree when the required operations are only full-path creation and full-path lookup.

Let |path| be the number of characters in the path. createPath takes O(|path|) expected time because it finds the last slash, creates the parent substring, and then uses Python dictionary operations that are O(1) on average. get performs an O(1) average dictionary lookup after Python hashes the path key. Auxiliary space is O(total stored path characters) because the dictionary keeps every successfully created full path and its value.

Common mistakes include inserting a child path without checking its immediate parent, allowing the root path to be created again, and allowing an existing path to be overwritten. Another mistake is extracting the wrong parent for a top-level path such as "/docs". Some candidates modify the dictionary before every validation check passes. Others return None instead of -1 for a missing path. It is also incorrect to describe Python dictionary operations as guaranteed O(1); they are O(1) on average.

State the invariant before writing code: the dictionary contains only successfully created paths, and every stored non-root path had an existing immediate parent when it was inserted.

I would use breadth-first search because every move has the same cost. Each queue state stores the row, column, and remaining obstacle eliminations. I process the queue level by level, so the first time I dequeue the destination, the current level is the minimum number of moves. I mark each full state as visited before enqueueing it. The time complexity is O(rows × cols × (k + 1)), and the auxiliary space complexity is the same.

The problem asks for the minimum number of moves from the top-left cell to the bottom-right cell. A cell with value 1 is an obstacle. We may enter it only when at least one elimination remains. Breadth-first search fits because each move costs one step. It explores all states at a smaller distance before states at a larger distance.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

A position alone is not enough. We must also know how many obstacle eliminations remain.

I represent each state as:

(row, column, remaining eliminations)

For example, (1, 0, 0) means that we are at row 1, column 0, and have no eliminations left.

The same cell may need to be explored again with a different remaining budget. Therefore, the visited set stores the complete state, not only the row and column.

The search starts at the top-left cell. The initial state is (0, 0, k).

For the example, k is 1. The initial queue is:

[(0, 0, 1)]

The visited set initially contains (0, 0, 1). The move count starts at 0.

Each breadth-first-search level represents one move.

For every state in the current level, I remove it from the front of the deque. If its row and column are the destination, I return the current move count.

Otherwise, I try four directions in this order: down, up, right, and left.

For each valid neighbor, I calculate:

next_remaining = remaining - grid[next_row][next_col]

An open cell has value 0, so the budget stays the same. An obstacle has value 1, so the budget decreases by 1.

I skip the neighbor when it is outside the grid, when next_remaining is negative, or when the exact new state has already been visited. Otherwise, I mark the state visited and add it to the queue.

The grid is [[0, 1, 0], [1, 1, 0], [0, 0, 0]], and k is 1. The expected result is 4.

At level 0, the queue contains (0, 0, 1). The reachable neighbors are (1, 0) and (0, 1). Both cells contain 1, so entering either one spends the only elimination. We enqueue (1, 0, 0) and (0, 1, 0).

At level 1, we process those two states. From (1, 0, 0), the open cell (2, 0) creates (2, 0, 0). Returning to the start creates the distinct state (0, 0, 0), because its remaining budget differs from the original state. From (0, 1, 0), the open cell (0, 2) creates (0, 2, 0).

At level 2, the useful frontier reaches (2, 1, 0) and (1, 2, 0).

At level 3, one of those states reaches the destination and enqueues (2, 2, 0).

At level 4, the destination state is removed from the queue. The algorithm stops and returns 4.

One valid shortest route is (0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2). It uses one obstacle elimination and finishes with budget 0.

Breadth-first search processes states in increasing move count. All states that need fewer moves are processed before states that need more moves.

The visited set includes the remaining budget. This prevents duplicate work without incorrectly merging states that have different future possibilities.

Because every move costs one step, the first time the destination is dequeued, the current level is the minimum possible number of moves.

The code uses collections.deque because removing an item from the front is efficient.

The outer while loop processes one BFS level. The inner loop processes every state that was already in that level.

A valid state is marked visited before it is added to the queue. This prevents the same full state from being enqueued repeatedly.

After the complete level is processed, the move count increases by 1. If the queue becomes empty before the destination is reached, the function returns -1.

There are rows × cols cells. Each cell may be paired with k + 1 possible remaining-budget values, from 0 through k.

Therefore, the time complexity is O(rows × cols × (k + 1)). The deque and visited set may also contain that many states, so the auxiliary space complexity is O(rows × cols × (k + 1)).

Important edge cases include a 1 × 1 grid, an exhausted elimination budget, reaching the same cell with a different remaining budget, and a grid where no valid route exists.

Use breadth-first search on an expanded state space. Each state is the triple (row, column, remaining eliminations). The queue processes these states in increasing distance order. The central invariant is that every queued state represents a reachable cell with an exact remaining budget, and the current BFS level equals the number of moves used to reach it. A visited set containing only row and column would be incorrect because reaching the same cell with more eliminations left can create different future paths.

Let rows be the number of rows and cols be the number of columns. A cell can be reached with k + 1 possible remaining-budget values, from 0 to k. This gives at most rows × cols × (k + 1) distinct states. Each state checks four neighbors, which is constant work. Therefore, the time complexity is O(rows × cols × (k + 1)). The deque and visited set may store the same number of states, so the auxiliary space complexity is also O(rows × cols × (k + 1)).

A common mistake is storing only (row, column) in the visited set. The remaining budget is part of the state. Another mistake is marking a state visited only after it is removed from the queue, which can create duplicate queue entries. Candidates may also forget to subtract the neighbor cell value, allow the remaining budget to become negative, increase the move count after every state instead of after every level, or claim O(rows × cols) space while ignoring the k + 1 possible budget values.

State the BFS invariant before coding: every queue item is a reachable (row, column, remaining budget) state, and every queue level represents one move. This makes the visited key, stopping condition, and complexity easier to explain.

I would use bottom-up dynamic programming. I create a table where dp[i][j] means the first i characters of the string match the first j characters of the pattern. Exact characters and '?' use the diagonal cell. A '*' uses the left cell to match nothing or the cell above to consume one more character. The final answer is dp[m][n]. This solution takes O(m × n) time and O(m × n) auxiliary space.

The problem asks whether the complete pattern matches the complete input string. The character '?' matches exactly one character. The character '*' matches an empty sequence or any number of characters. Dynamic programming fits because the answer for two prefixes depends on answers already calculated for smaller prefixes.

1. What input sizes, value ranges, and edge cases should the solution handle?
2. What output should be returned for empty, invalid, or duplicate input?
3. Should I prioritize execution time or memory use, and may I use the standard library?

The inputs are the string s and the pattern p. The function returns True only when the entire pattern matches the entire string.

Let m be the length of s and n be the length of p.

I define dp[i][j] to mean that the first i characters of s match the first j characters of p. The rows represent prefixes of s. The columns represent prefixes of p. The final answer is dp[m][n].

I create a Boolean table with m + 1 rows and n + 1 columns. Every cell starts as False.

I set dp[0][0] to True because an empty string matches an empty pattern.

Then I initialize the first row. A pattern prefix can match an empty string only when every character in that prefix is '*'. Therefore, when p[j - 1] is '*', I set dp[0][j] to dp[0][j - 1].

For p = "a*?de", dp[0][1] is False because 'a' cannot match an empty string. dp[0][2] is also False because the prefix "a*" still contains the required character 'a'.

I process i from 1 through m. Inside that loop, I process j from 1 through n.

If p[j - 1] equals s[i - 1], the current characters match. I copy the diagonal value dp[i - 1][j - 1].

If p[j - 1] is '?', it also consumes exactly one character from each input. I again copy dp[i - 1][j - 1].

If p[j - 1] is '*', there are two valid choices. The '*' can match an empty sequence, so I use dp[i][j - 1]. It can also consume one more character from s while remaining on the same pattern character, so I use dp[i - 1][j]. The cell is True when either dependency is True.

For every other mismatch, the cell remains False.

The example uses s = "abcde" and p = "a*?de". The expected result is True.

First, dp[1][1] becomes True. The character 'a' in the pattern matches the character 'a' in the string, so the value comes from dp[0][0].

Next, dp[1][2] becomes True. The pattern character is '*'. It can match an empty sequence after the first 'a', so the left dependency dp[1][1] makes this cell True.

Then dp[2][2] becomes True. The '*' consumes the character 'b'. This uses the value above, dp[1][2].

The table also records dp[2][3] as True because '?' can match 'b' after the '*' matches an empty sequence. This is a valid intermediate state, although it is not the final successful path.

The '*' can continue covering characters, so dp[3][2] is True. More importantly for the final match, dp[3][3] becomes True because '?' matches 'c' and uses dp[2][2]. On this successful path, '*' matches 'b' and '?' matches 'c'.

Next, 'd' matches 'd', so dp[4][4] becomes True from dp[3][3]. Finally, 'e' matches 'e', so dp[5][5] becomes True from dp[4][4].

The function returns True because dp[5][5] is True.

The invariant is that every cell dp[i][j] correctly states whether s[:i] matches p[:j].

An exact character and '?' both consume one character from the string and one character from the pattern. That is why they use the diagonal dependency.

A '*' has exactly two possibilities. It can match nothing, represented by the left cell. It can consume one more string character, represented by the cell above.

The base cases correctly handle empty prefixes. Every later cell uses smaller states that have already been solved. Therefore, dp[m][n] correctly answers whether the complete string matches the complete pattern.

The code creates the full DP table and sets dp[0][0] to True. It initializes the first row for pattern prefixes made entirely of leading '*'. It then fills the table from top to bottom and left to right. Exact matches and '?' use the diagonal cell. A '*' uses the left cell or the cell above. The code returns dp[m][n].

The table contains (m + 1) × (n + 1) cells. Each cell takes constant work. The time complexity is O(m × n).

The complete table uses O(m × n) auxiliary space.

Relevant edge cases include an empty string with an all-'*' pattern, an exact-character mismatch, '?' being unable to match an empty sequence, and '*' matching zero, one, or many characters.

The key insight is to solve the problem for smaller string and pattern prefixes before solving it for the complete inputs. The central invariant is that dp[i][j] correctly tells whether s[:i] matches p[:j]. Exact characters and '?' consume one character from both prefixes, so they use dp[i - 1][j - 1]. A '*' either matches an empty sequence and uses dp[i][j - 1], or consumes one more string character and uses dp[i - 1][j]. These transitions cover every valid wildcard behavior shown in the diagram.

Let m be the length of the string and n be the length of the pattern. The algorithm fills a table with (m + 1) × (n + 1) cells. Each cell takes constant work, so the time complexity is O(m × n). The table also uses memory that grows with both input lengths, so the auxiliary space complexity is O(m × n). Auxiliary space means extra memory used by the algorithm.

A common mistake is defining dp[i][j] without saying that i and j are prefix lengths. Another mistake is forgetting the first-row initialization for leading '*'. Candidates may use the wrong dependencies for '*'. The correct dependencies are the left cell and the cell above. It is also wrong to let '?' match zero or several characters. Finally, returning any True cell instead of dp[m][n] would allow a partial match instead of requiring the complete string and pattern to match.

Before writing code, state the meaning of dp[i][j] and draw the three dependencies. Say that an exact character or '?' moves diagonally, while '*' comes from the left or from above.

At a high level, I would expose one versioned public API for uploads, downloads, metadata, folders, sharing, permissions, and version history. The client sends HTTPS requests through the Public API Gateway and Version Router. The gateway checks the JWT through Auth and Identity, then routes each request to the correct API. Upload sessions track the next offset, Object Storage keeps file bytes, and the Metadata DB stores file details and permissions. Responses return through the gateway. The trade-off is more internal services, but each responsibility stays clear.

The goal is to provide one clear public API for a cloud file-storage service. The main challenge is supporting large uploads, permissions, versions, pagination, and older clients together. I would explain the design by following each request through the attached diagram.

1. Which clients and core use cases must the API support?
2. What authentication, authorization, and data-validation rules should I assume?
3. What scale, error handling, idempotency, and versioning requirements matter?

I would start with the Client App or SDK. It sends HTTPS REST requests across the trust boundary.

Every public request enters the Public API Gateway and Version Router. The gateway hides internal services from the client. It also routes /v1 and /v2 to stable contracts. This supports backward compatibility for older clients.

The gateway sends JWT validation to Auth and Identity. A JWT is a signed token that identifies the caller. Auth and Identity returns auth OK or 401. A 401 means authentication is missing or invalid.

The client begins with POST /v1/uploads. The gateway sends an initiate-upload request to the Resumable Upload API.

The upload API creates a session in the Upload Session Store. The session includes nextOffset, which shows where the next chunk must begin. The store returns the session state.

The upload API returns 201 uploadId + nextOffset to the gateway. The gateway then returns 201 Created or an error to the client.

This session lets a large upload continue after a temporary failure.

The client sends a chunk with PUT /v1/uploads/{id}/chunks. The gateway forwards it to the Resumable Upload API.

The upload API sends append chunk to Object Storage. Object Storage returns chunk stored. The upload API also sends update offset to the Upload Session Store. The store returns offset saved.

When the upload is finalized, the upload API commits file metadata and a new version to the Metadata DB. The database returns fileId + versionId.

The upload API then returns 200 nextOffset / complete through the gateway. The gateway sends the chunk response or retryable error back to the client.

The client calls GET /v1/files/{id}/download. The gateway routes the request to the Download API.

The Download API asks the Metadata DB to look up the file and latest version. The database returns the metadata and version.

The Download API then requests the file bytes from Object Storage. Object Storage returns the stream or a not-found result.

The Download API sends 200 stream or 404 to the gateway. The gateway returns the download response to the client.

The client uses GET/PATCH /files/{id}/metadata for file metadata. The gateway sends a metadata request to the Metadata and Folder API.

That API reads or writes metadata in the Metadata DB. The database returns metadata or paginated results. The API returns 200 metadata / paginated list through the gateway.

Folder operations use GET/POST /folders and GET /folders/{id}/children?pageToken=.... The pageToken identifies the next result page. The Metadata DB returns the folder tree and nextPageToken. The API returns the folder response through the gateway.

The client uses POST /shares and PATCH /permissions. The gateway sends the share or permission request to the Sharing and Permissions API.

That API stores ACLs, share links, and role bindings in the Metadata DB. An ACL is a list describing who may access a resource. The database returns the current ACL state.

The Sharing and Permissions API also sends a share event to Audit and Logs. Audit and Logs returns an acknowledgement. The API returns 200 share result or 403 through the gateway. A 403 means the caller is authenticated but not allowed.

The client calls GET /files/{id}/versions. The gateway sends a version request to the Version History API.

The Version History API sends read version history to Audit and Logs. Audit and Logs returns an acknowledgement. The Version History API then returns 200 versions / pageToken through the gateway.

The API uses consistent failures. 400 means a bad request. 401 means authentication failed. 403 means access is denied. 404 means a resource is missing. 409 means a version conflict. 429 means the rate limit was exceeded. Retryable server failures use 5xx.

The benefit is clear ownership. The downside is more services and data flows to operate.

The design separates upload sessions, file bytes, metadata, permissions, and logs. The benefit is that each component has one clear job. Object Storage is good for large file bytes. The Metadata DB is good for file details, folders, versions, and ACL state. The Upload Session Store tracks nextOffset for resumable uploads. The downside is that one upload touches several systems. This creates more failure points. Pagination keeps folder and version responses small, but clients must manage pageToken. API versioning protects older clients, but the gateway must maintain stable contracts. JWT validation improves security, but it adds work before routing. We accept this added complexity because resumable uploads, sharing, and backward compatibility are core needs.