Meta Software Engineer Interview Experience — Nearest-Duplicate-Within-K, Then a DFS Question I Didn't Finish

The first question was to find the nearest matching numbers in an array, where the index distance needs to be within k.

Honestly a pretty simple question — basically just use a map to store value-to-index, then do one pass through the array. The follow-up was how to improve the space complexity. My first thought was that I'd need to clear out the earlier entries in the map, so she had me write the code and then analyze it. I went and scanned the map to delete entries, and after writing it I realized this would actually increase the time complexity. I then answered verbally that I'd need an extra queue to help with the clearing, since a queue preserves order — that needs O(2k) space. (Thinking back on it now, you'd only need to keep a pointer scanning from the front as you iterate through the array — if what's stored in the map matches the pointer's value, you can delete it. That only needs O(k) space.)

The second question was a simplified version of a problem I only know by the nickname "Erbaer" (the name as I heard it, meaning unclear).

The task was to insert plus signs, minus signs, or blanks between the digits 1 through 9 (you can also add one before the first digit) and check whether the result evaluates to a target number. It's really a simplified version of the original problem, but I haven't been grinding backtracking and string problems that much lately — I keep telling myself to practice more new problems, and some of the older fundamentals have gotten a bit rusty. I wrote it with DFS, generating all the possible combinations of operators, and then evaluating them against the array of digits. I felt like I got a little stuck, so I merged the digits and operators into a string and evaluated that instead. I think I ended up writing two helper functions, and in the end I didn't finish the code.