Google Python Developer Interview Questions & Answers

Python's buffer protocol lets an exporter expose its existing binary memory to a consumer. memoryview is the main built in Python interface for accessing that memory without copying the payload. The consumer must still respect the exporter's format, shape, strides, writable state, and lifetime. Operations that request new bytes or a different layout can still create a copy.

Use the buffer protocol when large binary data should be shared without duplicating its payload. For example, memoryview(bytearray_data) creates a small view object that refers to the bytearray's existing storage. It allocates metadata for the view, but it does not allocate another payload buffer.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

The object that owns and exposes the memory is the exporter. bytes, bytearray, array objects, and many binary libraries can be exporters. The object or function that requests the memory is the consumer. The exported description can include the element format, item size, dimensions, shape, strides, and writable state.

Contiguous data stores the requested elements next to each other. Strided data can contain gaps or represent selected rows, columns, or steps. A consumer must support that layout. Otherwise, conversion to contiguous storage may copy the data.

Mutability is controlled by the exporter. A view of bytes is read only. A view of bytearray is normally writable, so changes affect the original bytearray. The view keeps the exporter alive. Exporters such as bytearray also prevent resizing while an active view exists.

Zero copy therefore describes compatible access to the same payload, not every later operation. tobytes, incompatible layout conversion, and ownership requirements create copies.

Common mistakes include claiming that every memoryview operation is zero copy, ignoring shape and stride information, writing through a read only view, and assuming every external library accepts noncontiguous data. Another mistake is calling tobytes and still describing the result as shared memory. Developers may also try to resize a bytearray while it has an active exported view, which raises BufferError. Keeping a small view can also keep a much larger exporter alive, so long lived views may retain more memory than expected.

Explain the idea in this order: exporter, consumer, shared payload, and then limitations. State clearly that memoryview avoids copying the payload only when the requested format and layout are compatible.

Python audit hooks observe sensitive operations by receiving named events and a tuple of event arguments. I can add a hook for the current interpreter with sys.addaudithook, while an embedding application can install a native hook with PySys_AddAuditHook. Hooks can log an event or raise an exception to abort many operations, but they are not a complete sandbox because code inside the same process may disable or bypass Python level hooks.

Use audit hooks for observation and carefully tested policy checks, not as the only security boundary. Python and its standard library emit named events by calling sys.audit or the native PySys_Audit API. Each event has a stable name and a defined tuple of arguments.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

A callback added with sys.addaudithook belongs to the current interpreter. Hooks run synchronously in the thread that emits the event, in registration order. Native hooks added with PySys_AddAuditHook run first and apply to all interpreters created by that runtime. For security sensitive monitoring, a native hook should be installed before Python is initialized.

A hook can record the event, raise an exception, or end the process. sys.audit rethrows the first hook exception. This can abort an operation, but the result depends on where that event is emitted. The behavior must be tested for each event.

Calling sys.addaudithook also emits a sys.addaudithook event. An existing hook can prevent the new Python hook from being registered by raising RuntimeError.

Hooks add synchronous callback work to every observed event. Their direct memory cost is usually small, but logging or retaining arguments can increase memory use. They are not a sandbox because malicious in process code may alter state, use unsafe native access, or bypass Python level hooks.

The example registers one Python audit hook for the current interpreter. The hook filters events so it only prints the file open event and one custom application event. Opening the operating system null device causes Python to emit an open event. Calling sys.audit emits the custom event with one string argument. The hook observes these events synchronously. It does not create a sandbox or claim that every sensitive operation can be blocked.

A common mistake is treating sys.addaudithook as a secure sandbox. Another is assuming every sensitive action emits an event before any work occurs. Developers may also assume that raising an exception always reverses an operation, perform slow network or file work inside the hook, retain large argument objects, or log passwords and tokens contained in event arguments. It is also incorrect to assume that calling sys.addaudithook guarantees registration, because an existing hook can reject the new hook.

Start with the main limit: audit hooks provide visibility, not complete isolation. Then explain event names, argument tuples, synchronous execution, native hook order, exception behavior, registration blocking, and the need for operating system security controls.

A cyclic import can expose a module before Python has finished initializing it. Python creates the module object and places it in sys.modules before executing the module code. If that code imports another module that imports the first module again, Python returns the same cached but incomplete object. A name defined later may not exist yet. The preferred fix is to remove the cycle by changing the dependency direction or moving shared definitions into a separate module.

