I gave the naive approach first. The interview asked me to optimize it and it took me some time but I then suggested to store it as a binary tree. Didn't have time to code it out. I wasn't well versed with runtime complexities so I don't expect a call back, but hoping for the best.