Implement four data-structure/string geometry tasks
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem A — Multiply two non-negative integer strings
You are given two strings `num1` and `num2` representing non-negative integers in base-10.
- Return their product as a base-10 string.
- You **must not** convert the inputs to built-in integer/big-integer types.
- The output must not contain leading zeros (unless the value is exactly `"0"`).
**Input:** `num1`, `num2` (strings)
**Output:** product as a string
**Constraints (typical):** `1 <= len(num1), len(num2) <= 10^4`, digits only.
---
## Problem B — Parse email addresses from a huge log string
You are given a very large string `s` that contains multiple **records**. Conceptually:
- Records are separated by a semicolon `;` **only when the semicolon is not inside**:
- double quotes `"..."` (display name), or
- parentheses `(...)` (a comment).
- Each record corresponds to one email entry, but the record can contain optional parts:
- an optional display name (possibly quoted),
- an email address token containing exactly one `@`,
- optional comments in parentheses, and a comment may appear **anywhere** in the record.
**Task:** Extract all email addresses from the string and return a **deduplicated** list.
- If an email appears multiple times, keep only the first occurrence.
- You may assume the email address itself does not contain spaces/semicolons/parentheses/quotes.
**Input:** one string `s`
**Output:** list of unique email strings
---
## Problem C — Maximum area axis-aligned rectangle from points
You are given `N` distinct points on a 2D integer grid: `points[i] = (xi, yi)`.
A rectangle is **axis-aligned** (sides parallel to axes). A valid rectangle requires all four corners to be present in the input set.
**Task:** Return the maximum rectangle area possible. If no rectangle can be formed, return `0`.
**Input:** array of points
**Output:** integer maximum area (or `0`)
**Constraints (typical):** `1 <= N <= 2000` (or similar), coordinates fit in 32-bit signed int.
---
## Problem D — Stock price tracker with corrections
Design a data structure supporting these operations:
- `update(timestamp, price)`: record the stock price at `timestamp`.
- If the timestamp already exists, this call **overwrites/corrects** the previous price.
- `current()`: return the latest stock price (price at the maximum timestamp seen so far).
- `maximum()`: return the maximum price among all timestamps currently stored.
- `minimum()`: return the minimum price among all timestamps currently stored.
**Input:** sequence of operations
**Output:** values returned by `current/maximum/minimum`
**Constraints (typical):** up to `2e5` operations; timestamps and prices are positive integers.
Quick Answer: This multi-part question evaluates manual big-integer string multiplication, robust parsing and tokenization of complex log formats, computational geometry for axis-aligned rectangle detection, and dynamic data-structure design for time-series updates and aggregate queries.
Multiply Integer Strings
Multiply two non-negative integer strings without converting the full inputs to built-in integers.
Constraints
- Inputs contain digits only
Examples
Input: ('123', '456')
Expected Output: '56088'
Input: ('0', '999')
Expected Output: '0'
Input: ('99', '99')
Expected Output: '9801'
Hints
- Simulate grade-school multiplication into digit positions.
Parse Unique Email Addresses
Extract unique email tokens from records separated by semicolons outside quotes and comments. Keep first occurrence order.
Constraints
- Email tokens contain exactly one @ and no spaces or separators
Examples
Input: ('Alice <a@example.com>; Bob (x@y) <b@example.com>; a@example.com',)
Expected Output: ['a@example.com', 'b@example.com']
Input: ('"Last; First" <lf@example.com>; note (skip@x.com) c@example.com',)
Expected Output: ['lf@example.com', 'c@example.com']
Hints
- First split records while tracking quotes and parentheses.
Maximum Axis-Aligned Rectangle Area
Given distinct grid points, return the largest area of an axis-aligned rectangle whose four corners are present, or 0.
Examples
Input: ([[0, 0], [0, 2], [3, 0], [3, 2], [1, 1]],)
Expected Output: 6
Input: ([[0, 0], [1, 1]],)
Expected Output: 0
Input: ([[0, 0], [0, 1], [1, 0], [1, 1], [2, 0], [2, 1]],)
Expected Output: 1
Hints
- For each x column, remember the previous x where each pair of y values appeared.
Stock Price Tracker with Corrections
Process update/current/maximum/minimum operations. update overwrites a timestamp. Return outputs from query operations.
Constraints
- Timestamps and prices are positive integers
Examples
Input: ([['update', 1, 10], ['update', 2, 5], ['current'], ['maximum'], ['update', 1, 3], ['maximum'], ['minimum']],)
Expected Output: [5, 10, 5, 3]
Input: ([['update', 5, 7], ['current'], ['update', 5, 2], ['current'], ['minimum'], ['maximum']],)
Expected Output: [7, 2, 2, 2]
Hints
- Use timestamp->price plus min/max heaps with lazy deletion.