k*n
发帖数: 150 | 1 第一题两两比较，可以每一对数少一次比较
找subset这个我不确定有没有比greedy更好的办法
不加预处理应该没有吧 |
|
d******a
发帖数: 238 | 2 some of them might be easy to give out idea, but a little hard to write bug-
free code.
1 merge-sort without recursion
we should use loop to sovle it. we could use loop to get n/2 sorted
subarrays, then n/4 sorted arrays...I think we should be careful to consider
the boundary conditions.
2 Find whether one string is a subset of another string (not need to be
contiguous, but order should match).
use the idea of hash, > is a pair. e.g. "abcaeaf", "aaf"
a 0, 3, 5
b 1,
c 2,
e 4... 阅读全帖 |
|
d****j
发帖数: 293 | 3 我就把所有technical的题罗列下来吧。很多都是常见题。
1. 给一个array of integers, 需要多少个comparison能找到min? how about min and
max? what's the best worst-case? (3n/2)
====>
n-1 comparison to find min
两两比较之后再在大的一堆中找大的，小的一堆中找小的
n/2 + n/2 - 1 + n/2 -1 = 3n/2.
记得MIT Algorithm (CLRS)上面有提到这个。
2. 怎么merge两个sorted的array，n 个呢？
====>
两个很容易，n个的话，用每个array的第一个元素构建一个heap，再heap sort，每挑
出一个值，再去对应的array中取一个值添到heap中。具体实现可能要修改数据结构。
3. 给一个tree，把同层的nodes都连起来，assume每个node都有个指针，你要让它指向
下一个同层的node。
====>
见 ihas1337code 的blog：
http://www.ihas1337code.... 阅读全帖 |
|
|
f*******4
发帖数: 1401 | 5 用DP可以解吗？用subset sum的方法一个一个解？ |
|
g*********s
发帖数: 1782 | 6
hash_set, or sort + binary_search.
sort + binary_search
external sort?
randomly generate 2 arrays;
generate two identical arrays;
generate two non-overlap arrays;
generate one array and all its subsets;
... |
|
|
j********x
发帖数: 2330 | 8 k is a fixed number... subset sum considers the case that k is not fixed,
which forces to explore all possible combinations.
I believe the complexity is n^(k-1) just guess |
|
F**********r
发帖数: 237 | 9 the problem is (subset sum), which is NP complete. So I suppose my solution
wasn't that bad? |
|
e*****e
发帖数: 1275 | 10 哇~~~不是吧
经典DP啊~~
subset sum....
The array can now be filled in using a simple recursion. Initially, for N ≤
s ≤ P, set
Q(1,s) := (x1 = s).
Then, for i = 2, …, n, set
Q(i,s) := Q(i − 1,s) or (xi = s) or Q(i − 1,s − xi)
for N ≤ s ≤ P. |
|
l*********r
发帖数: 674 | 11 来自主题: JobHunting版 - 一个面试题 如果所有数的和S，那不就是找个subset sum = S/2，不是NP么？ |
|
k*****7
发帖数: 72 | 12 找Maximum sum of non-conjoint subsets of a integer array,non-conjoint就是
说所选择的两个item在原数组中不相邻， 比如【1,2,3,4,5】，选5就不能选4，选3就
不能选
2,4。。。。这个case的结果就应该是9，选【1,3,5】. （全负数数组，取空集子集，
结果为
0）。
这道题给我的时候大概只剩10分钟了，我连第一版都没写完。。。。。请教谁有比较好
的解法？
实在很想抱怨一下，版里潜水很久了，看了很多前辈们的面经，但我phone interview
和on-site
的时候总是遇不到大家常讨论到的经典算法、经典数据结构或者其变形，比如BST，
HashMap，
LinkedList什么的，这些题我基本都能一次写对，有点tricky的变形题也能有思路，不
一定直接
就是最优但可马上写个解出来。可我实际遇到的，从第一轮电面起要么是很high level
的设计题要
么是繁琐的编程。。。都是fresh grad无工作经验咋待遇就不能一样呢？？？
提供最近遇到的其他一些还记得的题给大家参考，攒攒人品。倒是比上一个好... 阅读全帖 |
|
d*****o
发帖数: 28 | 13 The question is hard and challenging, although it's hard at first, if you
can learn from it, you will have a good result.
your rp will accumulate and more chance in the future you will get easy
question.
>> Maximum sum of non-conjoint subsets of a integer array,non-conjoin
Is a DP problem
>> 1.实现文本（以String形式）在一定宽度的窗口散列对其（在本行内所有单词间均
匀的 增加空白
is also DP
>>3.设计一个购物网站中的“购物车功能”，支持大量用户，用户购物流程不一定，可将
商品加入或移出
自己的购物车，要求可靠性和“结账”时迅速响应。用什么数据结构，系统怎么设计以
满足可靠性和快
速响应，每个用户的“购物车”数据存储在哪里，这样设计的优点缺点trade off
is ve... 阅读全帖 |
|
b******e
发帖数: 432 | 14 没想到自己的帖子上了首页，攒RP，发发小公司面经，还有自己自找工作以来的一点经
验。
之所以另开一帖，并在名字中点名公司名称，主要是为了大家搜索方便。
有些公司面过很久了，有些题目可能记不全了，先从全的开始吧。
1 consilience software
第一轮的30分钟technical面试。大概问了20-30道题吧。打通电话，紧接着就是一个又
一个的
面试问题，问的很快很多。我下面记录的只是部分jot down的题目，可能不是很全。能
在25分钟
之内问这么多问题，大家可以想象他家的面试了。。。
关于java的，大家上网搜索“java interview questions”，大概有100道左右，把这
个看完
了，就没有问题了。比方说，abstract class 和 interface的区别， checked and
unchecked exception, overriding, overloading, iterator, synchronize,
immutable object, mutiple threading, dead lock, collection, fin... 阅读全帖 |
|
j**y
发帖数: 462 | 15 Find a pair of numbers that sums up to zero (or any other number), then
find three (and then four) numbers that sum up to zero
有什么好的方法？ 多谢 |
|
j**y
发帖数: 462 | 16 俺只会把所有3个数或4个数组合列出来
有啥好办法？ |
|
|
j**y
发帖数: 462 | 18 找了半天也没找到下面算法
There is a simple algorithm to solve 3SUM in O(n2) time.
有code吗 多谢 |
|
j**y
发帖数: 462 | 19
public static int count(int[] a) {
int N = a.length;
Arrays.sort(a);
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
int k = Arrays.binarySearch(a, -(a[i] + a[j]));
if (k > j) cnt++;
}
}
return cnt;
} |
|
g**e
发帖数: 6127 | 20 this is O(n^2*lgn). there is o(n^2) algorithm.
use head and tail pointers in your second loop to do the search. |
|
|
g***s
发帖数: 3811 | 22 函数不单调，这个方法不对。
不过，如果是这个理解的话，全算一遍也是O(n）啊。
难的是subset |
|
|
g*****k
发帖数: 623 | 24 如果允许负数，应该是指对数没有限制吧，没有限制的话，subset就是指数级的啦。 |
|
g*****k
发帖数: 623 | 25 不觉得a1+a2=a3+a4就能保证这4个数分在两个subsets中。 |
|
d*******l
发帖数: 338 | 26 我觉得这个做法正确性应该是没问题的，相当于是背包问题的一个变化。不过背包问题
本身就是NP问题，上面说的也没错。
程序有点小问题，第二维是subset的和的话，开max(a)是不够的，应该是想写sum(a)吧
？不过这个方法简单易行，真要是面试的时候就它了 |
|
g******0
发帖数: 221 | 27 2 numbers sum up to k is simple.
How to find 3 numbers sum up to K?, 4 numbers sum up to K? 5 numbers
etc...
How to find a subset of numbers that add up to K?
What's the running time? |
|
v***n
发帖数: 5085 | 28 不是
A是一个坐标的Subset
比如B是实际的数据库 A是传入的参数
根据参数取出一个路径啥 |
|
v***n
发帖数: 5085 | 29 One of the best reviews online (not from glassdoor though)
From Verona, WI — 11/14/2008
I worked at Epic for 7+ years as a developer. Left the company roughly
4 months ago.
Pay: I more than doubled my salary in my 7+ years. Starting pay was
so-so but thru nice raises, I quickly felt like I was well
compensated.
Respect: I respect the vision of the company. Being privately held in
this industry is a huge competitive advantage as Epic can really put
the patient and customer ahead of the shareholde... 阅读全帖 |
|
g*****i
发帖数: 2162 | 30 第五题line sweeping里面说"This range can be extracted from the sorted set in
O(log N) time". 这是不是代表java里面TreeSet.subSet()能在O(log N)实现?具体是
如何实现的你知道吗? 谢谢 |
|
g*****i
发帖数: 2162 | 31 第五题line sweeping里面说"This range can be extracted from the sorted set in
O(log N) time". 这是不是代表java里面TreeSet.subSet()能在O(log N)实现?具体是
如何实现的你知道吗? 谢谢 |
|
|
|
d*******d
发帖数: 2050 | 34 这不是dp coin问题,这是subset sum问题,经典的NPC问题. |
|
|
d*******d
发帖数: 2050 | 36 这不是背包问题,这是subset-sum问题,是npc问题. |
|
h*********n
发帖数: 915 | 37 given array X and target t, find k elements in X such that sum {X[i]|i=1~k}
= t.
k = 2, 3 is classical
k = 4 sometimes is asked too
how about k = 5, and any given constant k? any general solution and what's
the complexity with respect to k? |
|
j********x
发帖数: 2330 | 38 find all n(n-1)/2 combinations of two numbers, put them into a hash-table.
Now look for two number in this hash-table that sums equal to k.
We can always follow such pattern, if we are asked to find m numbers that
sum up equals to k, can be solved using hash-table with
O(n^ceil(m/2)) time and space complexity |
|
g**********y
发帖数: 14569 | 39 基本想法：把Element映射到数字，然后用Bitmap来计算包容关系。
pesudo-code =>
foreach set in sets {
Bitmap b1 = transform(set);
boolean add = true;
foreach b2 in map.keySet() {
Bitmap b3 = b1.and(b2);
if (b3.equals(b2)) {
bitmaps.remove(b2);
}
else if (b3.equals(b1)) {
add = false;
}
}
if (add) map.put(b1, set);
}
return map.values(); |
|
r*******y
发帖数: 1081 | 40 So it is using hashing. But how to do hashing here is also a big deal, right
?
Thanks |
|
x****3
发帖数: 62 | 41 http://www.careercup.com/question?id=3190687
How do you partition an array into 2 parts such that the two parts have
equal average?...each partition may contain elements that are non-contiguous
in the array.
老看到这道题， 一直想不出比较简洁的解法。能想到的就是穷举所有的subset，计算
比较。 |
|
c****x
发帖数: 61 | 42 这是NPC，看着不像真的面试题
subset sum can be reduced to this problem
contiguous |
|
B*******1
发帖数: 2454 | 43 Given an array of strings of 0s and 1s. X and Y are also given. Return the
maximum number of elements in a subset of the array elements which will X
number of zeroes and Y number of 1s when combined. For eg: if array[] = {"01
", "10", "0", "110"} X=3, Y=2
Answer should be 3 since first 3 strings when combined will give the
required number of 0s and 1s.
这题是不是要用dp啊。 |
|
g*****i
发帖数: 2162 | 44 partition problem变种,应该可以用subset problem的dp solution来做,wiki上说的.
greedy方法的approximation factor是4/3,很接近了.
楼主我觉得你老是钻研这种难题没啥必要,面试这种题目出现的概率极低,出了面试官也
会引导你的. |
|
h*********e
发帖数: 91 | 45 不好意思来晚了， 朋友最近度假了，一直没发给我职位描述，他也还没来得及看简历
，现在终于发来了，更新一下，想申请的人发email : t********[email protected]
Technical Support Engineer
In this exciting role, you will be part of the Premium Services global
organization with an emphasis on collaboration and customer focus. You will
be responsible for interacting with a subset of PTC’s largest most
strategic customers that require the highest level of service PTC offers.
Technical Support Engineers in PTC’s Premium Services group are experts in
one or more line of pr... 阅读全帖 |
|
c**j
发帖数: 103 | 46 ding! Can we do it without sorting??
请问Bayesian1， 还有link没？
加个条件： 这个题如果还要要求 答案是*连续位置的*的subarray呢？
e.g.:
input: 4,5,1,5,7,4,3,6,3,1,9
sort以后1，1，3，3，4，4，5，5，6，7，9
output{5,7,4,3,6}
check careercup:
http://www.careercup.com/question?id=11256218
Microsoft Interview Question about Algorithm asm on October 19, 2011
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
39
http:/... 阅读全帖 |
|
c**j
发帖数: 103 | 47 这个表面简单的题Goolge MS 都考了啊。干脆发给新话题吧，还请大牛们指教啊
2个variation
MS 要求连续位置，考虑duplicate，DP， divide conquer, sort 貌似都有难度。。
Google 没有要求连续位置，简单不少，但是不让sort。。。。。又难回去了
check careercup:
http://www.careercup.com/question?id=11256218
Microsoft Interview Question about Algorithm asm on October 19, 2011
you have an array of integers, find the longest
subarray which consists of numbers that can be arranged in a sequence, e.g.:
a = {4,5,1,5,7,4,3,6,3,1,9}
max subarray = {5,7,4,3,6}
39
http://www.careercup.com/question?id... 阅读全帖 |
|
g**********y
发帖数: 14569 | 48 check a number wether in a hashset is O(1). what is that n*R.size*logm?
Since you are possibly printing out 2^n subsets, there's nothing you can do
to reduce that 2^n. |
|
n*******w
发帖数: 687 | 49 一个distributed database，各个host上都只保留了所有数据的一个subset。
现在要在每个host上restore所有数据。也就是对于每个host，把missing的数据从其它
host copy过来。至于选哪一个host，没有要求。
assume 所有host上数据的union就是整个database。
input是
host 1: 1 3 5
host 2: 2 3 4
host 3: 1 2 4 5 6
一种可能的output是
copy 2 from host 2 to 1
copy 4 from host 2 to 1
copy 6 from host 3 to 1
copy 1 from host 1 to 2
copy 5 from host 3 to 2
copy 6 from host 3 to 2
copy 3 from host 1 to 3
所有input要从stdin输入。
跟上一题同样的，最难的不在算法，而是短时间内写出code编译运行出正确结果。这题
可能还需要点数据结构。 |
|
|
