买房的路上 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

买房的路上

买房的路上# Joke - 肚皮舞运动

j*x2011-06-21 07:06

1 楼

finbonaci number，是前三个数的和而不是两个；写代码；改进；logn算法
range sum query，array，给[i,j]算区间内元素和，给出不同的space/time
complexity组合，在提示下给出一个n^1/2 space/time complexity的算法
同上，现在的数组是2维，给出一个O(n^2) time/space complexity的预处理方法，然
后是一个O(1)的query
最后一个设计题，一个目录下面有别的目录和source file，要把所有的source file的
一个name替换，考regular expression，然后修改的时候要备份所有文件
然后问了他两个问题
本来是定的一个中国人，临时换了印度人，不过这个印度人挺正常，没感觉针对我

x*o2011-06-21 07:06

2 楼

r*y2011-06-21 07:06

3 楼

thanks.
what is the space complexity and time complexity in #2 ?

【在 j********x 的大作中提到】

: finbonaci number，是前三个数的和而不是两个；写代码；改进；logn算法
: range sum query，array，给[i,j]算区间内元素和，给出不同的space/time
: complexity组合，在提示下给出一个n^1/2 space/time complexity的算法
: 同上，现在的数组是2维，给出一个O(n^2) time/space complexity的预处理方法，然
: 后是一个O(1)的query
: 最后一个设计题，一个目录下面有别的目录和source file，要把所有的source file的
: 一个name替换，考regular expression，然后修改的时候要备份所有文件
: 然后问了他两个问题
: 本来是定的一个中国人，临时换了印度人，不过这个印度人挺正常，没感觉针对我

C*g2011-06-21 07:06

4 楼

这么脏的水，不会感染吧？

j*x2011-06-21 07:06

5 楼

可以有：
O(N^2) space O(1) time
O(N) space O(1) time
O(1) space O(N) time
O(N^1/2) space O(N^1/2) time, find the sum for all intervals of N^1/2 length
. Given any [i,j] interval, find the sum included in it, and count the ones
on both end points. Easy to say its at most 3N^1/2

【在 r*******y 的大作中提到】

: thanks.
: what is the space complexity and time complexity in #2 ?

r*y2011-06-21 07:06

6 楼

smart for the last idea
How to get O(N) space and O(1) time ? thanks.

length
ones

【在 j********x 的大作中提到】

: 可以有：
: O(N^2) space O(1) time
: O(N) space O(1) time
: O(1) space O(N) time
: O(N^1/2) space O(N^1/2) time, find the sum for all intervals of N^1/2 length
: . Given any [i,j] interval, find the sum included in it, and count the ones
: on both end points. Easy to say its at most 3N^1/2

j*x2011-06-21 07:06

7 楼

last one is hint from the interviewer
put a table T, T(i) <= sum(0, i) <= T(i-1) + array(i);
given [i,j] = T(j) - T(i)

【在 r*******y 的大作中提到】

: smart for the last idea
: How to get O(N) space and O(1) time ? thanks.
:
: length
: ones

c*o2011-06-21 07:06

8 楼

你有offer了还到处面~~

【在 j********x 的大作中提到】

: last one is hint from the interviewer
: put a table T, T(i) <= sum(0, i) <= T(i-1) + array(i);
: given [i,j] = T(j) - T(i)

g*i2011-06-21 07:06

9 楼

这题不错,但是有点unfair啊.知道矩阵解法的人就很简单,不知道的人估计是想不出来
的.
2维的也是给[i,j]求和,类似于两个数组的部分区间总和?那感觉和一维没啥区别吧,所
有一维能用的方法似乎都能很容易的扩展到2维. 是不是有其他条件?
能说说为啥修改的时候要备份吗?
这题有需要linux的command吗?还是说个写程序的思路+写出正则表达式就可以了?

【在 j********x 的大作中提到】

j*x2011-06-21 07:06

10 楼

actually to find the sub sum table is non trivial for multiple diminutional
array. A n^3 operation is needed to ciopile such table with constant space.
As for Fibonacci, to know the long solution is not so difficult. I believe
it should be in many books, after all, Fibonacci number is so widely used in
interviews, right?
You are right, the last question is for some commands in Linux or any shell.
Backup is always the must to doin practical engineering. I learned this
long time ago when I accidantally run a command: chmod 777 /. If I were the
interviewer, if not mention backup, I will sure know that this candidate has
little engineering experience, I mean real engineering.

【在 g*****i 的大作中提到】

:
: 这题不错,但是有点unfair啊.知道矩阵解法的人就很简单,不知道的人估计是想不出来
: 的.
: 2维的也是给[i,j]求和,类似于两个数组的部分区间总和?那感觉和一维没啥区别吧,所
: 有一维能用的方法似乎都能很容易的扩展到2维. 是不是有其他条件?
: 能说说为啥修改的时候要备份吗?
: 这题有需要linux的command吗?还是说个写程序的思路+写出正则表达式就可以了?

j*x2011-06-21 07:06

11 楼

I was wrong for the 2d array, it's easy to get n^2 time and constant space
by walking through th array, left to right top to down, keep the sum of the
element on the current row, and before the current column, and to add it to
the previous known sub-array.

【在 g*****i 的大作中提到】

r*y2011-06-21 07:06

12 楼

thanks a lot

【在 j********x 的大作中提到】

: last one is hint from the interviewer
: put a table T, T(i) <= sum(0, i) <= T(i-1) + array(i);
: given [i,j] = T(j) - T(i)

m*q2011-06-21 07:06

13 楼

O(n^1/2)的思路不错，学习了
想到另外一个O(n^1/2) time, O(n^1/2) space的思路:
计算长度为1，2，3，4，...的子数组和，假设共有k组，
那么总长度为 k(k+1)/2，每一段的最大长度为k
则时间和空间都是O(n^1/2)的。不过你的方法更简洁些。

length
ones

【在 j********x 的大作中提到】

j*x2011-06-21 07:06

14 楼

看看topcoder的algorithm tutorial，里面有这个方法

【在 m**q 的大作中提到】

: O(n^1/2)的思路不错，学习了
: 想到另外一个O(n^1/2) time, O(n^1/2) space的思路:
: 计算长度为1，2，3，4，...的子数组和，假设共有k组，
: 那么总长度为 k(k+1)/2，每一段的最大长度为k
: 则时间和空间都是O(n^1/2)的。不过你的方法更简洁些。
:
: length
: ones

C*l2011-06-21 07:06

15 楼

re ^^

l*y2011-06-21 07:06

16 楼

最后一个设计题，一个目录下面有别的目录和source file，要把所有的
source file的一个name替换，考regular expression，然后修改的时候要备份所有
文件
请问这题是要写script还是c code？
谢谢！

j*x2011-06-21 07:06

17 楼

script

【在 l*********y 的大作中提到】

: 最后一个设计题，一个目录下面有别的目录和source file，要把所有的
: source file的一个name替换，考regular expression，然后修改的时候要备份所有
: 文件
: 请问这题是要写script还是c code？
: 谢谢！