Imagine you’re interacting with Alexa. When you command Alexa to “acquire a certain item”, it begins to retrieve information from a variety of sources, which we’ll refer to as “catalogues”. Each catalogue responds with a sorted list of potential matches. Your task is to write a program that can consolidate these sorted lists into one coherent list.
Example – When you ask Alexa to buy bananas, it retrieves information from Prime, Whole Foods, Pantry, etc. Each of these catalogues returns a sorted list of potential matches, and our goal is to consolidate these sorted lists into one coherent list.
This problem is a classic multi-way merge task: given several already sorted lists, combine them into one globally sorted result. The most efficient approach is usually to use a min-heap that keeps track of the current smallest candidate from each list; each time you pop the smallest item, you push the next item from the same list. This preserves sorted order while keeping the runtime efficient, especially when the number of lists is large. A simpler pairwise merge approach also works, but the heap-based solution is typically the best fit for interview and online assessment settings.
