Amazon Interview Question Software Engineers
Country: United States
Interview Type: In-Person
def get_hotels(scores,min_a):
count ={}
sum1 ={}
res =[]
for a in scores:
try :
sum1[a["hotel_id"]] += a["score"]
count[a["hotel_id"]] += 1
except :
sum1[a["hotel_id"]] = a["score"]
count[a["hotel_id"]] = 1
for k,v in sum1.items():
if v/count[k] >= min_a:
res.append(k)
print(res)
return res
{
def get_hotels(scores,min_a):
count ={}
sum1 ={}
res =[]
for a in scores:
try :
sum1[a["hotel_id"]] += a["score"]
count[a["hotel_id"]] += 1
except :
sum1[a["hotel_id"]] = a["score"]
count[a["hotel_id"]] = 1
for k,v in sum1.items():
if v/count[k] >= min_a:
res.append(k)
print(res)
return res
}
private static void get_hotel(String scores, int avg_score) throws JSONException {
Set<Integer> id = new HashSet<Integer>();
JSONArray arr = new JSONArray(scores);
for (int i=0; i<arr.length(); i++){
JSONObject jsonProductObject = arr.getJSONObject(i);
int score = jsonProductObject.getInt("score");
if(score>=avg_score){
id.add(jsonProductObject.getInt("hotel_id"));
}
}
System.out.println(id);
//if hotel_id needs to be sorted
TreeSet sortedId = new TreeSet<Integer>(id);
System.out.println(sortedId);
}
public static void avgRatingHotels(){
Multimap<String, Integer > multimap = ArrayListMultimap.create();
multimap.put("hotel1", 5);
multimap.put("hotel1", 6);
multimap.put("hotel2", 4);
multimap.put("hotel2", 3);
multimap.put("hotel1", 8);
multimap.put("hotel3", 5);
multimap.put("hotel2", 5);
multimap.put("hotel3", 7);
Set<String> str = multimap.keySet();
for(String str2 : str){
int k=0;
Collection<Integer> c = multimap.get(str2);
int count = c.size();
Iterator<Integer> itInt = c.iterator();
for(int c1 : c){
k+=c1;
}
System.out.println("Avg for "+str2+" is :"+k/count);
}
}
public static void avgRatingHotels(){
Multimap<String, Integer > multimap = ArrayListMultimap.create();
multimap.put("hotel1", 5);
multimap.put("hotel1", 6);
multimap.put("hotel2", 4);
multimap.put("hotel2", 3);
multimap.put("hotel1", 8);
multimap.put("hotel3", 5);
multimap.put("hotel2", 5);
multimap.put("hotel3", 7);
Set<String> str = multimap.keySet();
for(String str2 : str){
int k=0;
Collection<Integer> c = multimap.get(str2);
int count = c.size();
Iterator<Integer> itInt = c.iterator();
for(int c1 : c){
k+=c1;
}
System.out.println("Avg for "+str2+" is :"+k/count);
}
}
public static void avgRatingHotels(){
Multimap<String, Integer > multimap = ArrayListMultimap.create();
multimap.put("hotel1", 5);
multimap.put("hotel1", 6);
multimap.put("hotel2", 4);
multimap.put("hotel2", 3);
multimap.put("hotel1", 8);
multimap.put("hotel3", 5);
multimap.put("hotel2", 5);
multimap.put("hotel3", 7);
Set<String> str = multimap.keySet();
for(String str2 : str){
int k=0;
Collection<Integer> c = multimap.get(str2);
int count = c.size();
Iterator<Integer> itInt = c.iterator();
for(int c1 : c){
k+=c1;
}
System.out.println("Avg for "+str2+" is :"+k/count);
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class HotelScore {
public static class Score {
private int hotel_id;
private int user_id;
private int score;
public Score(int hotel_id, int user_id, int score) {
this.hotel_id = hotel_id;
this.user_id = user_id;
this.score = score;
}
}
public static void main(String[] args) {
Score[] scores = {
new Score(1001, 501, 7),
new Score(1001, 502, 7),
new Score(1001, 503, 7),
new Score(2001, 504, 10),
new Score(3001, 505, 5),
new Score(2001, 506, 5)
};
//int min_avg_score = 7;
int min_avg_score = 5;
System.out.println(get_hotels(scores, min_avg_score));
}
private static List<Integer> get_hotels(Score[] scores, int min_avg_score) {
Map<Integer, List<Integer>> averageMap = new TreeMap<>();
for (Score score : scores) {
if (!averageMap.containsKey(score.hotel_id)) {
averageMap.put(score.hotel_id, new ArrayList<>());
}
List<Integer> tempList = averageMap.get(score.hotel_id);
tempList.add(score.score);
averageMap.put(score.hotel_id, tempList);
}
List<Integer> finalList = new ArrayList<>();
for (int hotel_id : averageMap.keySet()) {
List<Integer> hotelScoreList = averageMap.get(hotel_id);
int totalScore = 0;
for (int score : hotelScoreList) {
totalScore += score;
}
float averageScore = (float) totalScore / hotelScoreList.size();
if (averageScore >= min_avg_score) {
finalList.add(hotel_id);
}
}
return finalList;
}
}
def get_hotels(score_list, min_avg_score):
hotel_list = {}
# Create a dictionary where we classify scores by hotel id
for hotel_score in score_list:
hotel_id = hotel_score['hotel_id']
if not hotel_id in hotel_list.keys():
hotel_list[hotel_id] = []
hotel_list[hotel_id].append(int(hotel_score['score']))
# Create a list of hotels that have at least the min_avg_score
hotel_result_list = []
for hotel_id in hotel_list.keys():
score_average = (sum(hotel_list[hotel_id]) / len(hotel_list[hotel_id]))
if score_average >= min_avg_score:
hotel_result_list.append(hotel_id)
return hotel_result_list
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,5) -> " + str(get_hotels(scores,5))
print "get_hotels(scores,7) -> " + str(get_hotels(scores,7))
def get_hotels(scores,min_avg_score):
hotels = []
for item in scores:
if item['hotel_id'] not in hotels and item['score'] >= min_avg_score:
hotels.append(item['hotel_id'])
return hotels
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}
]
first_result = get_hotels(scores,5)
for item2 in first_result:
print str(item2)
second_result = get_hotels(scores,7)
for item3 in second_result:
print str(item3)
Quite a simple solution
import java.util.HashMap;
import java.util.TreeMap;
public class MinAverage {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] scores = {{1001,7},{1001,7},{1001,7},{2001,10},{3001,5},{2001,5}};
System.out.println(get_hotels(scores, 5));
System.out.println(get_hotels(scores, 7));
}
public static String get_hotels(int[][] scores, int min_avg) {
TreeMap<Integer, Integer> scoreSum = new TreeMap<Integer, Integer>();
HashMap<Integer, Integer> scoreCount = new HashMap<Integer, Integer>();
for(int i=0; i < 6; i++) {
int val = scores[i][0];
if(!scoreSum.containsKey(val)) {
scoreSum.put(val, scores[i][1]);
scoreCount.put(val, 1);
}
else {
scoreSum.put(val, scoreSum.get(val)+ scores[i][1]);
scoreCount.put(val, scoreCount.get(val) + 1);
}
}
String result = "";
for(int val : scoreSum.keySet()){
if(scoreSum.get(val)/scoreCount.get(val) >= min_avg) {
result +=val+" ";
}
}
return result;
}
}
We can solve this by maintaining an unordered_map with key as hotel_id and value as a pair of {'sum_of_scores', 'count_of_scores'}. Once we have exhausted all scores, we go through each the unordered_map and get the average score for each hotel and put it in the result list if its greater than or equal to the min_avg_score
- as09 July 10, 2016Time complexity is O(n) because we go through the list once. It changes to O(nlogn) if the result list needs to be sorted by hotel_ids
Space complexity is O(n) to store intermediate results and the final result list