渥太华IT面试编程试题

[苦逼热狗]

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 ...

That might be incorrect. With most of compilers and languages like C++, you could just push the array pointer or reference object into stack and just use the pointer instead of the actual array itself or sub-arrays. You are actually pushing the same memory size of context into a stack.

32位 x86方面:
内存大小方面(wchar_t *) = (unsigned int)都是dword的

 

[wiiwii]

That might be incorrect. With most of compilers and languages like C++, you could just push the array pointer or reference object into stack and just use the pointer instead of the actual array itself or sub-arrays. You are actually pushing the same memory size of context into a stack.

32位 x86方面:
内存大小方面(wchar_t *) = (unsigned int)都是dword的

编程的活直接OUTSOURCING到中国或者印度不就妥妥了?
题外话,我觉的美加应该把监狱也OUTSOURCING出去

 

[苦逼热狗]

试题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, 这个有点难度了 ！

第一眼看我觉得可以这么做
因为a,b都是排好续的
利用b[0]跟b[n-1]找到在a对应的位置例如

a: 1,6,8,9,55,323
b: 10,25,99
b[0]从0开始
10 > 1 0
10 > 6 1
10 > 8 2
10 > 9 3
10 < 55 4
b[n-1]从4开始
99 > 55 5
99 < 323 6
你要sort的只是 这个subset : 55,10,25,99
如果b[n-1]小于55的话,只需要把b插入到a[index],然后把剩下的元素往后移动就好了
最差情况排序a+b
运行时间应该比普通的merge sort快吧,因为你事先就把 2个 数组给排列好了

 

[苦逼热狗]

编程的活直接OUTSOURCING到中国或者印度不就妥妥了?
题外话,我觉的美加应该把监狱也OUTSOURCING出去

咱这不也是中国出来的嘛,我朋友倒是在大连提外包公司工作,一顿打听有没有项目
我之前去西安跟一些人也咨询了一下外包的事情,前1,2年的时候找刚毕业的大学生真是到处都是

 

[旭日阳刚]

移动A中的元素有点费时间吧，因为每次插入B中的元素都要移动后面的所有元素。
10插入之后，可以把a中10后面的元素全部弄出来建立成数组c，然后每次都通过比较c和b，找出最小的，放入a的尾部。
只是一个想法，也许不成熟。

第一眼看我觉得可以这么做
因为a,b都是排好续的
利用b[0]跟b[n-1]找到在a对应的位置例如

a: 1,6,8,9,55,323
b: 10,25,99
b[0]从0开始
10 > 1 0
10 > 6 1
10 > 8 2
10 > 9 3
10 < 55 4
b[n-1]从4开始
99 > 55 5
99 < 323 6
你要sort的只是 这个subset : 55,10,25,99
如果b[n-1]小于55的话,只需要把b插入到a[index],然后把剩下的元素往后移动就好了
最差情况排序a+b
运行时间应该比普通的merge sort快吧,因为你事先就把 2个 数组给排列好了

 

[闲得慌]

第一眼看我觉得可以这么做
因为a,b都是排好续的
利用b[0]跟b[n-1]找到在a对应的位置例如

a: 1,6,8,9,55,323
b: 10,25,99
b[0]从0开始
10 > 1 0
10 > 6 1
10 > 8 2
10 > 9 3
10 < 55 4
b[n-1]从4开始
99 > 55 5
99 < 323 6
你要sort的只是 这个subset : 55,10,25,99
如果b[n-1]小于55的话,只需要把b插入到a[index],然后把剩下的元素往后移动就好了
最差情况排序a+b
运行时间应该比普通的merge sort快吧,因为你事先就把 2个 数组给排列好了

你的那个subset 不一定比A+B小， 因为B的第一个元素可以小于A的第一个。

 

[闲得慌]

移动A中的元素有点费时间吧，因为每次插入B中的元素都要移动后面的所有元素。
10插入之后，可以把a中10后面的元素全部弄出来建立成数组c，然后每次都通过比较c和b，找出最小的，放入a的尾部。
只是一个想法，也许不成熟。

假设A和B的元素都是从小到大排列的。结果也是从小到大排列。 应该每次找出最大的， 从最尾部放起，因为A的尾部是空的。

 

[苦逼热狗]

你的那个subset 不一定比A+B小， 因为B的第一个元素可以小于A的第一个。

也不会比a+b大,我那个方法不是最优的,这个我自己很肯定.

 

[旭日阳刚]

对！从尾部放起。这样就不用建立第三个数组。这个想法应该是正解的。

假设A和B的元素都是从小到大排列的。结果也是从小到大排列。 应该每次找出最大的， 从最尾部放起，因为A的尾部是空的。

 

[该出手时就出手]

That might be incorrect. With most of compilers and languages like C++, you could just push the array pointer or reference object into stack and just use the pointer instead of the actual array itself or sub-arrays. You are actually pushing the same memory size of context into a stack.

32位 x86方面:
内存大小方面(wchar_t *) = (unsigned int)都是dword的

关键看你的函数里是否新开了内存，而不是在于内存开在stack里还是开在heap里。不论是push pointers to stack,还是把数组本身push to stack，反正新开的内存得等后面调用的函数返回之后才能用上。

 

[dollhouse]

O(n)

int i = A.length -1;
int j = B.length -1;
int k = 0;
for (k = A.length + B.length -1; k >= 0; k--) {
if(i < 0) {
A[k] = B[j];
break;
}
if(j < 0) {
A[k] = A;
break;
}
if(A >= B[j]){
A[k] = A;
i--;
}else {
A[k] = B[j];
j--;
}
}

 

[闲得慌]

O(n)

int i = A.length -1;
int j = B.length -1;
int k = 0;
for (k = A.length + B.length -1; k >= 0; k--) {
if(i < 0) {
A[k] = B[j];
break;
}
if(j < 0) {
A[k] = A;
break;
}
if(A >= B[j]){
A[k] = A;
i--;
}else {
A[k] = B[j];
j--;
}
}

不错，但是有个bug

 

[苦逼热狗]

关键看你的函数里是否新开了内存，而不是在于内存开在stack里还是开在heap里。不论是push pointers to stack,还是把数组本身push to stack，反正新开的内存得等后面调用的函数返回之后才能用上。

I lost you right there about 把数组本身push to stack.
recursion的原理跟function call的原理这个我们都清楚.
不过你的意思是把数组复制以后或者切成subset以后再把所有数组内容push to stack?

你应该不是这个意思吧.

内存消耗(硬件资源)跟性能这个应该看很多东西的吧.
如果是手机程序的话,可用资源不够,我们可以牺牲一些性能
如果是服务器程序的话,我们有很多硬件资源,完全可以牺牲硬件,提升性能啊
但是如果这时候服务器已经正在进行大规模的数据处理了，我们硬件资源不够了，这时候就需要牺牲一些性能了，其实就是load balance了

闲得慌来点load balance，cloud computing一类的的问题吧，没接触过，想学

 

[dollhouse]

不错，但是有个bug

别卖关子啊。。。。如果是说A.length包括buffer了那就换成别的写法：）

 

[闲得慌]

别卖关子啊。。。。如果是说A.length包括buffer了那就换成别的写法：）

觉得第一个break有问题， 因为当i < 0的时候， B可能还有多于1个的元素没过来。