渥太华IT面试编程试题

[该出手时就出手]

闲兄请继续，俺一直在关注中。

估计不会有别人参与了。

public static TreeNode convertArrayToTree(int arr[], int start, int end)
{
     if (end < start) return null;

     int mid = (start + end) / 2;
     TreeNode n = new TreeNode(arr[mid]);
     n.left = convertArrayToTree(arr, start, mid - 1);
     n.right = convertArrayToTree(arr, mid + 1, end);
     return n;
}

public static TreeNode createBST(int array[])
{
     return convertArrayToTree(array, 0, array.length - 1);
}

 

[苦逼热狗]

闲兄请继续，俺一直在关注中。

别光关注,要参与啊,重在搅和~

 

[该出手时就出手]

别光关注,要参与啊,重在搅和~

有你在，不需要俺动手了。

 

[苦逼热狗]

有你在，不需要俺动手了。

那我不成了动物园里头的动物让人围观了,不好不好

 

[该出手时就出手]

那我不成了动物园里头的动物让人围观了,不好不好

没啥不好。进来的都是专业人士，听你做报告。

 

[该出手时就出手]

别光关注,要参与啊,重在搅和~

那小小搅和一下。你的递归调用的解法在内存使用上不优吧？

 

[苦逼热狗]

那小小搅和一下。你的递归调用的解法在内存使用上不优吧？

benchmark一下看看呗,先做出来,然后看看bottletnet,再做优化

 

[该出手时就出手]

benchmark一下看看呗,先做出来,然后看看bottletnet,再做优化

不用benchmark 应该可以看到递归算法不停地压堆栈啊。比如前面那个反转字符串的，最直接的算法需要开一个字符的存储空间，递归一下，大概要用nlogn字符的存储空间吧。(没细想）

 

[苦逼热狗]

呃,你的意思是前头那些recursion,一直在call function时候push pop进出内存空间? 我没在国内上过大学,有些词真没见过,我还要google......
反转字符串的那个,其实还有个方法就是,知道每个unicode字符占用的内存大小,然后头跟尾字符做3次XOR就对调过来来了.

一定要强调运行时候的存储空间的话,
直接在原数组的内存空间做操作不就好了;

for i = 0 ... n/2; j = n -1 ... n/2 loop

array ^= array[j]; //array = xor array array[j]
array[j] ^= array; //array[j] = xor array[j] array
array ^= array[j]; //array = xor array array[j]

end loop;

用java的话,在performance方面已经是个失败了.

 

[该出手时就出手]

呃,你的意思是前头那些recursion,一直在call function时候push pop进出内存空间? .

Yeap, that is what I meant. I presume that function calls in any language involve pushing the contexts into stacks. In your recursion code for reversing a string, if the input string has length N, then the (computation) tree should have depth log(N) (base 2). At each depth, your code would presumably push size-N context into a stack. The total memory used should be N log(N) ...

The reversing-string problem should be solvable in O(N) time and O(1) memory. In this sense, the recursion algorithm is not optimal ... if what I wrote above is correct ...

 

[闲得慌]

Yeap, that is what I meant. I presume that function calls in any language involve pushing the contexts into stacks. In your recursion code for reversing a string, if the input string has length N, then the (computation) tree should have depth log(N) (base 2). At each depth, your code would presumably push size-N context into a stack. The total memory used should be N log(N) ...

The reversing-string problem should be solvable in O(N) time and O(1) memory. In this sense, the recursion algorithm is not optimal ... if what I wrote above is correct ...

很高兴有人帮助分析 BIG O.

用recursion 肯定多用memory， 因为每call一次，都产生一个 function context 被加到 stack上。 一般的原则是不要在loop里用recursion。

具体到reversing-string problem， 总的function call应该少于N (logN?)， function call占用的memory多，是 cN， c 是大于1的常数。 再加上放结果用了N， 总的memory 就是 cN + N = (c+1)N --> O(N).

同意 The reversing-string problem should be solvable in O(N) time and O(1) memory. 旭日阳刚的解法就是这样的：
http://bbs.comefromchina.com/6569288-post10.html

 

[该出手时就出手]

具体到reversing-string problem， 总的function call应该少于N (logN?)， function call占用的memory多，是 cN， c 是大于1的常数。 再加上放结果用了N， 总的memory 就是 cN + N = (c+1)N --> O(N).

总的函数调用的次数大概是N次（或N-1次之类的），但是不是每次调用压入堆栈的context的size都一样。

那个recursion呈二叉树，高度logN,在每个节点有一次函数调用。在root,context的size是N(加点overhead),每往下一层，context的size减半。所以可以大概估计，每一层被压的总的context的size是N。

所以整个算法内存用量是NlogN.

...唉，本来只是想看你们玩，怎么俺又跳进来较真了？

 

[旭日阳刚]

大水牛呀。那个log是怎么出来的？一直搞不懂。

总的函数调用的次数大概是N次（或N-1次之类的），但是不是每次调用压入堆栈的context的size都一样。

那个recursion呈二叉树，高度logN,在每个节点有一次函数调用。在root,context的size是N(加点overhead),每往下一层，context的size减半。所以可以大概估计，每一层被压的总的context的size是N。

所以整个算法内存用量是NlogN.

...唉，本来只是想看你们玩，怎么俺又跳进来较真了？

 

[闲得慌]

大水牛呀。那个log是怎么出来的？一直搞不懂。

一个N个元素的数组， 变成2叉平衡树， 树的高度是logN with base 2. 必须的！

 

[闲得慌]

试题3. Given two sorted arrays, A and B, and assume A has a large enough buffer at its end to hold B. Write code to merge B into A in sorted order.

Merge, sort, 这个有点难度了 ！