Given the program image, all you need to trace to determine program execution is know which branches were taken, by outputting the addresses of each taken branch in order. You could further compress by removing the addresses of the branches and instead saying 'we are starting at address xxx and evaluated the branches that follow in the order: taken, taken, not taken, taken, not taken....etc.' You could compress loops even more by identifying a loop and outputting 'branch at address xxx was taken 36 times, then not taken.' At the time of the interview I had not been told that the position was for working on Arm's ETM (Extended Trace Macrocell) architecture which uses this exact procedure (with some added complexity) to generate program trace!