This topic has been archived. It cannot be replied.
-
工作学习 / 学科技术 / 一道面试题，大家给出出主意哈，我一点头绪都没有
-unhappy_popular(unhappy_popular);
2016-2-8
{1453}
(#9934209@0)
-
you can practice at topcoder.com and get familiar with this kind of questions
-benbenli(大岭);
2016-2-8
(#9934246@0)
-
谢了，没时间看这些东西啊。
-unhappy_popular(unhappy_popular);
2016-2-8
(#9934275@0)
-
数学题而已。最长答案也就50。一个个试呗。只用加法。从最小的difference开始加。
-kakaka(小胖子);
2016-2-8
(#9934274@0)
+1
-
你这样做面试题，立马废掉
-bbb333(ccc);
2016-2-10
(#9937661@0)
-
1.sort the list. 2. ThenLongest seq must either contain the smallest or not contain the smallest.
a) contains the smallest: use for loop to go thru the rest of the list as the second number, you will get the leap size. Try to use this leap size to test how long the seq can go.
b) doesn't contain the smallest number: use tail recursive to go thru the rest of the list.
Worst time complicity: O(n^3). Average should be close to O(n^2) because the inner loop will end when the first missing number is found.
-iamflying(自食其水果);
2016-2-9
{487}
(#9935295@0)
-
how to tell it contains the smallest or it doesn't contain the smallest?
for example:
list:
{1, 31, 61, 2, 22, 42,62,82, 3, 13, 23,33}
the longest list is 2, 22, 42,62,82, how to tell 1 is not in the list and 2 is in the list.
-sxffff(lookingforjob);
2016-2-10
(#9936821@0)
-
我实现并不需要知道最小数是否在序列中，因为算法会分别对此计算。case a 这个步骤计算最小的数在序列中，返回一个最大值。case b通过递归计算最小的数不在序列中的情况，返回一个最大值。最终结果就是case a, b中最大的数。
-iamflying(自食其水果);
2016-2-10
{147}
(#9936841@0)
-
Java Implementation is here:
-iamflying(自食其水果);
2016-2-10
{908}
(#9937189@0)
+2
-
xiang ni xuexi! !
me green hand in java, glad I'm getting the identical result.
-mustang(mustang);
2016-2-10
(#9937493@0)
-
你的程序最坏是O(n^3)， 平均也是O(n^3). 这个题O(n^2)可以解决。
-juanzhulian(UnlessYouShowMeHow);
2016-2-10
(#9937638@0)
-
Show us how to get O(n^2)
-iamflying(自食其水果);
2016-2-10
(#9937715@0)
-
人多力量大，O(n^2) 写法下面楼主已经给了。
-juanzhulian(UnlessYouShowMeHow);
2016-2-10
(#9938383@0)
-
还有待商榷 (#9938404@0)
-benbenli(大岭);
2016-2-10
(#9938405@0)
-
两重循环内的hashTable.get(diff)的worst case是O(n)。如果换成TreeMap，那就是O(log(n))，那也只能做到(n^2)Log(n)。
-iamflying(自食其水果);
2016-2-10
(#9938487@0)
-
要对java, c#的hash function有信心，In amortized case, hashmap的get()是O(1). 所以这题平均时间复杂度O(n^2).
-juanzhulian(UnlessYouShowMeHow);
2016-2-11
(#9938555@0)
-
他的算法大致是O(n^4)，和hash function没关系。buildHashTable()生成的hash table的尺寸已经是n^2了，analyze() loop里又每次遍历n个数和可能n^2个pair。虽然两个n^2不会同时出现，但是算法复杂度的量级不会减低。
-geekcode(文心雕码);
2016-2-11
{55}
(#9938565@0)
-
您回贴快糙猛啊，n^4一出，别人很难跟你的贴。拜托花5分钟好好读一下人家的代码。我还是先潜水玩吧:-) 提个醒，hash function决定了那个get()最坏情况的O(n)有多大可能出现。
-juanzhulian(UnlessYouShowMeHow);
2016-2-11
(#9938575@0)
+1
-
昨天没仔细看，是O(n^3)。key的size是n^2级, 不管怎么hash，也不会是n级。
-geekcode(文心雕码);
2016-2-11
(#9938600@0)
-
计算时间复杂度的Worst case依旧没有达到O(n^2)。倒是消耗的存储空间不少。
-iamflying(自食其水果);
2016-2-11
(#9938606@0)
-
- Solution should NOT use a 2-dimensional array/matrix as the main data structure
-sxffff(lookingforjob);
2016-2-11
(#9938568@0)
-
不错，思路干净简洁。感觉平均不会close to O(n^2) ，可能会O(n^2*log(n))。我觉得应该有O(n^2)的算法，不过解释起来比较复杂，如果周末有空我会贴上来。
-geekcode(文心雕码);
2016-2-10
(#9938556@0)
-
我感觉楼主找出的O(n^2*log(n))的解法的时间复杂度算是最优了。但在面试中当场板书，除非已知该算法，否则我是写不出来。
-iamflying(自食其水果);
2016-2-11
(#9938616@0)
-
check this out
-mustang(mustang);
2016-2-9
{197}
(#9936192@0)
-
眼高手低的我来了。你的程序假定满足条件的序列,在拍好序的数组里是相邻的，这个好像不对。 1, 2, 6, 7, 11, 可以有1,6, 11满足条件吧。也可能我理解错了。
-juanzhulian(UnlessYouShowMeHow);
2016-2-9
(#9936717@0)
-
我的理解是：在给出的一组数中，找出这样一组数，这组数的特点是，每后一个数减其相临前一个数的差，都是相等，题目要求找到最长的那组数的长度。
例如： １ ２ ６ ７ １１
结果可以是 １，２ （差是１） or ６，７ （差也是１）， 上面那段代码会返回２。
-mustang(mustang);
2016-2-9
{239}
(#9936770@0)
-
1,6,11 是3 个数，所以你的答案不对
-sxffff(lookingforjob);
2016-2-9
(#9936784@0)
-
你对了，俺错了。谢谢
-mustang(mustang);
2016-2-9
(#9936806@0)
-
thanks all who pointing out the issue with my code, here is revised one:
1,2,6,7,11 = > 1,6, 11 (5), new code here
-mustang(mustang);
2016-2-10
{76}
(#9937438@0)
-
大家讨论啥呢？不就是个双循环的事情？
-guestagain(guest again);
2016-2-10
(#9937306@0)
-
My two cents
-kakashi(kakashi);
2016-2-10
{578}
(#9937402@0)
-
说的这么啰嗦，简单点，不就是找一个最长的等差数列嘛
-bbb333(ccc);
2016-2-10
(#9937664@0)
-
I wrote the code in C# (replaced leading spaces to dots to keep indentation).
-benbenli(大岭);
2016-2-10
{4914}
(#9937690@0)
+1
-
首先谢谢各位的热心，没想到很多的高人，提供了不少的思路
-unhappy_popular(unhappy_popular);
2016-2-10
{4188}
(#9937838@0)
-
I believe this implementation is too complicated for interview answer. Have a look at mine above which is simple and straightforward.
-benbenli(大岭);
2016-2-10
(#9938208@0)
-
my code:
-zhouziren1(zhouziren);
2016-2-10
{1375}
(#9938278@0)
+1
-
我的代码对这组数结果是6， 但是你的是5. 其实我很惊讶O(N^2)能算出来。Question series: [ 2, 2, 4, 5, 6, 8, 10, 12 ]
Returns: 6
Result series: [ 2, 4, 6, 8, 10, 12 ]
-benbenli(大岭);
2016-2-10
(#9938404@0)
-
没什么好惊讶的，这就是错误的解决方案，前面讨论过了。
-iamflying(自食其水果);
2016-2-10
(#9938478@0)
-
我看读了好几遍，不还是不理解为什么最大长度最后还要加1： ret = repeatCnt[repeatCnt.Length - 1] + 1;
-benbenli(大岭);
2016-2-10
(#9938448@0)
-
1, 2, 6, 7, 11, 可以有1,6, 11满足条件吧。 -juanzhulian(UnlessYouShowMeHow); 2-9 (#9936717@0)
-geekcode(文心雕码);
2016-2-11
(#9938567@0)
-
有论文：
-sxffff(lookingforjob);
2016-2-11
(#9938578@0)
-
试试这个办法？先排序，然后用二分法， 给每一个部分里面数列最长到最短的进行排序。
然后是merge, merge中把左子集和右子集已有的相差距离数列相加然后再统计一下从最多到最少就不用说了，必须做的，最关键的是要把大于子数列距离的数距离都要统计一边，当然这些新出现的距离是“最少的”因为才出现了1次么，但这个是这里的关键，否则会漏掉有可能会成为最长数列的距离，这一步有O(k^2)。
二分法是O(nlogn),但是merge用了O(k^2), 所以有可能会变成 O(n2) O(n^2logn) O(n^3),我没算啊，错了别骂我。
-zhengy4(zhengy4);
2016-3-29
{453}
(#10017807@0)