Feature #6: Reorganizing Search Results

Description

For this search engine feature, we are given all the search results to display on one page. Each page shows a maximum of twenty-five search results at a time. Multiple pages in the search results can belong to the same domain. However, the team has decided that we do not want adjacent results to be from the same domain because they are likely to be similar and might favor only one site. To give our users a wide range of results, we want to rearrange the results such that two results from the same domain are not consecutive.

Suppose, we denote each domain with a character. There can only be twenty-five results on a page, so the maximum number of simultaneous domains in the search results will also be 25. Thus, denoting them with a character will be simple. Now, you are given a string that represents the initial order of the search results. Your job is to reorganize this string so adjacent characters are not identical. For example, if the input string is bbnnc, then the output should be bnbcn or any other reordering of characters such that it fulfills the conditions. If this is not possible, we will just show the original order of results.

Solution

The optimal way to solve this question is to use the greedy technique using the heap data structure. If we build the resultant order from the most common letter followed by the second most common letter and keep following this trend, we are likely to get the needed result. If this fails, it means it is not possible to rearrange the string. The condition for failing occurs when the frequency of a character exceeds (n+1) / 2 ...