Solve stock-pattern trading and substring elimination
Company: Jump Trading
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Quick Answer: 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
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.
Input: ([1, 2, 2, 3], [1, 1], [-1])
Expected Output: [0, 0, 0, 0]
Explanation: The flat day creates sign 0, which breaks any length-2 match that would cross it.
Input: ([10], [1], [-1])
Expected Output: [0]
Explanation: With only one price, there is no day-to-day movement, so no trade can happen.
Input: ([], [1], [-1])
Expected Output: []
Explanation: Empty input should return an empty holdings array.
Solution
def solution(prices, buyPattern, sellPattern):
n = len(prices)
if n == 0:
return []
holdings = [0] * n
kb = len(buyPattern)
ks = len(sellPattern)
buy_target = 0
for x in buyPattern:
buy_target = (buy_target << 1) | (1 if x == 1 else 0)
sell_target = 0
for x in sellPattern:
sell_target = (sell_target << 1) | (1 if x == 1 else 0)
buy_mask = 0
sell_mask = 0
buy_keep = (1 << kb) - 1
sell_keep = (1 << ks) - 1
held = 0
nonzero_streak = 0
for t in range(1, n):
diff = prices[t] - prices[t - 1]
if diff > 0:
bit = 1
nonzero_streak += 1
elif diff < 0:
bit = 0
nonzero_streak += 1
else:
bit = 0
nonzero_streak = 0
buy_mask = ((buy_mask << 1) | bit) & buy_keep
sell_mask = ((sell_mask << 1) | bit) & sell_keep
sell_match = nonzero_streak >= ks and sell_mask == sell_target
buy_match = nonzero_streak >= kb and buy_mask == buy_target
if sell_match and held > 0:
held -= 1
if buy_match:
held += 1
holdings[t] = held
return holdings
Time complexity: O(n + len(buyPattern) + len(sellPattern)). Space complexity: O(1) extra space beyond the output array.
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
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.
Input: ("abcde", ["xy", "zz"])
Expected Output: 5
Explanation: No adjacent pair ever matches the forbidden list.
Input: ("aaaa", ["aa"])
Expected Output: 0
Explanation: The string disappears as two 'aa' pairs are eliminated.
Input: ("", ["ab"])
Expected Output: 0
Explanation: An empty string stays empty.
Solution
def solution(s, forbidden):
bad = [[False] * 26 for _ in range(26)]
for pair in forbidden:
a = ord(pair[0]) - 97
b = ord(pair[1]) - 97
bad[a][b] = True
stack = []
for ch in s:
stack.append(ch)
if len(stack) >= 2:
a = ord(stack[-2]) - 97
b = ord(stack[-1]) - 97
if bad[a][b]:
stack.pop()
stack.pop()
return len(stack)
Time complexity: O(len(s) + len(forbidden)). Space complexity: O(len(s)) in this Python implementation.
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.