x**********z
发帖数: 131 | 1 今天接到HR的电话，被告知onsite挂了。。
其实也不打算去他们家，方向不match。但是郁闷的是挂在了一个闲扯的问题上，而且
是国人手里，哎。。。
先上面经：
OA zentest3
1, 一个字典。从一个word删除一个字母可以与另一个word相连。问字典中的词能组成
的最长路径。
Solution: 建图，然后DP
2, n-queens的变种。当时读题读了好久还是把题目理解错了，最后又几个testcases跑
不过。。
Skype:
小印，总说不要给我讲思路，写就行了。。
1，http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=129807&page=1 第一题
2，two difference. 但是不让用hash table。Solution: 排序+双指针
Onsite:
1, 第一轮两个年轻国人，每人一道题
1.1, 首先是一个coding题，问给一个 Node* 数组，怎么判断是不是一个valid的
binary tree。
Solution: 算每个 node 的 indegree 和 o... 阅读全帖 |
|
r**i
发帖数: 2328 | 2 如果一个N(N>=1)个vertices的DAG是weekly connected，其中一个的indegree=0 and
outdegree>=0，其他N-1个的indegree=1 and outdegree=0 or 1，这样的DAG是不是一
定是tree？ |
|
x*****p
发帖数: 1707 | 3 This is actually a direct graph and we are going to find a node with
indegree N-1 and outdegree 0. |
|
w***s
发帖数: 17 | 4 跟版上其他帖子相比不难，但是已挂。自己的编程水平还是不够吧。。。
麻烦大虾解一下面试3那道题？谢
电面1，写大整数，能够应付溢出。自己决定用什么数据结构，实现add
电面2，实现一个队列，主要实现加到队列尾和从队列头删除这两个函数
面试1，搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
何算才能比较快的拿到每个结点的等级。答案关键是 把 indegree算法转成 outdegree
算法
面试2，给一个NxN的矩阵，找包括连续递增数字最长的子串的长度。比如
4 3 9
6 5 1
7 8 2
这个返回4，因为5，6，7，8，方向可以是上，下，左，右，不可以斜角
面试3，有好多文挡，每个文挡可能有一个或零个父文挡，每个文挡可能有零个一个或
多个子文挡。要求重排所有文挡，重排后，所有文挡的父文挡都出现在子文挡前面。自
己设计数据结构和算法。用什么数据结构，我当时用双向链表，程序写的乱七... 阅读全帖 |
|
h****n
发帖数: 1093 | 5 第四题 leetcode原题吧 Longest Consecutive Sequence
outdegree |
|
i******m
发帖数: 375 | 6 第二题，把每个数字看成一个节点，每对相邻的连续数字看成一条权为1的有向边。问
题等价于求最长路径。因为没有环，用floyd算法，最坏情况O(n^4)就可以了，不知道
有没有更好的方法。
outdegree |
|
f********x
发帖数: 2086 | 7
outdegree
第三题这种不是topo排序么？ |
|
c*******n
发帖数: 442 | 8 第三题是不是用tree来表示更好一点啊？
加个root做所有没有父文档的节点的Parent
然后输出结果的时候直接做个BFS就好了？
outdegree |
|
w****3
发帖数: 110 | 9 就是扫描每一个点的out degree和in degree如果是0和n-1就输出结果，如果不是将
indegree来自的点全部放入visited一个hashset里，这些点就不用扫了因为
outdegree不是0。每个点最多被visit一遍（要么是扫过，要么是被之前的节点
indegree排除）。所以是O（N） |
|
c*******2
发帖数: 60 | 10 哦, 对, 是在找到结果就终止了.
空间上我还是觉得重复了.
比如 start = "abcd", end = "efgh".
dict 是所有长度为4的string.
那么中间的每个字母的indegree和outdegree都大于1.
比如: "abcd" -> "ebcd" -> "efcd" -> "efgd" -> "efgh"
"abcd" -> "afcd" -> "efcd" -> "efch" -> "efgh"
由于你只有一个pointer, "efcd"这个Ladder object至少要创建两次, 不管这个
pointer是指向前还是后.
。 |
|
h****n
发帖数: 1093 | 11 来自主题: JobHunting版 - 问个G题吧 搜索引擎中，web page的等级（rank）问题。比如页面被引用的越多，这个页
面就等级约高，搜索结果中，等级高的应该排列在前面。这个问题被转化成graph, 被
引用就表示为directed edge。每个结点存储此结点所指向（引用）的其他结点。问如
何算才能比较快的拿到每个结点的等级。答案关键是 把 indegree算法转成 outdegree
算法
这个是用什么算法转换？thx |
|
r**i
发帖数: 2328 | 12 写错了，其他N-1个的indegree=1 and outdegree>＝0。不过不影响证明 |
|
