Google Python Developer Interview Questions & Answers

I would build a set from the first array, then scan the second array from left to right. For each value, I check whether it exists in the first set. If it does, I add it to a result set called common. The result set removes duplicates automatically. After the scan, I return list(common). The expected time is O(n + m), because Python set operations are O(1) on average. The auxiliary space is O(n + k), commonly reported as O(n).

The problem asks us to return the distinct integer values that appear in both arrays. We return values, not indices. The output order does not matter. A set-based solution fits well because a set supports fast membership checks and stores each value only once.

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 two integer arrays named nums1 and nums2.

For the diagram example:

nums1 = [1, 2, 2, 1, 3]

nums2 = [2, 2, 3, 4]

The values that appear in both arrays are 2 and 3. Each value must appear once in the result. One valid returned list is [2, 3]. The order may vary.

First, convert nums1 into a set named values_in_nums1. For the example, it becomes {1, 2, 3}.

This set stores values only. It does not store indices or frequencies. It lets us check whether a value from nums2 appears in nums1 in O(1) time on average.

Create another empty set named common. This set stores the distinct values found in both arrays. Because common is a set, adding the same value more than once keeps only one copy.

The central invariant is this: after processing the first i elements of nums2, common contains exactly the distinct processed values that also appear in nums1.

The initial state is:

values_in_nums1 = {1, 2, 3}

common = {}

Traversal begins at nums2[0]. The values in nums2 are processed from left to right in this order: 2, 2, 3, 4.

Step 1 uses index 0. The current value is 2. common is {} before the check. Since 2 is in values_in_nums1, add 2 to common. common becomes {2}.

Step 2 uses index 1. The current value is 2 again. common is {2} before the check. Since 2 is in values_in_nums1, add it again. A set keeps only one copy, so common remains {2}.

Step 3 uses index 2. The current value is 3. common is {2} before the check. Since 3 is in values_in_nums1, add 3. common becomes {2, 3}.

Step 4 uses index

3. The current value is
4. common is {2, 3} before the check. Since 4 is not in values_in_nums1, make no change. common remains {2, 3}.

All four values from nums2 have now been processed. The final result set is {2, 3}. One valid returned list is [2, 3].

Before each iteration, common contains exactly the distinct matching values found in the part of nums2 already processed.

If the current value exists in values_in_nums1, it belongs to the intersection, so adding it is correct. If it does not exist in values_in_nums1, it cannot belong to the intersection, so skipping it is correct.

The set common removes repeated matches automatically. Therefore, when the scan finishes, common contains exactly the distinct values present in both arrays.

The code creates values_in_nums1 with set(nums1). It creates common as an empty set.

The for loop reads each value from nums2 in order. The if statement checks whether the current value appears in values_in_nums1. When the condition is true, common.add(value) stores the match.

After the loop, list(common) converts the result set into a list and returns it. The order of that list is not guaranteed, which is allowed by the problem.

Let n be the length of nums1 and m be the length of nums2.

Building set(nums1) takes O(n) time. Scanning nums2 takes O(m) time. Python set lookup and insertion take O(1) time on average. Therefore, the expected total time is O(n + m).

The first set can store up to n distinct values. The result set can store k distinct intersection values. The auxiliary space is O(n + k), commonly reported as O(n) because k cannot be greater than the number of distinct values in nums1.

The method handles duplicate values, negative values, zero, empty arrays, and arrays with no common values.

The key idea is to use one set for fast membership checks and another set for distinct results. values_in_nums1 stores the distinct values from nums1. Then the algorithm scans nums2 from left to right. If a value is in values_in_nums1, it is added to common. The invariant is that after processing the first i elements of nums2, common contains exactly the distinct processed values that also appear in nums1. This avoids the slower nested-loop method that compares every pair of values.

Let n be the number of elements in nums1 and m be the number of elements in nums2. Building values_in_nums1 takes O(n) time. Scanning nums2 takes O(m) time. Python set lookup and insertion take O(1) time on average, so the expected total time is O(n + m). values_in_nums1 uses O(n) extra space. common uses O(k) space, where k is the number of distinct matching values. The total auxiliary space is O(n + k), commonly reported as O(n).

A common mistake is storing matches in a list without checking for duplicates. Another mistake is returning indices even though the problem asks for values. Some candidates use nested loops, which can take O(n × m) time. Another mistake is claiming guaranteed O(n + m) time instead of expected O(n + m) time for Python sets. It is also wrong to claim that [2, 3] is the only valid output order.

State the invariant before writing the loop: common contains exactly the distinct processed values from nums2 that also appear in nums1. Then use the example to show how each iteration keeps that invariant true.

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 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 a sliding window with two frequency maps. The need map stores the required count for each character in t. I expand the right pointer until the window contains every required frequency. Then I move the left pointer while the window stays valid and record the smallest window. This works because each valid window is minimized for its current right boundary. The expected time is O(|s| + |t|), and the auxiliary space is O(k), where k is the number of distinct required characters in t.

The problem asks for the shortest contiguous substring of s that contains every character from t with the required frequency. A sliding window fits because the answer must be one continuous part of s. The right pointer grows the window until it becomes valid. The left pointer then removes unnecessary characters. Frequency maps let us update and check the window without recounting every character.

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 two strings, s and t.

