Given some ids of hotels and several reviews of these hotels, Sort the hotels based on their reviews. To evaluate reviews you are given a list of words. A review is better than another review if those words found in one review more than another one. In case two hotels get same word count in their reviews, consider hotel id while sorting.

Example:

Number of hotels: 3
List of words: "happy", "nice", "you", "view", "liked", "cheap"
Number of reviews: 5
Review 1 for hotel 1: I liked the bedroom, although the balcony was little
Review 2 for hotel 2: Everything was nice. I am happy with their service
Review 3 for hotel 3: Do you want cheap hotel with nice view. This one is definitely good
Review 4 for hotel 2: Overall nice. I liked it and happy
Review 5 for hotel 3: Cheap but liked it

In review 1, found 1 word
In review 2, found 2 words
In review 3, found 4 words
In review 4, found 3 words
In review 4, found 2 words

Result:
Hotel 3 = Total 6 words found
Hotel 2 = Total 5 words found
Hotel 1 = Total 1 word found

Apporach 1:

This approach is based on Robin Karp pattern matching algorithm.

  1. Make hash of all given words.
  2. Traverse each review of hotel and count matched words.
  3. Add the count to corresponding hotel.
  4. Sort hotel in terms of count, If two hotel has same count then sort in terms of hotel index.

Code:

public class HotelReviews_Demo {

    static final int MOD = 101;

    static int noHotels;
    static String[] words;
    static Hotel[] hotels;

    static int b = 31;
    static int wordHash[];

    static class Hotel implements Comparable<Hotel> {
        int index, count;

        public Hotel(int index, int count) {
            this.index = index;
            this.count = count;
        }

        @Override
        public int compareTo(Hotel o) {
            if (this.count == o.count) return this.index - o.index;
            return o.count - this.count;
        }
    }

    static int hash(String str) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash = ((hash * b) + str.charAt(i)) % MOD;
        }
        return hash;
    }

    static void preProcessWords() {
        wordHash = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            wordHash[i] = hash(words[i]);
        }
        Arrays.sort(wordHash);
    }

    static int search(String review) {
        int ret = 0;

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < review.length(); i++) {
            char ch = review.charAt(i);
            if (ch == ' ' || ch == '.') {
                int hash = hash(sb.toString());
                if (Arrays.binarySearch(wordHash, hash) >= 0) ret++;
                sb = new StringBuilder();
                continue;
            }
            sb.append(ch);
        }
        if (sb.length() > 0) {
            int hash = hash(sb.toString());
            if (Arrays.binarySearch(wordHash, hash) >= 0) ret++;
        }
        return ret;
    }

    public static void main(String[] args) {
        Scanner scanner = inputFromFile();

        noHotels = scanner.nextInt();
        hotels = new Hotel[noHotels];
        for (int i = 0; i < noHotels; i++) {
            hotels[i] = new Hotel(i, 0);
        }

        int wordCount = scanner.nextInt();
        words = new String[wordCount];
        for (int i = 0; i < wordCount; i++) words[i] = scanner.next();

        preProcessWords();

        int noReviews = scanner.nextInt();
        for (int i = 0; i < noReviews; i++) {
            int index = scanner.nextInt();
            String review = scanner.nextLine().trim();
            hotels[index-1].count += search(review);
        }

        Arrays.sort(hotels);

        for (int i = 0; i < hotels.length; i++) {
            System.out.println(hotels[i].index+1 + " " + hotels[i].count);
        }
    }

    static Scanner inputFromFile() {
        try { return new Scanner(new FileInputStream("input.txt")); }
        catch (FileNotFoundException e) { e.printStackTrace(); }
        return null;
    }

    static Scanner inputFromSystem() {
        return new Scanner(System.in);
    }
}

Approach 2:

This approach is based on Aho-Corasick multiple pattern matching algorithm and this problem is designed to to be solved this algorithm.

  1. Build string matching machine using the given words.
  2. Run Aho-Corasick for each review and found matched words.
  3. Add matched count to corresponding hotel
  4. Sort hotel in terms of count, If two hotel has same count then sort in terms of hotel index.

Code:

public class HotelReviews_Demo2 {

    static final int MAXS = 500;
    static final int MAXC = 29;

