How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

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

Solve permutation successor and evaluate expressions

Quick Overview

This question evaluates understanding of lexicographic permutation generation with in-place array manipulation and linear-time arithmetic expression parsing and evaluation, focusing on algorithmic efficiency, constant extra space constraints, and correct operator semantics.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Part A: Given a sequence of integers that forms a permutation, rearrange it in-place to produce the immediate next sequence in lexicographic order. If no greater ordering exists, rearrange it to the smallest possible ordering. Target O(n) time and O( 1) extra space, and explain the algorithmic steps and edge cases. Part B: Implement an evaluator for an arithmetic string containing non-negative integers and the operators +, -, *, /. No parentheses are present; spaces may appear. Return the integer result, using truncation toward zero for division. Aim for O(n) time and constant extra space. Follow-up (discussion only): How would you extend your evaluator to support parentheses and maintain correct operator precedence and nested expressions?

Quick Answer: This question evaluates understanding of lexicographic permutation generation with in-place array manipulation and linear-time arithmetic expression parsing and evaluation, focusing on algorithmic efficiency, constant extra space constraints, and correct operator semantics.

Next Permutation (in-place, lexicographic successor)

Given a sequence of integers `nums` that forms a permutation, rearrange it IN PLACE to produce the immediate next sequence in lexicographic order. If no greater ordering exists (the sequence is in descending order), rearrange it to the smallest possible ordering (ascending). You must use only O(1) extra space and run in O(n) time. Return the modified list. Algorithm: (1) Scan from the right to find the first index i where nums[i] < nums[i+1] (the 'pivot'). (2) If such an i exists, scan from the right to find the smallest element greater than nums[i] and swap them. (3) Reverse the suffix starting at i+1 to make it ascending (the smallest arrangement of that suffix). If no pivot exists, the whole array is descending, so reversing it yields the smallest ordering.

Constraints

1 <= nums.length <= 10^5 (the reference also handles the empty-list edge case)
0 <= nums[i] <= 100
The rearrangement must be performed in place using only constant extra memory.

Examples

Input: ([1, 2, 3],)

Expected Output: [1, 3, 2]

Explanation: 1 2 3 -> the next larger permutation is 1 3 2.

Input: ([3, 2, 1],)

Expected Output: [1, 2, 3]

Explanation: Already the largest ordering, so it wraps around to the smallest (ascending).

Input: ([1, 1, 5],)

Expected Output: [1, 5, 1]

Explanation: Pivot is the first 1 (index 0); swap with 5 and reverse the single-element suffix.

Input: ([1],)

Expected Output: [1]

Explanation: A single element has no successor; it stays unchanged.

Input: ([],)

Expected Output: []

Explanation: Empty input is returned unchanged.

Input: ([1, 3, 2],)

Expected Output: [2, 1, 3]

Explanation: Pivot is 1 (index 0); swap with 2, then reverse suffix [3,1] -> [1,3].

Input: ([2, 3, 1],)

Expected Output: [3, 1, 2]

Explanation: Pivot is 2 (index 0); swap with 3, then reverse suffix [2,1] -> [1,2].

Input: ([1, 5, 1],)

Expected Output: [5, 1, 1]

Explanation: Pivot is 1 (index 0); swap with 5 (rightmost value greater than pivot), reverse the suffix [1,1].

Hints

Find the longest non-increasing suffix; the element just before it is the pivot.
Swap the pivot with the smallest suffix element that is still larger than the pivot.
Reversing the suffix turns it from descending into ascending — the smallest possible arrangement of those values.

Basic Calculator II (no parentheses, +-*/ with precedence)

Implement an evaluator for an arithmetic string `s` containing non-negative integers and the operators `+`, `-`, `*`, `/`. There are NO parentheses. Spaces may appear anywhere and should be ignored. Return the integer result. Multiplication and division have higher precedence than addition and subtraction. Integer division must truncate TOWARD ZERO (e.g. 3/2 = 1). Approach: Make one left-to-right pass tracking the current number and the operator that precedes it. Keep a stack of pending additive terms. On `+`/`-`, push the (signed) number. On `*`/`/`, pop the top of the stack and combine it with the current number, then push the result back. This defers the additive sum until the end, where you sum the stack. Use a sentinel so the final number is also flushed. Follow-up (discussion only): To support parentheses, recurse (or use an explicit operand/operator stack) — when you hit '(', evaluate the inner sub-expression first and treat its result as a single operand; ')' closes the current scope.

Constraints

1 <= s.length <= 3 * 10^5
s consists of digits, the operators '+', '-', '*', '/', and spaces ' '.
s represents a valid expression; all intermediate values fit in a signed 32/64-bit integer.
Integer division truncates toward zero.
Note: the stack is O(n) in the worst case for an all-additive expression; a true O(1)-space variant tracks only a running total plus the last term.

Examples

Input: ("3+2*2",)

Expected Output: 7

Explanation: 2*2 = 4 first (higher precedence), then 3 + 4 = 7.

Input: (" 3/2 ",)

Expected Output: 1

Explanation: Spaces ignored; 3/2 truncates toward zero to 1.

Input: (" 3+5 / 2 ",)

Expected Output: 5

Explanation: 5/2 = 2 first, then 3 + 2 = 5.

Input: ("42",)

Expected Output: 42

Explanation: A bare number evaluates to itself.

Input: ("14-3/2",)

Expected Output: 13

Explanation: 3/2 = 1, then 14 - 1 = 13.

Input: ("1-1+1",)

Expected Output: 1

Explanation: Left to right additive: 1 - 1 + 1 = 1.

Input: ("2*3*4",)

Expected Output: 24

Explanation: Chained multiplication: ((2*3)*4) = 24.

Input: ("10-2-3",)

Expected Output: 5

Explanation: Subtraction terms accumulate: 10 + (-2) + (-3) = 5.

Input: ("7-3*2",)

Expected Output: 1

Explanation: The 3 is pushed as -3, then *2 makes it -6; 7 + (-6) = 1.

Input: ("100",)

Expected Output: 100

Explanation: Multi-digit single number flushed at end of string.

Hints

Carry the operator that PRECEDES the current number; act on it only once you've finished reading the number.
Handle * and / immediately by combining with the top of the stack; defer + and - to a final sum.
Trigger evaluation on each non-space operator AND on the last character so the final number is flushed.
Use int(a / b) (not Python floor division //) so negative quotients truncate toward zero, e.g. -7/2 = -3.

Quick Overview