Determine subsequence expression equals target
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Given a sequence of positive 32-bit integers A and an integer target, determine whether there exists a subsequence of A (each element used at most once) such that, by inserting '+' or '*' between the chosen numbers and evaluating strictly from left to right (addition and multiplication have equal precedence), the resulting expression equals target. Follow-up: propose pruning techniques to accelerate the search.
Quick Answer: This question evaluates a candidate's ability to perform combinatorial search and expression evaluation over subsequences with operator insertion, testing algorithm design, state-space reasoning, and handling integer arithmetic constraints.