f*********i
发帖数: 197 | 1 Given are a set of intervals S = {I1,I2.....In}, each interval have
different positive weight (weight is independent to the interval, there may
be the case that a long interval has a low weight but a short interval has
high weight).
Purpose: Find out a subset of S, say Sub, such that for every interval in S,
there is an interval I in Sub such that they are somehow overlap.
Requirement: the total weight of Sub is minimum.
就是说，找到一部分的interval,使得S内的所有interval和他们（中的某一个interval
）都有交集，并且要求最小的weight
希望大... 阅读全帖 |
|
g*********8
发帖数: 64 | 2 赞举一反三
似乎in general是subset sum问题 |
|
c********d
发帖数: 173 | 3 如果给定一个长度为2n的整数数组，要从中选出n个元素，使得它们的和和余下的n个元
素的和最接近
这个问题的算法是什么？谁能给出c++/java程序？ |
|
P***P
发帖数: 1387 | 4 先求总和 = x, 然后找n个元素使其和约为x/2, 剩下的就是Knapsack problem了
当然这个肯定不是最优的 |
|
i*******6
发帖数: 107 | 5 Greedy Algorithm:
排序，然后分两半，计算值差/2 = N
两个指针找绝对值最接近N的两个数，记录差t，要求t不大于上次查找的t
直到N=0或者没有这样的t存在
比如
11,5,4,7,4,2,9,3,10,1
先排序：
1,2,3,4,4,5,7,9,10,11
分成
1,2,3,4,4
5,7,9,10,11
计算差
N=28/2 = 14
第一次
找到11和1， 差t=10, N=N-t=4， 交换11和1
第二次
找到7和3， 差t=4<上次的10， N=N-t=0， 交换7和3
结束
结果
11,2,7,4,4
5,3,9,10,1
时间复杂度：
最坏情况O(n^2)，如果能改进找差值的算法，可以做到nlogn |
|
i*******6
发帖数: 107 | 6 又想了下，找差值可以考虑这样搞
1,2,3,4,4
|
pointer1
5,7,9,10,11
|
pointer2
两个都指向当前最后一个数
这样如果两个差大于N,那么减pointer2,否则减pointer1.
交换过的就不再考虑了（因为排过序，可以保证每次都是最优解）
不过这样也是O(n^2)
再想想... |
|
r*******n
发帖数: 266 | 7 你看就是POMDP做多了..不是啥问题人家都认approximation的... |
|
|
g**********y
发帖数: 14569 | 9 这个是对USACO的解答，你的问题改一下就行
private long solve(int N) {
if (N*(N+1)%4 != 0) {
return 0;
}
int M = N*(N+1)/4;
long[] dp = new long[M+1];
dp[0] = 1;
for (int i=1; i<=N; i++) {
for (int j=M-i; j>=0; j--) {
dp[j + i] += dp[j];
}
}
return dp[M]/2;
} |
|
|
|
g**********y
发帖数: 14569 | 12 USACO的题是1~N的数字，换成int[] a也差不多。
就是把和/2， 就是目标值。然后用DP计算可以到达x的办法总数，存在dp[]里。
计算的时候，倒序计算，就不需要额外空间。
最后dp[sum/2]就是办法总数，因为对称性，所以除2. |
|
|
s********r
发帖数: 277 | 14 我怎么觉得这个事NP complete的， 可以转成set cover 问题。
把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
algorithm |
|
s********r
发帖数: 277 | 15 我怎么觉得这个事NP complete的， 可以转成set cover 问题。
把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
algorithm |
|
k*****y
发帖数: 744 | 16 you might need to do a swap after you pick i, and a swap back after the
recursive call. |
|
H*****1
发帖数: 4815 | 17
~~~~~~~~~~~~~~~~~~~~~~~~~~
这个循环不应该有
应该是对m[l]分支，加入或者不加入这个元素 |
|
p*i
发帖数: 411 | 18 不对
[2, 3] 跟[3, 2]是一样的，注意是set/集合不是permutation |
|
k*****y
发帖数: 744 | 19 Thanks, good point. How about
========================================
def Subset_m(v,b,l,m,output):
if l==m:
print output
return
for i in range(b,len(v)-(m-(l+1))):
output[l]=v[i]
Subset_m(v,i+1,l+1,m,output)
========================================
Add a variable b to indicate where to start for the current selection. |
|
l*****a
发帖数: 14598 | 20 void GetSubset(T array[],size_t size,int start,size_t target,vector&vec)
{
if (vec.size()==target) {PRINT; return;}
if(start ==size) return;
for(int i=start;i
{
vec.push_back(array[i]);
GetSubset(array,size,i+1,target,vec);
vec.pop_back();
}
return;
} |
|
x*******5
发帖数: 152 | 21 谢谢大牛指导，但是好像C++的还是不work
void Pearl::GetSubset(vector& array, int target,int start,vector&
vec){
if (vec.size()==target){
Pearl::Print(vec);
return;
}
if (start==array.size()) return;
for (int i=start;i
vec.push_back(array[i]);
GetSubset(array,target,start+1,vec);
vec.pop_back();
}
return;
}
测试：
int a[]={1,2,3};
vector v(a,a+3);
vector vec;
Pearl::GetSubset(v,2,0,vec);
Outp... 阅读全帖 |
|
l****e
发帖数: 1718 | 22 updates:
老印面试：
1.why bloomberg, why software engineering
2. two to find square root for doubles instead of int
3, maximum sum of a subset from a array, two cases: 1) continuous sequence 2
)not continuous
4. find a 6 digits: first 3 digits sum= last 3 digits sum |
|
c*****o
发帖数: 1702 | 23 maximum subset in an array有时间O(n)的解么？ |
|
z**x
发帖数: 16 | 24 我的想法是：
1.设上限为 sum（1，n）/2
2.背包DP,求出子集A，such that for all possible subset A, ( sum(1,n)/2- A.sum
) is minimized
3.所以有A的补集B， （ B.sum-sum(1,n)/2）is minimized
4.所以对于这个partition， |A.sum - B.sum| is minimized
另外想请问背包问题的DP解法的前提是要保证物品的weight要不小于零吗（如本题的O
到K），另外这个上限K有没有实际的作用呢 |
|
c**********e
发帖数: 2007 | 25 This is great. So the problem becomes to select a subset to minimize n*(n+1)
/2-A.sum.
sum
O |
|
x*******5
发帖数: 152 | 26 这个是我的题库，还有一些题没有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_... 阅读全帖 |
|
w****x
发帖数: 2483 | 27 前天刚做过
//permutation of string with duplicate characters
//different from the subset problem, can't solve duplicated chars
//situation by sorting the array
void _inner_print(char strOrg[], char strCur[], int nLen)
{
assert(strOrg && strCur && nLen >= 0);
if (0 == nLen)
{
cout<
return;
}
//record if a character is calculated as a header
//to eliminate duplicated characters
bool bRec[256];
memset(bRec, 0, sizeof(bRec));
for (int i = ... 阅读全帖 |
|
t*********7
发帖数: 255 | 28 不是吧...要考虑每个子集和只出现一次啊,不是单纯的找出所有的SUBSETS啊 |
|
n********k
发帖数: 40 | 29 这是最典型的NPC问题，lz可以狗一狗 subset sum problem 看看 |
|
j********e
发帖数: 1192 | 30 除了N，还有set的最大size （K）要考虑吧。
假如K是很小的常数，可以建一个大的Hashtable，把每个set的所有subset
（O（N*2^K）但是K是constant)都放进去，然后扫描一遍就知道了。
set。 |
|
w***y
发帖数: 6251 | 31 我就不一一说是哪个公司的题目了:)
1. write a function to calculate the cube square root of x
2. given a set of elements, all possible subset
3. prefix search -- given a set of words, and a prefix, find the words
starting with the prefix
4. anagram bucket - anagram means different words with the same character
set, e.g., 'cat' and 'act' are anagram . Given a set of words, group them by
anagram.
=========================================
1. iterator with filter, 跟这个帖子的 2A一样
http://www.mitbbs.com/article_t/JobHunti... 阅读全帖 |
|
S*****e
发帖数: 229 | 32 two sigma
先是coding test，题目在glassdoor上有，虽然不难但是也得小心。他们家onsite时间
很长，4个人面一人一个半小时，有很多behavior问题，体力和耐心要好。只说技术题了
第一次onsite:
1. find cubic root of a number
2. 10个硬币，有一个硬币两面都是head，现在随机抽了一个硬币，投了一次发现是
head，问抽到的是坏硬币的概率
3. given a set, find all subsets
4. linear regression, integration of gaussian, max heap insertion and
deletion ….
5. how to design a web server that monitors the usage of backend servers and
display results
6. 记得有个同学说过的题，有两个矿A，B，有2n个工人，每个工人在A和B中挖矿的效
率不同，由两个数组给出。如果必须要有n个工人在A，n个工人在B里面，问如何使效率
最... 阅读全帖 |
|
S*****e
发帖数: 229 | 33 two sigma
先是coding test，题目在glassdoor上有，虽然不难但是也得小心。他们家onsite时间
很长，4个人面一人一个半小时，有很多behavior问题，体力和耐心要好。只说技术题了
第一次onsite:
1. find cubic root of a number
2. 10个硬币，有一个硬币两面都是head，现在随机抽了一个硬币，投了一次发现是
head，问抽到的是坏硬币的概率
3. given a set, find all subsets
4. linear regression, integration of gaussian, max heap insertion and
deletion ….
5. how to design a web server that monitors the usage of backend servers and
display results
6. 记得有个同学说过的题，有两个矿A，B，有2n个工人，每个工人在A和B中挖矿的效
率不同，由两个数组给出。如果必须要有n个工人在A，n个工人在B里面，问如何使效率
最... 阅读全帖 |
|
v****c
发帖数: 29 | 34 他从subset sum做reduction
其实从3-partition problem reduce过来就可以了
即使整数是bounded，也是NPC |
|
g***s
发帖数: 3811 | 35 说的是有范围正整数，指的是所有数字的和S是有范围，我们找算法是S的多项式级就可
以了。
Subset sum在这个条件下有DP解。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
|
p*****2
发帖数: 21240 | 37 target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)
不就是在一个数组里找subset，使得sum为target吗？ |
|
r*****e
发帖数: 264 | 38 我用C++常干的事情是minimum spanning trees, subsets sorting, max submatrices,
max cliques, graph traverse, linear transformation之类的，算法比较复杂（在
版上大牛看来可能不算什么吧），但是没有怎么用到OO的地方。感觉自己很落伍。
对了，博士还没读完，all but dissertation这样的可以么？ |
|
s****r
发帖数: 41 | 39 it will be be helpful if you know the nature of the data set. In many cases,
the median of a big data set is no much difference than the median of its
subset. In network traffic analysis, we have observed that the median
becomes stable fairly quickly, when we counted the sizes of transferred
objects on network. So usually, we need only compute the median for the data
objects in a small time window, and use it to represent the media for the
whole day, or other long time ranges. |
|
g***s
发帖数: 3811 | 40 这个解法是指数级别的
DP很少会用subset作为状态。 |
|
s***h
发帖数: 662 | 41
他的nlogk 有点奇怪...不知道这个k是什么
define k to be |desired subset|,
use heap, then it is k * log n.
not sure what n * log k is... |
|
h*****3
发帖数: 1391 | 42 我觉的你要把leetcode上所有的题都问一遍。 |
|
f*********m
发帖数: 726 | 43 没有搜到合适的答案，自己又不会做，能有什么别的办法呢？ |
|
|
f*********m
发帖数: 726 | 45 请问能show一下code吗？
非常感谢。
我写了一个，不过没有通过online judge.
void SubsetII(vector & I, int start, vector &A, vector
> &ret, int level) {
if(level == I.size()) {
ret.push_back(A);
return;
}
int i = start;
int prev = -1;
if (I[i] != prev) {
A.push_back(I[i]);
SubsetII(I, i + 1, A, ret, level + 1);
A.pop_back();
prev = I[i];
}
SubsetII(I, i + 1, A, ret, level + 1);
}
vector > subsetsWithDup(vector &S) {
vector > ret;
ve... 阅读全帖 |
|
|
a*******y
发帖数: 1040 | 47 why dont you just check if(find(ret.begin(), ret.end(), A) == ret.end()) and
then add into the vector
int> |
|
|
j********2
发帖数: 82 | 49 这个是不是还是先产生解再检查是否已经产生过？正解应该是不产生重复解吧（就像
permutation的问题一样） |
|
R******1
发帖数: 58 | 50 对的 是在插入vector之前先检查是否产生过
开始是想不产生重复解的，但是程序是recursive的，混起来之后有点儿乱，就偷懒了
一下
有什么办法可以不用先生成再check的吗 |
|
