m*****w
发帖数: 3 | 1 - offer 1
第一个offer来的很突然。我的一个同学跟我说他的一个朋友的公司在招人，就问我要
不要试试，说人家prefer C++比较熟悉的。我就投了简历。
该公司是一个200人左右的小公司，位于长岛附近。在投了简历后第二天，人家就直接
打电话来面试我，问了大概一个多小时，涉及C,C++，算法还有网络，记得很清楚的是
人家要求我说qsort的四个参数分别是什么，还有TCP的滑动窗口的算法如何实现。我觉
得答的不错，果然，两个小时后就接到onsite的消息。
第二天就去了该公司，该公司给我安排了9个人面试，从早上9点一直面试到晚上5点。
都是上个人还没结束，下个人就在门外等了。这个公司给我的印象不是很好，每个面试
的人问的问题都非常的细，细到每个小函数都要你在黑板上写完，连一个分号错误都会
纠正。问的问题不难，但是都需要你从头到尾写完。我一天就站在黑板面前没有移动过
。5点的时候，本来以为可以走了。最后一个人送我到门口，我都要走了，前台跑过来
说，CEO要见见我。
CEO是个很慈祥的中年人，他说我did a good job today，所以很有可能给我offer。然
后问了我一 |
|
p*******g
发帖数: 2 | 2 onsite后的三天，终于拿到了这个offer。
WISC
78k
没有啥面经，一共两轮电话，一轮做题，然后onsite。
onsite太搞笑了，就是带大家兜风，没有问任何技术问题。
记得的问题有：
database的基本概念，什么是join，什么是B+ tree
algorithm的基本概念，qsort的原理以及复杂度分析。
C++，什么情况下vector的search比map好
Design Pattern,什么是singleton，如何实现
不知道还有没有人记得我以前发的帖子，说manager提醒我我的H1B是不能保证的，要看
我的表现而定。然后我从那开始找工作，一个月了，手头有offer两个，那一个在WI。
打算把手头的事情整理一下，然后就和他们byebye了，让他们去找愿意为了H1B而拼命
加班的人吧。
希望板上的xdjm们找工作顺利。 |
|
g********e
发帖数: 1142 | 3 刚刚onsite归来。
昨晚的飞机，ny大雪，delay了两个小时。入住hotel，很小的一间房子。。。
吃了顿比较奢侈得早餐后，check out，走去那个大楼。
上午10点开始，一个小时零10分钟的技术问题后，交代我坐着等一会儿，下个人马上过
来。谁知一会儿后，小米来说大头开一个big meeting不能来。之前联系的hr也没来，
今天全部结束。我顿时觉得不妙，感觉很差，不知结果如何。
技术问题，是两个工程师，一个senior，一个junior。senior的那个连珠炮，一刻不停
的问。头一次被问这么细致的C问题。从 static，word size，stack，procedure
frame，heap，process，thread(safe否，什么情况不用thread用process)，memory和
process关系，file descriptor，malloc失败原因，customized new。同时也问了数据
结构的问题，包括hash_table，bst，heap，hash失败，为什么实际中往往用bst而不用
hash表，hash表的弱点。sort部分问了qsort和h |
|
w********p
发帖数: 948 | 4 类似qsort要用O(nlogn) space, merge sort要用O(n) space, 不合要求
有关array shift, rotate 的操作running time 是O(n), 也不合要求
用linked list O(n)running time 和 O(1) space
1, you have a linked list for {1，5， -5， -8，2， -1，15 }
2. remember the original linked list head, scan all note one by one, if
the
number is negative, remove it from the original liked list, and put it to
new linked list, you will get
1, 5, 2, 15
-5, -8, -1,
3. link the tail of second linked list to head of original linked list
-5, -8, -1, 1, 5, 2, 1 |
|
t******e
发帖数: 1293 | 5 http://www.careercup.com/question?id=296729
Give two parking locations P1 and P2, P1 and P2 both have n slots. n-1 cars
with same IDs are parked in n-1 slots in both P1 and P2. Design an algorithm
to let n-1 cars in P1 and P2 park in the same slots
看了小尾羊的回复，还是没有很清楚。
首先题目的意思不是很明确，我的理解是每次只能动一辆车，只能把车移动空位上去。
以下面的例子为例
P1: 1 3 _ 4 2 5 先把 _ 移动最后 --> P1: 1 3 4 2 5 _
P2: 2 5 1 4 _ 3 --> P2: 2 5 1 4 3 _
分别对P1和P2进行qsort，假设_的取值等于(n+1)/2 + 0.5，也就是3.5，这样，我们分
别对P1和P2扫描并且交换，一趟之后，分别如下：
P1: 1 3 2 |
|
w*****e
发帖数: 197 | 6 I think you can no better. Consider following algorithm:
Extract the n/3 and 2n/3'th elements from each row.
You have altogether 2n elements. Do a pivot operation
(refer to qsort for details), and by some clever bookkeeping,
you can determine whether your target value is in
the first, middle or the last n/3 elements in each row.
So basically speaking, you pay O(2n) time, but you trim your
size by 1/3. Solving this recursion gives a linear time
search!
I am really proud of myself for solving this |
|
k*n
发帖数: 150 | 7 qsort的确应该20分钟内写下来吧。。。这么经典的东西，呵呵。。。 |
|
k*n
发帖数: 150 | 8
like qsort partition
keep a counter of past steps, change the num to current num in 1/step
probability
下楼梯问题是啥。。。 |
|
b******v
发帖数: 1493 | 9 就是用qsort的思想，找到第k小的元素，并partition
时间复杂度平均是O(n) |
|
r****o
发帖数: 1950 | 10 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: roufoo (五经勤向窗前读), 信区: InterviewHackers
标 题: The time complexity on finding the kth largest element in a
发信站: BBS 未名空间站 (Tue Jun 1 22:42:09 2010, 美东)
We can use the partition() in qsort. Each time, we can partition the array
into two parts, array_a and array_b. Let the number of elements in array_a
and array_b be sa and sb, respectively.
If sa is smaller than k, then find the (k-sa)th largest element in array_b;
If sa is larger than or equal to k, then find |
|
j*****g
发帖数: 223 | 11 For the sorting w/ k elements problem, it's easy to achieve O(n) time
complexity and O(1) space complexity by using counting/frequency sort:
step 0: initialize counting/freq array k, where k0 ... kn elements can be
indexed into 0 to n of the array. And array is initialized to be 0.
step 1: scan the array, and for each a[i] do k[a[i]]++;
step 2: rescan the array and put final sorted element back in.
count = 0;
for (i = 0; i < k; i++)
for (j = 0; j < k[i]; j++)
a[count++] = i;
(a bit simpli... 阅读全帖 |
|
c******n
发帖数: 4965 | 12 I think you guys can stop wasting time on this,
if merge sort O(n) time O(1) space is possible, no one would use qsort
in ur step 2)
": 2，把前n个数的块和后m个数的块，做merge，用最后一个sqrt(n + m)大小的块做
swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。"
why is "空间复杂度是O(1)" ? the "swap" space u use, isn't it already
occupied by the last sqrt(n+m) block? even if u can use that block, it's
size sqrt(n+m)
的块。这样最多有sqrt(n + m)个块。
swap空间。这样下来的时间复杂度是O(n + m)，空间复杂度是O(1)的。
复杂度是O(1)的。
答。 |
|
s*********t
发帖数: 1663 | 13 heap sort很常用，比如找top k，动态的，就可以开个k size的heap
merge sort我在搜索引擎的应用里用过，搜两个关键字，索引返回两个集合，这时候需
要合并。 这两个集合应该是有序的，此时只需要merge sort的merge即可。
qsort很省事，一般的排序，算法题目，都可以使用。 |
|
f****g
发帖数: 313 | 14 My algorithm for this question is:
Assume there is a set of points on the plane S = {P0, P1,..., Pn-1}
maxNumOfPoint = 0
for(i = 0; i < n; i ++)
{
for( j = 0; j < n; j ++)
{
if(i == j)
{
slope Ki = 0;
}
else
{
Calculate the slope between Pi and Pj: Kj = (Yj-Yi)/Xj-Xi;
}
}
qSort(K0,...,Kn-1);
Find all the points with the same slope M;
if( M > maxNumOfPoint)
{
maxNumOfPoint = M;
|
|
r*********s
发帖数: 2157 | 15 using "void*" in C is the only way to get polymorphism.
你看看有些function, 比如 qsort(void *arr, int..)就理解了 |
|
j****a
发帖数: 55 | 16 就算是平均complexity也不可能是LogN吧？像qsort run一个iteration也要O(N)啊？
请指教... |
|
|
j*****g
发帖数: 223 | 18 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
j*****g
发帖数: 223 | 19 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
w*********s
发帖数: 277 | 20 我现在有一些keyword和keyword所对应在文本中“出现的次数”
如何使用二维数组来对“出现的次数”进行降序排列，输出打印结果呢？
用的是perl，需要速度比perl自带的sort()要快。perl里面的sort()是qsort。
请指点！
谢谢！
5个包子！ |
|
j*****u
发帖数: 1133 | 21 比qsort要快就是O(n)了，如果你知道“出现的次数”不超过某个值可以用基数排序
e.g.如果max=1M，开个1M的string array A，对keyword k如果出现n次，A[k] = n
scan一遍完就排好序了
如果有重复的，可以用数组或者链表作为数组中的元素 |
|
f****g
发帖数: 313 | 22 Hey, todayzj
Could you share the link for the discussion? I tried several key words, and
but
I still cannot find it..
I think without the constraints of keeping the same order of the elements,
it
is easy to be done in O(n) time and O(1) space ( refer to the implementation
of
qsort) |
|
f****g
发帖数: 313 | 23 I got it.
First round, place all the positive numbers in fronts of negative numbers. (
refer the implementation of qsort pivot placement) O(n) time
So the positive numbers are in order and negative numbers are in reserved
order.
Second round, swap the negative numbers to put them in order. O(n) time
Over all it is O(n) |
|
J******8
发帖数: 132 | 24 The question is not hard. But I missed two key points.
The details below.
==========================================================
/*
example
char *words[] = {"foo", "bar", "baz", NULL};
setup(words);
1) First step:
isMember("foo") -> true
isMember("garply") -> false
2) Second step:
isMember("f.o") -> true
isMember("..") -> false
*/
#include
#include
#include
char *words[] = {"foo", "bar", "baz", "caz","cat",NULL};
int num=0;
void print_words(void)
{
int i=0... 阅读全帖 |
|
c******n
发帖数: 4965 | 25 Divide and Conquer 做法要从min point 分开， 这个导致只有平均情况才能 nlog(n
)
吧？ 跟qsort 一样
其实那个O(n) time 的stack 做法倒是更natural 一些 |
|
c********0
发帖数: 112 | 26 用qsort? 每次把大于Pivot的flip到后面？ |
|
e********s
发帖数: 248 | 27 1. Recoding the characters:
ABBFKCEDG => A B B FK C EDG
012345678 -2 -3 -3 34 -1 678
'B' => -3
'A' => -2
'C' => -1
2. Then use the regular qsort. |
|
c**y
发帖数: 2282 | 28 那天本版有人说的我觉得挺有道理：如果一样的水平，EE面试写不出qsort没关系，CS
写不出来就废了。 |
|
M******n
发帖数: 164 | 29 问题是ECE的别人根本不给你写qsort的机会。
CS |
|
d*****o
发帖数: 28 | 30 Thanks for sharing.
for q 1, if there are 4 numbers, does DP work better than Hash table?
for Q2: use DP, one dimensional array to keep the min accumulate sum for
current level. iterate through all the levels to get the min value.
For Q3: without using heap, but use the same partition approach as qsort. |
|
d*****o
发帖数: 28 | 31 Q1: three numbers, use qsort, the time complexity is O(N^2).
Q3: for each 2K elements, use partition, so the first k elements must be the
first k elements in the final result, just disordered. use count sort to
sort the first k elements. for k+1 to 3k, do the same.
Total complexity is O(n). |
|
d*****o
发帖数: 28 | 32 array: 2 4 1 3
k = 2
qsort partition:
21 43
count sort:
12 34 |
|
x***n
发帖数: 70 | 33 q1：请问DP应该怎么写呢？非常感谢
for
qsort. |
|
n**z
发帖数: 155 | 34 Java? Arrays only have a sort function |
|
n**z
发帖数: 155 | 35 static void sort(Object[] a)
Sorts the specified array of objects into ascending order,
according to the natural ordering of its elements. |
|
S**I
发帖数: 15689 | 36 #include
#include
#include
struct StringCount{
char s[100];
int count;
};
int compare(const void * a, const void * b){
return ((*(struct StringCount *)a).count < (*(struct StringCount *)b).count);
}
void printSortedWords(char * s, FILE * file){
int size = strlen(s);
struct StringCount sc[100];
int num = 0;
char newstr[100];
int i = 0;
for(; i < size; i++){
if(s[i] != ' '){
int j = 0;
while(s[i]... 阅读全帖 |
|
B*******1
发帖数: 2454 | 37 这哥们写的code也挺难学的，其实不就是qsort就好了？ |
|
a********1
发帖数: 750 | 38 主要是要用step＊2比较suffix
直接qsort 的复杂度是n^2 logn ， 因为sorting nlogn, 每个compare是n |
|
q****x
发帖数: 7404 | 39 theory vs practice.
in theory qsort is O(N^2) in worst case. so? |
|
d*******l
发帖数: 338 | 40 我现在觉得面试要考察的有知识的掌握，临场应变，交流沟通能力，背景的匹配程度等
多方面，解算法题只占一小部分。像楼主说的那些问题都是边界比较多的，快速写出来
全无bug非常困难，三分数组要是在平时我一定倾向于用两次典型的qsort的partition
来做到，这样不容易出错。atoi我也不会一上来就处理溢出。
我现在觉得算法水平在所有人中达到90%就不错了，再往上提高很不容易，还不如用来
准备design或者是别的问题。临场的时候能展现出真实水平我就很满意了。 |
|
|
s****a
发帖数: 528 | 42 qsort 的话如何 randomize pivot 呢？ |
|
b*****c
发帖数: 1103 | 43 qsort 取pivot的吧，一般不用random的，花销大 |
|
b******v
发帖数: 1493 | 44 按你说的规则定义一个新的比较函数。然后用qsort按这个比较函数排序。O(n logn)
in average.
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
P***P
发帖数: 1387 | 45 qsort最好上点median of 3， 还要注意array有重复的情况 |
|
w****o
发帖数: 2260 | 46 来自主题: JobHunting版 - 一道面试题 对，排序后，就是O(n)了。我自己写了一个，应该是对的。不过有点儿ugly.
typedef struct {
int start;
int end;
} Interval;
int intcomp (const void * p1, const void * p2)
{
return *(int *)p1 - *(int *)p2;
}
Interval find_interval_cover(int a[], int N, int L)
{
Interval result;
int i, j;
int count = 0;
qsort(a, N, sizeof(int), intcomp);
print_arr(a, N);
for (i = 0, j = 0; j < N; ) {
if (a[j] <= a[i] + L) {
j++;
} else {
if (j- i > count) {
c... 阅读全帖 |
|
l*****a
发帖数: 14598 | 47 不会DP
就用求组合的常规办法吧
qsort(a,0,size-1);
void getCombination(int a[],int size,int target,int start,vector&vec)
{
if(target==0) { ... return;}
for(int i=start;i
{
if(a[i]
vec.push_back(a[i]);
if(i
vec.pop_back();
}
} |
|
l*****a
发帖数: 14598 | 48 qsort(a,0,size-1);
void GetPermutation(int a[],int size,int start)
{
if(start==size) {...;return;}
for(int i=start;i
{
if((i!=start)&&(a[i]==a[i-1]) continue;
swap(a,start,i);
GetPermutation(a,size,start+1);
swap(a,i,start);
}
} |
|
n********k
发帖数: 40 | 49 国内数学本科，新加坡计算机博士，读到第三年末不想读了，开始找工作。找了一年，终于找到了脸书，
这里面的起伏辛酸相信大家都明白的。如果按照投简历算的话，我找了将近五十多个工
作吧，一开始找的都在新加坡，大家应该也没什么兴趣，我就抛出几个小结论吧：1.
amd ibm都是sb公司，你们懂的；2.我这种情况脸书给了我offer，但我就是无法在新加
坡找到SGD4000（相当于美元3300）一个月的工作，不得不感叹这里人工成本太低；3.
这里的公司更看重马上就能给公司创收，所以会要求新毕业的学生懂很多具体的技术啊
语言啊。
1.NV总部。
>事实：我博士是做GPU的，所以加入NV一直是我的理想。我傻到第一份简历就投给了NV
，然后去年九月拿到了我这辈子第一个电话面试，可想而知，被拒。
>题：讲讲你自己；讲讲这一个你做过的项目；你给我讲讲shared memory是什么，应该
怎么用；你给我讲讲atomic operation是什么，怎么用；你会什么语言，各个语言的自
信程度；C++里面的virtual function是什么，pure virtual function是什么；你用过
C++ S... 阅读全帖 |
|
s*******f
发帖数: 1114 | 50 哈哈。挺伟大的公司，我是去不了。
leetcode比面试题难，假设对于比leetcode简单的基本功bubble sort, qsort啥的，你
也扎实
，我想只剩下design了。 |
|
