由买买提看人间百态

topics

全部话题 - 话题: subset
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
R**y
发帖数: 72
1
来自主题: JobHunting版 - 攒RP,ZocDoc 面经
ZocDoc是一个不错的公司。市场前景不错,没有对手。
Skype Interview,一个亚裔小伙,人很nice,题目也不难
Reverse Linked List.
我开始用stack实现,结果返回的head是为null,初始化赋值的地方出错
Node result = null;
Node head = result; // 这个地方,即时将来result 会赋上新值,head依然为null。
然后处理头节点的时候,没有将其的next赋为空。。。。
接着一看不行,用for loop 直接做,返回值又弄错了,返回了是反转结果的最后一个
节点。。。。
no.2 打印一个string所有可能的subset的anagram,
这道题饿做错了,我只打印了当前字符串所有可能的anagram,而且面试官没看出来我
错了,他也误以为是只打印所有anagram。
这道题如果要打印所有subset的 anagram,我觉得至少O(2^n),字串就有这么多。。。
攒个RP,这是第二个电面,发现如果做新题,很容易慌,直接就容易跪,即使能做出来
也经常出这样那样的小bug,需要面试官带着才能做对
----... 阅读全帖
R**y
发帖数: 72
2
来自主题: JobHunting版 - 攒RP,ZocDoc 面经
大牛,能解释一下,到底有多少个subset么? 我觉得应该是2^n个,然后每个subset找
出所有permutation。
p*****2
发帖数: 21240
3
来自主题: JobHunting版 - 今天计划做20题

