r****m
发帖数: 1204 | 1 ADD is a subset of Life. |
|
w***n
发帖数: 1519 | 2 Market being efficient doesn't mean investors focusing on a narrow subset of
securities are sufficiently rewarded for the risk they are taking; neither
does it mean investors should just go ahead and invest in anything because
hopefully it is "fairly" priced.
I'm sure you are an expert on this particular investment vehicle. So, I'm
all ears. Please enlighten me:
- When you say "Not guaranteed, but almost" (IMO very misleading), it sounds
like a sure thing. Then why preferred stocks have a yield ... 阅读全帖 |
|
t**e
发帖数: 208 | 3 dynamic programming, matrix sum[i][j] = 1 indicate there is a subset of a0..
ai which sum up to j, then update like:
sum[i][j] = sum[i-1][j] || sum[i-1][j-vi]
until j==expected sum |
|
Q******e
发帖数: 85 | 4 This is Subset sum problem, NP-complete |
|
|
g*******y
发帖数: 1930 | 6 Google » Algorithm
Algo on November 09, 2009 | Question #245697 (Report Dup) | Edit | History
given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
想知道这个是否有可能做到。我怎么觉得做到O(n^2)就没法提高了 |
|
g*******y
发帖数: 1930 | 7 好像是对的
挺好的方法啊，这么说来只要这个subset的元素个数是常数，都统一是nlogn的复杂度
不愧是传说中的牛人~
a
that |
|
g*******y
发帖数: 1930 | 8 I was thinking about the same flaw in algorithmics' solution. But I was not
courageous enough be to believe algorithmics was wrong. Hehe
By the way, where do you see a proof for Omega(n^ceil(x/2))? I might have
seen it somewhere for the Subset Sum NPC, but didn't know for sure.
wants you to prove this results. |
|
g*******y
发帖数: 1930 | 9 yes, it's NPC
set partition
正号和符号其实就是对数组的一个partition，F等于0，就是要求partition的两个subset相等。这不就是NPC了嘛。
可以用knapsack类似的DP，或者用backtracking的方法做。
1 |
|
r****o
发帖数: 1950 | 10 大虾能不能详细说说怎么用DP做啊？
subset相等。这不就是NPC了嘛。 |
|
g*******y
发帖数: 1930 | 11 就是跟knapsack类似的方法啊。
伪多项式算法。
bool state[i][j] = whether you can find a subset from A[1...i] that sums to
j;
i<=N;
j<=Total_Sum/2
state[i][j] = state[i-1][j-A[i]] || state[i-1][j] |
|
a**********s
发帖数: 588 | 12 Consider if this is possible in O(m*lg(n)):
Given a sequence of n numbers, and we know that their sum is mS. Pick a
subset of them such that their sum is S? |
|
g*******y
发帖数: 1930 | 13 不是NPC，题目是分成m段(切m-1刀)，不是m个subset
partitioned
multiset
such |
|
H*M
发帖数: 1268 | 14 given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
想不出什么天外飞仙的算法达到O(nlgn)
谁有点idea? |
|
g*******y
发帖数: 1930 | 15 niu～
can also use it to solve subset sum ? |
|
a******t
发帖数: 34 | 16 given an array of n elements, find if there is a subset of 3 elements sum up
to value T
with time complexity O(nlgn).
Given a M*N matrix A in which all the elements in a row and all the elements
in a column are strictly
increasing. Find a path from the smallest element (ie A[0][0]) to the
largest element (ie A[M-1][N-1])
such that the sum of the elements in the path is maximum. Time Complexity O(
m+n). Use efficient space. |
|
B*****t
发帖数: 335 | 17 1. O(nlgn) can be achieved by using FFT under some conditions. But generally
the best algorithm to find a subset of 3 elements sum up
to a given value T is O(n^2). The relationship is like radix sort vs quick
sort. But I doubt the interviewers from MS would ask such kind of questions.
2. I don't think there is such kind of algorithms with O(m+n) complexity. |
|
g*****e
发帖数: 282 | 18 牛人们的dp不太看得懂。这个subset到底是M里任意k个数，还是array里连续k个。如果
是任意k个不是npc？ |
|
V*****i
发帖数: 92 | 19 This is not correct. For example M = 5, K = 3 and the number is {1, 5, 6, 8,
11}. Obviously, the subset is {1, 6,
11}. But according to your solution, you will delete 6 first. |
|
b******g
发帖数: 1721 | 20 hehe, very nice. It is a NPC problem like subset sum problem. |
|
w******1
发帖数: 520 | 21 最大的subset就是自己吧？
如果不是自己， 答案也不唯一啊。 |
|
|
q***e
发帖数: 474 | 23 可能我没描述清，求和最大 的subset。
另：本人背景ME |
|
g*******y
发帖数: 1930 | 24 对
DP只是解决问题的一种方法，跟问题的计算复杂度没有直接关系。
NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
漂亮的快速解。后来
尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
溯可能平均性能
好些。 |
|
l******o
发帖数: 144 | 25 嗯，TSP还能用DP做呢。
对
DP只有解决问题的一种方法，跟问题的计算复杂度没有直接关系。
NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
漂亮的快速解。后来
尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
溯可能平均性能
好些。 |
|
l*********y
发帖数: 142 | 26 given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
感觉这道题定义很清晰，但是只能想出O(n^2*lgn) 的brute force解法.
careercup上的讨论不清楚。谢谢。 |
|
B*****t
发帖数: 335 | 27 thanks a lot for your comment!
but there are still 2 things not clear to me.
1. how can you prove that the LIS in the circular array is a
subset of the LIS in the doubled array, or the length of LIS in
the circular array is equal to the length of some sub-array of
the LIS in the doubled array, such that the sub-array is a legal
LIS in the circular array?
2. In the extreme case, there are might be multiple equal length
LIS in the doubled array, which might approach O(n), and the
second step in yo |
|
j***t
发帖数: 50 | 28 How to solve this problem? what algorithm should be used?
For a list of strings, find the largest subsets, within it, no string is a
prefix of another one.
For example,
a, abc, acd, df, dfe
The largets sub sets would be (both are of size 3):
abc, acd, def
or
abc acd, dfe
|
|
B*****i
发帖数: 831 | 29 within the subset no string is the prefix of another one
是不是要先找一下weakly connected component，然后分别取最大的那部分啊？ |
|
a***9
发帖数: 364 | 30 这个是NP hard吧，reduce subset sum to this one |
|
t*******e
发帖数: 274 | 31 来自主题: JobHunting版 - 问道编程题 最近遇到的一道题，用java实现，结果要是在单个class内，还要有test case验证，有
人知道么？
题目： Given a set of retrofitting options (String name, double cost, double
benefit), and a budget, produce the highest benefit subset whose total cost
fits within the budget. Repeat this exercise, given a set of mutual
exclusivity constraints (i.e. measure X and measure Y cannot be used
together) |
|
h**k
发帖数: 3368 | 32 来自主题: JobHunting版 - 问道编程题 polynomial时间不可能找到最优解，这个是NP-hard问题。
exponential solution: check every possible subset of strings.
linear approximating solution: Greedy algorithm. calculate rate of benefit
to cost, then always choose maximal rate string first.
double
cost |
|
s**9
发帖数: 207 | 33 http://people.csail.mit.edu/bdean/6.046/dp/ is a good resource for DP.
For this problem, DP complexity is O(n**2 10**k) where k is the number of
digits.
Let the array be a1,...,an
Define p(i,j)=1 if the sum of a subset of a1,...,ai is j. It holds that
p(i,j)=1 if p(i-1,j)=1 or p(i-1, j-ai)=1.
#include
using namespace std;
bool subsum(int a[], int n){
int sum=0;
int minI=0;
for(int i=0;i
sum+=a[i];
minI=(a[minI]>a[i]?i:minI);
}
if(sum%2==1)
|
|
i**r
发帖数: 40 | 34 Hmmm...
I was thinking the question was related to maxmium subarray problem or
subset sum problem. I was probably wrong.
The brutal force solution can achieve O(n^2) time complexity. To find an
O(n) solution, the problem need to be formulated as a recursion on a one-
dimensional subproblem space. I simply fail to see optimal substructures
among the prefix subproblems. Is it really possible to get an O(n) time
solution?
sum |
|
h**6
发帖数: 4160 | 35 If we are looking for a subset of arbitrary size
it is O(2^n) |
|
|
P*******b
发帖数: 1001 | 37 Input an integer array of size n and an integer k (k<=n), output all subsets
of size k.
thanks |
|
f*********5
发帖数: 576 | 38 almost the same as get combination.
but not output everyone,just output when there is K items
subsets |
|
w******t
发帖数: 69 | 39 别疑神疑鬼了， 广告也不用在这做吧。 review 很好。
The Ultimate Retro Rally (SALE PRICE – $0.99)
Version 1.2
I’ve never really gotten into racing games all that much. I mean, if I
wanted to race, I’d get in my car and race. It’s the same reason I’m not
really into sports games in general. There is, however, a subset of racing
games that I have always really liked, and that’s arcade racing games. You
know, games where realism is completely thrown out the window and you’re
doing crazy stuff and where physics is ignore... 阅读全帖 |
|
A*********r
发帖数: 564 | 40 先把duplicate的去掉，就转化成一般情形的找k-element subset的问题了。。 |
|
A*********r
发帖数: 564 | 41 看到所有这个字眼，我第一念头就会想到用DP, 呵呵，貌似是经典的subset sum
problem， 呵呵 NPC啊。。 |
|
G******i
发帖数: 5226 | 42 ☆─────────────────────────────────────☆
webornot (淡去) 于 (Sun Sep 12 04:40:40 2010, 美东) 提到:
发信人: webornot (淡去), 信区: Working
标 题: 被雷BF事件后续， 哈哈， 我们结婚了
关键字: lay off,求职，结婚，iphone 游戏
发信站: BBS 未名空间站 (Sun Sep 12 04:38:47 2010, 美东)
几个月前bf被雷，当时有点shock,所以发了个矫情的帖子， 被拍的挺狠的。
几个月过去了， 发个后续，分享一下我在这个经历中学到什么。
第一， 我们决定没找到工作之前就不去夏威夷了， 但婚还是要结。我们夏天的时候注
册了， 没有任何
仪式，简单到不能再简单， 不过大家都觉得很踏实。
第二， 关于失业， 其实没那么可怕。 心理建设很重要， 不要把目标当成目标， 只
当成行动的结果
就可以。我给自己的心里建设是， 不要设限说什么时候一定要找到工作，而是告诉自
己， 总会找到工
作的，或早或晚， 总有一份工作等着每个人。而且，当找到新工作的... 阅读全帖 |
|
M**u
发帖数: 10158 | 43 来自主题: JobHunting版 - 请教个题目 subset sum，动态规划 |
|
a***c
发帖数: 2443 | 44 it's called subset sum, look it up
also, hardness is hardness, complexity is complexity. |
|
d****j
发帖数: 293 | 45 面试官没提到题目不可以外泄，而且也都是常见的， 所以就在这里发了。
两轮电话面试都是45分钟，2道编程题，白板共享文档写程序。
简单寒暄5-10分钟，谈谈research，最近做的project等等。
然后直接告知共享文档link，写程序。
Round 1：
A. Given an arbitrary tree, can you print it level by level (with each level
printed on the same line).Define your own tree node structure, can be
binary tree or n-ary tree.
B. Given a set of distinct integers, can you print out all subsets?
Round 2:
A. Remove duplicated integers in an array, and then return an array without
duplicates. Follow up: what if allow duplic... 阅读全帖 |
|
d****j
发帖数: 293 | 46 第一轮第二题
电面之前刚好练过这道题，但是用ArrayList 和ArrayList of ArrayList 实现的，用
recrusive 的方法，返回前k个元素的幂集合之后，再复制一边添加当前k+1元素入每个
子集合。最终返回幂集之后在打印，效率不好。但是当时想都没想就写上去了。
面完了就想起，完全可以用一个等长的int数组来标识是否取当前元素，代码如下。（
Careercup有这道题，使用一个int数i的每一位来做标识，把i从0递增到2^32-1就能打
印出所有的subsets，但最多只能实现到32个数的数组）
public static void printPowerSet(int[] set) {
int[] index = new int[set.length];
int endidx = 0;
printPowerSetSolver(set, index, endidx);
}
public static void printPowerSetSolver(int[] set, int[] index, int endidx) {
if (... 阅读全帖 |
|
d****j
发帖数: 293 | 47 面试官没提到题目不可以外泄，而且也都是常见的， 所以就在这里发了。
两轮电话面试都是45分钟，2道编程题，白板共享文档写程序。
简单寒暄5-10分钟，谈谈research，最近做的project等等。
然后直接告知共享文档link，写程序。
Round 1：
A. Given an arbitrary tree, can you print it level by level (with each level
printed on the same line).Define your own tree node structure, can be
binary tree or n-ary tree.
B. Given a set of distinct integers, can you print out all subsets?
Round 2:
A. Remove duplicated integers in an array, and then return an array without
duplicates. Follow up: what if allow duplic... 阅读全帖 |
|
d****j
发帖数: 293 | 48 第一轮第二题
电面之前刚好练过这道题，但是用ArrayList 和ArrayList of ArrayList 实现的，用
recrusive 的方法，返回前k个元素的幂集合之后，再复制一边添加当前k+1元素入每个
子集合。最终返回幂集之后在打印，效率不好。但是当时想都没想就写上去了。
面完了就想起，完全可以用一个等长的int数组来标识是否取当前元素，代码如下。（
Careercup有这道题，使用一个int数i的每一位来做标识，把i从0递增到2^32-1就能打
印出所有的subsets，但最多只能实现到32个数的数组）
public static void printPowerSet(int[] set) {
int[] index = new int[set.length];
int endidx = 0;
printPowerSetSolver(set, index, endidx);
}
public static void printPowerSetSolver(int[] set, int[] index, int endidx) {
if (... 阅读全帖 |
|
s*******f
发帖数: 1114 | 49 //A. Given an arbitrary tree, can you print it level by level (with each
level
//printed on the same line).Define your own tree node structure, can be
//binary tree or n-ary tree.
struct Node{
int d;
std::vector children;
};
void PrintByLevel(Node *r){
if (!r)
return;
std::queue q;
q.push(r);
int pre_count = 1;
int count = 0;
while (!q.empty()){
Node *p = q.front();
for (std::vector::const_iterator ci = p-
>children.begin(); ci != p->children.end(); ++ci){
q.push(*ci);
++cou... 阅读全帖 |
|
l****y
发帖数: 44 | 50 面的是business platform division 的SQL Server team。我简历上一个DB的keyword
都没有，我连DB的课都没上过，不
知道他们怎么选的。尽管这样，题目全是基本的算法和coding，没有考DB的任何问题。
可惜我还是表现很差，感觉脑子进
水了（或者是进seattle的雨了）。面试从12：30开始（本来说是10点，临时改了，说
是他们上午有会），见了4个人。3
个是印度人，还有一个不知道是什么国籍的。
我就把所有technical的题罗列下来吧。很多都是常见题。
给一个array of integers, 需要多少个comparison能找到min? how about min and
max? what's the best worst-
case? (3n/2)
怎么merge两个sorted的array，n 个呢？
给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向下
一个同层的node。
count 1's in an integer.
mergeSort, mergeSort without r... 阅读全帖 |
|
