f**l
发帖数: 44 | 1 来自主题: JobHunting版 - G新鲜面经 1.2 就是说一个数组，找一个序列，使得第一个小于第二个，第二个大于第三个，第三
个小于第四个，第四个大于第五个。。一个大牛的解法是先sort，然后头尾分别取，这
个应该work。但follow up是如何返回所有的valid序列，这个我没打上来。
4. generalized tree其实就是一个list，就是说，树上任何一个节点，如果至多只有
一个child，那么就是valid的结果。很明显所有的leaf节点都满足，我上面的例子中，
2也符合，因为他只有一个child，其他节点1和3不符合，因为他们都有两个子节点。 |
|
s********u
发帖数: 1109 | 2 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
l*n
发帖数: 529 | 3 这里可以用两个不算做数据的dummy head、tail node，否则考虑头尾的conner case很
麻烦。
key |
|
r********7
发帖数: 102 | 4 嘻嘻，没看懂。。 啥叫dummy head， tail 啊？ 怎么实现呢？
每次都考虑头尾，确实很麻烦，弄得头大。。 |
|
m********o
发帖数: 796 | 5 的确，种族斗争需要的是几个聪明的大脑去指挥几百个没脑的，金字塔结构；而我们的
问题是大部分人都有点脑子，但又没有顶尖的，金字塔中上部过于雍肿头尾过轻，自保
还行开拓无力 |
|
|
|
f*****e
发帖数: 2992 | 8 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。 |
|
e********3
发帖数: 18578 | 9 对，你这个解法是更优化的，多谢了,我应该想到的，其实in-place quick sort和你这
样用两个头尾index方法类似。
的。 |
|
f*****e
发帖数: 2992 | 10 是不是必须从头开始复制？可以先peek n 遍知道头尾什么元素，再压一个INT_MAX。 |
|
e********3
发帖数: 18578 | 11 对，你这个解法是更优化的，多谢了,我应该想到的，其实in-place quick sort和你这
样用两个头尾index方法类似。
的。 |
|
w******g
发帖数: 189 | 12 就是那道双向链表题：
"
一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
"
题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
thanks in advance! |
|
w******g
发帖数: 189 | 13 就是那道双向链表题：
"
一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
"
题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
thanks in advance! |
|
A*****o
发帖数: 284 | 14 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
请大牛给个指点.谢谢 |
|
p**o
发帖数: 3409 | 15 双向链表其实可以封装一下，加个属性表示正向和逆向（翻转只要改这个值即可）
头尾指针用二重指针来做，中间结点的next和prev指针变量靠offset来区别 |
|
z*******3
发帖数: 13709 | 16 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
z*******3
发帖数: 13709 | 17 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
t***t
发帖数: 6066 | 18 可是进去的时候如果是高点就一分赚不到。当年ESPP还给头尾低点15%折扣的，后来只
给尾部5%了。结果大家都把它cancel掉了。 |
|
h*******q
发帖数: 5 | 19 从准备面试开始潜水，在本版上收获不少。所以想尽一点绵薄之力，贡献一点电面面经。
L家 - 挂了：
电面1： 白人，HM.
Chat 5 min.
Basic Question: 10 min: TCP vs UDP, Virtual Memory, Page fault, etc...
Question 1: Mirror a Tree
Solution: recursive
Question 2: Implement a data structure class support: insert, delete and
random get
Solution: two hash map and move last to fill the hole when deleting
电面2： 国人
Question: Java Blocking Queue,
Solution: 参见本版讨论
G家 - 挂了：
电面1: 三哥，很不友好，解题的时候一个劲打岔，想挑个错，结果发现是他错了。然
后让我refine code 15分钟。
Question: Double Circular Sorted... 阅读全帖 |
|
y***n
发帖数: 1594 | 20 这个有点看晕了，我可能会用一个map 存一下被Flatten的List 的头尾
节点，然后Restore 一下。 |
|
w*****d
发帖数: 105 | 21 来自主题: JobHunting版 - 一道面试题 有parent指针就好说：找到p和q的最低共同祖先r，然后打印出以r为根的子树的所有叶
子，头尾去掉p和q即可。
如果没有parent指针，只能中序遍历，条件判断每个节点是否叶子，是否在p和q中间了
。 |
|
m*****n
发帖数: 2152 | 22 非科班出身，看都看不懂什么最小子集，唉~~。
用个最土的方法，BFS来解，时间复杂度可能不是最优，抛砖引玉。
建一个bitset table，C++用vector >
每个row就是dynamic_bitset<> 存dict里面长度与target相同的string的第column位的
与target第column位的异同值，比如
apple, [blade] -> [[0],[0],[0],[0],[1]]
apple, [“plain”, “amber”, “blade”] -> [[0,1,0],[0,0,0],[0,0,0],[0,0,0]
,[0,0,1]]。
完成转换以后可以一眼看出，如何得到答案，就是每个row全0的可以完全区分。以上第
二题1p3,2p2,3l1都是答案。
其中，头尾两个row最特殊，比中间row要abbr度要高，比如第一题a4,显然比1p3,2p2,
3l1要高。
对于复杂问题，没有一个row全0的话，就要用BFS，逐个logic_and组合，得到全0的row
。组合时
可以把全1的row全部踢掉，因为没帮... 阅读全帖 |
|
m*****n
发帖数: 2152 | 23 target: abcde 字典：[aaaaa, bbbbb, ccccc, ddddd, eeeee]
编码是[[10000],[01000],[00100],[00010],[00001]]所以最小的是取任意 两个row
and就可以了。但是要优先取头尾两个row，原因上面说过了。所以这题答案是ab3, 3de
, a3e都行，其他的如a1c2,等等，abbr度不够， |
|
m*****n
发帖数: 2152 | 24 非科班出身，看都看不懂什么最小子集，唉~~。
用个最土的方法，BFS来解，时间复杂度可能不是最优，抛砖引玉。
建一个bitset table，C++用vector >
每个row就是dynamic_bitset<> 存dict里面长度与target相同的string的第column位的
与target第column位的异同值，比如
apple, [blade] -> [[0],[0],[0],[0],[1]]
apple, [“plain”, “amber”, “blade”] -> [[0,1,0],[0,0,0],[0,0,0],[0,0,0]
,[0,0,1]]。
完成转换以后可以一眼看出，如何得到答案，就是每个row全0的可以完全区分。以上第
二题1p3,2p2,3l1都是答案。
其中，头尾两个row最特殊，比中间row要abbr度要高，比如第一题a4,显然比1p3,2p2,
3l1要高。
对于复杂问题，没有一个row全0的话，就要用BFS，逐个logic_and组合，得到全0的row
。组合时
可以把全1的row全部踢掉，因为没帮... 阅读全帖 |
|
m*****n
发帖数: 2152 | 25 target: abcde 字典：[aaaaa, bbbbb, ccccc, ddddd, eeeee]
编码是[[10000],[01000],[00100],[00010],[00001]]所以最小的是取任意 两个row
and就可以了。但是要优先取头尾两个row，原因上面说过了。所以这题答案是ab3, 3de
, a3e都行，其他的如a1c2,等等，abbr度不够， |
|
M*******a
发帖数: 1633 | 26 就是左右子数都返回个sorted list，这回个list包含头尾指针，然后再三段连起来。 |
|
w******e
发帖数: 1621 | 27 这个能不能greedy？看起来有点像leetcode的trap water
更新：这个应该就是greedy证明和trap water一样。
左右2个指针指头尾，指的数小的那个移动，记录最大距离。 |
|
w******e
发帖数: 1621 | 28 这个能不能greedy？看起来有点像leetcode的trap water
更新：这个应该就是greedy证明和trap water一样。
左右2个指针指头尾，指的数小的那个移动，记录最大距离。 |
|
y*****e
发帖数: 712 | 29 我觉得和container那题有类似之处，但不是完全相同
两个指针分别指头尾，算右指针左移的cost
costR = A[r - 1] - A[r] - 1;
左指针右移的cost
costL = A[l + 1] - A[l] - 1；
比较costR, costL大小，哪个大就往哪边移
呀。 |
|
|
m****t
发帖数: 555 | 31 triplet那道题，简单的做法和3sum差不多。先排序，转化为2sum问题。对于每个a[i],
计算a[j], a[k] 的 2sum。 头尾 j,k 两二个指针往中间走，if a[j]+a[k]<=X-a[i]
，则count += k-j;最后输出count.
这样的时间复杂度是O(n^2). |
|
D*******r
发帖数: 2323 | 32 它的解法是在头尾两端各加一个lower - 1和upper + 1的element，以此来简化edge
cases的处理。
public List findMissingRanges( int[] vals, int start, int end) {
List ranges = new ArrayList<>();
int prev = start - 1;
for (int i = 0; i <= vals.length; i++) {
int curr = (i == vals.length) ? end + 1 : vals[i];
if (curr - prev >= 2) {
ranges.add(getRange(prev + 1, curr - 1));
}
prev = curr;
}
return ranges;
}
private String getRange( int from, int to) {
return (from == to)... 阅读全帖 |
|
y*****n
发帖数: 1235 | 33 Int r=-1就可以了。
有可能全是正面。然后必须flip一个。选头尾的就行。 |
|
M**********7
发帖数: 378 | 34 这个观察不错，就是头尾的对子可以拿掉。
可算法上好像还是有问题，像以下这种情况，要交换2和0位，就不是最优了。
0 1 2
A B B
2 |
|
M**********7
发帖数: 378 | 35 首先感谢推荐以及陪同午饭的大牛哥，以及一直帮忙的美女！
本着同样帮同胞的精神回馈一下版面。
今天接到人力电话，说反馈还不错，但是很遗憾只能明年见了，不知道啥原因。
当时面试感觉挺好的，面之前就知道这个据点不怎么招人，不知道是不是这个原因。
电面两轮。
共五轮，有三轮和面试官谈的双方都很开心，其他的一轮也算中上，有一轮一般，但题
也做出来了。
所有题不是leetcode加面经覆盖过的，就是思路不怎么难的题。
不按照顺序上题
一、一道面经里面提到过讨论过，但是不太一样的。改用中文例子。
就是字符串编码解码。
编码规则是
原字串：
春节快乐喜气羊羊羊年大吉
编码为：
春节快乐喜气3x羊年大吉
两个情况下会有歧义：一个是原字串中的数字加x
之前面经提到的是用两个x转义，但是我遇到的要求是解码程序的逻辑不能改变。
此外还有压缩后前面的数字问题，比如
3羊羊羊开泰
变成33x羊开泰则解码程序会出错。
实际上这两个问题是一个问题，就是编码后源串中代表数字的字符恰好出现在数字加x
前面怎么办。
经过讨论，解决方法是将所有的领头数字编码例如：
3羊羊羊开泰
就编码成
1x33x羊开泰
要求尽量优化，也就... 阅读全帖 |
|
S***w
发帖数: 1014 | 36 二、每个字串可以编码为头尾字符和中间的字符数
例如
新春快乐万事如意
变成
新6意
实现方法给一个字典，一个字串，返回字串的编码是否在字典里面有冲突。
确认了字串是否一定在字典里；反问你怎么设计；我说如果在的话还是返回是否有冲突
，如果不在的话返回是否和现有的有冲突；认可这个设计。
确认字串长度不足3怎么办；反问你怎么设计；我说不足就是返回原串；认可这个设计。
确认思路是每个字串都可以直接得到编码，之后用这个编码字串判断冲突就可以。
实现很直接；写的时候，提到如果工作中遇到的话，一般要构建这个字典，所以可以保
留一个编码到字串的哈希表，用来直接判断。
对方听了以后让设计这个类的api。
这题目 什么意思
没看懂 :-) |
|
x*******6
发帖数: 262 | 37 二、每个字串可以编码为头尾字符和中间的字符数
例如
新春快乐万事如意
变成
新6意
实现方法给一个字典，一个字串，返回字串的编码是否在字典里面有冲突。
这个题好像当年叫i18n？
发现现在好多公司出老题
原字串：
春节快乐喜气羊羊羊年大吉
编码为：
春节快乐喜气3x羊年大吉
这个一两年前也好像也见到过，aabccc －》 a2bc3
赞面经 |
|
M**********7
发帖数: 378 | 38 首先感谢推荐以及陪同午饭的大牛哥，以及一直帮忙的美女！
本着同样帮同胞的精神回馈一下版面。
今天接到人力电话，说反馈还不错，但是很遗憾只能明年见了，不知道啥原因。
当时面试感觉挺好的，面之前就知道这个据点不怎么招人，不知道是不是这个原因。
电面两轮。
共五轮，有三轮和面试官谈的双方都很开心，其他的一轮也算中上，有一轮一般，但题
也做出来了。
所有题不是leetcode加面经覆盖过的，就是思路不怎么难的题。
不按照顺序上题
一、一道面经里面提到过讨论过，但是不太一样的。改用中文例子。
就是字符串编码解码。
编码规则是
原字串：
春节快乐喜气羊羊羊年大吉
编码为：
春节快乐喜气3x羊年大吉
两个情况下会有歧义：一个是原字串中的数字加x
之前面经提到的是用两个x转义，但是我遇到的要求是解码程序的逻辑不能改变。
此外还有压缩后前面的数字问题，比如
3羊羊羊开泰
变成33x羊开泰则解码程序会出错。
实际上这两个问题是一个问题，就是编码后源串中代表数字的字符恰好出现在数字加x
前面怎么办。
经过讨论，解决方法是将所有的领头数字编码例如：
3羊羊羊开泰
就编码成
1x33x羊开泰
要求尽量优化，也就... 阅读全帖 |
|
S***w
发帖数: 1014 | 39 二、每个字串可以编码为头尾字符和中间的字符数
例如
新春快乐万事如意
变成
新6意
实现方法给一个字典，一个字串，返回字串的编码是否在字典里面有冲突。
确认了字串是否一定在字典里；反问你怎么设计；我说如果在的话还是返回是否有冲突
，如果不在的话返回是否和现有的有冲突；认可这个设计。
确认字串长度不足3怎么办；反问你怎么设计；我说不足就是返回原串；认可这个设计。
确认思路是每个字串都可以直接得到编码，之后用这个编码字串判断冲突就可以。
实现很直接；写的时候，提到如果工作中遇到的话，一般要构建这个字典，所以可以保
留一个编码到字串的哈希表，用来直接判断。
对方听了以后让设计这个类的api。
这题目 什么意思
没看懂 :-) |
|
x*******6
发帖数: 262 | 40 二、每个字串可以编码为头尾字符和中间的字符数
例如
新春快乐万事如意
变成
新6意
实现方法给一个字典，一个字串，返回字串的编码是否在字典里面有冲突。
这个题好像当年叫i18n？
发现现在好多公司出老题
原字串：
春节快乐喜气羊羊羊年大吉
编码为：
春节快乐喜气3x羊年大吉
这个一两年前也好像也见到过，aabccc －》 a2bc3
赞面经 |
|
|
|
x******8
发帖数: 48 | 43 根据mitkook2大神的代码改了一下，思路是一致的，大家参考一下
// O(n*k) time, O(n) space
boolean alibaba(int numCaves, int[] strategy) {
// survival[i] means theft can be in spot i or not on this day
boolean survival[] = new boolean[n + 2];
// init the first day
// 在头尾加一个房间，且小偷不可能出现在这两个房间（为了处理下面j - 1
和j + 1越界的情况）
Arrays.fill(survival, true);
survival[0] = false;
survival[n + 1] = false;
survival[strategy[0]] = false;
for (int i ... 阅读全帖 |
|
s****3
发帖数: 270 | 44 Word abbreviation 需要有rule吗还是就是剩头尾? |
|
h**p
发帖数: 211 | 45 上面有人说了，总结下2种方法（需要建立有向图）
#1 recursion + back track
设一个set来存所有的edge，走过的就删掉
base case 是当edge为空，此时又刚好到达终点
另一个是当edge为空，此时到达不了终点，或者当前点无路可走。然后返回上一步，换
一条路径
#2 permutation，permute所有线段，然后走一遍检测。优化条件是每段线的头尾是否
是相连 |
|
t**r
发帖数: 3428 | 46 哈哈
矩阵多简单，index搞搞 还是比哪个link来link去容易多了。
一个循环 link折腾四次 也是晕晕的。还要考虑空指针 和头尾结点的corner cases.
一次写bug free简直是梦。 |
|
l*****a
发帖数: 14598 | 47 如果转成list的话,一个就够了
头尾两个index,swap string only and skip symbols |
|
s****3
发帖数: 270 | 48 kmp 要怎么解阿? 第一题是随处都可加character 还是只能加在头尾? |
|
e****e
发帖数: 1885 | 49 众位看官，且听我一原创故事 by ertrue
话说很近很近以前，东胜神州崇山峻岭之间诞生一小马农，听风便长，闻水即壮，几年
间便修的身体强健，耳聪目明。一日，忽闻一则消息，说西方西牛贺州出了一大国，刚
刚攻克宇宙难题之“围棋精要”，该国动则呼风唤雨，静则万众敬仰。此马工随心向往
之，潜心修行许久，后方出关，自名曰“行者”，携娟秀彩云投名状，打算往西前行，
妄图攀上该国之仙福，共享该国之富贵。
长话短说，却道日月潜行，道路迢迢。这好行者，虽前途艰险、却不畏强难，虽关隘重
重、却一心一意，虽万水千山、却勇往直前。威威乎似山中之猛虎下山，凛凛兮若盘云
之巨蟒吞日，行如云长之千里单骑，动若悟空之万里取经。这行者一路上过关斩将、披
坚执锐，所到之处无不偃旗息鼓、望风而降。一路通行无碍，所遇关卡兵隘一一投降。
有诗为证：
东方神州出马农
一心向西定从容
到得西方真经处
无畏艰险为繁荣
话说，行者一人独自披荆斩棘，路途行至十九，眼见就要到达真经所在，西方大国卧佛
之处，却不巧踏上本地天竺国境内。原来这西牛大国原本不在天竺之中，怎奈天竺人本
就在西方，所谓近水楼台先得月，久而久之竟也把诺大个国家划入... 阅读全帖 |
|
k******a
发帖数: 44 | 50 第5题可以这样做吧？
把数组分为4段，那个5个端点为1，2，3，4，5.
先判断1-2，2-3，3-4，4-5是否头尾为同一数字，如果是那么就是答案
如果不是，那么答案为2，3，或者4的点。分别从2，3，4开始向左右进行二分查找，找
边界。找到边界后，总体长度大于25%的就是答案。 |
|
