p*******l
发帖数: 67 | 1 刚刚linkedin的电话面试完毕，题目很简单，主要是coding了（用的是collabedit）
1.int Fibonacci(int n)。我居然一开始给了n阶乘的实现><不知道自己怎么想的......
2.interviewer给了个interface，其中有两个method要实现，自定义数据结构。
1）int store(int n)； //把n保存到你的数据结构里面去
2) boolean twoSum(int sum)；就是经典的给一个magic number sum，看是否存在
两个数之和等于这个sum。
我开始给了个O(1)的store和O(n)的twoSum。之后interviewer问如果store用到的不多
，但是twoSum会被频繁的用到，该怎样实现。想了会儿就给了个O(n)的store和O(1)的
twoSum的实现。
平时IDE用惯了，编程的时候出了好些不应该的错误，比如我居然会写ArrayList<
Integer, Integer>这样子的定义，sigh。interviewer看似对我的solution很满意，但
是犯了好些低级错误，估计会挂了吧。待会躲到角落去哭。这个帖子写出来主要是给自
己总结一下。 | r*******y
发帖数: 1081 | 2 bless
...
【在 p*******l 的大作中提到】
: 刚刚linkedin的电话面试完毕，题目很简单，主要是coding了（用的是collabedit）
: 1.int Fibonacci(int n)。我居然一开始给了n阶乘的实现><不知道自己怎么想的......
: 2.interviewer给了个interface，其中有两个method要实现，自定义数据结构。
: 1）int store(int n)； //把n保存到你的数据结构里面去
: 2) boolean twoSum(int sum)；就是经典的给一个magic number sum，看是否存在
: 两个数之和等于这个sum。
: 我开始给了个O(1)的store和O(n)的twoSum。之后interviewer问如果store用到的不多
: ，但是twoSum会被频繁的用到，该怎样实现。想了会儿就给了个O(n)的store和O(1)的
: twoSum的实现。
: 平时IDE用惯了，编程的时候出了好些不应该的错误，比如我居然会写ArrayList<
| a********m
发帖数: 15480 | 3 bless!
O(1)的store和O(n)的twoSum咋做的？ | c********1
发帖数: 161 | 4
O（1） twoSum的方法：
建一个hash table，里面存所有可能的twoSum的值为Key，每store一个num时就update
这张hash table就好了。
O（N） twoSum的方法：
同样建hashtable 每当store一个num就push这个num为hashtable的key， freqency就是相对
应的value，当check twoSum是，只要traverse这张hashtable一次就OK了。
题目不难，可能就看编程水平吧，bless。
【在 a********m 的大作中提到】
: bless!
: O(1)的store和O(n)的twoSum咋做的？
| c***c
发帖数: 22 | | P**********c
发帖数: 3417 | 6 第一个方法，存的是twoSum的话，store一个num怎么update这张hash table呢？如何找到原来的数去跟新的num相加？
需要另存原数吗？
update
是相对
【在 c********1 的大作中提到】
:
: O（1） twoSum的方法：
: 建一个hash table，里面存所有可能的twoSum的值为Key，每store一个num时就update
: 这张hash table就好了。
: O（N） twoSum的方法：
: 同样建hashtable 每当store一个num就push这个num为hashtable的key， freqency就是相对
: 应的value，当check twoSum是，只要traverse这张hashtable一次就OK了。
: 题目不难，可能就看编程水平吧，bless。
| c********1
发帖数: 161 | 7 每store一个数n，就用n和每个已经存在数据结构中的数字想家求和，将这个和作为key
插入hashtable中，比如首先是empty，依次存入以下数，相对应的hashtable的key：
insert 2 -> ht: empty,
insert 3 -> ht: 5 (2+3)
insert 10 -> ht: 5, 12(2+10), 13(3+10)
insert 1 -> ht: 5, 12, 13, 3, 4, 11
insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
insert .......
这样store的代价很高，但是twoSum却很容易了。 | P**********c
发帖数: 3417 | 8 所以你还是需知道之前是什么数，不能只存sum, 是么？你的数据结构包括一个以sum为key的hash table，和一个存原数的array。另外这个只能找到sum是否存在，不能找到相加等于sum的pair, 当然如果想找pair也可以一并把pair存进去。
key
【在 c********1 的大作中提到】
: 每store一个数n，就用n和每个已经存在数据结构中的数字想家求和，将这个和作为key
: 插入hashtable中，比如首先是empty，依次存入以下数，相对应的hashtable的key：
: insert 2 -> ht: empty,
: insert 3 -> ht: 5 (2+3)
: insert 10 -> ht: 5, 12(2+10), 13(3+10)
: insert 1 -> ht: 5, 12, 13, 3, 4, 11
: insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
: insert .......
: 这样store的代价很高，但是twoSum却很容易了。
| y*r
发帖数: 590 | 9 问个实际问题。
具体给面试官写程序的时候hashtable具体是用什么数据结构怎么实现的?
update
是相对
【在 c********1 的大作中提到】
: 每store一个数n，就用n和每个已经存在数据结构中的数字想家求和，将这个和作为key
: 插入hashtable中，比如首先是empty，依次存入以下数，相对应的hashtable的key：
: insert 2 -> ht: empty,
: insert 3 -> ht: 5 (2+3)
: insert 10 -> ht: 5, 12(2+10), 13(3+10)
: insert 1 -> ht: 5, 12, 13, 3, 4, 11
: insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
: insert .......
: 这样store的代价很高，但是twoSum却很容易了。
| b*******8
发帖数: 37364 | 10 用Java的Hashtable吧。
【在 y*r 的大作中提到】
: 问个实际问题。
: 具体给面试官写程序的时候hashtable具体是用什么数据结构怎么实现的?
:
: update
: 是相对
| | | h**********8
发帖数: 267 | | y*r
发帖数: 590 | 12 如果c呢？
【在 b*******8 的大作中提到】
: 用Java的Hashtable吧。
| a********r
发帖数: 857 | | s**********e
发帖数: 326 | 14 同问
【在 y*r 的大作中提到】
: 如果c呢？
| b*******8
发帖数: 37364 | 15 还是用C++的STL吧。C不知道。
【在 y*r 的大作中提到】
: 如果c呢？
| p*******l
发帖数: 67 | 16 I am sorry I cant type Chinese at the moment.
I was using Java during the interview. They don't really care which language
you want to use. For the O(1)/O(n) solution, I used HashMap. For the O(n)/O
(1) solution, I used HashMap as well, but actually, HashSet would be good
enough.
Thanks a lot for the bless. You guys are sweet <3 I got the onsite
invitation two days after the phone interview. Didn't get time to update the
post here. I will update my onsite experience once it's done :) | b***r
发帖数: 4186 | 17 没看懂第二个方法，给我解释一下吧
update
是相对
【在 c********1 的大作中提到】
: 每store一个数n，就用n和每个已经存在数据结构中的数字想家求和，将这个和作为key
: 插入hashtable中，比如首先是empty，依次存入以下数，相对应的hashtable的key：
: insert 2 -> ht: empty,
: insert 3 -> ht: 5 (2+3)
: insert 10 -> ht: 5, 12(2+10), 13(3+10)
: insert 1 -> ht: 5, 12, 13, 3, 4, 11
: insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
: insert .......
: 这样store的代价很高，但是twoSum却很容易了。
| y*r
发帖数: 590 | 18 hehe, 有下文吗？期待onsite面经:)
language
/O
the
【在 p*******l 的大作中提到】
: I am sorry I cant type Chinese at the moment.
: I was using Java during the interview. They don't really care which language
: you want to use. For the O(1)/O(n) solution, I used HashMap. For the O(n)/O
: (1) solution, I used HashMap as well, but actually, HashSet would be good
: enough.
: Thanks a lot for the bless. You guys are sweet <3 I got the onsite
: invitation two days after the phone interview. Didn't get time to update the
: post here. I will update my onsite experience once it's done :)
| i******w
发帖数: 214 | 19 第二个方法直接要个hashtable就可以了， 自己的数据结构没太大必要了
update
是相对
【在 c********1 的大作中提到】
: 每store一个数n，就用n和每个已经存在数据结构中的数字想家求和，将这个和作为key
: 插入hashtable中，比如首先是empty，依次存入以下数，相对应的hashtable的key：
: insert 2 -> ht: empty,
: insert 3 -> ht: 5 (2+3)
: insert 10 -> ht: 5, 12(2+10), 13(3+10)
: insert 1 -> ht: 5, 12, 13, 3, 4, 11
: insert 7 -> ht: 5, 12, 13, 3, 4, 11, 9, 10, 17, 8
: insert .......
: 这样store的代价很高，但是twoSum却很容易了。
| y*******g
发帖数: 6599 | 20 祝福，
...
【在 p*******l 的大作中提到】
: 刚刚linkedin的电话面试完毕，题目很简单，主要是coding了（用的是collabedit）
: 1.int Fibonacci(int n)。我居然一开始给了n阶乘的实现><不知道自己怎么想的......
: 2.interviewer给了个interface，其中有两个method要实现，自定义数据结构。
: 1）int store(int n)； //把n保存到你的数据结构里面去
: 2) boolean twoSum(int sum)；就是经典的给一个magic number sum，看是否存在
: 两个数之和等于这个sum。
: 我开始给了个O(1)的store和O(n)的twoSum。之后interviewer问如果store用到的不多
: ，但是twoSum会被频繁的用到，该怎样实现。想了会儿就给了个O(n)的store和O(1)的
: twoSum的实现。
: 平时IDE用惯了，编程的时候出了好些不应该的错误，比如我居然会写ArrayList<
| h*********n
发帖数: 915 | 21 interviewer看似对我的solution很满意，但是犯了好些低级错误，估计会挂了吧。待
会躲到角落去哭。
自相矛盾啊。
...
【在 p*******l 的大作中提到】
: 刚刚linkedin的电话面试完毕，题目很简单，主要是coding了（用的是collabedit）
: 1.int Fibonacci(int n)。我居然一开始给了n阶乘的实现><不知道自己怎么想的......
: 2.interviewer给了个interface，其中有两个method要实现，自定义数据结构。
: 1）int store(int n)； //把n保存到你的数据结构里面去
: 2) boolean twoSum(int sum)；就是经典的给一个magic number sum，看是否存在
: 两个数之和等于这个sum。
: 我开始给了个O(1)的store和O(n)的twoSum。之后interviewer问如果store用到的不多
: ，但是twoSum会被频繁的用到，该怎样实现。想了会儿就给了个O(n)的store和O(1)的
: twoSum的实现。
: 平时IDE用惯了，编程的时候出了好些不应该的错误，比如我居然会写ArrayList<
| j********x
发帖数: 2330 | |
|
