狗家跪经（题真的巨简单跪的也莫名其妙

刚收到了hr的电话告诉我面试官的feedback是不moveon
面的内容真的非常简单。以下是面试过程。
面试官寒暄很多分钟 然后面试官让我打开doc给题。
一堆灯泡，有两个function一个叫做isOn一个叫做Toggle（start， end)对这个range里面的灯泡状态切换。
让我implement两个function。到这里我是惊呆状态，我之前的心理准备是至少medium hard也非常有可能。结果我感觉可能出了个easy-水平的。
然后我就说最基本的想法建一个list

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我在过程中基本没有浪费一分一秒。感觉他也对我的每个结果表示满意。
感觉地里都是莫名其妙就过了的，我是莫名其妙就挂了的。hr也不想给任何feedback，被冻了一年。
虽然难过的哭了一下午，但还是不得不move on。今年的FLAG面试以各种狗血结局收场。

复盘楼主的面试过程，其实跪的并不是那么莫名其妙。（以下假设toggle的操作次数为m，isOn的操作次数是n）

1.这个面试官很鸡贼，出的第一题就是一个区分度很强的题目。这种题目往往看似简单，但套路很深。经验不丰富的coder很容易直接给出暴力解法，这样就会给面试官一个很negative的印象。

2.面试官发现你把这个问题想得太简单的时候，给过一个hint：“需要操作的灯泡数量很少怎么办？”，就是暗示你要考虑到时间空间复杂度。很显然这个hint是让你用位运算来做，因为这样的时空复杂度是最优的（时间 o(m+n))。如果这时候能根据不同计算机的字长（32位？64位？）来回答，肯定是加分项。

3.然后面试官发现你还是没明白他想要考你什么，就非常直白的告诉你，“现在你这个time complexity不太好”，然而你接下来回答的方法的时间复杂度是 o(n*m)。。。

4.最后面试官问你“call很少几次toggle但是call很多次isOn”，意思就是想让你把isOn 操作的时间复杂度降到最低。如果内存足够的的时候，时间复杂度就是o(1)；如果内存不够用，时间复杂度是o(logm)。

从中可以总结两个tips：
1.虽然算法题很重要，但绝不简单的等同于智力题。因为，在实际情况中，用什么样的算法很大程度上取决于具体的应用场景（比如这道题里的各种follow up）和实际的硬件条件（比如，字长是多少？内存够不够？）。所以，熟练掌握计算机相关的基础知识也很重要。面试官往往都是实际经验很丰富的工程师，如果能结合实际情况来答算法题，给面试官的印象肯定要加分不少。

2.对于这种看似简单但套路很深的题目，一定不要上来就给暴力解，这样会正中面试官的下怀。应该直接把题目里隐藏的套路点出来，才能让面试官开心。

kuankuan_umich 发表于 2017-10-24 11:53
楼主，我觉得面试官应该是想要bit解法，而且还应该会有一个follow up问你如果说灯泡数大于32的话怎么存储。 ...

层主，我想你不太懂的是，bit=binary index tree 而不是bit manipulation。而且面试官让我处理的是几千几万的数据量不是32这种很小很小的数据量。层主麻烦下次搞清楚再judge吧。

Indexed Tree解法：https://www.careercup.com/question?id=5668664122540032
Bit解法：http://massivetechinterview.blogspot.com/2015/08/0-toggle-bulbs.html

Bit还行，Indexed Tree的解法想的出来也来不及写完啊，按理说lz应该能进onsite的应该是最近变难了。

拍拍. 面试都是看缘分~

面试官可能是想要Binary Index Tree的那个解法

cuijinxxx 发表于 2017-10-24 05:43
面试官可能是想要Binary Index Tree的那个解法

对 但是每一步的优化都是他给的提示和进一步要求。比如第二问是让我优化一点点。第三问是问我toggle次数少的话能不能存和toggle一样的空间。我后来也想到可能是BIT。

我也面了个据简单的……心虚啊，真是怕挂

论坛匿名用户 发表于 2017-10-24 05:46
对 但是每一步的优化都是他给的提示和进一步要求。比如第二问是让我优化一点点。第三问是问我toggle次数 ...

有可能是面试官故意带偏了节奏，楼组别灰心，继续加油。现在google bar很高，没办法。

cuijinxxx 发表于 2017-10-24 05:43
面试官可能是想要Binary Index Tree的那个解法

用bit怎么做呢？ 求详解

clould365 发表于 2017-10-24 05:56
用bit怎么做呢？ 求详解

google一下～有个geekforgeeks的例子就是差不多的。

想问下lz是哪天面的诶～

zns1204zns 发表于 2017-10-24 06:08
想问下lz是哪天面的诶～

10. 18 zishuzishuzishu