I was absolutely rekt by this exact question several years back for a Microsoft internship interview. I had just finished my first CS class where I learned binary search, heaps, hash tables, but unfortunately not cumulative sums.