-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathDomain.java
More file actions
81 lines (79 loc) · 2.99 KB
/
Domain.java
File metadata and controls
81 lines (79 loc) · 2.99 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.*;
public class Domain {
public static void main(String[] args){
String[][] domains = {
{"google.com", "60"},
{"yahoo.com", "50"},
{"sports.yahoo.com", "80"}};
System.out.println(sub_domain_total(domains));
String[] user1 = {"/nine.html", "/four.html", "/six.html", "/seven.html", "/one.html" };
String[] user2 = {"/nine.html", "/two.html", "/three.html", "/four.html", "/six.html", "/seven.html"};
System.out.println(LCH(user1,user2));
}
/*
第一题：求广告的每个sub domain被click的总次数
input: {
{"google.com", "60"},
{"yahoo.com", "50"},
{"sports.yahoo.com", "80"}};
output : "com",90 "google.com",60 "yahoo.com",130 "sports.yahoo.com","80
* */
public static List<List<String>> sub_domain_total(String[][] domains){
List<List<String>> res = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
for(String[] domain:domains){
String name = domain[0];
int click = Integer.parseInt(domain[1]);
// helper function: find all sub domains of current domain name
for(String sub : subs(name)){
map.putIfAbsent(sub,0);
map.put(sub, map.get(sub)+click);
}
}
for(Map.Entry<String, Integer> entry : map.entrySet()){
res.add(Arrays.asList(entry.getKey(), String.valueOf(entry.getValue())));
}
return res;
}
private static List<String> subs(String domain){
List<String> res = new ArrayList<>();
String[] parts = domain.split("\\.");
String s = "";
for(int i = parts.length-1; i >= 0; i--){
s = "." + parts[i] + s;
res.add(s.substring(1));
}
return res;
}
/*
第二题：给每个user访问历史记录，找出两个user之间longest continuous common history
就是longest common substring问题：
如果 s.at(i) == s.at(j)
dp[i][j] = dp[i-1][j-1] + 1;
else: dp[i][j] = 0
* */
public static List<String> LCH(String[] user1, String[] user2){
// maintain[0] = max length, maintain[1] index of end
List<String> res = new ArrayList<>();
int[] maintain = new int[2];
int[][] dp = new int[user1.length+1][user2.length+1];
for(int i = 1; i <= user1.length; i++){
for(int j = 1; j <= user2.length; j++){
if(user1[i-1] == user2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
// find a longer one
if(dp[i][j] > maintain[0]){
maintain[0] = dp[i][j];
maintain[1] = i;
}
}else{
dp[i][j] = 0;
}
}
}
for(int i = maintain[1]-maintain[0]; i < maintain[1]; i++){
res.add(user1[i]);
}
return res;
}
}