I interviewed for SDE but in the survey, I filled in “frontend” for the field. The interviewer immediately asked a front-end related question: how to write an algorithm to calculate the difference between two DOM trees.
After clarifying the input and output, where a node can have multiple children and the node value is just a string, considering only cases where nodes are removed or added, the output should return the changed nodes. The children nodes are ordered. I initially suggested using a list to store children nodes and then mentioned using BFS to compare each node.
The problem was then simplified to diff two nodes’ children. The example given by the interviewer was:
A
B C D
A
C D B
The change from BCD to CDB represents B being removed once and then added again. The output should record these changes.
I later thought of an example myself:
AB -> ACB
Should this be considered adding a C? If it is counted as removing B and then adding CB, it would be too simple. However, I didn’t think of this example during the interview.
At one point, the interviewer suggested using a linked list to store these children nodes, which simplified the algorithm to diff two linked lists of node changes.
My algorithm skills were lacking, so I couldn’t come up with a solution and we moved on. Any expert who can provide a solution, and also, happy new year!