p*****2
发帖数: 21240 | 1 来自主题: JobHunting版 - 电面犯二了 也就是说所有A树的value, B树也必须有，且出现的次数一致？所以用hashmap记录一下
就可以了。 |
|
P*******U
发帖数: 203 | 2 就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
要求：不能用loop
如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
的one statement。
面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
表示仍然不会做，有大牛支招吗？ |
|
P*******U
发帖数: 203 | 3 就是那个什么tie toe game，一个N*N的board，里面的数值为0或者1，只要任意一行全
为1或者任意一列全为1或者两个对角线中任意一个全为1，就输出true，否则输出false。
要求：不能用loop
如果N=3，能否不用loop且只用一个statement判断，不能是那种很长的if枚举各种case
的one statement。
面试官给的提示：把board存成一维的bit array，用到类似hashtable的思想
表示仍然不会做，有大牛支招吗？ |
|
h********3
发帖数: 2075 | 4 当然是。只要random产生数是独立且不相关的就行了。概率上也可以证明。 |
|
h********3
发帖数: 2075 | 5 你按照你的均匀密度产生的点集。在极坐标空间内不是均匀的。
在极坐标空间了，球体被转换成了一个3维的立方体。r从0到半径, theta从0到PI, phi
从0到PI。这个立方体的体积是多少？
X,Y,Z任意一个点有且仅有一个点跟极坐标空间内的一个点对应。既然我在极坐标内
uniform产生的点，为什么在X,Y,Z内就不是uniform产生的？ |
|
z********c
发帖数: 72 | 6 F的：
1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
2 单链表倒序输出
3. Dutch Flag Problem
4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
中出现且仅出现一次，比如两个人，
初始 {}
move(1): {1}
move{2}: {1, 2}
move{1}: {2}
G的：
1. BST求某个节点的next节点，有parent指针
2. 两个BST，求他们merge后的BST
3. 一个硬盘上全是文件，求把同样文件不同文件名去重怎么做
4. 一堆数求最大1000个
5. sleep sort，跟我讨论os kernel进程调度的实现和复杂度
6. 拓扑排序
7. scramble string，对一个string，比如tiger，可以随便找一个partition tree
tiger
/ ... 阅读全帖 |
|
t**********t
发帖数: 364 | 7 来自主题: JobHunting版 - G家面试题 N x N integer矩阵。
每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
求取法。
感觉应该可以用DP做? |
|
t**********t
发帖数: 364 | 8 来自主题: JobHunting版 - G家面试题 N x N integer矩阵。
每一行取一个数, 且取出的每一个数必须不同列。取出N个数使得其sum最小.
求取法。
感觉应该可以用DP做? |
|
h****n
发帖数: 1093 | 9 最近A家感觉很缺人，组织了很多不需要电面的group onsite event
小弟也有幸参加了一次这种onsite，接到recruiter的邀请，准备了一个月参加了
Amazon的面试。不过可能还是由于准备不充分并且是第一次面试，最后挂了，说说过程
，求大牛分析为什么挂了
第一个是一个白人年轻GG，上来寒暄了一阵子，大概介绍了一下自己的research，貌似
他不怎么感兴趣，接着开始问behavior问题，印象比较深的是问了一个如果项目中有很
多bug，但是deadline快到期了，你会怎么办，我说首先我会尽量想办法fix掉bug，如
果还是预期还是没法fix完可以找manager多allocate一些resources，比如多一些人手
来一起fix bugs。我说任何bug都有可能导致程序崩溃，那个GG貌似很不满意，继续问
，如果这些bug很不重要呢，举了个例子，我没听清，大体就是和产品功能无关之类的
，我说我会找manager商量商量要不要忽略这些bug继续deliver产品。感觉他还是很不
满意。。。
然后开始问coding题，coding题其实满简单的，就是一个字符串的str... 阅读全帖 |
|
l******d
发帖数: 530 | 10 我也是。除非你的背景很强且跟他们很match，能够弥补口语的不足，否则基本悲剧 |
|
g*****e
发帖数: 282 | 11 给了入口还是NP hard的，且非常理论，不方便用code描述。或者面试官考察的就是图
论知多少。。。 |
|
g*****e
发帖数: 282 | 12 给了入口还是NP hard的，且非常理论，不方便用code描述。或者面试官考察的就是图
论知多少。。。 |
|
d*********g
发帖数: 154 | 13 第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
，如果不等于，那就一定有duplicate。
这样做不就可以了么？Or am I missing something？ |
|
d*********g
发帖数: 154 | 14 第二题：如果没有duplicate而且N个元素都在0到N-1之间，那么只可能0到N-1之间的每
个数都出现且仅出现一次把。那么只需要看array所有元素的和是不是等于0+1+...+N-1
，如果不等于，那就一定有duplicate。
这样做不就可以了么？Or am I missing something？ |
|
y***u
发帖数: 174 | 15 我没多少，全给你吧。反正留着也没用。谢谢你的面经。这就转账。 |
|
d**********x
发帖数: 4083 | 16 恩，我想了一下，主要是靠灵感，要是灵错了请指出。。
直接按照问题定义来，是可以做到时间O(n)空间O(1)的
具体就是使劲往右边走，然后输出，记录当前输出的最后一层层数 -- 当且仅当当前层
数大于记录的层数时输出。
当没有right child的时候，就往parent方向走，找到第一个具有left child的(注意区
分返回时是从right返回还是left返回)，然后继续重复以上算法
这样可以保证遍历的时候每层总是这一层的最右边节点先被访问到
没有parent指针的话可以利用child指针，不碍事。 |
|
O******i
发帖数: 269 | 17 确实是只有删除了。
现在才知道这题应该这样分析才有冷静的思路
1) 读入初始数据后，就是正数轴上以非负整数为端点的一系列排序好且不相交的线段
，有些线段退化为单个的离散点
2) 给定的x, 必须位于某条线段上
3) 下一个数，就是扩展x所在线段(长度增加1）后新的右端点
4) 线段扩展后，填补了gap,可能导致两条相邻的线段合并为一条更长的线段
5) 如果我们用有序数组(每个元素是一个区间)表示这些线段，就是经典的合并区间那
道题，但是考虑到删除两个区间为一个区间会引起其他元素的O(N)移动，改用平衡BST,
可以把这个操作降为O(logN)
这道题的核心，一个是“以线代点", 另外一个是“以树代替数组”
可惜我明白的太晚了，虽然区间合并题和BST都知道，就是没有想到把这两个结合起来。 |
|
K*****k
发帖数: 430 | 18 我自己后来想了下，应该和二爷的思路大体一致，只不过二爷好像是从尾部倒着来，我
的是从头部顺着来。
二爷能否看看对不对。
假如char str[0 .. n - 1]是输入字符串
定义int dp[0 .. n - 1]，全部初始化为0
dp[j]表示str[0 .. j]的最小的划分词数，先计算出dp[0]来
求dp[j + 1], 就是
1) 如果str[0 .. j + 1]在字典中，直接设dp[j + 1] = 1
2) 遍历1 <= k <= j + 1, 如果str[k .. j + 1]在字典中且dp[k - 1]大于0,把最小的
那个dp[k - 1]加上1放到dp[j + 1]中
最后的结果就是返回dp[n - 1], 如果值为0表示无法分词。 |
|
b********e
发帖数: 43 | 19 第二题我的想法是把所有的doc按照size大小排序然后分别从两头开始比较， 因为符合
条件的最大概率应该是最短的doc里面有且只有一个与最长doc相同的word.
不知道是否正确。 |
|
d**********x
发帖数: 4083 | 20 难么？只要记住切入点就可以了
1. 从这个节点是叶子节点的最简单情况开始
2. 推及如果这个节点不是叶子节点，且只有一个子树，则直接删掉把子树和父节点一
连就完事
3. 再推及如果这个节点有两个子树，就去找这个节点的中序前驱，如果中序前驱是个
叶子节点，则换一下，删掉完事，如果中序前驱不是叶子节点，则其必然没有右子树，
于是参考2可以解决
关键是逻辑清楚，记两个关键点，剩下的现推都能推出来。背的话，算法这么多怎么背
得过来，25岁以后记忆力都在减退了 |
|
P**********a
发帖数: 12 | 21 出题人刚从某热门公司到这个更热门的公司不久，所以很难说是哪个公司或者是他个人
出题风格，就不说公司名以免误导大家。
已有一个线程池的类，要求写一个类可以顺序执行需要run的functions，确保不能多线
程，且必须用那个线程池类执行函数。
具体类名/成员名自己定义就可以了，没有标准的。 |
|
N*****N
发帖数: 238 | 22 看了回复，欧这个amat的小心肝巴凉巴凉的。 工资低，晋升慢，加班多且长是肯定的
。稳定不稳定嘛，欧待了3年了没见过认真干活的毛驴被干掉的（他们好多都跑掉了）
。 办绿卡呢，如果回复里ibm的有关情况是真的，那amat办eb1b肯定要容易多了，只要
律师同意就可以。 |
|
M*********y
发帖数: 300 | 23 IBM NY 是非常苦B的公司，气候恶劣，薪水低且不涨，绿卡巨慢，除非你EB1，非常闷
的小地方，里面的人没几个不想跳出来的。
AMT也比较苦B，但好歹在湾区，生活好的多。也有利于另一半找工作。 |
|
m********l
发帖数: 791 | 24 虽然不方便透露薪资，但是确实被榨了不少。
当时另一个staffing company 叫populus group也帮我找到了同样的职位，但是我没从
这个，从了TEK...
我当时随便和populus聊了一下，这个公司的确是有三哥，也确实可以议价，比如你不
要这个benefit那个benefit，工资就可以给你涨多少多少啊 这样的。这个公司也确实
给的钱比TEK多，我算了一下多17%。 但是之前就已经和TEK合作过，觉得确实正规，而
且里面的manager参与感非常强。让我觉得比较靠谱，于是就从了。
个人经验，希望对大家有帮助 |
|
r*********n
发帖数: 4553 | 25 Q: 如果已经是Sorted Order，且每个非unique的数出现两次。你的算法能优化么？
A: 用类似Binary Search, 每次找到中点，如果它和邻居都不同，则就是它
否则，找到相同的邻居（左或者右）。以他俩为分界，看两遍区间哪个区间
长度为奇数，就在哪个子区间找。对于每次查看，时间为O(1)，然后把问题
规模变为1/2原问题。所以总的时间复杂度为
T(n) = T(n/2) + O(1) = O(logN)
其实这到题还可以稍微再快一点点：仅仅对偶数index进行BS，找到mid，如果mid ==
mid+1，则lo = mid + 2; 如果mid != mid + 1 && mid != mid -1，则找到了; 如果
mid != mid +1 && mid == mid - 1，则hi = mid -2 |
|
s*******s
发帖数: 1031 | 26 来自主题: JobHunting版 - 问个面试题 ////////////////////////////////////////////////////////////////////////
// Note: it is O(n) time, O(1) space, use tree can verify. ////////////
// http://blog.csdn.net/qq675927952/article/details/6326525 ////////////
////////////////////////////////////////////////////////////////////////
#include
using namespace std;
/*
输入a1,a2,...,an,b1,b2,...,bn, 在O(n)的时间,O(1)的空间将这个序列顺序改为a1,
b1,a2,b2,a3,b3,...,an,bn，且不需要移动，通过交换完成，只需一个交换空间。
一
a1a2a3a4 b1b2b3b4
a1a2b1b2 a3a4b3b4
二
a1a2... 阅读全帖 |
|
t****a
发帖数: 1212 | 27 来自主题: JobHunting版 - 一道电面题 首先，构造f(n)=n(n-1)/2结果的方法可以用递推产生：
f(1)=0
f(2)=1
..
f(n+1)=f(n)+n # 第n+1个点指向点1..n，所以加入n条边且不会产生环
其次，n(n-1)/2最大的原因是再加任何一条边进去都会形成a<=>b |
|
b***e
发帖数: 1419 | 28 来自主题: JobHunting版 - 问个面试题 Dijkstra求连通算法可解。在adjacent matrix上执行Dijkstra算法，如果某一个cell
的值为1且从未被改变过，那么这个cell所对应的edge是一个canonical edge。 |
|
s********u
发帖数: 1109 | 29 #####请问括号里面的数字是什么意思？
当时他是在演示一个path。但按照他后来说的这个意思，这根本不是个有效的path，而
且不止一个path。所以你就无视这个吧。我觉得按我的意思理解，就是个有效的题。
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
比如最简单的recursion，阶乘，就是从top一直走到down，这个是单向的，只有一个
end那就是n == 1。
backtracking就是回溯，递归的一种，最典型的就是树或者图的DFS和八皇后问题，就
是从一个点出发，往不同的方向走，直到走不通。跟阶乘的区别是，他是多向的，end
有很多。。
### 如果用vector 保存结果，直接push_back
就行了， 这里用list好像没有什么必要？
这里可以用vector，只是他正好提到结果输出lists of points.
的确是可以直接push_back(),因为push_back()传的参数是对象的“复制”而不是“引
用”。我这里clone了一下，主要是因为有时经常用比如 int p... 阅读全帖 |
|
s********u
发帖数: 1109 | 30 #####请问括号里面的数字是什么意思？
当时他是在演示一个path。但按照他后来说的这个意思，这根本不是个有效的path，而
且不止一个path。所以你就无视这个吧。我觉得按我的意思理解，就是个有效的题。
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
比如最简单的recursion，阶乘，就是从top一直走到down，这个是单向的，只有一个
end那就是n == 1。
backtracking就是回溯，递归的一种，最典型的就是树或者图的DFS和八皇后问题，就
是从一个点出发，往不同的方向走，直到走不通。跟阶乘的区别是，他是多向的，end
有很多。。
### 如果用vector 保存结果，直接push_back
就行了， 这里用list好像没有什么必要？
这里可以用vector，只是他正好提到结果输出lists of points.
的确是可以直接push_back(),因为push_back()传的参数是对象的“复制”而不是“引
用”。我这里clone了一下，主要是因为有时经常用比如 int p... 阅读全帖 |
|
s*****4
发帖数: 25 | 31 Unit test要写到多详细呢 有人可以给个例子吗?
test cases我只想到这三个:
1. last hit和cur hit发生在同一秒
2. last hit和cur hit发生在不同秒, 检查结果是否正确的把last hit到cur hit之间
的element reset 0
3. 同2, 且last hit跟cur hit发生的间隔很大(ex. 30000s), 检查run time, 看是否
在reset完300个element后就early return
concurrency是不是只需要用一个mutex把hit()头尾用mutex.lock(), nutex.unlock()
包住就行了? 不是很确定... |
|
s*****4
发帖数: 25 | 32 Unit test要写到多详细呢 有人可以给个例子吗?
test cases我只想到这三个:
1. last hit和cur hit发生在同一秒
2. last hit和cur hit发生在不同秒, 检查结果是否正确的把last hit到cur hit之间
的element reset 0
3. 同2, 且last hit跟cur hit发生的间隔很大(ex. 30000s), 检查run time, 看是否
在reset完300个element后就early return
concurrency是不是只需要用一个mutex把hit()头尾用mutex.lock(), nutex.unlock()
包住就行了? 不是很确定... |
|
T******e
发帖数: 157 | 33 你确定吗？ 我那天用hashmap试了试，对于两个不同的arraylist，如果都是空的话，
hash值是不一样的，如果里面是1 2 3 且顺序一样，可以用list1找出list2的value |
|
h******1
发帖数: 34 | 34 不到1，option，要自己掏钱买。strike price不低。由于给的是option且我自己没积
蓄，一旦恋战便脱不了身。也是我不敢盲接的原因。 |
|
D**********d
发帖数: 849 | 35 他的要求是string 总长度是下界 10^4+3. 也就是图中经过每点一次且仅一次 |
|
w*****e
发帖数: 931 | 36 如果只有一个root节点且值为MIN_VALUE岂不是输出false？
reused |
|
w*****e
发帖数: 931 | 37 如果只有一个root节点且值为MIN_VALUE岂不是输出false？
reused |
|
E********c
发帖数: 37 | 38 嗯，是啊，我也觉得技术性上东西几乎没有人把关。面试官是1黑人1亚裔4白人，没有
烙印额。纯粹是运气吧。
behavior questions很多都很tricky，关于那个和manager冲突的我举了两个例子，说
明不同的manager有不同的managing style,分别用不同的方式处理，一个比较tough,
perfectionist,喜欢不停的挑战你，又不说原因，我处理的方式是委婉地提出各种可能
性方案,另一个比较温和且有包容性，对于这个我是自信地提出自己的主张和依据。 |
|
l*****u
发帖数: 20 | 39 最后一题不太懂，相同结点必须是位置一样，value一样？且父结点的value和位置也一
样？ |
|
m**********0
发帖数: 18 | 40 最后那个其实我开始也没有很懂……相同结点首先是里面value一样，同时在第一个题
当中，它的父节点们也必须是一样的才行，比方说
树A：
A
B C
D F E G T
L
树B：
A
M C
D F G T E
L
同样的节点有A,C,G,E，尽管D俩树都有，但是第二个的D的父节点跟第一个D的父节点不
一样，所以不是。L尽管俩树都有，且第一个父节点一样，但是再上面父节点不同，所
以也不是。
第二问的话，相同的可以有不同的set选择，可以选择 {A,C,,G,T} 或者{A,C,E},让找
到最多成员的set的选择，使得成员中的相对顺序相同 |
|
y*******x
发帖数: 40 | 41 刚刚结束，面试官是三姐，囧，互相交流基本靠在collabedit上打字。
两道题目：
1. copy graph，coding完问复杂度，时间复杂度开始没答对。教训是刷题时一定要明
白复杂度等相关原理，不然很囧。
2. 假设在embed system上编程，不能malloc。给定一个int array，问如何实现
Linkedlist。
这题主要时间都花在讨论上，逐步明白她的要求是：实现insert,delete，且时空复杂
度都是O(1)
我回答为每个node申请3个数组元素，分别存储：data, next index,pre index。然后
使用free list维护空闲元素列表即可。由于交流问题，折腾了快20分钟。
最后时间不够，只让实现了insert。她觉得我假设做的太多，不满意。
总结：比第一轮发挥好一些，基础需要继续加强。英语有待提高，跪给阿三的英语了。 |
|
M********6
发帖数: 67 | 42 1. 极速测试： 2分钟内完成尽可能多的数学、英语类反、智力测验和逻辑题。共10道
，我只完成了六七道就被自动掐掉了。
2. 数学、智力、类反、逻辑、脑筋急转弯等（<=20道）：不限时但强调完成时间和准
确率共同作为评分标准。例如
a.给出一串数3 24 -168 1008 -5040求下一个数是什么
b.一个牛逼的人种了一颗神奇的树，每天高度翻一倍，第十天树高八十尺，问第多少天
树高十尺？
c. 两个木讷的程序员，分别从1号办公室和76号办公室匀速相向而行，1号办公室出发
的程序员每分钟行走5个办公室，76号办公室出发的程序员每分钟行走10个办公室，问
他们在几号办公室相遇。
d. 两个硬币总价值55美分，一个不是nickle，问这两个硬币分别是多少？（选择题，
可以选择不可能选项）
e. 数字填空 4，7，13， ？，49，97
f. 一只搞笑的山羊爬悬崖，崖高80.5英尺，该山羊每分钟上升3英尺后下降2英尺，问
羊多久可爬上悬崖顶端。
g. 公司有一个支票账号内有五万元，另有现金伍佰元。用现金买了一百五十张永久邮
票，每张44美分，又买了两台高配电脑，每台2025元，电脑开销的十... 阅读全帖 |
|
M********6
发帖数: 67 | 43 1. 极速测试： 2分钟内完成尽可能多的数学、英语类反、智力测验和逻辑题。共10道
，我只完成了六七道就被自动掐掉了。
2. 数学、智力、类反、逻辑、脑筋急转弯等（<=20道）：不限时但强调完成时间和准
确率共同作为评分标准。例如
a.给出一串数3 24 -168 1008 -5040求下一个数是什么
b.一个牛逼的人种了一颗神奇的树，每天高度翻一倍，第十天树高八十尺，问第多少天
树高十尺？
c. 两个木讷的程序员，分别从1号办公室和76号办公室匀速相向而行，1号办公室出发
的程序员每分钟行走5个办公室，76号办公室出发的程序员每分钟行走10个办公室，问
他们在几号办公室相遇。
d. 两个硬币总价值55美分，一个不是nickle，问这两个硬币分别是多少？（选择题，
可以选择不可能选项）
e. 数字填空 4，7，13， ？，49，97
f. 一只搞笑的山羊爬悬崖，崖高80.5英尺，该山羊每分钟上升3英尺后下降2英尺，问
羊多久可爬上悬崖顶端。
g. 公司有一个支票账号内有五万元，另有现金伍佰元。用现金买了一百五十张永久邮
票，每张44美分，又买了两台高配电脑，每台2025元，电脑开销的十... 阅读全帖 |
|
y*****h
发帖数: 22 | 44 patternPos表示从哪里开始匹配。初始值为0。
patternEnd表示模式结束的位置。初始值为0。
当前字符和patternPos不相等的话，说明pattern不成立，patternPos回到开始位置0，
patternEnd设为当前字符所在位置i。
当前字符和patternPos相等的话，patternPos加1移到下一个位置，patternEnd保持不
变。并检查下如果patternPos超过patternEnd的话，说明截止到当前字符成功匹配，
patternPos回到开始开始匹配下一串字符。注意，当i走到最后的话，patternPos就不
用清0了。
最后判断成功的条件是，patternPos大于patternEnd的时候，说明整个字符串pattern
且至少重复pattern两次。patternEnd大于零，说明pattern长度大于1。 |
|
t*********2
发帖数: 43 | 45 上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
式为(时间 访问者ID 访问网页)
每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
的log也不一定在一个文件里.
问:
用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
>另一个产品->.....), 针对每一串 访问序列,仅取前三个网页组成一个三元组(如上
面的例子,就是<主页,某搜索页面,某产品页面>), 统计TOP K 的三元组.
(跪在这题上了,先要确定如何判断用户的一次访问,然后是怎样从好多log文件中高效地
提取每个用户每次访问的前三个网页,存在什么地方,最后把这堆信息用heap或者其他什
么取top k).
2. 给一个二叉树,找到与给定节点距离为N的所有节点(没有parent link,有parent
link),两个节点间隔着几条边,就是距离为几
3. ... 阅读全帖 |
|
q****x
发帖数: 7404 | 46 1是map/reduce吧。
2就是BFS，没有parent用递归，有就用queue。
3/4.1经典。
4.2 edit distance，难了点。
上个月刚面的,45分钟一轮,一共4轮, 第一轮就碰上了bar raiser,已跪
1. (Bar Raiser) Amazon服务器有很多log文件记录用户访问Amazon的行为,每条log形
式为(时间 访问者ID 访问网页)
每个访问者访问Amazon网页所产生的每条log不一定在同一个log文件里,相近时间
的log也不一定在一个文件里.
问:
用户每次访问Amazon都会产生一串访问序列(类似先主页 ->搜索产品->产品介绍-
>另一个产品->.....), 针对每一串 访问序列,仅取前三个网页组成一个三元组(如上
面的例子,就是<主页,某搜索页面,某产品页面>), 统计TOP K 的三元组.
(跪在这题上了,先要确定如何判断用户的一次访问,然后是怎样从好多log文件中高效地
提取每个用户每次访问的前三个网页,存在什么地方,最后把这堆信息用heap或者其他什
么取top k).... 阅读全帖 |
|
u*****n
发帖数: 126 | 47 必定存在。考虑f(x) = h(x)-h(x+pi)， f(x) = -f(x+pi), 且h连续，所以根据中值定
理，f(x)中间必然经过0. |
|
I*******d
发帖数: 108 | 48 还是没看懂第一道题。。。一个node可能为0也可能为1
. 它的
value为1，当且仅当它所有的child的value均为1.
就是说不是所有的child的value都为1的话这个node的value可能为0？？但题目下面的
这个图怎么不make sense.
还有
1' clearBit(int offset, int len);里面的len是啥意思？ |
|
I*******d
发帖数: 108 | 49 还是没看懂第一道题。。。一个node可能为0也可能为1
. 它的
value为1，当且仅当它所有的child的value均为1.
就是说不是所有的child的value都为1的话这个node的value可能为0？？但题目下面的
这个图怎么不make sense.
还有
1' clearBit(int offset, int len);里面的len是啥意思？ |
|
y***e
发帖数: 32 | 50 Updated的题目。
1. 给定一个directed graph和一个s节点和一个d节点，判断s和d的距离是否<=3。距离
定义为s和d之间最短路径上link的数目。如果d是s的邻居，则距离为1。
注意，这个directed graph使用adjacent array来表示一个节点的所有neighbors，并
且每个节点最多有n个neighbors。每个节点都有一个Idx，并且每个节点的adjacent
array都是sorted。例如1有邻居2和3，那么1的adjacent array是[2,3] (sorted)
直接的BSF解法时间复杂度是O(n^3)。
要求设计Solution是时间 O(n^2)。
2. 设计一个hash table，实现set（int key，int val）和get（int key）
3. 给定一个整数array A (长度为n)，求出另外一个array B，使得B[i] = A[0]A[1]..
.A[i - 1]A[i + 1]...A[n - 1] (i.e., A[i] is missing from B[i])
如果不可以用除法，如何解？要求s... 阅读全帖 |
|
