Last active
October 2, 2019 09:03
-
-
Save liamcho/5f5959d86d374b2705ff81fad1e2ddf1 to your computer and use it in GitHub Desktop.
Moloco SWE Coding Test
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MolocoProbOne { | |
public static boolean equalsWhenOneCharRemoved(String x, String y) { | |
int xLen = x.length(); | |
int yLen = y.length(); | |
boolean isRemoved = false; | |
int xIdx = 0; | |
int yIdx = 0; | |
if (xLen - 1 == yLen) { | |
while (xIdx < xLen) { | |
if (x.charAt(xIdx) != y.charAt(yIdx)) { | |
if (!isRemoved) { | |
isRemoved = true; | |
} else { | |
return false; | |
} | |
} else { | |
yIdx++; | |
} | |
xIdx++; | |
} | |
return true; | |
} else if (xLen + 1 == yLen) { | |
while (yIdx < yLen) { | |
if (x.charAt(xIdx) != y.charAt(yIdx)) { | |
if (!isRemoved) { | |
isRemoved = true; | |
} else { | |
return false; | |
} | |
} else { | |
xIdx++; | |
} | |
yIdx++; | |
} | |
return true; | |
} | |
return false; | |
} | |
public static void main(String[] args) { | |
// TODO Auto-generated method stub | |
String s1 = "abcd"; | |
String s2 = "abced"; | |
System.out.println(equalsWhenOneCharRemoved(s1, s2)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.BufferedReader; | |
import java.io.FileNotFoundException; | |
import java.io.FileReader; | |
import java.io.IOException; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.HashMap; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.Set; | |
import com.google.gson.Gson; | |
public class MolocoProbTwo { | |
public static void main(String[] args) throws IOException { | |
//System.out.println(new File(".").getAbsoluteFile()); | |
List<Product> ps = readFile("./src/Q2.txt"); | |
System.out.println("Most popular product(s) based on the number of purchasers: " + | |
productWithMostUsers(ps)); | |
System.out.println("Most popular product(s) based on the quantity of goods sold: " + | |
productWithMostQuantity(ps)); | |
} | |
public static List<String> productWithMostUsers(List<Product> ps) { | |
Map<String, Set<String>> map = new HashMap<>(); | |
int maxCount = 0; | |
List<String> ans = new ArrayList<>(); | |
for (Product p : ps) { | |
String pid = p.getProductId(); | |
String uid = p.getUserId(); | |
map.putIfAbsent(pid, new HashSet<>()); | |
Set<String> users = map.get(pid); | |
users.add(uid); | |
int numUsers = users.size(); | |
if (numUsers > maxCount) { | |
ans = new ArrayList<>(); | |
ans.add(pid); | |
maxCount = numUsers; | |
} else if (numUsers == maxCount) { | |
ans.add(pid); | |
} | |
} | |
return ans; | |
} | |
public static List<String> productWithMostQuantity(List<Product> ps) { | |
Map<String, Integer> map = new HashMap<>(); | |
int maxQuantity = 0; | |
List<String> ans = new ArrayList<>(); | |
for (Product p : ps) { | |
String pid = p.getProductId(); | |
int quantity = p.getQuantity(); | |
if (map.containsKey(pid)) { | |
map.replace(pid, map.get(pid) + quantity); | |
} else { | |
map.put(pid, quantity); | |
} | |
int currQuantity = map.get(pid); | |
if (currQuantity > maxQuantity) { | |
ans = new ArrayList<>(); | |
ans.add(pid); | |
maxQuantity = currQuantity; | |
} else if (currQuantity == maxQuantity) { | |
ans.add(pid); | |
} | |
} | |
return ans; | |
} | |
public static List<Product> readFile(String filename) throws IOException { | |
List<Product> ps = new ArrayList<>(); | |
try (BufferedReader reader = new BufferedReader(new FileReader(filename))) { | |
Gson g = new Gson(); | |
String row; | |
while ((row = reader.readLine()) != null) { | |
Product p = g.fromJson(row, Product.class); | |
//System.out.println(p); | |
ps.add(p); | |
} | |
reader.close(); | |
} catch (FileNotFoundException e) { | |
// TODO Auto-generated catch block | |
System.out.println("file name " + filename + " not found."); | |
e.printStackTrace(); | |
} | |
return ps; | |
} | |
public static class Product { | |
private String user_id; | |
private String product_id; | |
private int quantity; | |
public Product(String user_id, String product_id, int quantity) { | |
this.user_id = user_id; | |
this.product_id = product_id; | |
this.quantity = quantity; | |
} | |
public void setUserId(String userId) { | |
this.user_id = userId; | |
} | |
public String getUserId() { | |
return user_id; | |
} | |
public void setProductId(String productId) { | |
this.product_id = productId; | |
} | |
public String getProductId() { | |
return product_id; | |
} | |
public void setQuantity(int quantity) { | |
this.quantity = quantity; | |
} | |
public int getQuantity() { | |
return quantity; | |
} | |
@Override | |
public String toString() { | |
return "pid: " + product_id + ", uid: " + user_id + ", quantity: " + quantity; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.BufferedReader; | |
import java.io.FileNotFoundException; | |
import java.io.FileReader; | |
import java.io.IOException; | |
import java.util.ArrayList; | |
import java.util.Comparator; | |
import java.util.HashMap; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.Set; | |
import java.util.regex.Pattern; | |
import java.util.stream.Collectors; | |
import org.javatuples.Pair; | |
import org.javatuples.Triplet; | |
public class MolocoProbThree { | |
public static void main(String[] args) throws IOException { | |
// TODO Auto-generated method stub | |
List<VisitedUser> vus = readFile("./src/Q3.csv"); | |
System.out.println(getSitesWithMostUsersForCountry(vus, "BDV")); | |
System.out.println(findUsersWithinTimestampRangeWithCutoffNumVisit( | |
vus, "2019-02-03 00:00:00", "2019-02-04 23:59:59", 10)); | |
System.out.println(findTopThreeSitesWithHighestLatestUsersCount(vus)); | |
System.out.println(getNumUsersWithSameFirstAndLastSites(vus)); | |
} | |
public static int getNumUsersWithSameFirstAndLastSites(List<VisitedUser> vus) { | |
Map<String, VisitedUser[]> userToFirstAndLast = new HashMap<>(); | |
for (VisitedUser vu : vus) { | |
String uid = vu.getUser_id(); | |
String ts = vu.getTs(); | |
if (userToFirstAndLast.containsKey(uid)) { | |
VisitedUser[] firstAndLast = userToFirstAndLast.get(uid); | |
VisitedUser currFirst = firstAndLast[0]; | |
VisitedUser currLast = firstAndLast[1]; | |
if (ts.compareTo(currFirst.getTs()) < 0) { | |
firstAndLast[0] = vu; | |
} else if (ts.compareTo(currLast.getTs()) > 0) { | |
firstAndLast[1] = vu; | |
} | |
} else { | |
VisitedUser[] temp = {vu, vu}; | |
userToFirstAndLast.put(uid, temp); | |
} | |
} | |
int ans = 0; | |
for (VisitedUser[] vals : userToFirstAndLast.values()) { | |
VisitedUser f = vals[0]; | |
VisitedUser l = vals[1]; | |
// To be more clear, I provide two answers: | |
// 1. Includes case where first/last visits have the same timestamp. | |
// if (vals[0].getSite_id().equals(vals[1].getSite_id()) && vals[0].getTs() != vals[1].getTs()) { | |
// System.out.println("f: " + f + ", l: " + l); | |
// ans++; | |
// } | |
// 2. Only includes cases where first/last timestamps are different. | |
if (vals[0].getSite_id().equals(vals[1].getSite_id())) { | |
ans++; | |
} | |
} | |
return ans; | |
} | |
public static List<VisitedUser> readFile(String filename) throws IOException { | |
List<VisitedUser> vus = null; | |
Pattern pattern = Pattern.compile(","); | |
try (BufferedReader reader = new BufferedReader(new FileReader(filename))) { | |
vus = reader.lines().skip(1).map(line -> { | |
String[] x = pattern.split(line); | |
return new VisitedUser(x[0], x[1], x[2], x[3]); | |
}).collect(Collectors.toList()); | |
} catch (FileNotFoundException e) { | |
// TODO Auto-generated catch block | |
System.out.println("file name " + filename + " not found."); | |
e.printStackTrace(); | |
} | |
return vus; | |
} | |
public static List<Pair<String, Integer>> findTopThreeSitesWithHighestLatestUsersCount(List<VisitedUser> vus) { | |
Map<String, VisitedUser> userTolatestTsMap = new HashMap<>(); | |
for (VisitedUser vu : vus) { | |
String uid = vu.getUser_id(); | |
String ts = vu.getTs(); | |
if (userTolatestTsMap.containsKey(uid)) { | |
String currLatestTs = userTolatestTsMap.get(uid).getTs(); | |
if (ts.compareTo(currLatestTs) > 0) { | |
userTolatestTsMap.replace(uid, vu); | |
} | |
} else { | |
userTolatestTsMap.put(uid, vu); | |
} | |
} | |
Map<String, Integer> siteToLatestUserCount = new HashMap<>(); | |
for (Map.Entry<String, VisitedUser> e : userTolatestTsMap.entrySet()) { | |
VisitedUser user = e.getValue(); | |
String site = user.getSite_id(); | |
if (siteToLatestUserCount.containsKey(site)) { | |
siteToLatestUserCount.put(site, siteToLatestUserCount.get(site) + 1); | |
} else { | |
siteToLatestUserCount.put(site, 1); | |
} | |
} | |
List<Pair<String, Integer>> topThreeSites = new ArrayList<>(); | |
siteToLatestUserCount.entrySet().stream().sorted(new Comparator<Map.Entry<String, Integer>>() { | |
@Override | |
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) { | |
return -o1.getValue().compareTo(o2.getValue()); | |
} | |
}).forEach(e -> {if (topThreeSites.size() < 3) { | |
topThreeSites.add(new Pair<String, Integer>(e.getKey(), e.getValue())); | |
}}); | |
return topThreeSites; | |
} | |
public static List<Triplet<String, String, Integer>> findUsersWithinTimestampRangeWithCutoffNumVisit( | |
List<VisitedUser> vus, String s, String e, int cutoffNumVisit) { | |
List<VisitedUser> filtered = vus.stream() | |
.filter(vu -> vu.getTs().compareTo(s) >= 0 && vu.getTs().compareTo(e) <= 0) | |
.collect(Collectors.toList()); | |
Map<String, Map<String, Integer>> userToSiteVisitCount = new HashMap<>(); | |
for (VisitedUser vu : filtered) { | |
String user = vu.getUser_id(); | |
String site = vu.getSite_id(); | |
if (userToSiteVisitCount.containsKey(user)) { | |
Map<String, Integer> siteVisitCounts = userToSiteVisitCount.get(user); | |
if (siteVisitCounts.containsKey(site)) { | |
siteVisitCounts.replace(site, siteVisitCounts.get(site) + 1); | |
} else { | |
siteVisitCounts.put(site, 1); | |
} | |
} else { | |
Map<String, Integer> siteVisitCounts = new HashMap<>(); | |
siteVisitCounts.put(site, 1); | |
userToSiteVisitCount.put(user, siteVisitCounts); | |
} | |
} | |
List<Triplet<String, String, Integer>> ans = new ArrayList<>(); | |
for (Map.Entry<String, Map<String, Integer>> e1 : userToSiteVisitCount.entrySet()) { | |
String uid = e1.getKey(); | |
for (Map.Entry<String, Integer> e2 : e1.getValue().entrySet()) { | |
String sid = e2.getKey(); | |
int vc = e2.getValue(); | |
if (vc > 10) { | |
ans.add(new Triplet<>(uid, sid, vc)); | |
} | |
} | |
} | |
return ans; | |
} | |
public static Map<String, Integer> getSitesWithMostUsersForCountry(List<VisitedUser> vus, String country) { | |
List<VisitedUser> filtered = vus.stream() | |
.filter(vu -> vu.getCountry_id().equals(country)) | |
.collect(Collectors.toList()); | |
Map<String, Set<String>> siteToUsers = new HashMap<>(); | |
int maxUsersCount = 0; | |
for (VisitedUser vu : filtered) { | |
String site = vu.getSite_id(); | |
String user = vu.getUser_id(); | |
if (siteToUsers.containsKey(site)) { | |
siteToUsers.get(site).add(user); | |
} else { | |
Set<String> users = new HashSet<>(); | |
users.add(user); | |
siteToUsers.put(site, users); | |
} | |
int currCount = siteToUsers.get(site).size(); | |
maxUsersCount = Math.max(maxUsersCount, currCount); | |
} | |
int max = maxUsersCount; | |
Map<String, Integer> ans = siteToUsers.entrySet().stream() | |
.filter(entry -> entry.getValue().size() == max) | |
.collect(Collectors.toMap(x -> x.getKey(), x -> x.getValue().size())); | |
return ans; | |
} | |
public static class VisitedUser { | |
private String ts; | |
private String user_id; | |
private String country_id; | |
private String site_id; | |
public VisitedUser(String ts, String user_id, String country_id, String site_id) { | |
this.ts = ts; | |
this.user_id = user_id; | |
this.country_id = country_id; | |
this.site_id = site_id; | |
} | |
public String getTs() { | |
return ts; | |
} | |
public void setTs(String ts) { | |
this.ts = ts; | |
} | |
public String getUser_id() { | |
return user_id; | |
} | |
public void setUser_id(String user_id) { | |
this.user_id = user_id; | |
} | |
public String getCountry_id() { | |
return country_id; | |
} | |
public void setCountry_id(String country_id) { | |
this.country_id = country_id; | |
} | |
public String getSite_id() { | |
return site_id; | |
} | |
public void setSite_id(String site_id) { | |
this.site_id = site_id; | |
} | |
@Override | |
public String toString() { | |
return "ts: " + ts + ", user_id: " + user_id + ", country_id: " + country_id + ", site_id: " + site_id; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Explanation for Q3.
(1) Filter data that matches given country value.
(2) Iterate filtered data to map each unique site to its unique users. (Using set is helpful for finding unique users) Also during iteration, update the max user count.
(3) Use stream() to conveniently filter out site key from the map with the matching max user count.
(1) Filter data with that match the given time range.
(2) Iterate over filtered data to map each unique user to its unique visited sites with total visited count (Here, I used nested maps (2D) but more convenient way is to store the whole data as value).
(3) Iterate over the updated map to collect [user, site, visitedCount] triplets based on the given cutoff count.
(1) Iterate over the data to map unique users to data where each data's timestamp value is the maximum of all data concerning the same user.
(2) Iterate over the map to map unique sites to total unique user count.
(3) Use stream() and Comparator() to conveniently sort the map in descending order to extract the top three sites.
(1) Iterate over data to map unique user to its first and last generated data based on the timestamp comparison.
(2) Iterate over first and last data values of each user to update the total count of users whose first and last visits have the same site value (You could exclude cases where first/last visits have the SAME timestamp to only consider cases where at least two separate visits were made for each user.)