The practical solution is to remove the dependency cycle rather than depend on a fragile import order. Suppose module a imports module b. Python creates the module object for a and places it in sys.modules before executing the code in a. This prevents endless recursive loading. ([docs.python.org](https://docs.python.org/3/library/importlib.html))

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

While a is still running, it imports b. Python creates and starts executing b. If b imports a, Python finds a in sys.modules and returns the same object. However, a may not have executed the lines that define the requested class, function, or constant. The object is therefore partially initialized.

A statement such as from a import Service can raise ImportError if Service is not ready. Access through a.Service during the cycle can raise AttributeError. Access may work when it is delayed until both modules finish importing.

The reliable production fix is to move shared definitions into a third module, place common interfaces in a lower level module, or pass dependencies into functions and classes. A local import inside a function can delay the lookup, but it may only hide the design problem. Python normally reuses the cached module object, so the cycle does not create a second initialized copy. The main risks are failed startup, confusing errors, and code that breaks when import order changes.

A common mistake is assuming Python fully executes one module before an imported module can refer to it. Another mistake is rearranging import statements until the error disappears, because a later change can break that fragile order again. Developers may also believe Python creates a second copy of the first module, but the cyclic import normally receives the same object from sys.modules. Moving every import inside functions can hide the cycle instead of removing it. Another mistake is using from imports between closely connected modules because the requested name must already exist when that statement runs.

Explain the order clearly. Python creates the module object, caches it in sys.modules, starts executing its code, enters the second module, and then returns the unfinished first module. Give one failure pattern and finish with the preferred design fix.

My practical rule is to use threads when tasks need shared memory, processes when strong isolation matters, and subinterpreters when I want isolated Python runtimes inside one process. Each subinterpreter has separate modules, global variables, and interpreter state. In current CPython, it can also have its own global interpreter lock, which allows parallel Python execution across CPU cores. Mutable objects are not shared directly, so data must be copied, serialized, or sent through supported communication tools. I would verify every native extension before using subinterpreters in production.

The practical choice depends on isolation and communication. Threads are simplest when tasks need shared objects. Processes provide the strongest memory and failure isolation. Subinterpreters sit between them because they provide separate Python runtimes inside one operating system process.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

Each subinterpreter has its own imported modules, global variables, builtins module, and interpreter state. Normal mutable objects cannot be used directly across interpreter boundaries. Data must be copied, serialized, or transferred through a supported communication mechanism.

Current CPython can give each isolated interpreter its own global interpreter lock. This allows interpreters to execute Python code on different CPU cores. Normal threads on a standard CPython build still share one interpreter lock. A free threaded CPython build changes that thread limitation, so the exact runtime build matters.

Subinterpreters usually avoid some operating system process overhead, but they still require interpreter creation, separate imports, object copying, and communication. Their speed and memory advantage is therefore workload dependent.

Native extension modules are an important limitation. An extension may reject subinterpreters or behave incorrectly if it keeps unsafe process wide state. Production use requires dependency testing, realistic benchmarks, controlled task boundaries, and a process based fallback when stronger isolation is needed.

A common mistake is treating a subinterpreter as an ordinary thread. A subinterpreter may run on a thread, but it owns separate Python runtime state. Another mistake is assuming that mutable Python objects can be shared directly across interpreters. They normally must be copied, serialized, or transferred through supported tools. Candidates may also claim that subinterpreters provide process level failure isolation. They do not, because all interpreters remain inside one process and a serious native failure can terminate that process. Another mistake is assuming that every native extension is compatible. Extensions with unsafe process wide state may reject multiple interpreters or behave incorrectly. Finally, lower operating system overhead does not guarantee better performance or lower memory use because imports, serialization, copied data, and workload size affect the result.

Compare threads, subinterpreters, and processes using five points: isolation, object sharing, parallel execution, startup and memory cost, and failure boundaries. Mention the runtime build and extension module support before recommending subinterpreters.

The main idea is that a code object contains reusable compiled instructions, while a frame contains the live state of one execution of those instructions. Each active function call has its own frame, even when several calls use the same code object. Frames expose local, global, and builtin mappings and link active calls into a call stack. Trace and profile functions receive events from those frames. They help debuggers, coverage tools, and profilers, but they add callback cost and can keep local objects alive if frame references are stored.

The practical rule is to separate reusable code from live execution state. Python compiles a function body into a code object. The code object stores instructions, constants, names, variable information, flags, and source position information. Calling the function starts an execution frame that refers to that code object. The frame tracks the current execution position and exposes local, global, and builtin mappings through f_locals, f_globals, and f_builtins. Its f_back reference points to the calling frame when one exists, so active frames form the call stack.

1. Should I focus on Python language behavior, or also explain the runtime and standard library?
2. Which Python version and execution environment should I assume?
3. Would you like a small code example together with production tradeoffs and edge cases?

Many calls can use the same code object, but every call has separate frame state. This is why recursion keeps different local values for each call. A suspended generator or coroutine can retain its frame and referenced objects until it finishes, closes, or is collected.

sys.settrace installs a trace function for the current thread. It can receive call, line, return, exception, and optional opcode events. sys.setprofile receives fewer events focused on Python calls, returns, and calls into C code. These hooks support debugging, coverage, and profiling. They can be expensive because callbacks run during execution. Stored frames and tracebacks can also retain local objects, so production tools should limit collection and release references promptly.

A common mistake is saying that a code object stores the current values of local variables. Those values belong to a particular execution frame. Another mistake is assuming Python recompiles a function for every call. Normal calls reuse the function code object and create separate execution state. Developers may also confuse the local mapping with a normal dictionary that always acts as the interpreter's internal storage. Function scopes may use optimized local storage that Python exposes through mapping behavior, so code should use documented frame and locals rules rather than old assumptions. Another mistake is treating tracing as free. Line and opcode events can create many callbacks and greatly slow a program. Finally, storing frames or tracebacks for too long can retain local objects and create reference cycles, so diagnostic code should process them and release them promptly.

Explain the relationship in three steps. First, a code object holds reusable compiled information. Second, each execution has a separate frame, and active frames form the call stack. Third, trace and profile hooks observe frame events but add runtime and memory cost. Mention recursion, suspended generators, and retained traceback references to show practical understanding.

I would use recursive depth-first search. For each node, I first find the maximum depth of its left subtree and then its right subtree. The base case is an empty node, which returns 0. A real node returns 1 plus the larger child depth. This works because every recursive call returns the correct depth for its own subtree. The time complexity is O(n), and the auxiliary space is O(h) for the recursion stack.

The problem asks for the number of nodes on the longest path from the root to any leaf. I use recursive depth-first search because the depth of a node depends on the depths of its two children. I compute both child depths first. Then I keep the larger one and add 1 for the current node.

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 the root of a binary tree. The output is one integer.

The integer is the number of nodes on the longest root-to-leaf path. Depth counts nodes, not edges.

For the example tree, the root is 3. Its left child is 9. Its right child is 20. Node 20 has children 15 and 7.

The correct result is 3. Two deepest paths are 3 -> 20 -> 15 and 3 -> 20 -> 7.

If the root is None, the tree is empty, so the answer is 0.

I use recursive depth-first search in postorder style. Postorder style means I compute the child results before I compute the parent result.

For each node, the recursive call returns the maximum depth of the subtree rooted at that node.

The base case is a None child. Its depth is 0.

For a real node, the depth is:

1 + max(left_depth, right_depth)

The 1 counts the current node.

I call maxDepth on node 3.

The traversal starts at the root. For each real node, the function recursively processes the left child first and the right child second.

The central invariant is that every recursive call returns the correct maximum depth of the subtree rooted at its current node.

The first completed node-level calculation is for node 9. Its left child is None, so that call returns 0. Its right child is also None, so that call returns 0. Node 9 returns 1 + max(0, 0), which is 1.

The recursion then enters the right subtree of node 3. Node 15 is a leaf. Both child calls return 0, so node 15 returns 1.

Node 7 is also a leaf. Both child calls return 0, so node 7 returns 1.

Node 20 receives left_depth = 1 from node 15 and right_depth = 1 from node 7. It returns 1 + max(1, 1), which is 2.

Finally, node 3 receives left_depth = 1 from node 9 and right_depth = 2 from node 20. It returns 1 + max(1, 2), which is 3.

The base case is correct because an empty subtree contains zero nodes.

Assume the recursive calls return the correct depths for the left and right subtrees. Any longest path from the current node must continue through either the left child or the right child.

Taking max(left_depth, right_depth) selects the deeper subtree. Adding 1 counts the current node. Therefore, the current call returns the correct subtree depth.

This reasoning continues up to the root, so the final result is correct.

The function receives root, which is either a TreeNode or None.

If root is None, it returns 0 immediately.

Otherwise, it recursively calculates left_depth from root.left and right_depth from root.right.

It then returns 1 + max(left_depth, right_depth).

The TreeNode class stores the node value and references to the left and right children.

The time complexity is O(n), where n is the number of nodes. Each node is visited once.

The auxiliary space is O(h), where h is the tree height. This space is used by the recursion stack.

For a balanced tree, h is O(log n). For a completely skewed tree, h can be O(n).

Important edge cases are an empty tree, a single-node tree, a skewed tree, and a balanced tree.

The key insight is that the depth of a node can be built from the depths of its children. A recursive call returns the maximum depth of the subtree rooted at its current node. This is the central invariant. A None child returns 0. A real node returns 1 plus the larger of its left and right subtree depths. Postorder-style DFS fits because both child results must be known before the parent result can be calculated.

The time complexity is O(n), where n is the number of nodes in the tree. The algorithm visits each node once and does constant work at that node. The auxiliary space is O(h), where h is the tree height. This extra memory is used by the recursion stack. A balanced tree uses O(log n) stack space. A completely skewed tree can use O(n) stack space.

A common mistake is forgetting the None base case, which causes the recursion to continue incorrectly. Another mistake is returning max(left_depth, right_depth) without adding 1 for the current node. Some candidates count edges instead of nodes, which makes the result one too small. Others claim O(1) auxiliary space and forget the recursion stack. It is also incorrect to assume the tree is a binary search tree because the problem only says binary tree.

State the invariant before writing code: each call returns the maximum depth of the subtree rooted at its node. Then write the None base case and the recurrence 1 + max(left_depth, right_depth).

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 use postorder depth-first search. Each recursive call returns the best one-branch path that starts at the current node and can continue to its parent. I ignore negative child gains by comparing them with zero. At every node, I also test a complete path that joins the left branch, the node, and the right branch. A global variable stores the best result. This takes O(n) time and O(h) auxiliary space for the recursion stack.

The problem asks for the largest sum along any nonempty path in a binary tree. The path may start and end at any nodes. It does not need to pass through the root. Postorder depth-first search works well because each node needs the results from both children before it can calculate its own path values.

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 the root of a binary tree. Each node contains an integer value.

The output is one integer. It is the maximum sum of any nonempty path.

A path follows parent-child links. The final best path may use both children of one node. However, a path returned to a parent can continue through only one child branch.

I use postorder depth-first search. Postorder means I process the left child and right child before the current node.

Each call to dfs(node) returns the maximum gain of a path that starts at node and can extend upward to its parent.

The global variable best stores the largest complete path sum found so far.

I initialize best to negative infinity. This is important because every node may have a negative value. Starting with zero would give the wrong answer for an all-negative tree.

A missing child returns zero. For each real child, I compare its returned gain with zero. A negative gain is ignored because adding it would reduce the path sum.

The tree is:

-10 / \ 9 20 / \ 15 7

The postorder traversal is 9, 15, 7, 20, -10.

At node 9, left_gain is 0 and right_gain is 0. The through sum is 9. best becomes 9. The call returns 9.

At node 15, both gains are 0. The through sum is 15. best becomes 15. The call returns 15.

At node 7, both gains are 0. The through sum is 7. best stays 15. The call returns 7.

At node 20, left_gain is 15 and right_gain is 7. The through sum is 20 + 15 + 7 = 42. best becomes 42. The upward gain is 20 + max(15, 7) = 35.

At node -10, left_gain is 9 and right_gain is 35. The through sum is -10 + 9 + 35 = 34. This is smaller than 42, so best stays 42. The upward gain returned by the root call is -10 + max(9, 35) = 25.

The final answer is 42. The maximum path is 15 → 20 → 7, and 15 + 20 + 7 = 42.

Every valid path has one highest node. At that node, the path may use the best downward branch from the left child and the best downward branch from the right child.

The algorithm calculates this through sum at every node. Therefore, every possible highest point of a valid path is considered.

The recursive return uses only one child branch. This is correct because a path that continues to the parent cannot split into two child directions.

The nested dfs function first handles the base case. A missing node returns 0.

It recursively calculates the left and right gains. It clips each gain to 0 when the gain is negative.

It calculates through_sum by joining both usable child gains through the current node. It then updates best.

Finally, it returns the current node value plus the larger child gain. After the root call finishes, maxPathSum returns best.

Each node is processed once, so the time complexity is O(n).

The recursion stack uses O(h) auxiliary space, where h is the tree height. A balanced tree uses O(log n) stack space. A skewed tree can use O(n).

Important edge cases are a single-node tree, all-negative values, a skewed tree, and a best path that does not pass through the root.

The key idea is to calculate two different values at each node. The first value is through_sum. It may use the best left branch, the current node, and the best right branch. This value can update the final answer. The second value is upward_gain. It uses the current node and only one child branch because a parent cannot extend a path that already splits in two directions. Postorder DFS gives each node the child results first. Negative child gains are replaced with zero because excluding a harmful branch gives a larger path sum. The invariant is that dfs(node) returns the best extendable path starting at node, while best stores the largest complete path found so far.

The time complexity is O(n), where n is the number of nodes. The algorithm visits each node once and does constant work at that node. The auxiliary space is O(h), where h is the height of the tree. This extra memory is used by the recursion stack. For a balanced tree, h is O(log n). For a fully skewed tree, h can be O(n).

A common mistake is returning node.val + left_gain + right_gain to the parent. That returned path would already contain two branches, so the parent could not extend it as one valid path. Another mistake is initializing best to 0. That fails when every node value is negative. Candidates may also forget to ignore negative child gains, update best using only one branch instead of both branches, assume the best path must pass through the root, or forget the base case for a missing child.

Clearly separate the two values calculated at each node: through_sum may use both children and updates the global answer, while upward_gain may use only one child and is returned to the parent.

The main idea is to check whether the second string appears inside the first string joined with itself. I first compare the lengths because a rotation cannot add or remove characters. If the lengths match, I build doubled = original + original and test whether candidate is a contiguous substring of it. For example, cdeab appears in abcdeabcde, so I return True. The standard interview analysis is O(n) time and O(n) auxiliary space.

The problem asks whether one string can be formed by rotating another string. A rotation keeps every character in the same circular order. It only changes the starting position. The useful pattern is to join the original string with itself. Every valid rotation then appears as one contiguous substring inside that doubled string.

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 named original and candidate.

It returns True when candidate is a rotation of original. Otherwise, it returns False.

A rotation must preserve all characters and their circular order. It cannot add or remove characters.

The first condition compares the string lengths.

If len(original) != len(candidate), the function returns False immediately.

This check is required because two strings with different lengths cannot be rotations of each other.

In the diagram example, original = "abcde" and candidate = "cdeab". Both strings have length 5, so the algorithm continues.

The algorithm creates:

doubled = original + original

For the example:

"abcde" + "abcde" = "abcdeabcde"

This places every possible cut point beside the characters that follow it in circular order.

The initial state is:

original = "abcde"

candidate = "cdeab"

len(original) = 5

len(candidate) = 5

The length check passes, so there is no early return.

The code then builds doubled = "abcdeabcde".

Next, it checks whether "cdeab" appears as a contiguous substring inside the doubled string.

The match starts at index 2:

abcdeabcde

cdeab

The condition is true, so the function returns True and stops.

Suppose original = x + y.

Moving the prefix x to the end produces the rotation y + x.

The doubled string is:

original + original = x + y + x + y

The sequence y + x appears contiguously inside this doubled string. Therefore, when the lengths are equal, candidate is a valid rotation exactly when it appears inside original + original.

The first if statement handles the required length check.

The next statement creates the doubled string once.

The expression candidate in doubled performs a substring test and directly returns either True or False.

The code follows the same three executed steps shown in the diagram: verify lengths, build the doubled string, and search for the candidate.

Let n be the length of each string.

The standard interview analysis is O(n) time. The algorithm builds a string of length 2n and performs one substring search.

The auxiliary space is O(n) because the doubled string grows with the input.

Relevant edge cases include strings with different lengths, identical strings, two empty strings, repeated characters, and strings that contain similar characters but are not rotations.

The key insight is that every rotation of a string appears inside that string concatenated with itself. If original = x + y, then moving the prefix x to the end gives candidate = y + x. The doubled string is x + y + x + y, which contains y + x as a contiguous substring. The central invariant is: after the equal-length check passes, candidate is a valid rotation exactly when it appears inside original + original. This avoids constructing and comparing every possible rotation separately.

Let n be the length of each input string. The standard interview analysis is O(n) time because the algorithm creates a doubled string of length 2n and performs one substring test. If the lengths differ, it returns before creating that string. The auxiliary space is O(n) because doubled stores two copies of original. The output itself uses only one Boolean value.

A common mistake is skipping the length check. A shorter string may appear inside the doubled string even though it is not a rotation. Another mistake is treating a subsequence as valid. The candidate must be one contiguous substring. Sorting both strings is also incorrect because sorting loses the required circular order. Some candidates generate every rotation, which adds unnecessary work and temporary strings. Another mistake is claiming O(1) auxiliary space even though the doubled string grows with the input.

Explain the proof before writing the code: if original = x + y, then its rotation is y + x, and y + x must appear inside x + y + x + y.