t********e
发帖数: 1169 | 1 有一题topological sort
给你两个数组， 一个代表一行排队的人的高度
一个代表每个人前面比他高的人数
让你根据这俩个数组决定次序
比如
高度 3 1 4 5
人数 1 2 1 0
那么正确的排队次序是这样的:
5 3 4 1
0 1 1 2
fresh phd给出的标准包裹是 140k + 10% bonus (跟个人表现无关）+ 400k |
|
s********a
发帖数: 1447 | 2 我对这题的理解是 如果emp1 级别低于emp2 级别低于emp3 那结果就是
打印emp1收到的info
然后打印emp2都到的info
然后打印emp3收到的info
这个可不可以用类似于topological sort
parse string的时候 如果是emp1 report to emp2 of info1
那么就用emp1 -> emp2 代表
info 1就存到emp2里面
这样级别就都出来了
然后用bfs打印就好了 |
|
T*******h
发帖数: 112 | 3 恩,topological sort是计算机数据结构的基础图论算法,和dijkstra程度差不多，反而
动态规划啥是相对高级的，LZ如果继续面偏CS的职位或许可以在多弄熟点数据结构那块。
不过，LZ作为统计学生已经面的是machine learning scientist，感觉专业知识应该更
重要吧。。。。。。 |
|
i*****h
发帖数: 1534 | 4 网上搜了下好像可以用topological sort 做？ 大牛们给指点下吧，谢谢 |
|
M**********g
发帖数: 59 | 5 这是个伪代码，挺直观的
L← Empty list that will contain the sorted elements
//这个会找吧？就是先得到一个集合，里面的顶点没有任何依赖
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
foreach node m with an edge e from n to m do
remove edge e from thegraph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least onecycle)
else
return L (a topologically sortedorder) |
|
t*********d
发帖数: 1103 | 6 clrs 那个那么厚， ３０ 多章。 topological sort 不算很基本了，它是 dfs 的
变种。我每次看完没多久就忘记。实在是因为用的很少。 |
|
k****i
发帖数: 128 | 7 trie和topological sort算老题吧 |
|
d******a
发帖数: 238 | 8 我面了这个组，他们这个在从头做，因为我就是做广告的，知道他们做的东西有多烂。
练手还行，你如果去的话就是完全被烙印当枪使了，烙印manager自己都不知道该做啥
。。
几个题目：
1. k window max in array
2. topological sorting
3. give a list of intervals, find a point intersect with most ittervals. |
|
|
r*********r
发帖数: 53 | 10 判断图是否有环：
我觉得可以直接用dfs，每一步记录当前访问的node，如果当前访问的node之前被访问
过那么就是有环的。
如果图是有向图，我们还可以用topological sorting 来判断。 |
|
r*********r
发帖数: 53 | 11 空间是省不了的吧……
如果是有向图，那么可以用topological sorting, 时间复杂度会低一些，大概是O(V+E
). 但是空间还是省不了。
呢？ |
|
x*****n
发帖数: 195 | 12 ADP那么烂的都值那么多钱，看好zenpayroll。自己在AngelList上直接投的。大概是因
为不在湾区，要求第3轮店面，挂了。前两面题目都不难，记不清了，leetcode easy到
medium的样子。但需要很快写完code然后在codepad里跑测试，然后改点条件，你马上
改code跑新的测试用例。
第三面的题目是简化欠钱还钱关系，比如A借给B 50元，B给C 50元，C给A 20元，那最
后可以简化为A给了C 30元。输入输出数据结构自己定义。A可以多次借钱给B，这些细
节都需要自己问出来。
开头就想到了直接算每个人汇总后到底是应得x元钱还是欠人x元钱这个简化思路，但想
不出之后怎么建立最优（少）的借钱还钱mapping关系。。。于是按类似topology sort
的思想直接按各个path简化，简化到简化不下去感觉应该是最优解，知道zenpayroll的
风格是要code能跑起来，拼命写还是没写完能跑的code。最后跟面试官讨论了他的解法
，就是按我最开始时的思路统计各个人的结余，然后他说按贪心法做好了，虽然不一定
最优（简化后的借钱欠钱关系数最少），但一般也接近最优了... 阅读全帖 |
|
i*****h
发帖数: 1534 | 13 明年继续呗，我也面的测试岗位以为简单一点，lc全刷完了，结果问了个topological
sort(那时候lc里还没这题）就傻了，烙印一上来还就让用hashmap做，然后马上挂了。
当时也挺不甘心的，现在想想也就这么回事，刷题顺便把那题也刷了。 |
|
b*****n
发帖数: 618 | 14 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给）
再上各个公司的面经和感受：
Yahoo：
最早面的公司，面的是Flurry Team，Yah... 阅读全帖 |
|
f*******r
发帖数: 976 | 15 恭喜，都是好包袱！
关键字: 面经
发信站: BBS 未名空间站 (Sat Jun 13 17:27:31 2015, 美东)
前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refres... 阅读全帖 |
|
b**********5
发帖数: 7881 | 16 那你是用什么hash？ 怎么做range query呢？ 我觉得workflow不是很难啊？ 难点就是
怎么hash， 怎么range query。。。
你的这题的storm 的topology是怎么设计的呢？ |
|
|
h****3
发帖数: 89 | 18 骑驴找马找工作结束，终于拿到心仪的offer，面试准备了大概半年多，前期复习时不
是很认真，每天刷一道lc的节奏。到后来两个月才认真起来，每天八小时左右学习
面经如下：
Snapchat
（1） Big integer (negative included)
（2） Topological sort
（3） Manager behavior question + N-queen II
（4） Unique BST I, II + lots of
Amazon
电面： dp 麦当劳买鸡块问题，比较简单
Recursion 类似subset
(1) Given an array of integers, return the result after calculate square
of each element(don’t worry overflow): eg [1,2,3] => [1,4,9]
(2) System Design yahoo news
(3) 给一个matrix和字典，matrix每一个ce... 阅读全帖 |
|
i*****h
发帖数: 1534 | 19 不一定啦，说不定就放你过了。
就算不过明年还可以去啦，没什么大不了的。
就当积累点经验呗，我当时面的时候来了个topological sort，那时候lc里没有这题，
结果就给了个大概思路code也没写完。现在想想还是自己水平不够，多准备准备总能去
的，不要急啊 |
|
|
|
c*******t
发帖数: 123 | 22 正在刷题的菜鸟说说我的想法：
第一题：笨办法，找出一对，踢掉这个或者那个。 或者用图，别人都指向这个人，这
个人不能指向任何人。这个人是sink point. topological sort.这个人是最后一个。
但问题是这个题目有比O（n）更优的算法吗？n是问问题的个数，比如一对人，你问a认
识b吗, b认识a吗，这算两个问题。如果能知道其他人之间互相熟识的程度，那就可以
用概率。
第二题： 键盘是3乘3， 密码可以从任何点开始，但不能成为闭环，就是访问过得不能
再访问。
不要用矩阵的思想去想，那样受制几何形状太复杂。做一个9个节点的
图，undirected. 比如1可以连到2，4，5.
问题变为从1出发，有多少种不同的路径？访问过得不能在访问。这个
应该是个经典算法问题吧？
9个不同出发位置加起来。 |
|
k******4
发帖数: 7 | 23 为了防止违反NDA，就不列出公司名了，就是一些常见公司。
1. Write a iterator to iterate a nested array.
For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
用了stack存(array, index)的tuple。
2. LeetCode 原题，120 - Triange。有一点变种，给的是一维数组。
3. Implement HashTable 主要看dynamic expanding
4. Implement MaxHeap.
5. Topology sort，就是版上常见的给一些排过序的未知语言的词，求该语言的字母序
。要求实现核心算法。可以给出一些helper function定义不需实现。
6. LeetCode 付费题 157 & 158 - Read N Characters Given Rea... 阅读全帖 |
|
a*******a
发帖数: 383 | 24 在别处看到别的公司也考，突然想起来我G onsite貌似挂在这题上了。想请教请教各位
大牛怎么做
“给你一棵树，不是binary的，每个节点会有任意个children，然后这棵树是存在一个
数组里的，数组的每个元素就是一个节点，节点包含了它的index以及它的parent的
index，而不是children的index哦，所以这棵树是从child指向parent的。最后是给我
这个数组和一个节点的index，让我删除这个index以及它的子树，只能用O(n)的空间复
杂度，而且大小是确定好的”
数组里各个node是打乱的，不是topologically sorted的
update：
举个例子：
[3,1,4,1,5,7,2,6]
删index 1
得到
[x,x,4,x,5,7,2,6] （x代表被删除）
最终输出
[1,2,4,0,3]
我觉得主要难点在找到哪些index要删，最后往前挪补空缺的步骤比较trivial |
|
b**********5
发帖数: 7881 | 25 no map reduce, no spark...
there are a lot of commonality between these big data technologies...
when i was at a spark tutorial thingy, and the speaker talked about how
spark distribute jobs across cluster, i am like, isn't it the same thing as
storm, you got nimbus serving as the master, giving tasks to different
workers, and the workers spins a thread to execute the subtask...
and then u read about the cassandra, and its topology aware replication
strategy, and i am like, isn't it similar to H... 阅读全帖 |
|
l*******i
发帖数: 7 | 26 买买提上好心人推荐的，onsite已挂，发个面经
OA Test2
1.flip 0 or 1
有一串0,1的数组，然后可以取中间任意一段，把0置换为1,1置换为0. 问这样一次置换
之后，这组数组最多还有多少个1.
2. uneaten leaves
给你一个数N,以及一个数组，让你统计在1到N之间，不能被这个数组里的数 整除的数
的个数。
具体内容考古
http://www.1point3acres.com/bbs/thread-136079-1-1.html
第二个问题，我有两个case时间超时没过，也给了电面
skype
Remove nth Node from the end of Node
Find element in rotate array
design a online application for bank account
onsite
round 1. Trapping rain water
写了时间空间O（N），后来要求空间O(1),最后没写完整。面试在一个四周都是墙的小
屋里，一开始就感觉比较压抑。面试官不说话一直玩手机，最后拍走了。
round 2. T... 阅读全帖 |
|
f*******r
发帖数: 976 | 27 Move on吧，希望LZ拿大offer
买买提上好心人推荐的，onsite已挂，发个面经
OA Test2
1.flip 0 or 1
有一串0,1的数组，然后可以取中间任意一段，把0置换为1,1置换为0. 问这样一次置换
之后，这组数组最多还有多少个1.
2. uneaten leaves
给你一个数N,以及一个数组，让你统计在1到N之间，不能被这个数组里的数 整除的数
的个数。
具体内容考古
http://www.1point3acres.com/bbs/thread-136079-1-1.html
第二个问题，我有两个case时间超时没过，也给了电面
skype
Remove nth Node from the end of Node
Find element in rotate array
design a online application for bank account
onsite
round 1. Trapping rain water
写了时间空间O（N），后来要求空间O(1),最后没写完整。面试在一个四周都是墙的小
屋里，一开始就感觉比较压抑。面试官不说话一... 阅读全帖 |
|
S********t
发帖数: 3431 | 28 anagram那个你没答好吧。想到count花的时候太多了些，期望值应该是能快速想到吧。
multi-count完全可以encode成string做为hashmap的key，比如aabccc -> a2bc3，你非
要自己设计一个hash function来hash这个count array，估计没有match interviewer
的思路
tree(actually DAG) cycle那个你也没说对, hint: DFS/topology sort
你自己也说了脑子是晕的。脑子晕还不reschedule？我知道有人onsite前睡觉没睡好，
第二天立马都找recruiter last minute reschedule的。
u |
|
b**********5
发帖数: 7881 | 29 第四面继续： 现在给你一个
class task implements runable{
void run();
List depedencies;
}
就是有一个task list， 每个task可能depends on some other tasks in the list，
让给个solution， so that tasks are run after their dependent tasks
我说， 不就是topology sort吗。。。 然后就哗啦哗啦用BFS写了一个function。 先
用java 8 filter一个sublist for those that dependencies size is 0. 然后
create一个 Executor。newFixedThreadPool， 把这些sublist给submit掉， 再把
sublist从原来的list里撤掉， 再iterate through the list， 把这个zero
dependecies的task从 每个task的dependency list... 阅读全帖 |
|
d*******s
发帖数: 65 | 30 这题为什么没人提topological sort呢 |
|
c*****m
发帖数: 271 | 31 不知道楼上们讨论的union find怎么做法？如何建立parent信息？
topological sort如果有环做不了吧？
"同时关键字一个hashset也要主动提出来。如果面试官想放水，不用adjancy list来描
述图，都是有可能的。"=>hashset是用来访问已经访问过的节点的吧？ |
|
I**********a
发帖数: 1183 | 32 发一批跪了的面经吧，大多都是LC原题，所以一直也没发，跪的原因除个别是被黑，大
多确实是自己没吃透，大牛们看着笑笑就好了
1. Top K : Min/Max heap (搞对用哪个，不然 O(nlogk)就变成 O(nlogn), partial
quickselect
2. round robin iterator: 注意循环时，应该剪去空的sub-iterator以降低外层循环
次数
3. using stack implement queue: 1号stack倒到2号了，不用倒回来
4. LRU cashe: JAVA里linkedhashmap就已经实现了，被问到了不知道被鄙视。。
5. uni-value tree: 用了global variable图省事，被逮住问有什么不好，怎么解决
，以后再不给自己挖这种坑了，老老实实Pair返回
其他各种原题：
topology sort
maximum subarray ( less than a target sum, LC原题好像是〉=target)
text justification
number o... 阅读全帖 |
|
|
b**********5
发帖数: 7881 | 34 看了看documentation， examples， 都是些简单的basic operation， 比如count，
join， filter啊什么的。。。
我以前有个storm topology， 很多bolt， 其实就是一个asynchronous http call to
some other API。。。 但是在apache stream里，好像没有哪个transforming step是
能够asynchronous http call的？
比如我现在有这个
class Tweet {
id;
text;
language;
}
我现在tweet DStream， 要call 一个3rd party web API， 那个3rd party web api
要text， response会告诉我是什么language， 然后我save到Tweet class的language
field。
这个在apache spark里怎么搞啊？ |
|
|
g*******d
发帖数: 73 | 36 第一题有点意思!
前面也分析了, 先排序, 然后我们要找的subset sum S1 = S*L1/L, 而如果S/L总平均
数可能不是整数, 那么需要检查一下S*L1%L是否为0, 是的话才能继续做, 进化版的
CombinationSum3 (L1, S*L1/L)
可以限制L1<=L/2. 如果到L/2还没找到就算失败.
由于已经排过序了, 那么找到的第一个组合就是长度最短,且topological最前的答案.
(所以也不用费神排除重复答案了)
原题链接: https://leetcode.com/problems/combination-sum-iii/
DFS+backtracking
感觉可以加进Leetcode成CombinationSum4, 难度的话算Hard里的中档题
PS: 刚开始找工作, 求各位前辈内推...CS fresh grad, 目标SDE, 会点ML |
|
m**********e
发帖数: 112 | 37 If you are interested in applying for the open position listed below, please
send resume to [email protected]/* */ Please highlight SQL Database
Developer as your targeted job in your resume
Job title SQL Database Developer
Reports to Senior Database DeveloperTeam Lead
Job purpose
Analyzing, developing SSIS projects, custom reports and work closely with
the team on any SQL issues.
Duties and responsibilities
• Develop SSIS projects to handle ETL, transmission, encryption,
an... 阅读全帖 |
|
l*********w
发帖数: 472 | 38 谢谢谢谢！我也在想我这算phd嘛。。。确实非常水。我觉得我读EE phd做的东西跟
security是相关的，很多principle是一样的，但是我也觉得我没能入得了CS security
的门。求推荐几本书我能赶紧恶补一下下～～～
我是EE的phd，做的都是privacy 相关的一些，但是从EE的出发点跟CS不太一样。CS用
的differential privacy做metric，因为针对的是数据库。但是在EE的很多场景内数据
库的概念不适用，所以我们用的是信息熵entropy。另外研究手段也不一样，CS往往是
提出算法，给出实验性能对比，因为针对的是实际问题。我们是抽象抽象变成控制问题
，然后用dynamic programming算期望，得到公式之后再优化或者放松条件找上限下限
。所以我们的contribution主要在提供insight。
另外我做的是network security，比如network topology和certificate distribution
之类的。但是和CS不一样的是，我们考虑的是如果通信网被攻击之后那么依赖通信网的
物理层会受到什么影响。比如... 阅读全帖 |
|
w*******r
发帖数: 14 | 39 我们组最近有两个openings for new grad, 主要是负责development of automation
test framework and automate test cases, and model-based testing. 主要的要求
是有基本的网络知识和编程能力。工作简介如下，如果有兴趣可以把简历发给我的邮箱
，[email protected]/* */。或者也可以发站内邮件来了解更多情况。
https://careers.vmware.com/job/palo-alto/qe-development-engineer-nsx-entry-
level/1567/2907389
QE Development Engineer, NSX (Entry Level)
We are seeking a QE Development Engineer with a passion to work in a complex
computing environment to join our Network Security development t... 阅读全帖 |
|
j********g
发帖数: 61 | 40 这是个DAG。能否solve，1.是否loop。2.是否全联通。
递归复杂度应该是 (N-1)!，N是 cell数目。
Parsing 字符串是预处理。topology sort代码不长。 |
|
R*****i
发帖数: 2126 | 41 我不明白这个问题为什么非要用topological sorting?我嚼着扫描+迭代就可以了。我
敢保证Excel的迭代次数不会超过三四次的。谁吃了没事干，A1表达式里用A2， A2的表
达式里用A3， A3的表达式用A4...An-1的表达式里用An, An的表达式里用B1，...,最多
嵌套个三四次吧？ |
|
发帖数: 1 | 42 楼主，B3-5是B3～B5呢还是B3减去5？我觉得这个题不用考虑太多复杂的表达式处理，
因为考点不在那里。或者topology sorting或者dfs每一个cell的关联的cell，如果有
cycle（B3=A5+A6，A5=B3+A6）就返回false。可以用visited和dependencies两个二维
boolean数组去做cache来优化dfs，结果应该是O（mn）的 |
|
x**********i
发帖数: 4964 | 43 new grad 选组 想做back end相关
希望过来人帮忙指点一下，感激不尽，能有过来人的前辈指点当然更好
希望能学到些东西，忙点累点都没问题，不要太多的oncall就好 谢谢啦
1.Amazon Cloud Drive
Amazon Drive is Amazon’s consumer cloud storage service, it lets customers
store photos, videos and file in a secure, redundant, online location. The
business is dedicated to the customer's experience around personal photos,
videos and files– we want to help people store and enjoy a lifetime of
memories. We have a focused vision to deliver secure storage, viewing
experiences, organi... 阅读全帖 |
|
|
|
|
z*********n
发帖数: 1451 | 47 都要，有些DFS非常好写，BFS很麻烦。但有些只能用BFS，DFS非常麻烦。 |
|
发帖数: 1 | 48 是吗是吗，是那些好用，那些不好用，我从来只用dfs
哈哈 |
|
|
z*********n
发帖数: 1451 | 50
一般情况都是dfs方便，尤其是需要打印某串路径，比如打出某个环的。而要判断是否
唯一sort结果，肯定bfs方便吧。比如1->2, 1->3，可以是1 2 3， 也可以是1 3 2，不
唯一。BFS这trivial啊，DFS咋整？肯定也能做出来，但肯定没BFS简单。 |
|