We must return a substring of s. A substring is a continuous section of the string. It is not a subsequence.

The substring must contain every character from t with the correct frequency. If no valid substring exists, we return an empty string.

For the example, s is "ADOBECODEBANC" and t is "ABC". The returned substring is "BANC". It starts at index 9, ends at index 12, and has length 4.

The window is the part of s from index left through index right, including both boundaries.

The need map stores each required character and its required count. For the example, need is {A: 1, B: 1, C: 1}.

The window map stores the current counts of required characters inside the window. Characters that are not in need do not have to be stored.

The variable required is the number of distinct characters in need. It is 3 for this example.

The variable formed counts how many distinct required characters currently meet their full required frequency.

The central invariant is: when formed equals required, s[left:right + 1] contains every required character with the needed frequency.

We begin with left equal to 0 and formed equal to 0.

The window map is empty because no characters have entered the window.

The best length starts as infinity because no valid window has been found. The best start index begins at 0 and is used after a valid window is recorded.

If s or t is empty, or if t is longer than s, a valid answer is impossible, so the function returns an empty string.

At right index 0, the character is A. A is required, so its window count becomes 1. This reaches the required count for A, so formed becomes 1 out of 3.

At right index 3, the character is B. Its count reaches 1, so formed becomes 2 out of 3.

At right index 5, the character is C. Its count reaches 1, so formed becomes 3 out of 3. The first valid window is "ADOBEC", from index 0 to index 5. Its length is 6, so it becomes the best answer.

The algorithm now shrinks the window. It removes A at index

1. The A count becomes 0, which is below the required count of
2. Formed becomes 2, the window becomes invalid, and left moves to index 1.

The right pointer continues through the string. At right index 10, another A enters. The relevant counts are A: 1, B: 2, and C: 1, so formed becomes 3 again. The window "DOBECODEBA" is valid.

The algorithm repeatedly moves left while the window remains valid. It passes the irrelevant characters at indices 1 and 2. It can also remove the B at index 3 because another B remains in the window. It then passes E at index 4. The best length remains 6. When C at index 5 is removed, the C count becomes 0. Formed becomes 2, the window becomes invalid, and left becomes 6.

At right index 12, another C enters. The window "ODEBANC" becomes valid again.

The algorithm shrinks it to "DEBANC", then "EBANC", and then "BANC". The best answer changes from length 6 to length 5 and then to length 4.

After recording "BANC", the algorithm removes B at index 9. The B count falls below its required count, so formed becomes 2. The window is invalid, and shrinking stops. The right pointer has reached the end of s, so the final answer is "BANC".

Whenever formed equals required, the current window is valid.

For one fixed right boundary, the algorithm moves left while the window stays valid. This finds the smallest valid window ending at that right boundary.

The right pointer visits every possible ending position. Therefore, the algorithm considers the smallest valid window for every possible right boundary.

The smallest window recorded across those positions is the global minimum.

Counter(t) creates the need map.

defaultdict(int) creates the window map and gives unseen characters a starting count of zero.

The for loop moves right across s. Only characters found in need update the window map. When a character count exactly reaches its required count, formed increases.

When formed equals required, the while loop runs. It first records the current window if it is shorter than the best one. It then removes the leftmost character and moves left forward.

If removing a required character makes its count lower than the needed count, formed decreases. The window is no longer valid, so shrinking stops.

After the scan, the function returns an empty string if no valid window was found. Otherwise, it returns the slice starting at best_start with length best_len.

Building the need map takes O(|t|) time.

The right pointer moves through s once. The left pointer also moves forward at most |s| times. Python dictionary lookup and update are O(1) on average. Therefore, the expected total time is O(|s| + |t|).

The two maps store at most k distinct required characters, so the auxiliary space is O(k), where k is the number of distinct characters in t.

Important edge cases are empty s or t, t being longer than s, repeated required characters such as t = "AABC", no valid window, and a case where the whole string is the answer.

The key insight is to maintain one adjustable window instead of generating every possible substring. The right pointer expands the window until all required frequencies are present. The left pointer then removes unnecessary characters while the window remains valid. The need map stores each required character and its target frequency. The window map stores the current frequency inside the window. The invariant is that formed == required exactly when every distinct required character has reached its needed count. Shrinking each valid window gives the smallest valid window for its current right boundary.

Let |s| be the length of s and |t| be the length of t. Creating the need map takes O(|t|) time. The right pointer moves forward |s| times, and the left pointer moves forward at most |s| times. Python dictionary lookup and update are O(1) on average. Therefore, the expected total time is O(|s| + |t|). The need and window maps store at most k distinct required characters, so the auxiliary space is O(k).

A common mistake is tracking only whether a character appears instead of tracking its required frequency. Another mistake is treating the answer as a subsequence rather than a contiguous substring. Some candidates shrink the window before recording the current valid answer. Others decrease formed whenever a required character is removed, even when enough copies remain. It is also incorrect to claim guaranteed O(|s| + |t|) time because Python dictionary operations are O(1) only on average.

State the invariant before coding: formed == required means the current window contains every required frequency. Then say that the best answer must be recorded before the left character is removed.

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 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 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.