    static int noHotels;
    static String[] words;
    static Hotel[] hotels;

    static int[] out;
    static int[] f;
    static int[][] g;

    static int charValue(char ch) {
        if (Character.isUpperCase(ch)) ch = Character.toLowerCase(ch);
        if (Character.isLowerCase(ch)) return ch - 'a';
        if (ch == '.') return 26;
        if (ch == ',') return 27;
        if (ch == ' ') return 28;
        return -1;
    }

    static int buildMatchingMachine(String keys[]) {
        out = new int[MAXS];
        g = new int[MAXS][MAXC];
        for (int i = 0; i < MAXS; i++) Arrays.fill(g[i], -1);

        int states = 1;

        for (int i = 0; i < keys.length; i++) {
            String key = keys[i];
            int currentState = 0;

            for (int j = 0; j < key.length(); j++) {
                int ch = charValue(key.charAt(j));
                if (g[currentState][ch] == -1) g[currentState][ch] = states++;
                currentState = g[currentState][ch];
            }

            out[currentState] |= (1 << i);
        }

        // Initialize values in fail function
        f = new int[MAXS];
        Arrays.fill(f, -1);

        Queue<Integer> q = new LinkedList<>();

        for (int ch = 0; ch < MAXC; ch++) {
            if (g[0][ch] != -1) {
                f[g[0][ch]] = 0;
                q.offer(g[0][ch]);
            } else {
                g[0][ch] = 0;
            }
        }

        while (!q.isEmpty()) {
            int state = q.poll();

            for (int ch = 0; ch < MAXC; ch++) {
                if (g[state][ch] != -1) {
                    // Find failure state of removed state
                    int failure = f[state];

                    // Find the deepest node labeled by proper
                    // suffix of string from root to current
                    // state.
                    while (g[failure][ch] == -1)
                        failure = f[failure];

                    failure = g[failure][ch];
                    f[g[state][ch]] = failure;

                    // Merge output values
                    out[g[state][ch]] |= out[failure];

                    // Insert the next level node (of Trie) in Queue
                    q.offer(g[state][ch]);
                }
            }
        }

        return states;
    }

    static int findNextState(int currentState, char nextInput) {
        int answer = currentState;

        int ch = charValue(nextInput);
        while (g[answer][ch] == -1)
            answer = f[answer];

        return g[answer][ch];
    }

    static int searchWords(String keys[], String text) {
        int ret = 0;

        int currentState = 0;

        for (int i = 0; i < text.length(); i++) {
            currentState = findNextState(currentState, text.charAt(i));

            if (out[currentState] == 0) continue;

            for (int j = 0; j < keys.length; j++) {
                if ((out[currentState] & (1 << j)) != 0) {
                    ret++;
                }
            }
        }
        return ret;
    }

    static class Hotel implements Comparable<Hotel> {
        int index, count;

        public Hotel(int index, int count) {
            this.index = index;
            this.count = count;
        }

        @Override
        public int compareTo(Hotel o) {
            if (this.count == o.count) return this.index - o.index;
            return o.count - this.count;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = inputFromFile();

        noHotels = scanner.nextInt();
        hotels = new Hotel[noHotels];
        for (int i = 0; i < noHotels; i++) {
            hotels[i] = new Hotel(i, 0);
        }

        int wordCount = scanner.nextInt();
        words = new String[wordCount];
        for (int i = 0; i < wordCount; i++) words[i] = scanner.next();

        buildMatchingMachine(words);

        int noReviews = scanner.nextInt();
        for (int i = 0; i < noReviews; i++) {
            int index = scanner.nextInt();
            String review = scanner.nextLine().trim();
            hotels[index-1].count += searchWords(words, review);
        }

        Arrays.sort(hotels);

        for (int i = 0; i < hotels.length; i++) {
            System.out.println(hotels[i].index+1 + " " + hotels[i].count);
        }
    }

    static Scanner inputFromFile() {
        try { return new Scanner(new FileInputStream("input.txt")); }
        catch (FileNotFoundException e) { e.printStackTrace(); }
        return null;
    }

    static Scanner inputFromSystem() {
        return new Scanner(System.in);
    }
}
Blog Comments powered by Disqus.

Previous Post