t*******2
发帖数: 182 | 1 一老印，电面迟到15分钟，打过来也不花两分钟介绍一下team之类的，直接上题。。
1) Can you explain dependency injection with an example, in java.
我一下子懵了，听都没听说过这个东西，什么也扯不出来，只好老实承认没听说过。。
事后google了一下，好像是Spring framework里面的一个概念。。
2) Can you create memory leak with a sample program.
也是完全没准备过，想了两分钟想不出什么来，老印直接开始问下题
3) What do you think is the output of this sample program
public class MyThread implements Runnable {
String myString = "Yes ";
public void run() {
this.myString = "No ";
}
public static void main(String[] args) {
MyThread t ... 阅读全帖 |
|
|
p*****2
发帖数: 21240 | 3 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 4 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
l*n
发帖数: 529 | 5 quora上有个解法，是用hashmap+array。hashmap的amortized O(1)应该能接受吧？莫
非c++的map单指treemap？ |
|
l********y
发帖数: 23 | 6 C++ map 类似treemap unordered_map 是hashtable |
|
z*******3
发帖数: 13709 | 7 楼主说的min heap是data structure里面的min heap
data structure里面所谓的min heap有特殊的定义，min指的是root
但是面试官说的max heap意思是max value的heap（包括min&max heap)
max说的是values，而不是root
严格说来，是max values的min heap
我神经快错乱了
这种题目其实深入下去很恶心，红黑树就在后面，如果说treemap的，要小心点
http://my.oschina.net/leejun2005/blog/135085 |
|
z*******3
发帖数: 13709 | 8 看别人博客上说
楼主用的min heap其实就是treemap的方式
其开销要大于priorityqueue |
|
z*******3
发帖数: 13709 | 9 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
z*******3
发帖数: 13709 | 10 楼主说的min heap是data structure里面的min heap
data structure里面所谓的min heap有特殊的定义，min指的是root
但是面试官说的max heap意思是max value的heap（包括min&max heap)
max说的是values，而不是root
严格说来，是max values的min heap
我神经快错乱了
这种题目其实深入下去很恶心，红黑树就在后面，如果说treemap的，要小心点
http://my.oschina.net/leejun2005/blog/135085 |
|
z*******3
发帖数: 13709 | 11 看别人博客上说
楼主用的min heap其实就是treemap的方式
其开销要大于priorityqueue |
|
z*******3
发帖数: 13709 | 12 对比一下queue和heap的效率哈
queue的删除很简单，尤其是删除头尾，对内部结构完全没有影响
heap的删除root之后，要heapify，这个开销很大
插入
两个都是lgn，所以queue可以省掉heapify这一个步骤
看hadoop什么都是用priorityqueue，而不是treemap
所以这题貌似heap并不是最优解，只是一个相对简单的解法
看来swjtuer是对的 |
|
m*******s
发帖数: 23 | 13 一个字符串由a到z的字符组成。
按字符出现的频率由高到低输出各个字符和字符的频率，
如果频率相等则按字母表顺序输出。
我用了HashMap统计字符频率然后用TreeMap排序能得到正确结果。
不知道有没有更简介的java解答？ |
|
m*****k
发帖数: 731 | 14 那就再加个map存中间结果不就dp了么。
public static BigInteger reach(char start, char end, int steps) {
Map keyboard = new TreeMap<>();
Map pathsMap = new HashMap<>();
keyboard.put('1', new int[] { 0, 0 });
keyboard.put('2', new int[] { 0, 1 });
keyboard.put('3', new int[] { 0, 2 });
keyboard.put('4', new int[] { 1, 0 });
keyboard.put('5', new int[] { 1, 1 });
keyboard.put('6', new int[] { 1, 2 });
keybo... 阅读全帖 |
|
|
z****e
发帖数: 54598 | 16 java吧
其它语言hashtable比较多
java里面对比hashmap vs treemap
你google一下，可以看到很多 |
|
z****e
发帖数: 54598 | 17 tree是一种结构
hashcode是另外一种结构
java常见两个对比
hashmap vs treemap，这个是结构的不同，索引方式的不同
hashmap vs hashtable，这个是并发差异，结构是类似的 |
|
w**********o
发帖数: 140 | 18 Java裡面的TreeMap
就是一個Red Black Tree的實現.
Rollback可以用Command(design pattern)實現. |
|
c*****m
发帖数: 271 | 19 treemap和generics都是第一次听说。像我这种情况，面试过程中面试官会解释这两个
概念么？还是直接pass了。。。 |
|
e***a
发帖数: 1661 | 20 use a red-black tree to implement TreeMap? too hard! |
|
y*****e
发帖数: 712 | 21 lz, 当把每个sequence都放到hashmap里后怎么sort才能达到O(n）啊，难道要用
treeMap? |
|
|
|
f********a
发帖数: 367 | 24 这个TreeMap怎么弄啊？ key是timestamp？ Object就是{totalLen， count}？ |
|
f********a
发帖数: 367 | 25 en, copy paste错了
那原题和那个REST server差不多， 我觉得。 你觉得怎么解呢？ 这个treemap的怎么
弄？ key就是timestamp么？ |
|
b******n
发帖数: 851 | 26 void helper (TreeNode node, TreeMap m, int level) {
List nodesAtThisLevel = m.get(level);
if (nodesAtThisLevel == null) ...
nodesAtThisLevel.add(node);
helper(node.left, m, level-1);
helper(node.right, m, level+1);
} |
|
w******e
发帖数: 3 | 27 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定 |
|
b******n
发帖数: 851 | 28 void helper (TreeNode node, TreeMap m, int level) {
List nodesAtThisLevel = m.get(level);
if (nodesAtThisLevel == null) ...
nodesAtThisLevel.add(node);
helper(node.left, m, level-1);
helper(node.right, m, level+1);
} |
|
w******e
发帖数: 3 | 29 只是不能用hashmap? 可以用treemap吗？如果可以，BFS一次pass搞定 |
|
r*******h
发帖数: 315 | 30 treemap是bst，一样O(lgn)的插入，所以还是O(nlogn)
我倒是想到了一点优化，因为n很大的时候算power会overflow，所以一个做法是取对数
，这样就变成了k*log2 vs. k*log3 vs. k*log5，因为log保持了单调递增，所以就好
处理多了。 |
|
s******7
发帖数: 1758 | 31 treemap从头到尾只有三个元素（3个篮子），是lg3常数，那里需要lgn的插入 |
|
|
b*****n
发帖数: 618 | 33 设计题比较open，不是很清楚需求到底是啥，听起来像是设计一个足够general的cache
framework。
算法题第一道不能做任何precomputation么？那样的话只能想到用trie暴力搜了。
第二道是hashmap + binary search？或者hashmap + treemap，假设所有data都在
memory里面。 |
|
c******n
发帖数: 4965 | 34 treeset/ treemap 这种数据结构平时很少用， 这个题显示它的作用 |
|
c******n
发帖数: 4965 | 35 常见的那个LRU cache 用 treemap 做要比自己写双链表简单多了 |
|
o*******y
发帖数: 362 | 36 Linkedlist就是双链表啊
[在 creation (努力自由泳50m/45sec !) 的大作中提到：]
：常见的那个LRU cache 用 treemap 做要比自己写双链表简单多了 |
|
w**z
发帖数: 8232 | 37 码了十几年，treemap 才用到过一次。Priory queue 也只用到过一次。 |
|
|
r******l
发帖数: 10760 | 39 brute force的O(nk)的做法会超时。看了几个Java的解法，用到了TreeMap的
ceilingkey/lowerkey或者用到了TreeSet的subset，但是C++没有相应的函数吧？C++的
map的find，如果key不存在没法返回一个最接近的吧？难道非要自己写一个BST不成？ |
|
C*7
发帖数: 234 | 40 snapchat写的LRU，测试没bug，面试官指出head，tail可以初始化为null省点空间，和
public标记的讨论（主要为了测试）。转天据信
zenefits写的Contains Duplicate I，II，III。非常扯淡的是，写II的时候，我写完
先走前指针的loop，后面一个loop刚写了框架，面试官国人＋shadow美国人一起说我第
一个loop条件有问题，暗示我指针多走了一位，我非常纳闷，我说这取决于我第二个
loop怎么操作，他们始终说我写错了，我看了半天也没错，我又重申这取决于我第二个
loop，他们就是不服，擦，我只能举个实例，问他哪有问题，然后俩人闭嘴了，我继续
写第二个，shadow还喋喋不休说一会看吧，还有个小错误，草。写完俩人开始自圆其说
“哦，原来你第二个loop这么走啊”，我都说几遍了。然后测试，各
种case他们改来改去，就想找出bug，可惜让他们失望了。
接着写III，我说用TreeMap，但之前没用过，说能不能查一下java doc，他说可以，我
就查了下写了。指出个问题，改了下，然后又陷入争论，shadow这时支持我写的没错，
面试官觉... 阅读全帖 |
|
j*****8
发帖数: 3635 | 41 明白了。java的话，value 用 treemap存 就行了
多谢楼上各位大侠！ |
|
s******4
发帖数: 24 | 42 Phone（烙印）
1. a lot questions about database sharding/partitioning
2. merge 2 linkedin list(lc 原题 已经问烂了)
onsite(4烙印＋1白人)
1. write producer/consumer for multi-threading environment(discussed
condition variable / synchronized), 建议看Java Condition API
2. find k-th largest element in unsorted array(lc 原题 已经问烂了)
3. 还有一个lc原题不记得了 也是很简单的
4. 在一个迷宫里，假设有一个机器人，怎么保证能走到出口。这个不画图比较难描述
。和一般bfs,dfs的区别就是，机器人只记得自己做过的决定（Left->Left->Straight
类似这样），没有整个图的概念。就想想一下自己在走迷宫好了。答案就是，一直往左
走，走到尽头就往回，没有左就往前走，没有前就往右走。然后会有一些followu... 阅读全帖 |
|
f*******r
发帖数: 976 | 43 祝LZ早日拿到大offer，eBay，PayPal等都是烙印的老巢，不去也罢
Phone（烙印）
1. a lot questions about database sharding/partitioning
2. merge 2 linkedin list(lc 原题 已经问烂了)
onsite(4烙印＋1白人)
1. write producer/consumer for multi-threading environment(discussed
condition variable / synchronized), 建议看Java Condition API
2. find k-th largest element in unsorted array(lc 原题 已经问烂了)
3. 还有一个lc原题不记得了 也是很简单的
4. 在一个迷宫里，假设有一个机器人，怎么保证能走到出口。这个不画图比较难描述
。和一般bfs,dfs的区别就是，机器人只记得自己做过的决定（Left->Left->Straight
类似这样），没有整个图的概念。就想想一下自己在走迷宫好了。答案就是，一直往左... 阅读全帖 |
|
z****e
发帖数: 54598 | 44 map也有很多种啊
不是所有的map都是hashmap那样amortised constant复杂度
比如treemap效率就比较低
switch的话，应该是写起来方便一点
而且这里几十种情况的话，建议你用上visitor
直接把这个switch去掉，还有古德霸说过那个反射的用法
也可以干掉switch
另外加上enum，有限数量的东西全部应该用enum
class是给无限数量用的 |
|
l*******e
发帖数: 127 | 45 写了一下第三题，基本思路是类似于sweep-line算法，用一个max heap保持当前权重最
高的alarm，按照时间顺序扫描， 碰到alarm start event, add alarm to the heap,
for alarm end event,
remove the alarm from the heap. keep track the top of the heap, which
should be kept.
public class WeightedInterval {
public List removeAlarms(List alarms)
{
SortedMap> times = new TreeMap<>();
for(Alarm alarm : alarms)
{
if(!times.containsKey(alarm.start)) times.put(alarm.start, new
Array... 阅读全帖 |
|
k****r
发帖数: 807 | 46 版上好心人帮忙内荐的，在这里表示感谢。
店面：
sudoku solver。
昂塞：4轮
1.1 anagrams，秒了。
1.2 input String“[email protected]
/* */..[email protected]
/* */^^^2134nn..uber@
hello.edu.cn”
output 返回所有合理的address。java写到后来没写完，但是思路被认可。
2. input(String[] str1, String[] str2) 返回match str2里任一个的所有str1中的
元素（白板）。比如说str2是“hiw”，“abc”； str1是“hiw2”，“3hiw”， “
def”，“abc1”，应该返回“hiw2”，“3hiw”，“abc1”。这题交流不顺畅，写出
来一种方法，他看半天不懂，解释了半天，他似懂非懂，又说我的方法不efficient，
最后我似乎明白他要考啥，我说了一个treemap来解决的办法，他说ok，没时间再写
code了，也不知道是不是真的ok。
3. 聊messaging sy... 阅读全帖 |
|
f*******r
发帖数: 976 | 47 Move on.
店面：
sudoku solver。
昂塞：4轮
1.1 anagrams，秒了。
1.2 input String“[email protected]
/* */..[email protected]
/* */^^^2134nn..uber@
hello.edu.cn” output 返回所有合理的address。java写到后来没写完，但是思路被
认可。
2. input(String[] str1, String[] str2) 返回match str2里任一个的所有str1中的
元素（白板）。比如说str2是“hiw”，“abc”； str1是“hiw2”，“3hiw”， “
def”，“abc1”，应该返回“hiw2”，“3hiw”，“abc1”。这题交流不顺畅，写出
来一种方法，他看半天不懂，解释了半天，他似懂非懂，又说我的方法不efficient，
最后我似乎明白他要考啥，我说了一个treemap来解决的办法，他说ok，没时间再写
code了，也不知道是不是真的ok。
3. 聊messaging system，聊背景。考了个a... 阅读全帖 |
|
b*****n
发帖数: 618 | 48 如果是求最长的subarray的话，用TreeMap可以O(nlogn)，
谨慎地认为没有更好的解了。。 |
|
z*********n
发帖数: 1451 | 49
内存能存下的话，这题不就是找两数组中和为1000的对数，太trivial了
存不下的话，你怎么分段？你把A的头1/10存到一个hashmap里然后把B扫一遍，然后再
把第二个1/10存hashmap里，把B再扫一遍？总共扫10遍？你确定这个比排序然后各过一
遍高效？
而且大数据处理的一个common的经验就是，数据越大，排序效率比Hashmap/Treemap的
效率越高。即使遍数接近，排序一般也会更高效。 |
|
l****r
发帖数: 119 | 50 EE火坑方向的fresh PhD，昨天去google onsite面试码工职位。感觉面试题不比
leetcode难，但没有leetcode原题，据说google内部有一个网上出现过的不能用的题库
，很大。所以leetcode只是锻炼思路。面试题全都答出来了，能录取么？
经验是基础要搞好，比如，我把java.util.*包里面的类都看了一遍，面试就用上了，
挺有用的。包括:
Collections.sort()
TreeMap
等
另外，Map的用法：Map() 一位面试官问我为什么要用Integer而不
是int。可能这个问题能问住一些速成的。当然我也是转行的 |
|