Id Question Difficulty Freqency Data Structures Algorithms
1 Two Sum 2 5
array
set
sort
two pointers
2 Add Two Numbers 3 4
linked list
two pointers
math
3 Longest Substring Without Repeating Characters 3 2
string
hashtable
two pointers
4 Median of Two Sorted Arrays 5 3
array
binary search
5 Longest Palindromic Substring 4 2
string
6 ZigZag Conversion 3 1
string
7 Reverse Integer 2 3
math
8 ... 阅读全帖
k*******2
发帖数: 84
4
来自主题: JobHunting版 - Walmart Lab onsite求指导
第二题是subset sum问题的变形,是一个NP问题;
http://en.wikipedia.org/wiki/Knapsack_problem#Subset-sum_proble
这题可以转化为求array里的元素是否可以sum到s
DP状态转移方程
D[i][s] = D[i-1][s] || (A[i] == s || D[i-1][s-A[i]])
设array中有n个元素 则扫一遍D[n][i] (i = 0 to sum of all elements in array)
找出abs(sum - i)最小的D[n][i]为1的值;
k*******2
发帖数: 84
5
来自主题: JobHunting版 - Walmart Lab onsite求指导
第二题是subset sum问题的变形,是一个NP问题;
http://en.wikipedia.org/wiki/Knapsack_problem#Subset-sum_proble
这题可以转化为求array里的元素是否可以sum到s
DP状态转移方程
D[i][s] = D[i-1][s] || (A[i] == s || D[i-1][s-A[i]])
设array中有n个元素 则扫一遍D[n][i] (i = 0 to sum of all elements in array)
找出abs(sum - i)最小的D[n][i]为1的值;
P*******r
发帖数: 210
6
来自主题: JobHunting版 - 一道onsite面试题
多谢。
晕了,居然忘了bitmap. 面试官提示状态机,但是当时脑子短路了。
对了,忘了说是 小于 整个长度的subset, 比如说 1,2,3,4,5,6. 要求输出size
《=4的所有subset.
略复杂一点,思路一样。
d********3
发帖数: 25
7
来自主题: JobHunting版 - 攒人品,yahoo电面面经
一个华人gg,挺腼腆,态度很nice,但最终还是fail了
一共面了三道题,全是leetcode上的高频题,
1) subsets,给一个整数数组,列出所有可能的subsets
2)2 sum
3) 4 sum
第一道题,其实用permutation比较直接,但那段时间刷DFS刷多了,脱口而出DFS,显
然不是面试官gg心里想的,于是他跟我纠缠了半天DFS,说如果你说DFS,神马是edge神
马是vertex,我自己也没讲清楚,但代码还是写了出来
后两道题,想也没想,实在是太熟了,直接就给出答案,但没时间写代码。因为是第一
次电面,经验不足,挂了也没什么可抱怨的,只是表现不好,太对不起推荐的师兄和好
朋友了~
b***e
发帖数: 1419
8
来自主题: JobHunting版 - 问道G家的题
Let’s see. The problem reduces to the following, formally:
Let U be the universe and S is a set of subsets of U. Find the minimal
subset of U, namely i, such that i intersects each s in S.
Here is how this problem can be reduced to max flow&min cost:
1. Build a bii-secting graph, where the left side vertices are elements of U
, and the right side vertices are elements of S. Connect left side with
right side if there is a “belongs-to” relation. Each connection has a
capacity of 1 and cost 0.
... 阅读全帖
b***e
发帖数: 1419
9
来自主题: JobHunting版 - 问道G家的题
Let’s see. The problem reduces to the following, formally:
Let U be the universe and S is a set of subsets of U. Find the minimal
subset of U, namely i, such that i intersects each s in S.
Here is how this problem can be reduced to max flow&min cost:
1. Build a bii-secting graph, where the left side vertices are elements of U
, and the right side vertices are elements of S. Connect left side with
right side if there is a “belongs-to” relation. Each connection has a
capacity of 1 and cost 0.
... 阅读全帖
s******y
发帖数: 936
10
来自主题: JobHunting版 - Amazon面筋
拿到了offer,很久以前的了,以前写好了 忘记发出来了。
Hr: indian girl general talk and told me the feed back from the phone
interview: communication problem
First: indian: two coding : find all files in the dir, and sub dir, non rec,
I proposed dfs/bfs like transverse a tree, he want me to use dfs with
stack.
Another coding is: use minheap and maxheap to find the median in a stream
of integers.
Second: one coding: subset, not exactly {1,2,3} is for subset input, his
input is {{1,2,3},{2,3},{0}},set includes sets
So... 阅读全帖
b******i
发帖数: 914
11
来自主题: JobHunting版 - leetcode这题太搞了
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
读题
y*****e
发帖数: 712
12
来自主题: JobHunting版 - F昂赛面经,已挂
power set就是找一个集合所有的subsets,包括空集和它自己,应该是subset I
s*********t
发帖数: 36
13
来自主题: JobHunting版 - Linkedin八月onsite面经
觉得下面的解法不对啊。longest palindrome subset of an array,我理解subset 至
少应是第一和最后一个字母相同,然后字串之间包含palindrome :
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样
s*********t
发帖数: 36
14
来自主题: JobHunting版 - Linkedin八月onsite面经
觉得下面的解法不对啊。longest palindrome subset of an array,我理解subset 至
少应是第一和最后一个字母相同,然后字串之间包含palindrome :
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样
s*********t
发帖数: 36
15
来自主题: JobHunting版 - Linkedin八月onsite面经
觉得下面的解法不对啊。longest palindrome subset of an array,我理解subset 至
少应是第一和最后一个字母相同,然后字串之间包含palindrome :
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样
s*********t
发帖数: 36
16
来自主题: JobHunting版 - Linkedin八月onsite面经
觉得下面的解法不对啊。longest palindrome subset of an array,我理解subset 至
少应是第一和最后一个字母相同,然后字串之间包含palindrome :
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样
s*********t
发帖数: 36
17
来自主题: JobHunting版 - Linkedin八月onsite面经
觉得下面的解法不对啊。longest palindrome subset of an array,我理解subset 至
少应是第一和最后一个字母相同,然后字串之间包含palindrome :
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样
s*********t
发帖数: 36
18
来自主题: JobHunting版 - Linkedin八月onsite面经
觉得下面的解法不对啊。longest palindrome subset of an array,我理解subset 至
少应是第一和最后一个字母相同,然后字串之间包含palindrome :
bool D[][]
D(i,i) = true (maxLen = 1)
D(i, i+1) = s(i) == s(i+1) ? true : false (true -> maxLen = 2)
len = [3, size()]
D(i, j) = (D(i+1, j-1) || D(i, j-1)|| D(i+1, j)) && s(i) == s(j)
maxLen = whatever longest above
不知是不是这样
l*******t
发帖数: 79
19
题目就是find all primes less or equal than n,要求体现OOD和写unit test。求拍
砖,多谢各位!
ps:不确定如果面试中让写C++ unit test,不用gtest, boost.test这些库,写成这样
可以吗?。。。因为之前自己写代码没有养成写unit test的习惯,感觉不太规范。。
#include
#include
#include
#include
#include
using namespace std;
class PrimeFinder {
friend class PrimeFinderTest;
public:
PrimeFinder(int n = 2) {
is_prime_.push_back(false);
is_prime_.push_back(false);
is_prime_.push_back(true);
primes_.... 阅读全帖
r****7
发帖数: 111
20
来自主题: JobHunting版 - Zazzle怎么样?
好像盈利很不错,组比较小,8-10个人,都是大S,MIT的牛人。就是用的技术的.net,
C#. 经理说和manufacturer接轨,历史遗留问题只能用这些。search和infra做的都很
不错,还没有谈pkg。
他家不需要onsite,,直接几轮skype发offer,但是好像卡出生,卡简历和过去经历卡
的非常严格。
上一下面经吧。
一棵树,先打印树的深度,再leetcode largest sum。再写largest subset sum,但
是subset里面的任意两个node要求不相邻。然后再问如果把binary tree改成 graph怎
么做。
第二面是翻转链表,然后说如果有环怎么改代码,然后是说不许改变指针的方向,只能
交换值怎么做。用递归以后问怎么用循环实现,其实就是自己搞一个stack。
本来说面3个小时,2个人面了1.5小时以后说,经理想找你谈。后来经理说希望我去一
趟公司,大概谈了谈组里情况,说pkg大概是110-120kbase,new grad,option具体没
谈。说很可能发offer,但是见面之前不能发paper offer
g*****y
发帖数: 94
21
来自主题: JobHunting版 - 问个Google的面经问题
大家好,问个Google问题,List> lists,Pair有两个属性,id和String型
的value,不同lists相同id的Pair可能value不同,最后要求在所有lists都出现的id的
List,相当于求intersection。所以返回类型是List String>>>,每个Pair对应id和a list of values。然后follow up是如果这个
intersection function如果call多次的话怎么优化?然后这个follow up加了额外的条
件是,有billions of lists,每次intersection求的是其中的subset的intersection
。我想到的方法是cache住已经计算过的subset的intersection,但是怎么设计key,然
后怎么通过key来lookup cache。但是感觉这个key也太难设计了,不知道大家有什么方
法?多谢啦
r*******g
发帖数: 1335
22
来自主题: JobHunting版 - 这道facebook的题怎么解
https://www.glassdoor.com/Interview/Given-a-set-of-n-jobs-with-
end-time-cost-find-a-subset-so-that-no-2-jobs-overlap-and-the-cost-is-
maximum-QTN_440168.htm
Given a set of n jobs with [start time, end time, cost ] find a subset so
that no 2 jobs overlap and the cost is maximum ?
想了一下dp,但是状态转移不好写。
谢谢了。
k***g
发帖数: 166
23
来自主题: JobHunting版 - 这道facebook的题怎么解
大家说的都是求maximum cost,但题目说的是find a subset that..
如果是要取这个subset应该怎么做呢?
r********k
发帖数: 258
24
来自主题: JobHunting版 - 奇怪的一个leetcode题
Take a look at the link. I agree with you. Using trie might have extra
features like find a longest prefix match of q with a subset of S. Here, a
subset of S is also found.
a********r
发帖数: 218
25
来自主题: JobHunting版 - 大牛过来看道题
找subsets的题,看到一个大牛的code:
vector> subsets(vector& nums) {
sort (nums.begin(), nums.end());
int elem_num = nums.size();
int subset_num = pow (2, elem_num);
vector> subset_set (subset_num, vector());
for (int i = 0; i < elem_num; i++)
for (int j = 0; j < subset_num; j++)
if ((j >> i) & 1)
subset_set[j].push_back (nums[i]);
return subset_set;
}
在这里,if ((j >> i) & 1) 怎么理解?
大牛能不能举个例子解释一下这个条件?跪谢了。

发帖数: 1
26
来自主题: JobHunting版 - 求FB 面试 leetcode题目列表
534 Design TinyURL 0.0% Medium
283 Move Zeroes 50.7% Easy
301 Remove Invalid Parentheses 35.5% Hard
273 Integer to English Words 22.4% Hard
621 Task Scheduler 42.4% Medium
67 Add Binary 33.2% Easy
325 Maximum Size Subarray Sum Equals k 43.1% Medium
689 Maximum Sum of 3 Non-Overlapping Subarrays 41.2% Hard
253 Meeting Rooms II 39.3% Medium
17 Letter Combinations of a Phone Number 35... 阅读全帖
i******e
发帖数: 1720
27
来自主题: Parenting版 - 学校好不如专业好
嗯,是不是可以这么说? - College of Liberal Arts 就是对Liberal Arts学分
要求高,所以颁 BA/MA. College of Art and Science 不一定就是对Liberal Arts
要求高,颁 BA还是BS要看所修Liberal Arts的学分。
这也侧面回应了是不是liberal arts == arts and science。
我觉得liberal arts是arts and science的subset. 但不是所有的arts and science都
是liberal arts。  不知这么想对不对?
或许应该是liberal arts是arts的subset. 但不是所有的arts都
是liberal arts ?
t******l
发帖数: 10908
28
来自主题: Parenting版 - 最高法院终于还了UT一个公道
你的这两贴跟 “多人囚徒困境数学上基本无解” 的关系不大。。。数学上基本无解是
因为 “理性经济人” 的存在,在大尺度大规模的问题上,到达最优解/可行解的概率
几乎是零。
至于你说的有人说的 “出卖华人利益”,其实上下文的意思是 “出卖 ‘a subset of
华人’ 的利益” && “你可能是属于该 subset”,而不是真的说 “the whole set
of 华人”。。。老实说 “the whole set of 华人” 的定义本来就很模糊,混血也
不知道算不算,自恨也不知道归哪个 set 里。。。反正灵长目的语言总是一堆的二
义性,死扣 formal logics 也不会有啥结果就是了。。。当罗素哥遇上灵长目。。。
i****z
发帖数: 75
29
这篇写妈妈创业者的英文文章也不错,和大家分享下:
http://www.inc.com/brent-gleeson/why-moms-make-the-fiercest-ent
ne of the things I love the most about Inc. is the unwavering support and
encouragement for entrepreneurs. And specifically, its support for various
subsets of entrepreneurs. For example, at every Inc. event I have attended,
there has been an entire day (or at least part of a day) devoted to military
veteran entrepreneurs, or "vetrepreneurs." Being a former Navy SEAL, combat
veteran, and entrepreneur, I have... 阅读全帖
I*D
发帖数: 40035
30
来自主题: WashingtonDC版 - 诚聘 IT 英才---ZZ
Role Title Description Start Date End Date Status Level From
Level To Standard Role Work Location Role Specialty 1 Level 1
Role Specialty 1 Level 2 Role Specialty 1 Level 3 Role Specialty 1
Level 4 Role Specialty 1 Level 5 Skill & Proficiency
PeopleSoft Administrator This person will be part of a team that supports
a PeopleSoft Financial system with several associated custom applications
and batches using ASP .NET, Hyperion, PL/SQL, SQL, and SQR. This ... 阅读全帖
d*******d
发帖数: 3382
31
来自主题: LeisureTime版 - 虎妈新战歌:《The Triple Package》
The 'Tiger Mom' Superiority Complex
A new book from Amy Chua and Jed Rubenfeld seeks to explain why some groups
succeed in America, and some fail. But when does cultural pride cross over
into racism?
By Suketu Mehta Monday, Feb. 03, 2014
From time to time, every Indian American finds an email in his or her inbox,
wearing a font of many colors, like the one my grandfather once sent me: "
Take a Pride--Being an Indian. 38% of Doctors in U.S.A. are Indians. 36% of
NASA employees are Indians. 34% of... 阅读全帖
y*b
发帖数: 3190
32
http://www.mirrorlessrumors.com/cea-introduces-new-terminology-
DSLR (short for Digital Single-Lens Reflex cameras): a subset of ILC cameras
that includes a mirror mechanism;
Mirrorless (short for Mirrorless Interchangeable Lens cameras): a subset of
ILC cameras that does not include a mirror mechanism;
ILC (short for Interchangeable Lens Cameras): includes both DSLR and
Mirrorless cameras which, by definition, have Interchangeable Lenses.
t******l
发帖数: 10908
33
来自主题: Joke版 - 3桶问题的证明(更新)
很多维持约束的力,在中学物理数学的范畴,很难计算。
在 superfluid helium-4 这种 ideal fluid 的情况,牛顿力学不一定能算这个内部的
力(区别于表面上的力)。。。因为 superfluid 用牛逼顿的光滑小球建模,可能要到
实数集层次的无限可分,如果出现 uncountable subset(不一定是 volume,因为容积
守恒要求 measurable,必须 countable。但 uncountable subset of surface 是可能
允许的,因为 ideal fluid 不要求表面积守恒),这样有导致在过程之中数学上都无
法计算这个力的可能。
当然真正的 ideal fluid superfluid helium-4,用薛定谔的猫,不需要无限可分的实
数集。但也不一定有通常的宏观牛顿力学的 “力” 的概念。

:这个力有多大?怎么算?
:你就瞎bb吧。哈哈哈
t******l
发帖数: 10908
34
来自主题: Joke版 - 那到物理题
很多情况需要半解析解。。。一种是马工项目前先估计一下不要把整个 server farm
给烤熟了。。。另一种是为了时间空间效率,算法只对所有理论可能输入的 subset 才
时空划算,但这样要预估客户的真实输入大概率的在 subset 里。

:找解析解是数学系的事
:有数值解足够了
G******t
发帖数: 1782
35
http://news.yahoo.com/china-ordain-more-bishops-amid-vatican-sp
原文出处
译文简介:“中国官方控制的天主教教会计划任命至少七任主教,”一位教会最高官员
如此说道。中国一直以来一系列任命主教的行为,已加剧了中国与梵蒂冈的紧张关系。
“中国官方控制的天主教教会计划任命至少七任主教,”一位教会最高官员如此说道。
中国一直以来一系列任命主教的行为,已加剧了中国与梵蒂冈的紧张关系。
中国天主教爱国会负责人刘柏年透露,这位新主教将在“吉日” 被任命,但没有给出
更多的细节。
刘柏年,现任第十一届全国政协常委、民族和宗教委员会副主任,中国天主教“一会一
团”名誉主席,山东省政协副主席。
梵蒂冈教廷一直与受北京控制的中国教会进行着艰苦的斗争。它声称,这次的任命并未
受到教皇的批准,是不正当的。
中国天主教爱国会继在中国南部广东省的城市汕头任命黄炳章为新主教后,又有了进一
步的举动。
中国已有570万基督教徒,而且人数还在不断增加,他们如果不愿忠于中国天主教爱国
会,情愿忠于教皇,就得成为“地下教会”的一份子。近日发生的一件事就证明了这一
... 阅读全帖
G*****9
发帖数: 3225
36
来自主题: TrustInJesus版 - 一个基本的问题
定义:
S_t --- 到时间t神要给人的全部教导;
B_t --- 到时间t《圣经》中包含的神要给人的教导;
C_t --- 到时间t《圣经》中包含的教导;
S --- \bigcup_tS_t
我想知道,下面这些结论是否成立:
a) S_t \subseteq S_{t+h}, for any h > 0;
b) B_t \subseteq B_{t+h}, for any h > 0;
c) C_t \subseteq C_{t+h}, for any h > 0;
d) S_t = S, for any t;
e) B_t \subset S_t;
f) B_t \subset C_t;
M****e
发帖数: 3715
37
来自主题: Apple版 - Apple Q&A on Location Data
http://www.apple.com/pr/library/2011/04/27location_qa.html
Apple would like to respond to the questions we have recently received
about the gathering and use of location information by our devices.
1. Why is Apple tracking the location of my iPhone?
Apple is not tracking the location of your iPhone. Apple has never done
so and has no plans to ever do so.
2. Then why is everyone so concerned about this?
Providing mobile users with fast and accurate location information while
preserving their secu... 阅读全帖
s********i
发帖数: 17328
38
you should not think with 2 ids, you should think about if you only have 1
id,
how do you achieve your goal? if any idevice can sync a subset of what is in
cloud and cloud can push a subset to any idevice, you problem is solved.

