Hotel Reviews
Given a set of reviews provided by the customers for different hotels and a string containing Good Words, you need to sort the reviews in descending order according to their Goodness Value (Higher goodness value first). We define the Goodness Value of a string as the number of Good Words in that string.
NOTE: Sorting should be stable. If review i and review j have the same Goodness Value then their original order would be preserved.
You are expected to use Trie in an Interview for such problems
Problem Constraints
1 <= No.of reviews <= 200
1 <= No. of words in a review <= 1000
1 <= Length of an individual review <= 10,000
1 <= Number of Good Words <= 10,000
1 <= Length of an individual Good Word <= 4
All the alphabets are lower case (a - z)
Input Format
First argument is a string A containing "Good Words" separated by "_" character
Second argument is a vector B of strings containing Hotel Reviews. Review strings are also separated by "_" character. Output Format
Return a vector of integers which contain the original indexes of the reviews in the sorted order of reviews. Example Input
Input 1:
A = "cool_ice_wifi"
B = ["water_is_cool", "cold_ice_drink", "cool_wifi_speed"]
Example Output
Output 1:
[2, 0, 1]
Example Explanation
Explanation 1:
sorted reviews are ["cool_wifi_speed", "water_is_cool", "cold_ice_drink"]
public class Solution {
static class Pair {
int index;
int value;
Pair(int i, int v) {
index = i;
value = v;
}
}
public int[] solve(String A, String[] B) {
Set<String> set = new HashSet<>();
for (String s : A.split("_")) {
set.add(s);
}
Pair[] list = new Pair[B.length];
for (int i = 0; i < B.length; i++) {
String s = B[i];
int count = 0;
for (String x : s.split("_")) {
if (set.contains(x))
count++;
}
list[i] = new Pair(i, count);
}
int[] ans = new int[B.length];
Arrays.sort(list, (a, b) -> b.value - a.value);
for (int i = 0; i < ans.length; i++)
ans[i] = list[i].index;
return ans;
}
}
Last updated