## 1) Implement fast exponentiation (`pow`) Implement a function `pow(x, n)` that returns \(x^n\). - Inputs: a floating-point base `x` and an integer exponent `n` (can be negative). - Output: `x` raised to the power `n`. - Requirements: - Improve time efficiency beyond multiplying `x` `|n|` times. - Handle edge cases such as `n = 0`, negative `n`, and large `|n|`. ## 2) Cancel/reduce a string by repeatedly removing adjacent duplicates Given a string `s`, repeatedly remove any **maximal contiguous group** of the same character with length \(\ge 2\). Continue until no more removals are possible. Return the final string. Examples: - `"abbba"` → `""` (remove `bbb` → `"aa"`, then remove `aa` → `""`) - `"Acbcccbac"` → `"Acac"` (one possible sequence: remove `ccc` → `"Acbbac"`, remove `bb` → `"Acac"`) Clarify in your solution whether the operation is case-sensitive (assume case-sensitive unless stated otherwise). ## 3) Build a binary tree from a parenthesized string You are given a string encoding of a binary tree using this grammar: - A node is encoded as: `value(leftSubtree)(rightSubtree)` - `value` is an integer (may be multi-digit; may be negative). - Each subtree is encoded the same way. - A missing child may be represented by empty parentheses: `()`. Task: Parse the string and construct the corresponding binary tree, returning the root. Example (illustrative): - Input: `"5(2() (3()()))(1()())"` (whitespace optional) - Output: a tree with root value `5`, left child rooted at `2`, and right child rooted at `1`. ## 4) Maze pathfinding: find and fix bugs, then extend features You are given buggy code for solving a maze/grid pathfinding problem (e.g., DFS/BFS from a start to an end cell). The interviewer asks you to: 1. **Fix a correctness bug**: the code prints an incorrect path because it fails to check whether the “current” cell is actually empty/passable before processing it. 2. **Fix a performance bug**: the maze solver is too slow or may revisit states; add a `visited` set / hash set to prevent revisiting cells. 3. **Extend the maze with one-way doors**: add a feature where certain cells represent doors that only allow traversal in one direction (e.g., you may pass through the door only when moving left→right, but not right→left). Ensure the solver respects one-way constraints. - Discuss corner cases such as a door adjacent to a wall where naive logic could incorrectly block valid paths. Define your movement rules (4-neighbor vs 8-neighbor), cell encodings (walls, empty, start/end, doors), and what output is required (existence, any path, or shortest path).