Vertu到底高大上在哪里？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

Vertu到底高大上在哪里？

Vertu到底高大上在哪里？# PDA - 掌中宝

j*62014-09-18 07:09

1 楼

题目觉得不难但是脑子很不给力想了好半天也没想好发出来大家看看
给一个
class Node{
public Node next();
}
就是说你不能修改这个list
一个list， A->B->C->D->E->F->G->........->Z (当然这只是个例子 list 无序)
给几个 list中的nodes, C, A, B, E, G
求 cluster 的个数
Cluster1: A->B->C
Cluster2: E
Cluster3: G
所以三个
然后要考虑 list size 为 1M node数量为10 的情况, 也就是说你牛别给我iterate
list了

d*i2014-09-18 07:09

2 楼

不建议交易打印胖子；胖子是免费的，收费的是服务:
ok
所求物品名称:
求amazon的20%尿布coupon
物品类别（coupon: mfc 等；血糖仪等）:
amazon的20%尿布coupon，A/S/X打头的。
物品来源（报纸夹页，厂家邮寄等）:
杂志夹页
可接受的价格（必须明码标价，必填）:
每张$3。愿用Gymboree的coupon交换。
邮寄损失方式哪方承担（若需邮寄，必填）:
不需要邮寄
付款方式说明:
paypal，
本贴有效期（必填）:
10天
联系方式（例：站内）:
站内联系

g*42014-09-18 07:09

3 楼

rt。人呢？

k*u2014-09-18 07:09

4 楼

看mate7有宝石屏，我还以为Vertu早就有了。
到底是什么让它成为装逼利器的？

z*82014-09-18 07:09

5 楼

leetcode有类似的吧，不过那个是数组可以双向搜索，比这个简单点

T*y2014-09-18 07:09

6 楼

多了个W开头的。好像大家都有。

【在 d***i 的大作中提到】

: 不建议交易打印胖子；胖子是免费的，收费的是服务:
: ok
: 所求物品名称:
: 求amazon的20%尿布coupon
: 物品类别（coupon: mfc 等；血糖仪等）:
: amazon的20%尿布coupon，A/S/X打头的。
: 物品来源（报纸夹页，厂家邮寄等）:
: 杂志夹页
: 可接受的价格（必须明码标价，必填）:
: 每张$3。愿用Gymboree的coupon交换。

L*32014-09-18 07:09

7 楼

瓜皮帽，最近买什么了。你的那个zhne真坚强。

w*y2014-09-18 07:09

8 楼

Vertu可不是装逼用的，装逼的一般是穷人，富人不需要装逼。

j*62014-09-18 07:09

9 楼

求链接这样的话我就撞死得了看来一遍果然不顶用都记不住啊

b*e2014-09-18 07:09

10 楼

看来明天涨不了多少

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

: rt。人呢？

y*g2014-09-18 07:09

11 楼

有人说多年前他一个朋友浴室里接电话生气拿一个2万多刀的vertu砸出去，把浴缸砸坏
手机没坏。后来回国把手机还卖了3万多美金。因为是什么限量版。

：看mate7有宝石屏，我还以为Vertu早就有了。
：到底是什么让它成为装逼利器的？
……

【在 k**u 的大作中提到】

: 看mate7有宝石屏，我还以为Vertu早就有了。
: 到底是什么让它成为装逼利器的？

n*e2014-09-18 07:09

12 楼

版内的面经有这道题

【在 j*********6 的大作中提到】

: 题目觉得不难但是脑子很不给力想了好半天也没想好发出来大家看看
: 给一个
: class Node{
: public Node next();
: }
: 就是说你不能修改这个list
: 一个list， A->B->C->D->E->F->G->........->Z (当然这只是个例子 list 无序)
: 给几个 list中的nodes, C, A, B, E, G
: 求 cluster 的个数
: Cluster1: A->B->C

g*42014-09-18 07:09

13 楼

zhne很好的，我今天决定留着它了，无论ER后怎么跌。Q4应该是又赚钱了，你想每个Q
都有30%的revenue增长，能不好吗。上次大跌是因为有个institute在selling，现在不
知它卖完了没。

c*n2014-09-18 07:09

14 楼

人还卖服务
就像amex黑卡有没有5%的cashback 有啥好处

l*n2014-09-18 07:09

15 楼

并查集吧，
C, A, B, E, G
C的next不认识，所以root是自己；
A的next是B，所以root是B；
B的next是C，所以root是C；
E的next不认识，root是E；
G的next不认识，root是G。
cluster数目是root位自己的点的个数。

【在 j*********6 的大作中提到】

p*t2014-09-18 07:09

16 楼

兄弟，收到给你的留言了吗？

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

: rt。人呢？

n*e2014-09-18 07:09

17 楼

把给的nodes放入set nodes里面
int count=0;
set::iterator iter = nodes.end();
while (!nodes.empty()) {
if (iter == nodes.end())
iter = nodes.begin();
Node temp = iter->next();
nodes.erase(iter);
iter = nodes.find(temp);
if (iter == nodes.end()) {
count++;
}
}
return count;

【在 j*********6 的大作中提到】

g*42014-09-18 07:09

18 楼

上次的吗，我回你了。后来没收到你的留言。谢谢你。

l*i2014-09-18 07:09

19 楼

一个set，每个node过一次，看看有几个node.next不存在。

