PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick 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.

  • Medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

Solve parsing, counting, ranges, and window problems

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Solve the following four algorithm problems: 1) 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). 2) 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( 1) extra space by locating the first and last positions via binary search. If target is absent, return 0. 3) 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. 4) 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.

Quick Answer: 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.

Expression Evaluator with + and *

Given a string `s` containing non-negative integers, the operators `+` and `*`, and optional spaces or commas as separators, compute the value of the expression. Multiplication has higher precedence than addition, and there are no parentheses. You may assume the input is valid, `s.length <= 1e5`, and all intermediate results fit in a 64-bit signed integer. Return the integer result. Aim for O(n) time. Example: `"2+3*4"` -> `14` (3*4 = 12, then 2+12). `"1, 2, 3 * 4"` -> `15` (commas/spaces are separators between tokens, so this is 1+2+3*4 = 1+2+12).

Constraints

  • 1 <= s.length <= 1e5
  • s contains only digits, '+', '*', spaces, and commas
  • The input expression is valid
  • All intermediate results fit in a 64-bit signed integer

Examples

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

Expected Output: 14

Explanation: 3*4 = 12, then 2 + 12 = 14 (multiplication first).

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

Expected Output: 15

Explanation: Commas and spaces are separators: 1 + 2 + (3*4) = 1 + 2 + 12 = 15.

Input: ("0",)

Expected Output: 0

Explanation: A single number evaluates to itself.

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

Expected Output: 28

Explanation: 3*3*3 = 27, then 27 + 1 = 28.

Input: ("10 + 20 + 30",)

Expected Output: 60

Explanation: Pure addition: 10 + 20 + 30 = 60.

Input: ("100*0+5",)

Expected Output: 5

Explanation: 100*0 = 0, then 0 + 5 = 5.

Hints

  1. Use a single left-to-right pass. Track a running `total` (committed sum) and a `cur` value representing the current multiplicative term.
  2. When you see a '+', commit `cur` into `total` and start a new term with the next number. When you see a '*', multiply the next number into `cur`.
  3. Initialize `cur = 0` and treat the first operator as '+'. Skip spaces and commas as token separators.

Count Target Occurrences in a Sorted Array

Given a nondecreasing (sorted) integer array `nums` and an integer `target`, return the number of times `target` occurs in `nums`. If `target` is not present, return 0. You must achieve O(log n) time by locating the first and last positions of `target` via binary search, using O(1) extra space. Example: `nums = [5,7,7,8,8,10]`, `target = 8` -> `2`.

Constraints

  • 0 <= len(nums) <= 1e5
  • nums is sorted in nondecreasing order
  • -1e9 <= nums[i], target <= 1e9

Examples

Input: ([5,7,7,8,8,10], 8)

Expected Output: 2

Explanation: 8 appears at indices 3 and 4, so the count is 2.

Input: ([5,7,7,8,8,10], 6)

Expected Output: 0

Explanation: 6 is not in the array.

Input: ([], 0)

Expected Output: 0

Explanation: An empty array contains no occurrences.

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

Expected Output: 5

Explanation: Every element equals the target.

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

Expected Output: 2

Explanation: -3 appears at indices 0 and 1 (negatives handled correctly).

Input: ([2], 2)

Expected Output: 1

Explanation: Single-element array containing the target.

Input: ([1,2,3,4,5], 6)

Expected Output: 0

Explanation: Target greater than every element.

Hints

  1. The count equals (index of last occurrence) - (index of first occurrence) + 1, or 0 if absent.
  2. Find the first index where nums[i] >= target (lower bound) and the first index where nums[i] > target (upper bound). The difference is the count.
  3. Use half-open binary search [lo, hi) to avoid off-by-one errors; the count is upper_bound - lower_bound.

Summarize Missing Ranges within [0, 99]

