s********u
发帖数: 1109 | 1 感觉各种不顺，本来是约在了昨天，然后面试官忘了就约在今天，然后又迟到20分钟（
导致做题时间很紧张）。这次这个老印口音是真听不清楚，而且中间手机还莫名重启了
，真是无语。希望老印看
在他两次爽约的份上，放我一马。
0.先问了简历，还问我说项目都是用C++，会不会其他语言之类
1.Leetcode 3Sum原题。最大的失误是，我居然没有想到切换到旁边打开着的leetcode
窗口！！可能是有点紧张，又记得这题比较简单。然后我就先sort做，结果面试官不知
道这种方法，让我解释了大半天。然后写完了我才发现忘了处理重复的元素，而且有点
忘了怎么处理了。（其实最简单一个set记录tripple不就搞定了！！
阴差阳错，前天把所有做过的leetcode题做了一遍，居然漏了这道？？
最后他问我重复的元素，我又解释说的确是没有处理，然后补充解释了下用hashtable
的方法，说这样就可以避免重复问题了。我估计面试官自己想的是这个方法。不过他好
像觉得我先sort的方法很“新颖”，所以还是说very good。
真是无奈，如果因为这种低级失误没过，真是怨不得别人了。
2.完全听不清楚他说什么，先问我有没有上过操作系统之类，最后才知道就是要设计一
个lru cache。
幸好前两天看了好几次这个，版上也在讨论。不假思索就说了hash table+list。
然后他就问我应该提供哪些函数，还纠正我说他觉得push和update函数应该是private
，不应该是public。然后我就说那就应该friend cpu和操作系统这些，因为他们需要调
用。
最后问了一下我，怎么判断cache的size太小了。我就说node记录一个插入时候的
timestamp，每次removetail的时候，检查当前时间和这个timestamp的差，如果太小了
（说明cache太小没多久就被pop出来）就增大cache。他好像还算满意。。
class Cache{
private:
int max_size;
list m_list;
unordered_map::iterator> table;
void removeTail();
public:
void update(const Data& d);
bool exist(const Data& d) const;
Data get(const int &dataid) const;
}
求bless。希望接下去直接onsite了，印度英语实在吃不消。 |
u*****o
发帖数: 1224 | |
s********u
发帖数: 1109 | 3 谢谢！
【在 u*****o 的大作中提到】
: 答的挺好的呀！ 不用担心， bless!
|
r********7
发帖数: 102 | 4 第一题，有没有问你Arrays.sort()的时间复杂度？ 那个方法的时间复杂度我一直不清
楚。。
对了，这个是java的function 不知道C++有木有。
leetcode
【在 s********u 的大作中提到】
: 感觉各种不顺，本来是约在了昨天，然后面试官忘了就约在今天，然后又迟到20分钟（
: 导致做题时间很紧张）。这次这个老印口音是真听不清楚，而且中间手机还莫名重启了
: ，真是无语。希望老印看
: 在他两次爽约的份上，放我一马。
: 0.先问了简历，还问我说项目都是用C++，会不会其他语言之类
: 1.Leetcode 3Sum原题。最大的失误是，我居然没有想到切换到旁边打开着的leetcode
: 窗口！！可能是有点紧张，又记得这题比较简单。然后我就先sort做，结果面试官不知
: 道这种方法，让我解释了大半天。然后写完了我才发现忘了处理重复的元素，而且有点
: 忘了怎么处理了。（其实最简单一个set记录tripple不就搞定了！！
: 阴差阳错，前天把所有做过的leetcode题做了一遍，居然漏了这道？？
|
J****3
发帖数: 427 | |
s********u
发帖数: 1109 | 6 没有，这个太细节了吧。大不了我用c的qsort，这个总明确了。总之量级肯定是nlogn
。只问了我总的，就是O(n^2)，好像没有更优的了。
就是没跳过重复的，脑子卡住了，悔啊。。
【在 r********7 的大作中提到】
: 第一题，有没有问你Arrays.sort()的时间复杂度？ 那个方法的时间复杂度我一直不清
: 楚。。
: 对了，这个是java的function 不知道C++有木有。
:
: leetcode
|
l********7
发帖数: 40 | 7 我记得Java里的Arrays.sort()同时实现了quicksort和mergesort，如果是primitive
type就用quicksort，如果是对象就用mergesort，所以应该是nlogn
【在 r********7 的大作中提到】
: 第一题，有没有问你Arrays.sort()的时间复杂度？ 那个方法的时间复杂度我一直不清
: 楚。。
: 对了，这个是java的function 不知道C++有木有。
:
: leetcode
|
s********u
发帖数: 1109 | 8 是因为对象的swap成本可能比较高？
【在 l********7 的大作中提到】
: 我记得Java里的Arrays.sort()同时实现了quicksort和mergesort，如果是primitive
: type就用quicksort，如果是对象就用mergesort，所以应该是nlogn
|
s********u
发帖数: 1109 | 9 feedback一下，这一轮过了，拿到onsite，所以也不是烙印个个刁难么。我google，
apple刁难的面试官都是白人。 |
m**********4
发帖数: 774 | 10 LZ说的最近版上讨论的那个关于LRU的问题在哪里啊？能不能给个联结
【在 s********u 的大作中提到】
: feedback一下，这一轮过了，拿到onsite，所以也不是烙印个个刁难么。我google，
: apple刁难的面试官都是白人。
|
s********u
发帖数: 1109 | 11 推荐搜索 lru cache + linkedlist，这个题其实cc150有
java可以再看看linkedhashmap
【在 m**********4 的大作中提到】
: LZ说的最近版上讨论的那个关于LRU的问题在哪里啊？能不能给个联结
|
