How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Implement power, reduce string, parse tree, debug maze

Q: Implement power, reduce string, parse tree, debug maze

This multi-part question evaluates numerical algorithms (fast exponentiation), string-processing and reduction logic, recursive parsing and tree construction, and graph search with debugging and constraint handling, covering algorithmic efficiency, parsing accuracy, state management, and edge-case reasoning.

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:

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.
Fix a performance bug : the maze solver is too slow or may revisit states; add a visited set / hash set to prevent revisiting cells.
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).

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:

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.
Fix a performance bug : the maze solver is too slow or may revisit states; add a visited set / hash set to prevent revisiting cells.
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).

Implement power, reduce string, parse tree, debug maze

Quick Overview

1) Implement fast exponentiation (`pow`)

2) Cancel/reduce a string by repeatedly removing adjacent duplicates

3) Build a binary tree from a parenthesized string

4) Maze pathfinding: find and fix bugs, then extend features

Submit Your Answer to Earn 20XP

Implement power, reduce string, parse tree, debug maze

Quick Overview

1) Implement fast exponentiation (`pow`)

2) Cancel/reduce a string by repeatedly removing adjacent duplicates

3) Build a binary tree from a parenthesized string

4) Maze pathfinding: find and fix bugs, then extend features

Submit Your Answer to Earn 20XP

Implement power, reduce string, parse tree, debug maze

Quick Overview