CareerCup

SELECT city.name, COUNT(*) as count FROM orders LEFT JOIN city ON orders.city=city.id GROUP BY orders.city ORDER BY count DESC LIMIT N

dmitry.labutin is right, of course - Or use a heap.

use hash table to get the count by city by going throught the list of cities and then sort the result using heap

bnb

mnm

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class MostOrders {
	
	public static List<Entry<String,Integer>> topNCities(Map inputMap,int n){
		
		//inputMap : Map of city to number of orders
		Set<Entry<String,Integer>> entrySet = inputMap.entrySet();
		
		List<Entry<String,Integer>> list = new ArrayList<Entry<String,Integer>>(entrySet);
		
		Collections.sort(list,new Comparator<Map.Entry<String, Integer>>() {

			@Override
			public int compare(Entry<String, Integer> e1, Entry<String, Integer> e2) {
				
				return (e2.getValue()).compareTo(e1.getValue());
			}
		});
		
		List<Entry<String,Integer>> outputList = new ArrayList<Entry<String,Integer>>();
		//count top n cities
		int count = 0;
		
		
		for(Map.Entry<String, Integer> entry:list){		
			count++;
			if(count<=n)
				outputList.add(entry);
			//System.out.println(entry.getKey()+" == "+entry.getValue());
		}
		
		return outputList;
	}
	
	

	public static void main(String[] args){
		Map<String,Integer> inputMap = new HashMap<String,Integer>();
		inputMap.put("Austin", 65);
		inputMap.put("Houston", 30);
		inputMap.put("Chicago",50);
		inputMap.put("New Your", 100);
		inputMap.put("Colarado", 20);
		
		List<Entry<String, Integer>> output = topNCities(inputMap, 2);
		System.out.println(output);
		
	}
}

Sorting-free optimal solution. O(n) time. Use a priority queue to solve the problem. Perfectly dealt with the cases when at rank 10 there are multiple cities with the same number of orders.

import java.util.*;

class CityOrder {
    private String city;
    int orderCount;

    public CityOrder(String city) {
        this.city = city;
        orderCount = 1;
    }
}
public class TopNOrderCities {

    private PriorityQueue<CityOrder> topN = new PriorityQueue<>((o1, o2) -> (o1.orderCount - o2.orderCount));   //keep top n cities with most orders in here
    private Set<CityOrder> minOrderInTopNCities = new HashSet<>();
    private Map<String, CityOrder> cityOrderMap = new HashMap<>();

    public TopNOrderCities(int n, String[] orders) {
        for(String city: orders) {
            CityOrder cityOrder;

            if(!cityOrderMap.containsKey(city)) {
                cityOrder = new CityOrder(city);
                cityOrderMap.put(city, cityOrder);

                if(topN.size() < n) {
                    topN.add(cityOrder);
                    cityOrderMap.put(city, cityOrder);
                } else if(topN.peek().orderCount == 1) {
                    minOrderInTopNCities.add(cityOrder);
                }
            } else {
                cityOrder = cityOrderMap.get(city);
            }

            CityOrder min = topN.peek();
            if(cityOrder.orderCount == min.orderCount) {
                minOrderInTopNCities.add(cityOrder);
            } else if(cityOrder.orderCount == min.orderCount + 1) {

                if(minOrderInTopNCities.contains(cityOrder)) {
                    minOrderInTopNCities.remove(cityOrder);
                    topN.add(cityOrder);
                }
                CityOrder temp;
                if(topN.size() == n + 1) {
                     temp = topN.poll();
                     if(topN.peek().orderCount == cityOrder.orderCount) {
                         minOrderInTopNCities = new HashSet<>();
                     } else {
                         minOrderInTopNCities.add(temp);
                     }
                }
                if(topN.peek().orderCount == cityOrder.orderCount) {
                    minOrderInTopNCities = new HashSet<>();
                }

                min = topN.poll();
                if(cityOrder.orderCount == topN.peek().orderCount && minOrderInTopNCities.contains(cityOrder)) {
                    minOrderInTopNCities.remove(cityOrder);
                    topN.add(cityOrder);

                }
            }
        }
    }


}

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

This problem can be easily solved using map and priority queue.as map has key and value pair in key we will store city and value will store number of orders.in this way we have hash the city according to the number of order.now we will use priority queue to store this result.the city with more number of order will be a top and city with less number of order will be at bottom.