g*42014-09-18 07:09

20 楼

你常在俱乐部遇见葛菲吗，代我问他好。
发信人: proteincryst (牛皮熊), 信区: Stock
标题: Re: 股版人气不旺啊，今晚。
发信站: BBS 未名空间站 (Wed Jan 27 00:04:00 2010, 美东)
兄弟，收到给你的留言了吗？

j*62014-09-18 07:09

21 楼

赞！看来还是自己的算法不过关~

【在 l*n 的大作中提到】

: 并查集吧，
: C, A, B, E, G
: C的next不认识，所以root是自己；
: A的next是B，所以root是B；
: B的next是C，所以root是C；
: E的next不认识，root是E；
: G的next不认识，root是G。
: cluster数目是root位自己的点的个数。

f*a2014-09-18 07:09

22 楼

我觉得把list还要存成hash table 这样每次找node.next就不必从头找，基本思路和那
个数组里面最长递增序列是差不多

★ 发自iPhone App: ChineseWeb 8.1

【在 l****i 的大作中提到】

: 一个set，每个node过一次，看看有几个node.next不存在。

q*02014-09-18 07:09

23 楼

//N is the number of nodes
HashMap hmap;
Node* pNode[N];
bool isClusterHeader[N]
for (int i=0; ihmap[pNode[i]] = i;
isClusterHeader[i] = true;
}
for (int i=0; iif (lookup(hmap, pNode[i]->next) { //its next is in hashmap
isClusterHeader[hmap[pNode[i]->next] = false; //link to next
}
}
for (int i=0; iif (isClusterHeader[i]) {
print(pNode[i])
//continue print its next until lookup(hmap, next) == true,
//which means a new cluster starts
}
}

s*x2014-09-18 07:09

24 楼

我觉得跟数组整数求连续子续列个数是一样的题。
就是放hash table , 慢慢相邻的grow and merge.

l*h2014-09-18 07:09

25 楼

请问这个list没有存value的地方，怎么知道是ABCDE的，即每一个节点有何记号？

d*82014-09-18 07:09

26 楼

这个不对吧，比如C会加１，到A不加，但是到B的时候C已经移走了，所以又会加一

【在 n****e 的大作中提到】

: 把给的nodes放入set nodes里面
: int count=0;
: set::iterator iter = nodes.end();
: while (!nodes.empty()) {
: if (iter == nodes.end())
: iter = nodes.begin();
: Node temp = iter->next();
: nodes.erase(iter);
: iter = nodes.find(temp);
: if (iter == nodes.end()) {

d*n2014-09-18 07:09

27 楼

O(n)的算法,n为链表中所有的节点数，可能比较大
空间为O(m), m为toFind的node数，m比较小
一旦所有的toFind的node找到就可以终止
所以平均时间应该会比较快
C#
public class Node
{
public Node Next;
}
public static int GetNumOfClusters(Node node, List toFind)
{
HashSet hs = new HashSet();
foreach (Node n in toFind) hs.Add(n);
int numNodes = toFind.Count, result = 0;
bool previousInHS = false;
while (numNodes > 0 && node != null)
{
if (hs.Contains(node))
{
numNodes--;
if (!previousInHS) result++;
previousInHS = true;
}
else
{
previousInHS = false;
}
node = node.Next;
}
return result;
}

n*e2014-09-18 07:09

28 楼

恩，你说的对。
如果是double linked list就好了，我记得以前的面经是double linked list的
这题是singly linked list

【在 d*******8 的大作中提到】

: 这个不对吧，比如C会加１，到A不加，但是到B的时候C已经移走了，所以又会加一

w*s2014-09-18 07:09

29 楼

不太清楚题目意思啊，大侠解释一下？另外对应leetcode中那个题，完全没有yinxiang
...

d*n2014-09-18 07:09

30 楼

用题目中的输入，到我之前的code走一遍就明白了

yinxiang

【在 w*******s 的大作中提到】

: 不太清楚题目意思啊，大侠解释一下？另外对应leetcode中那个题，完全没有yinxiang
: ...

s*e2014-09-18 07:09

31 楼

interesting question. how about sth like this:
1. for any m, hashes the given nodes, and then sorts the nodes based on the
list order. time will be O(n). finally, O(m) time to figure out the clusters
from the sorted node list.
2. if m << n, and every node is in the list, there is no need to check the
list, build the graphic relation from m directly.

t*d2014-09-18 07:09

32 楼

题目没看懂。求解释清楚一点。

n*f2014-09-18 07:09

33 楼

1.如果没有环：只把查询的node加到hash表里去，然后BFS。BFS开始时把查询的node都
加到队列里去，这样相当于每个node都按相同的速度向后扩展，每扩展一个节点，判断
一下是否在hash表里，如果在，总的cluster数就减1。扩展不下去了或cluster数减到1
了就停止。
2.如果有环：其实我感觉面试官更有可能考察的是有环的情况。这个题就相当于一个图
有n个点，每个点有一条出边，问构成了几个连通分量。它能构成的图有两种情况，一
种是一条链，一种是一个环上加若干条链，就像仙人掌一样。不管是哪种情况都可以用
上面那个BFS的方法来解决，唯一的不同是hash表里需要记每个遍历到的点防止遇到了
环会死循环。

c*p2014-09-18 07:09

34 楼

mark