Google Interview Question Software Engineers
Country: United States
1. HashMap to reference the hotel_id to its BinarySearchTree node.
2. BinarySearch Tree(RB Tree implementation) with average score as the key.
add_hotel h
- node* n = map.get(h.id)
- tree.erase(n)
- n.count++
- n.score_sum += h.score
- tree.insert(n)
get_list(avg_score):
- Binary Search to get to first node greater than equal to avg_score
- Traverse through the remaining nodes in the right to get the list of ids
- O(log n + k) [ k is the size of output]
// ZoomBA
def get_hotels( scores_file, avg_score ){
scores = json ( scores_file , true )
listing = mset ( scores ) -> { $.o.hotel_id }
avg_listing = dict ( listing ) -> {
key = $.o.key
items = $.o.value
total = sum ( items ) -> { $.o.score }
[ key, total / float( #|items| ) ] // do average
}
selected_hotels = select ( avg_listing ) :: {
$.o.value >= avg_score } -> { $.o.key }
}
Attempting this with Java.
/* Approach: Use counting sort to group hotel data together based on hotel Id. Iterate through the grouped data and compute
a moving average for each hotel Id/group's scores. If a group has an average score >= avg_min_score, add that hotel's id
to the list of ids to be returned. */
//Time Complexity: O(N).Space: O(N).
//Class representation of Input data.
class HotelData
{
String hotelId;
String userId;
int score;
}
public ArrayList<String> topHotels(HotelData[] scores,int min_avg)
{
if(scores==null||scores.length==0)
{
return Collections.<String>emptyList();
}
ArrayList<String> results=new ArrayList<String>();
if(scores.length==1){
if(scores[0].score>=minAvg)
{
results.add(scores[0].hotelId);
return results;
}
}
HashMap<String,Integer> counts=new HashMap<String,Integer>();
for(int i=0;i<scores.length;i++)
{
int ct=1;
if(!counts.containsKey(scores[i].hotelId))
{
counts.put(scores[i].hotelId,ct);
}else
{
ct=counts.get(scores[i].hotelId).intValue();
ct++;
counts.put(scores[i].ct);
}
}
HashMap<String,Integer> indices=new HashMap<String,Integer>();
int idx=0;
HotelData[] h=new HotelData[scores.length];
for(int i=0;i<scores.length;i++)
{
int p;
if(indices.containsKey(scores[i].hotelId))
{
p=indices.get(scores[i].hotelId).intValue();
}else{
p=idx;
idx=idx+(counts.get(scores[i].hotelId).intValue());
}
h[p]=scores[i];
indices.put(scores[i].hotelId;,++p);
}
int avg=h[0].score;
int ct=1;
for(int i=1;i<h.length;i++)
{
if(h[i].hotelId!=h[i-1].hotelId)
{
if(avg>=minAvg)
{
results.add(h[i].hotelId);
}
avg=h[i].score;
ct=1;
}else{
int sum=(avg*ct)+h[i].score;
ct++;
avg=sum/ct;
}
}
return results;
}
Assuming the order of the output does not matter.
C++
space: O(n)
time complexity: O(n)
struct Hotel{
int hotel_id, user_id, score;
Hotel(){}
Hotel( int _hotel_id, int _user_id, int _score){
hotel_id = _hotel_id;
user_id = _user_id;
score = _score;
}
};
vector<int> get_hotels(vector<Hotel> scores, float min_avg_score ){
unordered_map<int,pair<int,int> > hash;
unordered_map<int,pair<int,int> > :: iterator it;
vector<int> hotels;
int sz = scores.size();
for( int i = 0 ; i < sz ; ++i ){
hash[ scores[i].hotel_id ].first+=scores[i].score;
hash[ scores[i].hotel_id ].second++;
}
for( it = hash.begin(); it != hash.end() ; ++it ){
pair<int,int> values = it -> second;
float avg_current = values.first/(float)(values.second);
if( avg_current >= min_avg_score )
hotels.push_back(it -> first );
}
return hotels;
}
If order matters then it will be possible by changing the hash with a map. Time complexity will be O(nlogn) though.
//Class score
public class Scores {
String id;
String user_id;
int val;
public Scores(){}
public Scores(String id, String uid, int val){
this.id = id;
this.user_id = uid;
this.val = val;
}
}
// Class hotels
import java.util.*;
public class hotels {
public static void main(String args[]){
ArrayList<Scores> score = new ArrayList<Scores>();
score.add(new Scores("101","1001",5));
score.add(new Scores("101","1002",7));
score.add(new Scores("103","1003",3));
score.add(new Scores("104","1001",5));
score.add(new Scores("105","1001",4));
get_scores(score, 5); }
public static void get_scores(ArrayList<Scores> score , int avg){
HashMap<String,Integer> hmap = new HashMap<String,Integer>();
HashMap<String,Integer> hmapForCount = new HashMap<String,Integer>();
int numberOfEntries = score.size();
for(int i=0;i<numberOfEntries;i++){
String key = score.get(i).id;
int val = score.get(i).val;
if(!hmap.containsKey(key))
{
hmap.put(key, val);
hmapForCount.put(key, 1);
}
else{
hmap.put(key, hmap.get(key)+val);
hmapForCount.put(key,hmapForCount.get(key)+1);
}
}
ArrayList<String> a = new ArrayList<String>();
for(Map.Entry<String, Integer> e : hmap.entrySet() ){
String k = (String) e.getKey();
int val = (int)hmap.get(k);
int entries = (int)hmapForCount.get(k);
Integer newVal = Integer.valueOf(val / entries) ;
if(newVal>=avg)
a.add(k);
}
System.out.println(a);
}
}
//class Scores
public class Scores {
String id;
String user_id;
int val;
public Scores(){}
public Scores(String id, String uid, int val){
this.id = id;
this.user_id = uid;
this.val = val;
}
}
//class Hotels
import java.util.*;
public class hotels {
public static void main(String args[]){
ArrayList<Scores> score = new ArrayList<Scores>();
score.add(new Scores("101","1001",5));
score.add(new Scores("101","1002",7));
score.add(new Scores("103","1003",3));
score.add(new Scores("104","1001",5));
score.add(new Scores("105","1001",4));
get_scores(score, 5); }
public static void get_scores(ArrayList<Scores> score , int avg){
HashMap<String,Integer> hmap = new HashMap<String,Integer>();
HashMap<String,Integer> hmapForCount = new HashMap<String,Integer>();
int numberOfEntries = score.size();
for(int i=0;i<numberOfEntries;i++){
String key = score.get(i).id;
int val = score.get(i).val;
if(!hmap.containsKey(key))
{
hmap.put(key, val);
hmapForCount.put(key, 1);
}
else{
hmap.put(key, hmap.get(key)+val);
hmapForCount.put(key,hmapForCount.get(key)+1);
}
}
ArrayList<String> a = new ArrayList<String>();
for(Map.Entry<String, Integer> e : hmap.entrySet() ){
String k = (String) e.getKey();
int val = (int)hmap.get(k);
int entries = (int)hmapForCount.get(k);
Integer newVal = Integer.valueOf(val / entries) ;
if(newVal>=avg)
a.add(k);
}
System.out.println(a);
}
}
public List<String> getHotels(List<HotelRating> ratings, double minAverage) {
return ratings.stream()
.collect(Collectors.groupingBy(rating -> rating.hotelId,
Collectors.averagingDouble(rating -> rating.score)))
.entrySet().stream()
.filter(entry -> entry.getValue() >= minAverage)
.map(Map.Entry::getKey).collect(Collectors.toList());
}
import java.util.ArrayList;
public class hotels {
public static void main(String[] args) {
int [] [] scores = {{1001, 501, 7}, {1001, 502, 7}, {1001, 503, 7}, {2001, 504, 10}, {3001, 505, 5}, {2001, 506, 5}};
ArrayList<Integer> hotel_ids = get_hotels(scores,7);
System.out.println(hotel_ids);
}
public static ArrayList<Integer> get_hotels(int [] [] scores, int min_avg_score) {
//Step 1: Check the averages of all the unique hotels
ArrayList<Integer> subList = new ArrayList<Integer>();
ArrayList<double[]> compareTo = new ArrayList<double[]>();
for (int i = 0; i < scores.length; i++) {
//If the hotel already exist, Update the average and counter (how many items it appeared)
int indx = subList.indexOf(scores[i][0]);
if (indx != -1) {
double [] E = compareTo.get(indx);
E[1] = E[1] + 1; //How many times this hotel appeared (helps in calculating the average)
E[0] = (E[0]*(E[1]-1)+scores[i][2])/E[1]; //The new average
compareTo.set(indx, E); //update the average and counter of the existing hotel
}
//if it is new to the list, initiate the average to be the score and the counter to be 1
else {
subList.add(scores[i][0]);
double [] E2 = {scores[i][2], 1}; //average and counter
compareTo.add(E2); //add the new hotel to the list of available hotels
}
}
//Step 2: Check which hotels pass the test and add it to the list
ArrayList <Integer> result = new ArrayList<Integer>();
for (int i = 0; i < subList.size(); i++) {
if (compareTo.get(i)[0] >= min_avg_score) {
result.add(subList.get(i));
}
}
return result;
}
}
Python 3.5
def get_hotels(scores=scores, min_avg_score=5):
import collections
to_return = []
hotel_scores = collections.defaultdict(list)
for s in scores:
hotel_scores[s['hotel_id']].append(s['score'])
for hotel in hotel_scores.keys():
score_list = hotel_scores[hotel]
if sum(score_list) / len(score_list) >= in_avg_score:
to_return.append(hotel)
return to_return
def my_solution(data, ratting):
track = dict()
for hotel in data:
if track.get(hotel["hotel_id"], ""):
prev_sum = track[hotel["hotel_id"]][0]
prev_len = len(track[hotel["hotel_id"]][1])
left = prev_sum
total = left + (hotel["score"] * prev_len)
new_avg = int(total/(1 + prev_len))
track[hotel["hotel_id"]][1].append(hotel)
track[hotel["hotel_id"]][0] = new_avg
else:
track[hotel["hotel_id"]] = [hotel["score"], [hotel]]
ans = []
for i, j in track.items():
if j[0] >= ratting:
ans.append(i)
return ans
if __name__ == '__main__':
scores = [
{'hotel_id': 1001, 'user_id': 501, 'score': 7},
{'hotel_id': 1001, 'user_id': 502, 'score': 7},
{'hotel_id': 1001, 'user_id': 503, 'score': 7},
{'hotel_id': 2001, 'user_id': 504, 'score': 10},
{'hotel_id': 3001, 'user_id': 505, 'score': 5},
{'hotel_id': 2001, 'user_id': 506, 'score': 5}
]
print(my_solution(scores, 5))
print(my_solution(scores, 7))
Select hotel_id, Avg(score) as avg_score
From scores
Group by hotel_id
Having avg_score >= min_avg_score
Don't overcomplicate a simple problem. Your code should be doing the equivalent of this sql in the language of your choice. C# linq or java streams or functional programming makes this trivial.
Javascript solution. keep track of ids, the total score for that id, and the number of occurances of that id as we go through the list. Then go through our map, calculate the average score, and return everything that has a higher average.
function get_hotels(scores, min_avg_score){
var averageScores = {};
for (var i = 0; i < scores.length; i++){
if (scores[i].hotel_id in averageScores){
averageScores[scores[i].hotel_id].count++;
averageScores[scores[i].hotel_id].total += scores[i].score;
}
else
{
averageScores[scores[i].hotel_id] = {total: scores[i].score, count: 1};
}
}
var toReturn = [];
for (var key in averageScores) {
if (averageScores.hasOwnProperty(key)){
if (averageScores[key].total/averageScores[key].count >= min_avg_score){
toReturn.push(key);
}
}
}
return toReturn;
}
from collections import defaultdict
def get_hotels(scores, min_avg_score):
hotel_score = defaultdict(list)
for score in scores:
hotel_score[score['hotel_id']].append(score['score'])
hotel_avg = [key for key in hotel_score \
if sum(hotel_score[key])/len(hotel_score[key]) \
>= min_avg_score]
return hotel_avg
scores = [
{'hotel_id': 1001, 'user_id': 501, 'score': 7},
{'hotel_id': 1001, 'user_id': 502, 'score': 7},
{'hotel_id': 1001, 'user_id': 503, 'score': 7},
{'hotel_id': 2001, 'user_id': 504, 'score': 10},
{'hotel_id': 3001, 'user_id': 505, 'score': 5},
{'hotel_id': 2001, 'user_id': 506, 'score': 5}
]
print get_hotels(scores, 7)
I think it is easy implementing it in python.
def get_average_rating( arrayDict ):
average_rating = 0
hotel_id_rating = {}
for each_record in arrayDict:
# Sum of rating
average_rating += each_record['score']
hotel_id = each_record['id']
if hotel_id not in hotel_id_rating.keys():
hotel_id_rating[hotel_id] = each_record['score']
else:
hotel_id_rating[hotel_id] = ( hotel_id_rating[hotel_id] + each_record['score'] ) / 2
average_rating = average_rating / len(arrayDict)
print "Average Rating: %d" % average_rating
# List of hotel whose average rating is more than overall average rating
for key in hotel_id_rating:
if hotel_id_rating[key] >= average_rating:
print "Hotel ID: %d Avg Rating: %d" % ( key, hotel_id_rating[key])
1. BinarySearch Tree(RedBlack Tree) with average_score as the key
- Suraj Poudel July 07, 20162. HashMap to index hotel_id to BinarySearch Tree node
add_hotel(std::tuple<uint64_t, uint64_t, float> hotel) {
node* cur_node = map[std::get<0>(hotel)]; // checking inclusion avoided
tree.erase(cur_node) //O(log n)
cur_node.count++;
cur_node.sum+=std::get<2>(hotel);
tree.insert(cur_node)
get_list(floag avg_score) {
//binary search to get the nodes(reference the hotel_id) greater than avg_score as list
//O(k + log n) k = size of output
}