WeRide New Grad Software Engineer Interview Experience — Expression-to-Sum-of-Products Problem

WeRide New Grad SDE first-round technical screening, entirely on HackerRank, including video. The interviewer was 4 minutes late. We first talked about my resume for about 15 minutes — they asked how what I did during my PhD connects to an SDE role. Then we moved on to the problem, conducted entirely in Chinese. The question was as follows:

Given an expression made up only of lowercase English letters, the plus sign "+", the multiplication sign "", and left/right parentheses "(" and ")", return an equivalent expression that only uses "+" to connect terms. Part 1: first consider the case where there is no "+" outside the parentheses, for example: (a+b)(c+d) ---> return ac+ad+bc+bd; a*(b+c)*(d+e+f)*g ---> return abdg+abeg+abfg+acdg+aceg+acfg

Part 2 (a follow-up, needed a complete working solution): consider the case where there is "+" outside the parentheses too, for example: a+bc(d+e+f)+k+m*(g+h)+i ---> return a+bcd+bce+bcf+k+mg+mh+i

The code for part 1 is fairly simple — you don't need a stack. While traversing the input expression, you just need one variable to track the latest multiplication result, and once traversal ends, that variable holds the final result. O(1) space complexity.

The logic for part 2 is more involved — you need a stack whose top tracks the latest multiplication result, then depending on the most recently encountered symbol, you decide whether to update the expression at the top of the stack or push a new stack element. This needs extra O(n) space complexity.