Moloco SWE Coding Test

Q1 Answer

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));
	}

}

Q2 Answer

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;
		}
	}
}

Q3 Answer

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;
		}
	}
}

Explanation for Q3.

1. Consider only the rows with country_id = "BDV" (there are 844 such rows). For each site_id, we can compute the number of unique user_id's found in these 844 rows. Which site_id has the largest number of unique users? And what's the number?

(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.

2. Between 2019-02-03 00:00:00 and 2019-02-04 23:59:59, there are four users who visited a certain site more than 10 times. Find these four users & which sites they (each) visited more than 10 times. (Simply provides four triples in the form (user_id, site_id, number of visits) in the box below.)

(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.

3. For each site, compute the unique number of users whose last visit (found in the original data set) was to that site. For instance, user "LC3561"'s last visit is to "N0OTG" based on timestamp data. Based on this measure, what are top three sites? (hint: site "3POLC" is ranked at 5th with 28 users whose last visit in the data set was to 3POLC; simply provide three pairs in the form (site_id, number of users).)

(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.

4. For each user, determine the first site he/she visited and the last site he/she visited based on the timestamp data. Compute the number of users whose first/last visits are to the same website. What is the number?

(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.)