g**G
发帖数: 767 | 1 Sieve of Eratosthenes 已经很好了，如果只是面试，这个应该足够
再优化可以看看其他的sieve方法，在wiki下面有 |
|
n****n
发帖数: 568 | 2 but how do we find N to make sure the k-th prime is less than N? |
|
|
|
l*****s
发帖数: 774 | 5 第二种方法的话是不是 对于一个数 k，验证它是不是prime number，从 sqrt(k) 往小
的方向循环，一直循环到2，如果中间有可以整除的数字，立即break，这样的复杂度很
大吧。谢谢
不知道二爷是否可以贴个code来看看 |
|
p*****2
发帖数: 21240 | 6
大牛看看对不对
int findPrime(int count){
ArrayList al=new ArrayList();
int i=1;
loop:
while(count>0){
i++;
for(int j=0;j
if(i%al.get(j)==0){
continue loop;
}
}
al.add(i);
count--;
}
return al.get(al.size()-1);
} |
|
l*****s
发帖数: 774 | 7 惭愧，俺是半路出家的，
这样把所有都找过的 prime number都存起来，不浪费空间吗？谢谢
这个复杂度算是多少？谢谢 |
|
|
|
p*****2
发帖数: 21240 | 10
按照原题，空间直需要几M, 很少，时间大概2-3秒，很快的。我是在mac上测试的。 |
|
p*****2
发帖数: 21240 | 11
大牛有整出了没听说过的算法了。有时间学习一下。 |
|
u*****o
发帖数: 1224 | 12 二爷我想问问你的CODE中
loop:
...
... continue loop;
这种CONTINUE IN OUTER LOOP (while loop NOT the for loop)C++里可以这么用吗？
就是自己DEFINE SKIP后从哪里ITERATE。。我搜关键字没搜出来，我一直不清楚这种
CASE这么处理，机缘巧合竟然在这道题里看到这么用了。。 |
|
|
u*****o
发帖数: 1224 | 14 最近这道题很火爆！我找来貌似最EFFICIENT的CODE看（就是传说中的SIEVE OF
ERATOSHENES，多高端的名字！！），发现这么一行
请大家看第三行，第四行。。。为什么要用MEMSET这个function呢。。bool
array的话默认就是0吧。。。是不是为了省MEMORY呢？我直觉是。。。
走过路过的牛牛们指点一下吧。。。
void runEratosthenesSieve(int upperBound) {
int upperBoundSquareRoot = (int)sqrt((double)upperBound);
bool *isComposite = new bool[upperBound + 1];
memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
for (int m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite[m]) {
... 阅读全帖 |
|
|
|
|
r*********n
发帖数: 4553 | 18 upperBound是什么？比如让你找第999个prime number，你怎么确定upperBound呢？ |
|
|
r*********n
发帖数: 4553 | 20 999/N = 1/lnN
这还要数值解一个超越方程，还不如用简单的primarity testing了 |
|
r**h
发帖数: 1288 | 21 the guys in GOOG will ask you to provide the upper bound otherwise you'll be
rejected lol |
|
r*********n
发帖数: 4553 | 22 那只能说运气衰了
PS: 用简单的primarity testing，可以把已经找到的prime都存到一个hash set里面，
然后当set.size()==k的时候就停止。
be |
|
s**x
发帖数: 7506 | 23 今早突然想到， 仍然用筛子， 原先是用一个数去筛掉所有不是的， 你可以建立一个
已经得到的素数的 vector, 然后对每个数用这个 vector 的数来除就可以了。
vector primes;
primes.push_back(2);
for (int i=3; primes.size() < K; i+=2) {
bool isprime = true;
for(int j=0; j < primes.size(); j++) {
if (i % primes[j] == 0) {
isprime = false;
break;
}
}
if (isprime) primes.pushback(i);
}
return primes[K-1]; :) |
|
|
|
|
w**x
发帖数: 362 | 27 传统的 SIEVE OF ERATOSHENES
Time complexity 怎么分析？ wiki 是 nloglog(n) |
|
l******l
发帖数: 1088 | 28 两个组，第一个组周五电面，暂时没下文了。
1. return the kth last nodes from a linked list
2. given an array, return k most occurring numbers
what if data is huge that have to distribute to multiple machines(use
redundant for backup)
3. how to uniquely serialized and reconstruct a binary tree
第二个组没有电面，manager直接叫过去onsite(周二)，周三去跟director谈了谈，今
天offer到手，除了跟manager闲聊一共四轮。因为cisco都是老系统，所以全部用的c
1. reverse a string using recursion加上一些闲聊
2. 一共问了5-6个题，都很简单。有些记不起来了。。。有不用/实现除法，倒序输出
一个linked list之类的。比较雷的是不要求最优解法，只要写出来对就可以了。。。... 阅读全帖 |
|
k*******t
发帖数: 144 | 29 这个方法还是linear的。突然想起来有个求kth element of two sorted elements的题
, 比较优的方法用binary search的方法做的，感觉可以借鉴binary search的方法。不
知是否好点啦。 |
|
H********e
发帖数: 130 | 30 面经：
Autodesk Interview(Failed)
Phone 1: java foundations
Phone 2: product manager, research, java foundation, composition vs
inheritance. find time interval
Phone 3: test my javascript background
Bloomberg Phone interview(failed)
C++ basics.
(Selection Algorithm)find kth element in array
ZEFR:
Contacted by HR, given a 60 min online test: finished only 8 out of 14
questions, failed.
Epic:
Phone1: Ask about background, previous project, introduce for epic, Q/A, etc
Assesment:
20 math;
Intro new pr... 阅读全帖 |
|
f*********d
发帖数: 140 | 31 dp[k][c]: the optimal solution of painting the first k houses where the
kth house is colored with color c.
dp[k-1][1, C] => dp[k][1, C] transition cost can be reduce to O(C) |
|
l*******0
发帖数: 63 | 32 想出两种思路，都是O(N)的time复杂度。请看注释。
public class HelloWorld{
//Idea：put every element into its right position. which means input[i]
is placed at input[i]-1. Then if input[i]==0, then i+1 is one missing
number.
//this approach modifies the original array.
//O(N) time
public static void printMissing(int[] input){
for(int i=0;i
while(i+1
swap(input, i, input[i]-1);
}
... 阅读全帖 |
|
p*****3
发帖数: 488 | 33 来自主题: JobHunting版 - 周末上道题 给一个很大的maxHeap, size n, 数组形式表达，array A
给一个k+constant的数组 Array B，constant<< k << n
求kth max in maxHeap，不能改变maxHeap (Array A只读) |
|
s*******n
发帖数: 305 | 34 来自主题: JobHunting版 - 周末上道题
两位大大， 能不能在多说点， 没太明白。
a 为不可写的， 那就没法多次取max?
b 和 a 有重复吗，每次把b中max和a相同的数的孩子放到b中：
1. b中的max不一定是a中的max呀？怎么保证取到a的kth max?
2. 每次把孩子都放到b中， 会不会overflow, 因为b的size只有k+constant, constant
<
操作完后，就是b.size()+1了？
我的确没有理解， 请多讲讲， 谢谢。 |
|
a********m
发帖数: 15480 | 35 来自主题: JobHunting版 - 周末上道题 “求kth max in maxHeap”，所以只考虑a里面的内容，b是空的。
1。a不改变，所以b只需要存a的index就可以了。最开始只有一个值，0，表示a的第一
个元素，最大值。
2。每次把b里面第一个元素取走，添加这个元素在a里面的孩子，最多两个，所以每找
到一个数字b最多增加一个。取k个数字以后b里面元素不可能超过k+1.
constant |
|
S********t
发帖数: 3431 | 36 来自主题: JobHunting版 - 周末上道题 这跟一道两sorted数组求kth pair sum异曲同工吧？ |
|
D**********d
发帖数: 849 | 37 如果 size 相同的好办一点。不相同得加不少判断，例如是否有空 array etc. 不过原
理一样，深化为找 kth element 的问题就好办了。O(lgN), 不过每次大约能去 k/2。 |
|
s**x
发帖数: 7506 | 38
俺的思路是用 find kth largest in 2 sorted array.
Binary search on the smaller array, time is O(lg(min(m,n)).
The key is the same, you can verify a candidate in constant time.
Just need to make sure index does not go out range. |
|
n****e
发帖数: 678 | 39 kth smallest number of two sorted array
binary tree post-order traversal with iterative method |
|
a********9
发帖数: 129 | 40 之前稍微收集了一下
glassdoor
===================
edit distance
level traverse tree(高频）
1) Calculate the square root of a double（高频）
2) Given n intervals [si, fi], find the maximum number of overlapping
intervals.
3) Print all the paths from root to every leaf in a binary tree.
4) Print the sum of all the numbers at every vertical level in a binary tree
5) 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 ?
6) Given 1 trillion messages ... 阅读全帖 |
|
e******g
发帖数: 51 | 41
sorted
6,
the&
假设数组是A[n], B[m], n > m
if k > m + n return -1
else 对A[1:min(k,n)] 和 B[1:min(k,m)] 递归二分查找 |
|
n******f
发帖数: 318 | 42 O(Logn logm),最优解法，leetcode上有。
给A一个指针i，给B一个指针j。binary search，i,j初识化为k/2吧，如果，越界，适
当调整。比如其中一个取数组上限m，另一个取k-m。
如果A[i]
else if A[i]k, j= (j j-(i j-1))/2;
Else if A[i] >= B[j] and i j<=k, j=(j j-(j i-k-1))/2;
Else i = (i i-(i j-k-1)/2);
Repeat this process until i and j keep stable;
If (i j = k) return max(A[i], B[j]);
Else return min(A[i], B[j]);
Ipad打字真累，求轻拍。
一句话，就是找到两个数组的一个指针，使左边个数和等于k。 |
|
|
|
|
w**7
发帖数: 22 | 46 find median of two sorted array |
|
|
s**x
发帖数: 7506 | 48
Right, but a little more code that what leetcode site has.
The idea is do binary search in the array
A[0 .. Min(m,n,k)] |
|
c**y
发帖数: 172 | 49 Looks the best solution. This answer reminds me of an example my professor
gave in Algorithm class. In general, finding the kth element can be achieved
using a heap, which leads to an algorithm of O(n log k). However, finding
the 2nd elem can be done in 2n steps, and further be reduced to n + log n as
described below. |
|
B****D
发帖数: 132 | 50 Assuming that K is O(N), the best solution is O(N). It uses a modified
special binary search to find the Kth largest sum. After that you can
iterate all pairs.
If K is O(N^2), the best solution would be O(N^2) since you must iterate
through all K solutions. |
|
