Implement string-based candlestick classifier
Company: Robinhood
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that takes a single input string encoding N daily OHLC price records in the format "o1,h1,l1,c1;o2,h2,l2,c2;...;oN,hN,lN,cN" (semicolon-separated records, comma-separated fields). Return one output string of length N where the i-th character classifies the i-th candle: 'B' if ci > oi, 'S' if ci < oi, 'D' if ci == oi. A record is invalid if hi < max(oi,ci) or li > min(oi,ci), or if any field is missing or not a valid number; for invalid records output 'X' in that position. N can be up to 200,000; parse in one pass in O(total input length) time and O(
1) extra space beyond the output. Do not convert the input into arrays; parse the string directly. Provide code and brief tests.
Quick Answer: This question evaluates string parsing, streaming input processing, numeric validation, and attention to time/space complexity in the Coding & Algorithms category, focusing on efficient single-pass parsing and O(1) extra space constraints.
Write a function `solution(s)` that parses a single string containing N daily OHLC price records in the form `o1,h1,l1,c1;o2,h2,l2,c2;...;oN,hN,lN,cN` and returns a classification string of length N. For each record, output `B` if `close > open`, `S` if `close < open`, and `D` if `close == open`. If a record is invalid, output `X` for that position instead.
A record is invalid if any field is missing, any field is not a valid number, or if the candle shape is impossible: `high < max(open, close)` or `low > min(open, close)`.
Parse the input directly in one pass. Do not use `split` to materialize arrays of records or fields. Empty segments between semicolons count as records too, so `;;` creates an invalid empty record, and a trailing `;` creates a final invalid empty record. If the entire input string is empty, return an empty string.
For this problem, a valid number may have an optional leading `+` or `-`, at most one decimal point, and must contain at least one digit. Examples of valid numbers: `7`, `-3.5`, `+.5`, `10.`. Spaces and scientific notation are invalid.
Constraints
- 0 <= N <= 200000
- Let L be the total length of the input string; the solution should run in O(L) time
- Use O(1) extra space beyond the output string
- Do not convert the whole input into arrays of records or fields
- Each numeric token, if valid, has at most 30 characters including sign and decimal point
Examples
Input: ("10,12,9,11;8,9,5,6;5,6,4,5",)
Expected Output: "BSD"
Explanation: Record 1 is bullish, record 2 is bearish, and record 3 is a doji. All three records are valid.
Input: ("1,3,0,3;1,a,0,1;4,5,3,2;7,8,,7",)
Expected Output: "BXXX"
Explanation: The first candle is valid and bullish. The second contains a non-numeric field, the third has low > min(open, close), and the fourth is missing a field.
Hints
- Think of the parser as a small state machine: current record field count, current number state, and current record validity.
- To avoid floating-point issues, parse each number exactly as `(signed_integer_without_decimal_point, digits_after_decimal)` and compare by aligning scales.