ID2
o**o
发帖数: 3964
39
来自主题: Apple版 - mywi vs pdanet vs tetherme?
大家用那个?我想装过一个偶尔让pad或者laptop上网。
mywi和tetherme这两个好像都用mobile substrate,这玩意儿我以前用subsettings的
时候很耗电。后来不得已把subsettings和substrate都删掉了就好了。pdanet怎么样?
g*******g
发帖数: 18
40
两个都是NP-hard, reduction from Subset Sum.
PHASE 1:一维
it seems not NP hard.
PHASE is NP hard.
if not, just set N = 0, now, it is Subset Sum problem.
o****e
发帖数: 92
41
假设各面值储备充足,那么找零问题不是 Subset Sum

如果所有的面值都是整数的话,这个问题就是subset sum问题的optimization version
, 是np-hard。
动态规划算法的时间复杂度是O(nk),k是需要凑的面值的总和,n是所给的不同面值的个
数。
a*********e
发帖数: 35
42
多谢各位的指点,偶在一个newsgroup得到了一个答案,已经验证过了,
可以用应该还不错,贴出来大家看看,但是里面的实现好象没有在Oral
ce里见过. 麻烦那位帮我解释一下.
/***********
The answer is:
select "what you need" from (
select rownum line, "what you need" from "your table" )
where line between "start of subset" and "end of subset"
.....
E.g.:
select name, firstname from (
select rownum line, name, firstname from names)
where line between 10 and 20
order by name;
/***********************
M***7
发帖数: 2420
43
来自主题: Database版 - Query help
Hi there,
The table is like
ID1 ID2 similarity
1 2 95%
1 3 80%
...
1 10000 60%
2 3 70%
...
Suppose there are 10000 distinct IDs, and the table stores all pairwise
similarities. Now I want to retrieve a subset of IDs and make sure that the
pairwise similairity between every two IDs in the subset is in a specific
range (e.g. 70~85%).
Anyone help me out. Thanks.
M***7
发帖数: 2420
44
来自主题: Database版 - Query help
I want a subset of IDs, like
-------------------------
ID
1
3
4
.....
------------------------
that having all pairwise similarities between 70~85%.
The way you suggested is not working since it eliminates certain possible
pairwise comparison between IDs in the subset.

70
M***7
发帖数: 2420
45
来自主题: Database版 - Query help
First, the original table contains all possible pairwise similarities.
It is possible to get more than 1 subset. So I would want to get a whole subset, for example, 2000 out of
10000 while all possible pairwise similarities in the 2000 IDs are in the range, then use some other constraints to trim it down.
Thanks
s****o
发帖数: 18
46
如果有N个相同维数的向量,how to efficiently find those subsets whose members
are all orthogonal to each other?
E.g. if we have vectors X_1, X_2, ..., X_n
we may find in (X_1, X_5, X_7) all vectors are orthogonal, and we need all
other subsets.
Any references?
Thank you in advance!
k****f
发帖数: 3794
47
来自主题: Programming版 - 这个组合题目怎么做?
给定n个数,排好顺序:
a1 < a2 < a3 ....
假定任何的subset sum都不一样。
现在要求前10个最小的subset sum,能不能动态规划解呢?
g*******y
发帖数: 1930
48
来自主题: Programming版 - 问一个选区划分问题的复杂度
很简单的问题模型,N个选区,每个选区有m个人,每人投票给政党A或者B,你事先知道
了每个选区的投票结果,你想作弊,把N个选区划分为2个大选区,每个大选区由N/2个
小选区组成。你希望你所支持的政党在两个大选区都获胜(票数和过半)。
用更数学的语言讲,an integer set{m1,...mN},0<=mi<=m, partition this set
into two subset each with N/2 elements, such that the sum of each subset >=
N*m/4
这个问题是NP的? NPC的?或者有polynomial算法?
谢谢~
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)