Solve permutation successor and evaluate expressions
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.