Amazon Interview Question Software Engineers
Country: United States
Interview Type: In-Person
public class Main {
public static void main(String[] args) {
File file = new File("Log.txt");
HashMap<String,String> currentPageTracker = new HashMap<String,String>();
HashMap<String,HashSet<String>> links = new HashMap<>();
try {
Scanner input = new Scanner(file);
while(input.hasNextLine()){
String line = input.nextLine();
String[] tokens = line.split(" ");
//System.out.println(tokens[2]+" "+tokens[4]);
if(!currentPageTracker.containsKey(tokens[2])){
currentPageTracker.put(tokens[2], tokens[4]);
}else{
String prevPage = currentPageTracker.get(tokens[2]);
if(links.containsKey(prevPage)){
links.get(prevPage).add(tokens[4]);
}else{
HashSet<String> set = new HashSet<String>();
set.add(tokens[4]);
links.put(prevPage, set);
}
currentPageTracker.put(tokens[2], tokens[4]);
}
}
System.out.println(links);
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
import collections
def discover_site_map(log):
site_map = collections.defaultdict(set)
last_user_visits = {}
for record in log:
user = record['user']
page = record['page']
if user in last_user_visits:
site_map[last_user_visits[user]].add(page)
last_user_visits[user] = page
return site_map
For User C, after page 3 was visited after page 7 and page 1 was visited after page 3.
So link is from 7-> and 3->1 but 3->1 link was already there so duplicate link got ignored.
Here's how I think this can be implemented.
We maintain an unordered map to store last visited page for each user. So key for unordered map M1 is user and value is last visited page.
Then we have another unordered map, M2 with key as user and value as an map say M3.
For M3 the key is the starting page and value is a set, S4 of all pages linked to it.
We loop through the logs and fill in the above data structures for all link found.
Lets say there are m users and n pages, so the run time for this code would be
T = T1(m) + T2(m) + T3(n) + T4(n) = O(nlgn),as explained below
T1 - time to insert entry in M1 which would be O(1)
T2 - time to insert in M2 which would be O(1)
T3 - time to insert in M3 which would be O(nlgn)
T4 - time to insert in S4 which would be O(nlgn)
Space complexity in worst case would be
X = X1(m) + X2(m) * X3(n) * X4(n-1) = O(mn^2)
private static void getLinks(String[] users, int[] pages, String[] userTypes) {
int[][] graph = new int[8][8];
int[][] src_dst = new int[userTypes.length][2];
int userABC = 0;
String[] links = new String[9];
for(int i=0; i<pages.length; i++)
{
for(int u=0; u<userTypes.length; u++)
{
if ( userTypes[u].equals(users[i]))
{
userABC = u;
break;
}
}
/*if (users[i].equals("user-A"))
userABC = 0;
else if (users[i].equals("user-B"))
userABC = 1;
else if (users[i].equals("user-C"))
userABC = 2;*/
if ( src_dst[userABC][0] == 0)
src_dst[userABC][0]=pages[i];
else
src_dst[userABC][1]=pages[i];
if ( src_dst[userABC][0] >0 && src_dst[userABC][1] >0)
{
graph [ src_dst[userABC][0] ] [ src_dst[userABC][1] ] = userABC+1;
if ( links[ src_dst[userABC][0] ]==null)
links[ src_dst[userABC][0] ]= src_dst[userABC][0]+"-->";
else
links[ src_dst[userABC][0] ] += ",";
links[ src_dst[userABC][0] ] += src_dst[userABC][1];
src_dst[userABC][0] = src_dst[userABC][1]; // dest as source for other
src_dst[userABC][1] = 0; // if found a solution make dest empty.
}
}
for(int page =1; page<9; page++)
{
if ( links[ page ] != null)
{
System.out.println(links[ page ]);
}
}
}
private static void getLinks(String[] users, int[] pages, String[] userTypes) {
int[][] graph = new int[8][8];
int[][] src_dst = new int[userTypes.length][2];
int userABC = 0;
String[] links = new String[9];
for(int i=0; i<pages.length; i++)
{
for(int u=0; u<userTypes.length; u++)
{
if ( userTypes[u].equals(users[i]))
{
userABC = u;
break;
}
}
/*if (users[i].equals("user-A"))
userABC = 0;
else if (users[i].equals("user-B"))
userABC = 1;
else if (users[i].equals("user-C"))
userABC = 2;*/
if ( src_dst[userABC][0] == 0)
src_dst[userABC][0]=pages[i];
else
src_dst[userABC][1]=pages[i];
if ( src_dst[userABC][0] >0 && src_dst[userABC][1] >0)
{
graph [ src_dst[userABC][0] ] [ src_dst[userABC][1] ] = userABC+1;
if ( links[ src_dst[userABC][0] ]==null)
links[ src_dst[userABC][0] ]= src_dst[userABC][0]+"-->";
else
links[ src_dst[userABC][0] ] += ",";
links[ src_dst[userABC][0] ] += src_dst[userABC][1];
src_dst[userABC][0] = src_dst[userABC][1]; // dest as source for other
src_dst[userABC][1] = 0; // if found a solution make dest empty.
}
}
for(int page =1; page<9; page++)
{
if ( links[ page ] != null)
{
System.out.println(links[ page ]);
}
}
}
import java.util.*;
public class SiteMap {
public static class UserPage {
private String user;
private int page;
public UserPage(String user, int page) {
this.user = user;
this.page = page;
}
}
public static void main(String[] args) {
UserPage[] userPages = {
new UserPage("A", 1),
new UserPage("B", 5),
new UserPage("A", 2),
new UserPage("A", 1),
new UserPage("B", 2),
new UserPage("C", 7),
new UserPage("C", 3),
new UserPage("A", 3),
new UserPage("C", 1)
};
Map<String, Integer> latestPageMap = new HashMap<>();
Map<Integer, Set<Integer>> result = new TreeMap<>();
for (UserPage userPage : userPages) {
int value = userPage.page;
if (!latestPageMap.containsKey(userPage.user)) {
latestPageMap.put(userPage.user, value);
if (!result.containsKey(value)) {
result.put(value, new HashSet<>());
}
} else {
int previousLatest = latestPageMap.get(userPage.user);
latestPageMap.put(userPage.user, value);
if (!result.containsKey(previousLatest)) {
result.put(previousLatest, new HashSet<>());
}
Set<Integer> tempSet = result.get(previousLatest);
tempSet.add(value);
result.put(previousLatest, tempSet);
}
}
for (int finalValue : result.keySet()) {
System.out.print(finalValue + " -> ");
Set<Integer> linkedPages = result.get(finalValue);
for (int linkedPage : linkedPages) {
System.out.print(linkedPage + " ");
}
System.out.println();
}
}
}
def discover_site_map(log_list):
# Put the information in a dictionary where the key is the user and the
# value is an array of the pages visited
user_navigation_map = {}
for log in log_list:
user = log['user']
page = log['page']
if user in user_navigation_map.keys():
user_navigation_map[user].append(page)
else:
user_navigation_map[user] = [page]
# Create a new dictionary where the key is the page number and the value is
# a list of pages that users visited after the page number
site_map = {}
for user in user_navigation_map.keys():
pages_visited = user_navigation_map[user]
next_page = pages_visited.pop()
while len(pages_visited) > 0:
prev_page = pages_visited.pop()
if prev_page in site_map.keys():
site_map[prev_page] = [next_page] + site_map[prev_page]
else:
site_map[prev_page] = [next_page]
next_page = prev_page
print site_map
log_list = [
{'user': 'A', 'page': 1},
{'user': 'B', 'page': 5},
{'user': 'A', 'page': 2},
{'user': 'A', 'page': 1},
{'user': 'B', 'page': 2},
{'user': 'C', 'page': 7},
{'user': 'C', 'page': 3},
{'user': 'A', 'page': 3},
{'user': 'C', 'page': 1}]
discover_site_map(log_list)
def discover_site_map(log_list):
# Put the information in a dictionary where the key is the user and the
# value is an array of the pages visited
user_navigation_map = {}
for log in log_list:
user = log['user']
page = log['page']
if user in user_navigation_map.keys():
user_navigation_map[user].append(page)
else:
user_navigation_map[user] = [page]
# Create a new dictionary where the key is the page number and the value is
# a list of pages that users visited after the page number
site_map = {}
for user in user_navigation_map.keys():
pages_visited = user_navigation_map[user]
next_page = pages_visited.pop()
while len(pages_visited) > 0:
prev_page = pages_visited.pop()
if prev_page in site_map.keys():
site_map[prev_page] = [next_page] + site_map[prev_page]
else:
site_map[prev_page] = [next_page]
next_page = prev_page
print site_map
log_list = [
{'user': 'A', 'page': 1},
{'user': 'B', 'page': 5},
{'user': 'A', 'page': 2},
{'user': 'A', 'page': 1},
{'user': 'B', 'page': 2},
{'user': 'C', 'page': 7},
{'user': 'C', 'page': 3},
{'user': 'A', 'page': 3},
{'user': 'C', 'page': 1}]
discover_site_map(log_list)
def discover_site_map(log_list):
# Put the information in a dictionary where the key is the user and the
# value is an array of the pages visited
user_navigation_map = {}
for log in log_list:
user = log['user']
page = log['page']
if not user in user_navigation_map.keys():
user_navigation_map[user] = []
user_navigation_map[user].append(page)
# Create a new dictionary where the key is the page number and the value is
# a list of pages that users visited after the page number
site_map = {}
for user in user_navigation_map.keys():
pages_visited = user_navigation_map[user]
next_page = pages_visited.pop()
while len(pages_visited) > 0:
prev_page = pages_visited.pop()
if prev_page in site_map.keys():
site_map[prev_page] = [next_page] + site_map[prev_page]
else:
site_map[prev_page] = [next_page]
next_page = prev_page
print site_map
log_list = [
{'user': 'A', 'page': 1},
{'user': 'B', 'page': 5},
{'user': 'A', 'page': 2},
{'user': 'A', 'page': 1},
{'user': 'B', 'page': 2},
{'user': 'C', 'page': 7},
{'user': 'C', 'page': 3},
{'user': 'A', 'page': 3},
{'user': 'C', 'page': 1}]
discover_site_map(log_list)
Map<String,List<Integer>> map = new HashMap<>();
for(String s : logEntries)
{
//get userid 'userId' and pageId 'pageId' from 's'
List<Integer> list = null
if(!map.containsKey(userId))
{
list = new ArrayList<>();
}else{
list = map.get(userId);
}
list.add(pageId);
map.put(userId,list);
for(List<String> values : map.values())
{
if(values.size() == 1)// No navigation from one page to another
continue;
for(int i=1;i<values.size();i++)
System.out.println(values.get(i-1)+"->"+values.get(i));
}
}
This concept is equivalent to map-reduce approach where mapper emits key as userid and value as pageid and reducer takes in userid and list of pageids and emits the navigation
- telendt July 18, 2016import collections def discover_site_map(log): site_map = collections.defaultdict(set) last_user_visits = {} for record in log: user = record['user'] page = record['page'] if user in last_user_visits: site_map[last_user_visits[user]].add(page) last_user_visits[user] = page return site_map