Solve parsing, counting, ranges, and window problems
Overview
This set of problems evaluates parsing and string-processing, array and range reasoning, binary search, and sliding-window/frequency-counting competencies within the Coding & Algorithms domain, covering expression evaluation with operator precedence, counting occurrences in sorted arrays, summarizing missing ranges, and minimum-window substring problems. Such questions are commonly asked to assess the ability to implement efficient algorithms that meet specified time and space bounds while handling edge cases, and they require practical implementation skills (linear and logarithmic time techniques) combined with conceptual understanding of precedence, search boundaries, and two-pointer/window strategies.
Solve the following four algorithm problems:
- Expression evaluator with + and : Given a string s containing non-negative integers, '+' and ' ' operators, and optional spaces or commas as separators, compute the value of the expression. Multiplication has higher precedence than addition; no parentheses appear. Assume s length ≤ 1e5 and all intermediate results fit in 64-bit signed integer. Return the integer result in O(n) time and O( 1)/O(n) extra space (your choice). Clarify how to handle invalid tokens (you may assume input is valid).
- Count target occurrences in a sorted array: Given a nondecreasing integer array nums and an integer target, return the number of occurrences of target in nums. Achieve O(log n) time and O(
- extra space by locating the first and last positions via binary search. If target is absent, return 0.
- Summarize missing ranges within [0, 99]: You are given a sorted, unique list present of integers each in [0, 99] representing the values that exist. Output a list of strings summarizing all missing values in [0, 99] that are not in present. For any consecutive missing run [a, b]: if the count of missing numbers is at least 3, output "a->b"; otherwise list each missing number individually, joined by commas (e.g., "6,7"). Examples: present = [0,1,5,9,99] -> missing includes "2,3,4", "6->8", "10->98". If nothing is missing, return an empty list.
- Minimum window covering a multiset: Given strings s and t, return the shortest substring of s that contains every character of t with its required multiplicity. If multiple answers exist, return any one; if none exist, return the empty string. Aim for O(|s|) time and O(Σ) space using a sliding window with frequency counts.