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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 答的挺好的呀! 不用担心, bless!
|
r********7 发帖数: 102 | 4 第一题,有没有问你Arrays.sort()的时间复杂度? 那个方法的时间复杂度我一直不清
楚。。
对了,这个是java的function 不知道C++有木有。
leetcode
【在 s********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉各种不顺,本来是约在了昨天,然后面试官忘了就约在今天,然后又迟到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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题,有没有问你Arrays.sort()的时间复杂度? 那个方法的时间复杂度我一直不清 : 楚。。 : 对了,这个是java的function 不知道C++有木有。 : : leetcode
|
l********7 发帖数: 40 | 7 我记得Java里的Arrays.sort()同时实现了quicksort和mergesort,如果是primitive
type就用quicksort,如果是对象就用mergesort,所以应该是nlogn
【在 r********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题,有没有问你Arrays.sort()的时间复杂度? 那个方法的时间复杂度我一直不清 : 楚。。 : 对了,这个是java的function 不知道C++有木有。 : : leetcode
|
s********u 发帖数: 1109 | 8 是因为对象的swap成本可能比较高?
【在 l********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我记得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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : feedback一下,这一轮过了,拿到onsite,所以也不是烙印个个刁难么。我google, : apple刁难的面试官都是白人。
|
s********u 发帖数: 1109 | 11 推荐搜索 lru cache + linkedlist,这个题其实cc150有
java可以再看看linkedhashmap
【在 m**********4 的大作中提到】![](/moin_static193/solenoid/img/up.png) : LZ说的最近版上讨论的那个关于LRU的问题在哪里啊?能不能给个联结
|