You are given a sorted list of unique integers `present`, each in `[0, 99]`, representing the values that exist. Return a list of strings summarizing all values in `[0, 99]` that are NOT in `present`. For each maximal run of consecutive missing numbers `[a, b]`: - If the run contains at least 3 missing numbers, output the single string `"a->b"`. - Otherwise (1 or 2 missing numbers), output the missing numbers individually, joined by commas (e.g. `"6,7"` or `"6"`). If nothing is missing, return an empty list. Example: `present = [0,1,5,9,99]` -> `["2->4", "6->8", "10->98"]`.

Constraints

  • 0 <= len(present) <= 100
  • Each value in present is in [0, 99]
  • present is sorted and contains unique values

Examples

Input: ([0,1,5,9,99],)

Expected Output: ['2->4', '6->8', '10->98']

Explanation: Missing runs: 2-4 (len 3 -> range), 6-8 (len 3 -> range), 10-98 (len 89 -> range).

Input: ([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99],)

Expected Output: []

Explanation: Every value in [0, 99] is present, so nothing is missing.

Input: ([],)

Expected Output: ['0->99']

Explanation: Everything is missing: one run 0-99 (len 100 -> range).

Input: ([0,3,99],)

Expected Output: ['1,2', '4->98']

Explanation: Missing 1-2 (len 2 -> individual '1,2') and 4-98 (len 95 -> range).

Input: ([5],)

Expected Output: ['0->4', '6->99']

Explanation: Missing 0-4 (len 5 -> range) and 6-99 (len 94 -> range).

Input: ([0,1,2,3,4,5,6,7,8,9,11,99],)

Expected Output: ['10', '12->98']

Explanation: Missing 10 (len 1 -> individual '10') and 12-98 (len 87 -> range).

Hints

  1. Build a set of present values, then scan i from 0 to 99 to find maximal runs of consecutive missing integers.
  2. For each missing run [a, b], compute its length = b - a + 1.
  3. If the run length is >= 3, emit "a->b". Otherwise emit each missing number, comma-joined (a single missing number emits just its value as a string).

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 (i.e. covers `t` as a multiset). If multiple shortest windows exist, return any one (the reference returns the leftmost). If no such window exists, return the empty string. Aim for O(|s|) time using a sliding window with frequency counts. Example: `s = "ADOBECODEBANC"`, `t = "ABC"` -> `"BANC"`.

Constraints

  • 0 <= len(s), len(t) <= 1e5
  • s and t consist of arbitrary characters
  • If t is empty, return the empty string

Examples

Input: ("ADOBECODEBANC", "ABC")

Expected Output: 'BANC'

Explanation: BANC is the shortest substring containing A, B, and C.

Input: ("a", "a")

Expected Output: 'a'

Explanation: The whole string is the minimal window.

Input: ("a", "aa")

Expected Output: ''

Explanation: s has only one 'a' but t needs two, so no valid window.

Input: ("", "a")

Expected Output: ''

Explanation: Empty source cannot cover a non-empty target.

Input: ("aaflslflsslf", "")

Expected Output: ''

Explanation: Empty target -> empty string by definition.

Input: ("aaaaaaaaaab", "aab")

Expected Output: 'aab'

Explanation: Shortest window needs 2 a's and 1 b; the trailing 'aab' (last two a's + b) is minimal.

Input: ("abc", "cba")

Expected Output: 'abc'

Explanation: All three characters are required; the whole string is the only window.

Hints

  1. Build a frequency map `need` for t. Expand a right pointer, maintaining a `window` frequency map for the current substring of s.
  2. Track how many distinct required characters have reached their needed multiplicity (`formed`). When formed equals the number of distinct characters in t, the window is valid.
  3. While the window is valid, record it if it's the shortest so far, then shrink from the left to try to find a smaller valid window.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Shortest Unique Prefixes - Meta (medium)
  • Compute Exclusive Execution Times - Meta (medium)
  • Solve Tree Columns And Maze Variants - Meta (medium)
  • Solve Tree Diameter and Palindromic Counts - Meta (medium)
  • Simulate Monster Team Battles - Meta (hard)