w****o
发帖数: 2260 | 1 是8.10
给一个数组(数组的数没有任何的限制) 和一个target，要求一个subarray with the
sum closest to the target.
提示是说要用到cululative array,就是可以先算出来a[0...i]的和。 | p****n
发帖数: 148 | 2 8.10是什么啊？
第8章第10节？
第8章第10题？
是哪个版本，第几页啊？
贴上来看看？
这个问题有时间复杂度为O(n log(n))的算法。
能做得更好吗？我不知道
【在 w****o 的大作中提到】
: 是8.10
: 给一个数组(数组的数没有任何的限制) 和一个target，要求一个subarray with the
: sum closest to the target.
: 提示是说要用到cululative array,就是可以先算出来a[0...i]的和。
| x*******5
发帖数: 152 | 3 终于有人做pearl，给一个我的解答
此题是第9题的扩展，第9题求的是subvector whose sum is close to zero,解答如下
(python)
def Subvector_Zero(v):
"find the subvector whose sum is close to zero"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(1,len(v)):
minv=min(minv,s[i]-s[i-1])
return minv
C++:
/*Description: find the subvector whose sum is close to zero
Input: vector t
Output: int
K.O.: auxiliary sum array
*/
int Pearl::Vector_zero(vector t){
int n=t.size();
vector sum(n,0);
sum[0]=t[0];
for(int i=1;i
sum[i]=t[i]+sum[i-1];
sort(sum.begin(),sum.end());
int minv=numeric_limits::max();
for(int i=1;i
minv=min(minv,sum[i]-sum[i-1]);
return minv;
}
于是要求sum 为k, 就是在sum array中排序后进行binary search找离他距离为k的j，
然后比较找出最小值，即可，有点麻烦，不过还好
def BS_range(v,x):
"find x within v if found return index otherwise return the index\
of its closest value"
l,r=0,len(v)-1
if x<=v[l]: return l
if x>=v[r]: return r
while l<=r:
mid=l+(r-l)//2
if v[mid]<=x and x<=v[mid+1]: return mid+1
elif v[mid+1]
else:r=mid
def Subvector_k(v,k):
"find the subvector whose sum is k"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]-s[i]-k))
minv=min(minv,abs(s[jj]-s[i]-k))
return minv+k
C++:
/*Description: given an sorted array, if a value is in it, return its index;
otherwise return
the index of closest value
Input: vector t, int x
Output: int
K.O.: Binary Search Variant
*/
int Pearl::BS_range(vector t, int x){
int l=0,r=t.size()-1;
if(x<=t[l]) return l;
if(x>=t[r]) return r;
while(l<=r){
int mid=l+(r-l)/2;
if(t[mid]<=x&&x<=t[mid+1]) return mid+1;
else if(t[mid+1]
else r=mid;
}
return -1;
}
/*Description: find the subvector whose sum is close to K
Input: vector t, int x
Output:int
K.O.: similar to vector_zero but with BS_range*/
int Pearl::Subvector_k(vector t, int x){
int n=t.size();
vector sum(n,0);
sum[0]=t[0];
for(int i=1;i
sum[i]=t[i]+sum[i-1];
sort(sum.begin(),sum.end());
int minv=numeric_limits::max();
for(int i=0;i
int j=BS_range(sum,sum[i]+x);
int jj=(j
minv=min(minv,abs(sum[j]-sum[i]-x));
minv=min(minv,abs(sum[jj]-sum[i]-x));
}
return abs(minv-x);
} | p****n
发帖数: 148 | 4 返回值是什么意思？
一会儿 return minv+k
一会儿 return abs(minv-x);
下
【在 x*******5 的大作中提到】
: 终于有人做pearl，给一个我的解答
: 此题是第9题的扩展，第9题求的是subvector whose sum is close to zero,解答如下
: (python)
: def Subvector_Zero(v):
: "find the subvector whose sum is close to zero"
: s=[0 for a in range(len(v))]
: s[0]=v[0]
: for i in range(1,len(v)):
: s[i]=v[i]+s[i-1]
:
| x*******5
发帖数: 152 | 5 恩，对的，c++应该该为minv+x,谢谢啦
【在 p****n 的大作中提到】
: 返回值是什么意思？
: 一会儿 return minv+k
: 一会儿 return abs(minv-x);
:
: 下
| w***y
发帖数: 6251 | | p*****2
发帖数: 21240 | | z*********8
发帖数: 2070 | 8 subarray 是指连续的数吧？ 你sort之后顺序不就乱了？
下
【在 x*******5 的大作中提到】
: 终于有人做pearl，给一个我的解答
: 此题是第9题的扩展，第9题求的是subvector whose sum is close to zero,解答如下
: (python)
: def Subvector_Zero(v):
: "find the subvector whose sum is close to zero"
: s=[0 for a in range(len(v))]
: s[0]=v[0]
: for i in range(1,len(v)):
: s[i]=v[i]+s[i-1]
:
| l*********8
发帖数: 4642 | 9 he/she sorted the array of the sum,not the original array.
【在 z*********8 的大作中提到】
: subarray 是指连续的数吧？ 你sort之后顺序不就乱了？
:
: 下
| p****n
发帖数: 148 | 10 但你的返回值到底是什么意思呢？
最佳子数组的元素的和？
怎么猜似乎都和你的程序不符
【在 x*******5 的大作中提到】
: 恩，对的，c++应该该为minv+x,谢谢啦
| | | x*******5
发帖数: 152 | 11 返回的值是离k最近的值，如果要数组的开始和结束的话，就中间记录起点和终点就可
以了
其实不用猜，每一个程序都是runnable code,可以去运行 | p****n
发帖数: 148 | 12 运行后更猜不着了
比如
输入是
t = {11, -30, -20} x = 20
输出是
30 if return abs(minv+x);
10 if return abs(minv-x)
啥意思啊？
【在 x*******5 的大作中提到】
: 返回的值是离k最近的值，如果要数组的开始和结束的话，就中间记录起点和终点就可
: 以了
: 其实不用猜，每一个程序都是runnable code,可以去运行
| x*******5
发帖数: 152 | 13 谢谢指正，修正两个bug，原始程序中只考虑了vector s[j]-s[i]，也就是位于i和j之
间的subarray，person同学给出的test case 是[0，i]之间的subarray，程序修正如下
def Subvector_Zero(v):
"find the subvector whose sum is close to zero"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(1,len(v)):
minv=min(minv,abs(s[i]-s[i-1]))
for c in s:
minv=min(minv,abs(c))
return minv
返回值是离0的最近距离
test case
v=[11,-30,-20],
output:
11
def Subvector_k(v,k):
"find the subvector whose sum is k"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]-s[i]-k))
minv=min(minv,abs(s[jj]-s[i]-k))
for c in s:
minv=min(minv,abs(c-k))
return minv
test case
v=[11, -30, -20]
k=20
Output:
9 (离20的最近距离)
如果要求具体的subarray的start和end，可以在程序中记录
谢谢person同学坚持的质疑
【在 p****n 的大作中提到】
: 运行后更猜不着了
: 比如
: 输入是
: t = {11, -30, -20} x = 20
: 输出是
: 30 if return abs(minv+x);
: 10 if return abs(minv-x)
: 啥意思啊？
| x*******5
发帖数: 152 | 14 我是把pearl上的题做了3遍，用C++和python都写了一遍，收益很大，虽然每道题都测
试了，但还是会有bug，非常感谢person同学认真的阅读和质疑，给我很大帮助。希望
大家一起认真思考，认真coding, 认真找bug | p*****2
发帖数: 21240 | 15
一共有多少道习题呢？
【在 x*******5 的大作中提到】
: 我是把pearl上的题做了3遍，用C++和python都写了一遍，收益很大，虽然每道题都测
: 试了，但还是会有bug，非常感谢person同学认真的阅读和质疑，给我很大帮助。希望
: 大家一起认真思考，认真coding, 认真找bug
| a***g
发帖数: 234 | 16 几十道不到100道吧
【在 p*****2 的大作中提到】
:
: 一共有多少道习题呢？
| x*******5
发帖数: 152 | 17 这个是我的题库，还有一些题没有coding，比如back of envelop计算，idea思考，等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_
Permute; String::string_permute_noduplicate)
69. Output legal braces of { and } (String::brace)
70. Tokenize a string in C++ (stringstream) (String::Split)
71. Write the BS_first and BS_last (binary search for the first occurrence
of an element and last occurrence of an element ) in iterative and recursive
fashioin (BS_first; BS_last)
72. Write a function to compute the n-th power of x
73. Maximum sum subvector (auxiliary array, Divide and Conquer, Dynamic
Programming, Improved D&C) (Maxium_Vector; Maxium_Vector_dp; Maxium_Vector_
rec)
74 Maximum sum submatrix (extended to 2-dimension array) (Maxium_Rectangle)
75. Write a function to find the subvctor whose sum is close to zero (Vector
_zero)
76 Write a function to binary search the range of value in an sorted array (
BS_range)
77 Write a function to find the subvector whose sum is close to K (Subvector
_k)
78. Write an efficient memory allocation in C-style (mallocation)
79. InsertSort (insertSort)
80. QuickSort (time complexity improvement, space complexity improvement) (
quicksort)
81. Select k-th element (selectK)
82. RadixSort (radixSort; lsd_radix_sort; msd_radix_sort)
83. BubbleSort, SelectSort, ShellSort (bubbleSort; selectSort; shellSort)
84. Compare insertSort, mergeSort, quickSort and heapSort
85. Write a quickSort function with fat pivot (i.e. many elements are the
same with the pivot)
86. countSort for integers (quicksort_fatpivot)
87. Write a function to generate m distinct integer with equal probability
but chooses some subset with greater probability than others
88. Write a function to generate all m-size subarry of an array of size n (
SubArrayS_size_m)
89. Reservoir Sampling: sample 1 and k elements without knowing the total
sample size (ReservoirSampling)
90. Using bit operation to implement add, subtract, multiply and divide (add
subtract multiply divide)
91. Implement two functions of heap operation: siftup and siftdown (siftup,
siftdown)
92. Implement a Huffman tree using priority queue (HuffmanTree)
93. Compute the sum of a large set of float (Sum_float)
94. Find the largest k number from a large sequence of numbers (Find_Top_K)
95. Find the second minimum element in an array using least compare times (
SecondMin)
96. Given a bunch of words, build a hashtable of these words (Hash)
97. Given a string, find the longest duplication subarray (String::Duplicate
_Subarray). | p*****2
发帖数: 21240 | 18
都是很经典的题吗？
我也准备买本练练了。
【在 a***g 的大作中提到】
: 几十道不到100道吧
| x*******5
发帖数: 152 | 19 题目是37道，但是程序（函数数目）是70个，不少题都是要求编两三个程序的，比如
array rotation, string permutation, quick sort(这个就要编5个，各种quicksort,
解决时间，空间，tail-recursion问题, fat-pivot), quicksort还有变体: dutch
flag, select-k，等等
我自己在面试的时候，所有问题都来自这个，有一题还要我分析tournament tree（这
个是pearl的一个小题目，我当时偷懒没想清楚，所以不能偷懒啊），不过我当时的程
序做错了，和面试官一讨论发现错了。另一次面试全是quicksort，如果做了pearl的题
，应该不会有问题。
欢迎大家一起讨论，这些代码一定有不少hidden bugs | a***g
发帖数: 234 | 20 这书不错，值得收藏
作者很有趣
2爷加油！
【在 p*****2 的大作中提到】
:
: 都是很经典的题吗？
: 我也准备买本练练了。
| | | p*****2
发帖数: 21240 | 21
多谢推荐。这几天一直在犹豫买哪本呢。决定买它了。
【在 a***g 的大作中提到】
: 这书不错，值得收藏
: 作者很有趣
: 2爷加油！
| p****n
发帖数: 148 | 22 要不要再做一遍？
test case
v=[-10,-100,-1000,-10000]
k=123
Output:
23
【在 x*******5 的大作中提到】
: 我是把pearl上的题做了3遍，用C++和python都写了一遍，收益很大，虽然每道题都测
: 试了，但还是会有bug，非常感谢person同学认真的阅读和质疑，给我很大帮助。希望
: 大家一起认真思考，认真coding, 认真找bug
| h*********e
发帖数: 247 | 23 then at least O(n^2) 吧.
【在 w****o 的大作中提到】
: 是8.10
: 给一个数组(数组的数没有任何的限制) 和一个target，要求一个subarray with the
: sum closest to the target.
: 提示是说要用到cululative array,就是可以先算出来a[0...i]的和。
| x*******5
发帖数: 152 | 24 很好的test case，不过我再次阅读pearl发现，在原始题目中，即找subarray such
that its sum is maximal中有一个限制条件就是数组不能全为负，经过思考，我的程
序同样要满足这个限制条件，否则会出错。因为在这种情况，只要求出数组最大值就可
以了，o(n)解法。所以代码修改如下
def Subvector_k(v,k):
"find the subvector whose sum is k"
All_Negative=True
if [c for c in v if c>0]:
All_Negative=False
if All_Negative:
return max(v)
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
print v
print s
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]-s[i]-k))
minv=min(minv,abs(s[jj]-s[i]-k))
for c in s:
minv=min(minv,abs(c-k))
return minv
test case
v=[-10,-100,-1000,-10000]
k=123
Output:
-10
【在 p****n 的大作中提到】
: 要不要再做一遍？
: test case
: v=[-10,-100,-1000,-10000]
: k=123
: Output:
: 23
| x*******5
发帖数: 152 | 25 全部都是O(nlogn),主要用于对cumulative array 排序
【在 h*********e 的大作中提到】
: then at least O(n^2) 吧.
| p****n
发帖数: 148 | 26 test case
v=[ 10,-100,-1000,-10000]
k=123
Output:
23
要不要你再做一遍？
另，可否寄我一份你看的pearl啊？想看看原题的描述，包括上下文
【在 x*******5 的大作中提到】
: 很好的test case，不过我再次阅读pearl发现，在原始题目中，即找subarray such
: that its sum is maximal中有一个限制条件就是数组不能全为负，经过思考，我的程
: 序同样要满足这个限制条件，否则会出错。因为在这种情况，只要求出数组最大值就可
: 以了，o(n)解法。所以代码修改如下
: def Subvector_k(v,k):
: "find the subvector whose sum is k"
:
: All_Negative=True
: if [c for c in v if c>0]:
: All_Negative=False
| x*******5
发帖数: 152 | 27 这次还是要感谢，代码的Logic是错的，重新再看pearl, 如附件所示
重新修改代码如下
def Subvector_k(v,k):
"find the subvector whose sum is k"
All_Negative=True
if [c for c in v if c>0]:
All_Negative=False
if All_Negative:
return max(v)
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
if j==i: break
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]+s[i]-k))
minv=min(minv,abs(s[jj]+s[i]-k))
for c in s:
minv=min(minv,abs(c-k))
return minv
重要修改 原来的s[j]-s[i]-k编程s[j]+s[i]-k，如pearl上所示。理解不对，抱歉抱歉啊 |
|
