Palantir onsite面经

zhuang1992 发表于 2015-3-15 04:40
跟我想的一样。。只需要记录三个数字应该可以算是Constant了吧。

如果只记住三个数字确实是constant，可是调整数字的时候要查前面读入的数字，我觉得可能就不太算了吧。
你觉得呢？ 欢迎讨论哈。

lwt1104 发表于 2015-3-15 10:58
如果只记住三个数字确实是constant，可是调整数字的时候要查前面读入的数字，我觉得可能就不太算了吧。
...

嗯也有道理。如果是个输入流的话，要记住之前的数字还是需要额外空间的。
但是我之前看到的题稍微有点不同，它给的是一个数组，让计算从头到第i个数的median，这样就不需要额外空间了。
还有除了要考虑比较与上个median的大小，还需要考虑目前已经有了奇数个还是偶数个数字。
我在这里贴了代码。欢迎讨论。
http://www.1point3acres.com/bbs/ ... p;page=1#pid1753652

lwt1104 发表于 2015-3-14 21:56
第三题我觉得你说的是对的。当时我想到的方法是记住三个数（median, median 左边和右边的数），那个人没 ...

如果是NXM的board，复杂度就是O(MN), 对每一个位置，交换周围neighbor（最多4个），check有木有三连?
面试官是不是要想优化下，比如一行都没有两个相同的，那这一行怎么换都换不出三联了

shawlin 发表于 2015-3-15 11:35
如果是NXM的board，复杂度就是O(MN), 对每一个位置，交换周围neighbor（最多4个），check有木有三连?
面 ...

是啊，应该是有 更好的办法的。我当时的优化就只给出了一个交换相同颜色棋子就不用check了这一项。

lwt1104 发表于 2015-3-15 10:56
第三题我觉得你说的是对的。当时我想到的方法是记住三个数（median, median 左边和右边的数），那个人没 ...

想请问下楼主，这个第一题是求的所有能交换得到三个一样的坐标集，是每个交换事件是相互独立的吗？
我想了想好像做下来的O(N^2)啊，要优化貌似感觉也是在nested loop内部优化了。楼主有啥子优化的方法不。

大饭团 发表于 2015-3-16 11:21
想请问下楼主，这个第一题是求的所有能交换得到三个一样的坐标集，是每个交换事件是相互独立的吗？
我想 ...

交换事件是相互独立的，要求返回所有的坐标pair（两个点进行交换）
我感觉这个题本质是o(n2)是改不了的。可能有高手可以写的时间系数小一点把。
我当时没有给出什么特别的优化，因为时间有限嘛。就写了个如果两个交换的棋子是一样的值，就不用check了。

lwt1104 发表于 2015-3-16 12:24
交换事件是相互独立的，要求返回所有的坐标pair（两个点进行交换）
我感觉这个题本质是o(n2)是改不了的 ...

多谢楼主啦！表示楼主还是很牛的！！

感觉第三题为什么要keep 3个参数呢？感觉记住当前median就可以做了？
如果知道了当前的median，那么如果新增一个元素，假如当前数组长度为奇数，意味着median平分当前数组，如果新增的数大于median，那么median不变，因为偶数长度的话默认median把数组分成右边比左边多一个的情况。如果新增的数小于median，意味着按照当前median的分法，左边会比右边多一个，则搜索数组，得到比median小的最大值作为新的median.

假如当前数组长度为偶数，意味着median将数组分成右边比左边多一个的情况，如果新增的数大于median，那么搜索数组，把比median大的数的最小值作为新的median，如果新增数小于median，则median不变。

多谢楼主！祝楼主早日拿到offer！！

mayijie88 发表于 2015-6-7 06:25
感觉第三题为什么要keep 3个参数呢？感觉记住当前median就可以做了？
如果知道了当前的median，那么如果新 ...

好久没来了，我同意你的观点。反正都是O(n)。我现在想想，如果记录三个参数，小于median和大于median的那两个参数offline调整，这样时间复杂度算不算变相的O(1)了。就是说每新来一个数，先把median返回了，再offline的调整另外两个参数。