Katkat
Back

Solve permutation successor and evaluate expressions

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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?