Katkat
Back

Implement four data-structure/string geometry tasks

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests foundational skills in string arithmetic, parsing, coordinate geometry, and segment tree-based range queries.

Part 1: String Multiplication

Implement a function multiply(num1: str, num2: str) -> str that returns the product of two non-negative integers represented as strings. Do not use built-in big integer libraries.

Part 2: Log Tokenization

Given a log string format [TIMESTAMP] LEVEL: MESSAGE, write a parser parse_logs(logs: List[str]) -> List[dict] that extracts each component. Handle malformed lines by returning null for the specific entry.

Part 3: Axis-Aligned Rectangles

Given a list of 2D points [(x1, y1), (x2, y2), ...], determine if there exists at least one axis-aligned rectangle formed by four of these points. Points are axis-aligned if they form four right angles and their sides are parallel to the X and Y axes.

Part 4: Time-Series Aggregate

Design a data structure that supports two operations:

  1. update(timestamp: int, value: int): Set the value at a specific timestamp.
  2. query(start: int, end: int) -> int: Return the sum of all values where start "6"`

Rectangle Detection: Points [(0,0), (0,1), (1,0), (1,1)] -> True

Constraints

  • num1, num2 length <= 200.
  • Log list size <= 1000.
  • Number of points <= 500.
  • Time-series timestamps are integers between 0 and 10^5.

Hints

Hint 1

For multiplication, mimic the manual long-multiplication process using an array of size (len1 + len2) to store intermediate digits.

Hint 2

For rectangle detection, store points in a hash set and for every pair of points forming a diagonal, check if the other two corners exist in the set.

Hint 3

For the time-series query, a Fenwick tree (Binary Indexed Tree) or a Segment Tree is ideal for O(log N) updates and range sum queries.

Follow-up questions

  • How would you optimize the multiplication if one number is significantly smaller than the other?
  • How does your rectangle detection complexity change if the number of points grows to 10^5?
  • How would you modify the time-series structure to support 'moving average' queries over a window of size K?