Solve stock trading with pattern rules
Company: Jump Trading
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Given an array of daily stock prices and two pattern arrays: sellPattern and buyPattern, each consisting of 1 (price up) and -1 (price down) representing the required consecutive daily movements that must appear immediately before a sell or buy action respectively. On any day you may execute both a buy and a sell if both patterns match ending that day. Return an integer array shares[0..n-1] where shares[i] is the number of shares held after processing day i. Example: prices = ?, sellPattern = [1,1], buyPattern = [...]; expected output [0,0,1,2,1,0].
——
Given a string s and a fixed set of substrings combos (e.g., {"bc", "ab", "cd"}), repeatedly remove every occurrence of any combo from s until no such substring remains. Return the resulting string.
Quick Answer: This set of problems evaluates algorithmic skills in pattern recognition, state management, and sequence processing, specifically testing pattern-based decision rules on time-series stock data and iterative substring elimination in string processing within the Coding & Algorithms domain.
Pattern-Triggered Stock Trading: Shares Held Each Day
You are given an integer array `prices`, where `prices[i]` is the stock price on day `i` (0-indexed), and two integer pattern arrays `buyPattern` and `sellPattern`. Each pattern consists only of `1` (an up day) and `-1` (a down day) and describes the consecutive daily price movements that must occur **immediately before and including** the current day to trigger an action.
Define the movement on day `i` (for `i >= 1`) as the sign of `prices[i] - prices[i-1]`: `1` if the price went up, `-1` if it went down. (For these problems all price changes are strictly up or down.)
Process the days from left to right while maintaining a holdings counter `shares` (starting at 0):
1. On day `i`, if the last `len(buyPattern)` movements ending on day `i` exactly equal `buyPattern`, buy 1 share (`shares += 1`).
2. Then, if the last `len(sellPattern)` movements ending on day `i` exactly equal `sellPattern` **and** you currently hold at least one share, sell 1 share (`shares -= 1`). You can never sell what you do not own, so `shares` stays at 0 rather than going negative.
Both a buy and a sell may happen on the same day if both patterns match (buy is applied first). A pattern that is longer than the number of movements available so far never matches.
Return the array `shares[0..n-1]` where `shares[i]` is the number of shares held **after** processing day `i`.
Example: `prices = [10, 9, 8, 7, 8, 9, 10, 11]`, `buyPattern = [-1, -1]` (buy after two down days), `sellPattern = [1, 1]` (sell after two up days). Movements are `[-1, -1, -1, 1, 1, 1, 1]`. Day 2 and day 3 each trigger a buy; days 5 and 6 each trigger a sell. The answer is `[0, 0, 1, 2, 2, 1, 0, 0]`.
Constraints
- 0 <= n == len(prices) <= 10^5
- Every consecutive pair of prices is strictly increasing or strictly decreasing (no equal adjacent prices).
- 1 <= len(buyPattern), len(sellPattern) <= n (when n >= 1)
- Each pattern entry is either 1 or -1.
- shares is never negative: a sell is only executed when at least one share is held.
Examples
Input: ([10, 9, 8, 7, 8, 9, 10, 11], [-1, -1], [1, 1])
Expected Output: [0, 0, 1, 2, 2, 1, 0, 0]
Explanation: Movements [-1,-1,-1,1,1,1,1]. Buys on days 2 and 3 (two downs), sells on days 5 and 6 (two ups); the would-be sell on day 7 is skipped because no shares are held.
Input: ([], [1], [1])
Expected Output: []
Explanation: Empty prices array yields an empty result.
Hints
- First convert prices into a movements array of +1/-1, then a pattern match on day i is just comparing a fixed-length slice of movements ending at day i.
- Apply the buy rule before the sell rule on the same day, and clamp at zero so you never sell shares you do not hold.
- A pattern of length L cannot match until at least L movements (i.e. day index >= L) are available.
Repeatedly Remove Combo Substrings Until Stable
You are given a string `s` and a fixed set of substrings `combos` (for example `["bc", "ab", "cd"]`). Repeatedly delete combo substrings from `s` until none of the combos appears anywhere in the string, then return the resulting string.
Because the order of removals can matter for overlapping combos, the reduction is defined **deterministically with a left-to-right stack**: scan `s` one character at a time, pushing each character onto a stack. After each push, check whether the characters at the **top of the stack** (its suffix) form one of the combos — testing longer combos before shorter ones — and if so, pop those characters off. Repeat the check until the stack's suffix no longer matches any combo, then continue scanning. The final stack, read bottom-to-top, is the answer. This single, well-defined pass naturally handles cascading removals where deleting one combo exposes a new one.
Example: `s = "aaabbbccc"`, `combos = ["aa", "bb", "cc"]`. Adjacent equal pairs collapse, leaving `"abc"`.
Constraints
- 0 <= len(s)
- 1 <= len(combos); each combo is a non-empty string.
- Removals cascade: deleting a combo may create a new combo at the junction, which must also be removed.
- The stack rule (longer combos checked first on the suffix) makes the result deterministic even when combos overlap.
Examples
Input: ("abxabccba", ["aa", "bb", "cc"])
Expected Output: "abx"
Explanation: ...cc collapses, then the exposed bb, then aa, leaving "abx".
Input: ("aaabbbccc", ["aa", "bb", "cc"])
Expected Output: "abc"
Explanation: Each run of three equal letters loses one matching pair, leaving one of each: "abc".
Hints
- Maintain a stack of characters; after pushing each character, only the suffix of the stack can newly form a combo, so you never need to rescan the whole string.
- After a removal, immediately re-check the new suffix — one deletion can expose another combo at the seam.
- Check longer combos before shorter ones so the reduction is well-defined when combo strings overlap.