Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Sort hotel list challenge

Sharing is caring!

Problem statement
Given a set of hotels and its guests reviews, sort the hotels based on a list of words specified by a user. The criteria to sort the hotels should be how many times the words specified by the user is mentioned in the hotel reviews.

Input
The first line contains a space-separated set of words which we want to find mentions in the hotel reviews.

The second line contains one integer M, which is the number of reviews.

This is followed by M+M lines, which alternates an hotel ID and a review belonging to that hotel.

Output
A list of hotel IDs sorted, in descending order, by how many mentions they have of the words specified in the input.

Notes
– The words to be find will always be singe words line ‘breakfast’ or ‘noise’. Never double words like ‘swimming pool’.
– Hotel ud is a 4-byte integer.
– Words match should be case-insensitive.
– Dots and commas should be ignored.
– If a word appears in a review twice, it should count twice.
– If two hotels have the same number of mentions, they should be sorted in the output based on their ID, smallest ID first.
– In case one or more test cases time out, consider revisiting the runtime complexity of your algorithms.

Sample input

breakfast beach citycenter location metro view staff price
5
1
This hotel has a nice view of the citycenter. The location is perfect.
2
The breakfast is ok. Regarding the location, it is quite far from citycenter but price is cheap so it is worth.
1
Location is excellent, 5 minutes from citycenter. There is also a metro station very close to the hotel.
1
They said I could't take my dog and there were other guests with dogs! That is not fair!
2
Very friendly staff and goof cost-benefit ratio. Its location is a bit far from citycenter.

Sample output

2 1

Explanation
Hotel 2 has 7 mentions of the words: ‘location’ and ‘citycenter’ are mentioned twice while ‘breakfast’, ‘price’ and ‘staff’ are mentioned once. Hotel 1 in the other hand has 6 mentions in total ‘location’ and ‘citycenter’ also twice and then ‘view’ and ‘metro’ once.

Solution/Full code

public class SortHotelList {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        // Read dictionary
        String[] words = in.nextLine().split(" ");
        Set dict = new HashSet();
        for (String word : words) {
            dict.add(word.toLowerCase());
        }

        // Read number of reviews
        int m = in.nextInt();

        // Read review
        Map hotel2count = new HashMap(); // hotel ID -> Word Count
        for (int i = 0; i < m; i++) {
            // Read hotel id
            int id = Integer.parseInt(in.next());
            in.nextLine();

            // Put id in map in case of new
            if (!hotel2count.containsKey(id)) {
                hotel2count.put(id, 0);
            }

            // Read review text
            String[] review = in.nextLine().split(" ");
            for (String word : review) {
                // Remove any ' ', ',', '.', '!' or '?' from word
                word = word.replaceAll("[$,.!?]", "").toLowerCase();
                if (dict.contains(word)) {
                    hotel2count.put(id, hotel2count.get(id) + 1);
                }
            }
        }

        // Sort
        List> sorted = new ArrayList(hotel2count.entrySet());
        Collections.sort(sorted, new Comparator>() {
            @Override
            public int compare(Map.Entry o1, Map.Entry o2) {
                if (o1.getValue() == o2.getValue()) {
                    return o1.getKey() - o2.getKey();
                } else {
                    return o2.getValue() - o1.getValue();
                }
            }
        });

        // Print sorted list
        for (Map.Entry hotelEntry : sorted) {
            System.out.print(hotelEntry.getKey() + " ");
        }
    }
}