Solve stock-pattern trading and substring elimination
Company: Jump Trading
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Part A — Stock trading by pattern signals:
- Input: an integer array prices (length n) of daily stock prices; an array buyPattern and an array sellPattern, each containing only -1 or 1, where 1 means the price went up from the previous day and -1 means it went down.
- Define sign(prices[i] - prices[i-1]) as 1 if positive, -1 if negative, and 0 if zero. A pattern of length k matches on day t (t >=
1) if the last k day-to-day signs [sign(prices[t-k+1]-prices[t-k]), ..., sign(prices[t]-prices[t-1])] equals the pattern exactly (zeros break a match since patterns contain only -1 or
1).
- Start with 0 shares. On each day t, if a sellPattern match occurs, sell 1 share (only if holdings >
0); if a buyPattern match occurs, buy 1 share. Both actions can occur on the same day; process the sell before the buy. Shorting is not allowed; holdings never go below 0.
- Output: an array holdings of length n where holdings[t] is the number of shares held after processing day t. Example output format: [0,0,1,2,1,0].
- Target: O(n) time and O(
1) extra space beyond the output.
Part B — Remove fixed substrings repeatedly:
- Input: a string s and a set P of disallowed 2-character substrings (e.g., {"ab", "bc", "cd"}).
- Task: Repeatedly remove any occurrence of any substring in P until none remain. Return the final string length (and discuss how to return the final string as well).
- Constraints: n up to 2e5; |P| up to 26*26. Design an O(n) time solution with O(
1) or O(min(n, alphabet)) extra space, and explain correctness.
Overview: This question evaluates algorithmic skills in array pattern recognition and string processing, specifically detecting day-to-day sign patterns for simulated trading and repeated elimination of fixed two-character substrings; it belongs to the Coding & Algorithms domain for a Machine Learning Engineer position and targets practical application of linear-time, constant-extra-space techniques. It is commonly asked to evaluate efficient O(n) algorithm design, handling of stateful streaming simulations and in-place string reduction under tight time/space constraints, and correctness reasoning for edge cases.
Part 1: Stock Trading by Pattern Signals
You are given daily stock prices and two movement patterns: buyPattern and sellPattern.
For each day t >= 1, define sign(prices[t] - prices[t-1]) as:
- 1 if the price increased
- -1 if the price decreased
- 0 if the price stayed the same
A pattern of length k matches on day t if the last k day-to-day signs exactly equal that pattern. Since patterns contain only -1 and 1, any 0 inside that window breaks the match.
You start with 0 shares. On each day t:
1. If sellPattern matches, sell 1 share if you currently hold at least 1 share.
2. If buyPattern matches, buy 1 share.
If both match on the same day, process the sell before the buy. Shorting is not allowed, so holdings can never go below 0.
Return an array holdings where holdings[t] is the number of shares you hold after processing day t. Day 0 always starts with 0 shares.
Constraints
- 0 <= len(prices) <= 2 * 10^5
- 1 <= len(buyPattern), len(sellPattern) <= 2 * 10^5
- Each value in buyPattern and sellPattern is either -1 or 1
- -10^9 <= prices[i] <= 10^9
- Shorting is not allowed; holdings must stay >= 0
Examples
Input: ([5, 6, 7, 6, 5, 6], [1, 1], [-1, -1])
Expected Output: [0, 0, 1, 1, 0, 0]
Explanation: The buy pattern [1, 1] matches on day 2, so you buy once. The sell pattern [-1, -1] matches on day 4, so you sell once.
Input: ([5, 6, 7], [1], [1])
Expected Output: [0, 1, 1]
Explanation: Every up day matches both patterns. Selling is processed before buying, so day 1 ends with 1 share instead of 0.
Hints
- Convert each pattern into a bitmask: map 1 to bit 1 and -1 to bit 0, then keep rolling masks for the last k signs.
- Track the length of the current suffix of non-zero signs. A zero price change breaks every pattern ending on that day.
Part 2: Streaming Removal of Forbidden Pairs
You are given a lowercase string s and a collection forbidden of disallowed 2-character substrings.
To make the process deterministic, reduce the string in a left-to-right scan:
1. Start with an empty current string.
2. Append the next character from s.
3. If the last two characters of the current string form a forbidden pair, delete those two characters immediately.
After the full scan, return the length of the remaining string.
If you also wanted the final string, the same algorithm can return the remaining characters instead of just the length.
Constraints
- 0 <= len(s) <= 2 * 10^5
- 0 <= len(forbidden) <= 26 * 26
- s contains only lowercase English letters
- Each forbidden entry is a 2-character lowercase string
Examples
Input: ("abbc", ["ab", "bc"])
Expected Output: 0
Explanation: Reading 'b' removes 'ab', and later reading 'c' removes 'bc', so the result is empty.
Input: ("acbd", ["cb", "ad"])
Expected Output: 0
Explanation: Reading 'b' creates 'cb', which is removed. Then reading 'd' creates 'ad', which is removed.
Hints
- Think of the surviving characters as a stack.
- When you append one new character, only the last two surviving characters can create a new removable pair.