This is the exact problem I was given during 1st telephone interview (copy and pasted):
You’re given an array of CSV strings representing search results. Results are sorted by a score initially. A given host may have several listings that show up in these results. Suppose we want to show 12 results per page, but we don’t want the same host to dominate the results. Write a function that will reorder the list so that a host shows up at most once on a page if possible, but otherwise preserves the ordering. Your program should return the new array and print out the results in blocks representing the pages.
["host_id,listing_id,score,city",
"1,28,300.1,San Francisco",
"4,5,209.1,San Francisco",
"20,7,208.1,San Francisco",
"23,8,207.1,San Francisco",
"16,10,206.1,Oakland",
"1,16,205.1,San Francisco",
"1,31,204.6,San Francisco",
"6,29,204.1,San Francisco",
"7,20,203.1,San Francisco",
"8,21,202.1,San Francisco",
"2,18,201.1,San Francisco",
"2,30,200.1,San Francisco",
"15,27,109.1,Oakland",
"10,13,108.1,Oakland",
"11,26,107.1,Oakland",
"12,9,106.1,Oakland",
"13,1,105.1,Oakland",
"22,17,104.1,Oakland",
"1,2,103.1,Oakland",
"28,24,102.1,Oakland",
"18,14,11.1,San Jose",
"6,25,10.1,Oakland",
"19,15,9.1,San Jose",
"3,19,8.1,San Jose",
"3,11,7.1,Oakland",
"27,12,6.1,Oakland",
"1,3,5.1,Oakland",
"25,4,4.1,San Jose",
"5,6,3.1,San Jose",
"29,22,2.1,San Jose",
"30,23,1.1,San Jose"
]My approach is below, but try to solve it yourself first before reading this.
Idea: Put duplicates into a priority queue that is ordered according to the highest score listing of each host. Only use it when there are duplicates, otherwise we just iterate through the listings.
class Solution {
static class Listing {
Float score;
String hostId;
String listing;
Listing(float s, String h, String l) {
score = s;
hostId = h;
listing = l;
}
}
static class Host {
String hostId;
LinkedList<Listing> listings = new LinkedList<>();
Host(String s) {
hostId = s;
}
}
static Listing getListingFromString(String s) {
String[] fields = s.split(",");
String hostId = fields[0];
float score = Float.parseFloat(fields[2]);
return new Listing(score,hostId,s);
}
static List<String> getSortedPages(ArrayList<String> listings, int perPage) {
Set<String> set = new HashSet<>();
PriorityQueue<Host> duplicates = new PriorityQueue<>((a,b)->b.listings.getFirst().score.compareTo(a.listings.getFirst().score));
Map<String,Host> map = new HashMap<>();
List<String> output = new ArrayList<>();
int count = 0;
for(int i=1; i<listings.size(); i++) {
if(count > 0 && count % perPage == 0) {
set.clear();
count = 0;
LinkedList<Host> temp = new LinkedList<>();
while(!duplicates.isEmpty()) {
Host h = duplicates.poll();
output.add(h.listings.removeFirst().listing);
set.add(h.hostId);
temp.add(h);
count++;
}
while(!temp.isEmpty()) {
Host h = temp.removeFirst();
if(h.listings.size() > 0) {
duplicates.add(h);
}
}
}
Listing l = getListingFromString(listings.get(i));
if(!set.contains(l.hostId)) {
output.add(l.listing);
set.add(l.hostId);
count++;
} else {
Host h = map.computeIfAbsent(l.hostId, k->new Host(l.hostId));
h.listings.add(l);
if(h.listings.size() == 1) { // Not in priority queue
duplicates.add(h);
}
}
}
while(!duplicates.isEmpty()) {
Host h = duplicates.poll();
output.add(h.listings.removeFirst().listing);
if(h.listings.size() > 0) {
duplicates.add(h);
}
}
return output;
}
}During the interview I started working on a different approach but after some time realized it was not a good approach. When I figured out a better one, I ran out of time and wasn't able to optimize it. I didn't pass the tech screen.
I took some time after the interview to finish optimizing my approach and finished the solution above.
But is this the best solution? It's still a lot of code for a tech phone interview screen, and I feel there must be a more elegant solution.
The above is O(n) runtime best case, O(n log n) worst case, and O(n) worst case space complexity