Uber电面-4sum

今天uber电面
问了三年规划5年目标...(｀_′)ゞ

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

....

1. class Solution {
   
2.         // store index of pair
   
3.         static class Pair {
   
4.                 Integer[] eles;
   
5. 
   
6.                 public Pair(int a, int b, int c, int d) {
   
7.                         eles = new Integer[] { a, b, c, d };
   
8.                         Arrays.sort(eles);
   
9.                 }
   
10. 
    
11.                 static boolean valid(int a, int b, int c, int d) {
    
12.                         if (a == c || b == d || b == c)
    
13.                                 return false;
    
14.                         return true;
    
15.                 }
    
16. 
    
17.                 public int hashCode() {
    
18.                         Integer ans = 2;
    
19.                         for (int i : eles) {
    
20.                                 ans += ans * i;
    
21.                         }
    
22.                         return ans;
    
23.                 }
    
24. 
    
25.                 public boolean equals(Object that) {
    
26.                         if (!(that instanceof Pair))
    
27.                                 return false;
    
28.                         if (that == this)
    
29.                                 return true;
    
30.                         for (int i = 0; i < 4; i++) {
    
31.                                 if (this.eles[i] != ((Pair) that).eles[i])
    
32.                                         return false;
    
33.                         }
    
34. 
    
35.                         return true;
    
36.                 }
    
37. 
    
38.         }
    
39. 
    
40.         public static List<List<Integer>> sum4(List<Integer> list, int target) {
    
41.                 Collections.sort(list);
    
42.                 List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
43. 
    
44.                 // Map <2sum, list of pairs>
    
45.                 Map<Integer, List<List<Integer>>> map = new HashMap<Integer, List<List<Integer>>>();
    
46. 
    
47.                 for (int i = 0; i < list.size(); i++) {
    
48.                         for (int j = i + 1; j < list.size(); j++) {
    
49.                                 int sum2 = list.get(i) + list.get(j);
    
50.                                 List<Integer> pair = new ArrayList<Integer>();
    
51.                                 pair.add(i);
    
52.                                 pair.add(j);
    
53.                                 if (map.containsKey(sum2)) {
    
54.                                         map.get(sum2).add(pair);
    
55.                                 } else {
    
56.                                         List<List<Integer>> listofPair = new ArrayList<List<Integer>>();
    
57.                                         listofPair.add(pair);
    
58.                                         map.put(sum2, listofPair);
    
59.                                 }
    
60.                         }
    
61.                 }
    
62. 
    
63.                 Set<Pair> set = new HashSet<Pair>();
    
64.                 for (int key : map.keySet()) {
    
65.                         int anotherkey = target - key;
    
66.                         if (anotherkey < key)
    
67.                                 continue;
    
68.                         if (map.containsKey(anotherkey)) {
    
69.                                 for (List<Integer> firstValues : map.get(key)) {
    
70.                                         int a = firstValues.get(0);
    
71.                                         int b = firstValues.get(1);
    
72.                                         for (List<Integer> secondValues : map.get(anotherkey)) {
    
73.                                                 int c = secondValues.get(0);
    
74.                                                 int d = secondValues.get(1);
    
75.                                                 if (Pair.valid(a, b, c, d)) {
    
76.                                                         Pair pair = new Pair(a, b, c, d);
    
77.                                                         set.add(pair);
    
78. 
    
79.                                                 }
    
80. 
    
81.                                         }
    
82. 
    
83.                                 }
    
84. 
    
85.                         }
    
86.                 }
    
87. 
    
88.                 for (Pair p : set) {
    
89.                         List<Integer> path = new ArrayList<Integer>();
    
90.                         for (Integer ele : p.eles) {
    
91.                                 path.add(list.get(ele));
    
92.                         }
    
93.                         ans.add(path);
    
94.                 }
    
95.                 return ans;
    
96.         }
    
97. 
    
98.         public static void main(String[] args) {
    
99.                 ArrayList<String> strings = new ArrayList<String>();
    
100.                 Integer[] numbers = new Integer[] { 4, 2, 6, 1, 5, 3 };
     
101.                 List<Integer> list = Arrays.asList(numbers);
     
102.                 System.out.println(sum4(list, 16));
     
103. 
     
104.         }
     
105. }

复制代码

我怎么觉得这个代码不是很对。。。。比如｛1，2，3｝， pair会是｛1，2｝｛2，3｝｛1，3｝，但很明显这个array是没结果的，可是pair可能target等于7的时候有一个输出，似乎不太对

bluezebra 发表于 2015-8-29 11:09
这么良心的帖子没人顶？感谢楼主！

应该加分 XD


拿到onsite了 :)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这么良心的帖子没人顶？感谢楼主！

恭喜楼主，好像之前跟CS61B的时候见过你的帖子。从O(n3)到O(n2)就是将一层的遍历换成hashmap吗

如果array里面有重复元素的话，那么worst case 不止O(n^2)吧，因为map里的list会很长

学长还在匹村等TOC吗~

wenqiang88 发表于 2015-8-29 11:52
如果array里面有重复元素的话，那么worst case 不止O(n^2)吧，因为map里的list会很长

嗯...worst case可能要n^4了...

whdawn 发表于 2015-8-29 11:59
学长还在匹村等TOC吗~

不是学长
不等TOC
骑驴找马

jaly50 发表于 2015-8-29 13:10
不是学长
不等TOC
骑驴找马

那就是学姐了。。。我错了