Katkat
Back

Solve stock-pattern trading and substring elimination

Jump TradingMachine Learning Engineer · Online Assessment
MediumMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

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 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.