一道Coding面试题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道Coding面试题目

一道Coding面试题目# JobHunting - 待字闺中

g*72017-06-09 07:06

1 楼

找购买物品相关的物品，返回最长相关List。如果有一样长的，返回字典最小的一个。
Test case1：
[test1, test2]
[test3, test4]
==> [test1, test2]
Test case2:
[test1, test2]
[test3, test4]
[test4, test5]
==> [test3, test4, test5]
请教有没有比较好简洁的解法？

s*z2017-06-09 07:06

2 楼

可能没理解题直接bfs不可以吗

r*l2017-06-09 07:06

3 楼

看这些例子O（N）可解
俩字典，test1:([test1,test2])
Test2:([test1,test2]),value是同一个list/linkedlist
每加一个Link,看能不能和原来的连起来。其实就是
没法连，连一个，连两个三种情况
while loop就好。连起来的话两个字典要同步更新
每一步还要更新最长List
如果同一个Node可能指向不同的node,就麻烦得多
遍历有向图？

l*02017-06-09 07:06

4 楼

建立无向图，dfs

l*z2017-06-09 07:06

5 楼

O（N）能搞定
用两个hashmap, 一个存物品：集ID，一个是集ID：counter。扫描一遍更新即可

【在 g*******7 的大作中提到】

: 找购买物品相关的物品，返回最长相关List。如果有一样长的，返回字典最小的一个。
: Test case1：
: [test1, test2]
: [test3, test4]
: ==> [test1, test2]
: Test case2:
: [test1, test2]
: [test3, test4]
: [test4, test5]
: ==> [test3, test4, test5]

o*r2017-06-09 07:06

6 楼

class Pair {
Pair(String s, String e) {
_1 = s;
_2 = e;
}
public int hashCode() {
return _1.hashCode() | _2.hashCode();
}
public boolean equals(Object obj) {
if (obj == null) return false;
else {
if (obj instanceof Pair) {
Pair pair = (Pair)obj;
return _1.equals(pair._1) && _2.equals(pair._2);
} else {
return false;
}
}
}
String _1;
String _2;
}
public class Solution {
public List longest(Pair[] input) {
// 如果输入已经排序, O(N), 否则O(NlgN).
Arrays.sort(input, new Comparator(){
public int compare(Pair i1, Pair i2) {
if (!i1._1.equals(i2._1)) return i1._1.compareTo(i2._1);
else return i1._2.compareTo(i2._2);
}
});
int start = 0;
int len = 0;
int index = 0;
for (int i = 1; i < input.length; i++) {
if (input[i - 1]._2.equals(input[i]._1)) continue;
else {
if (i - index > len) {
len = i - index;
start = index;
}
index = i;
}
}
if (input.length - index > len) {
len = input.length - index;
start = index;
}
List ret = new LinkedList<>();
for (int i = start; i < start + len; i++) {
if (ret.isEmpty()) {
ret.add(input[i]._1);
ret.add(input[i]._2);
} else {
ret.add(input[i]._2);
}
}
return ret;
}
}

g*72017-06-09 07:06

7 楼

vector Longest(vector> items) {
}
For test case 1, need to sort the same len and return one in the
lexicographical order.
For test case 2, need to merge different pairs into large vector list.
It is not easy to resolve it with bug free during main shi if did not see
this question before.
Wonder some similar TIMU for this case?