s******o
发帖数: 2233 | 1 use qsort like partition |
|
f*****o
发帖数: 95 | 2 recruiter 会给一个大概要复习的范围，诸如要掌握一两个nlogn 的sorting(merge &
qsort)
binary tree traversal, red-black or avl-tree, graph msp, np etc, 电面咱的时
候考官花大概十分钟介绍他的project，然后大概十来分钟跟咱聊咱以前和现在的项目
，最后让咱logon google doc, 用C十十写螺旋输出一个方矩阵的毎个值，从没见过，
一下傻眼，一时也想不出好的方法，就用最傻的for loop 嵌套plus if-then-else, 坑
爹的iPad+google doc+disturbing spell correction使得C十十coding very
difficult, 折腾了一阵，考官说很close 了，时间也差不多了，跟考官说tree会不会
是好方法，考官说maybe |
|
g*****e
发帖数: 282 | 3 k-largest, quick sort, priority queue这种code背下来算了。根本不可能现场无bug
自己实现的
第3题，用heap比类qsort效率更稳定 |
|
g*****e
发帖数: 282 | 4 k-largest, quick sort, priority queue这种code背下来算了。根本不可能现场无bug
自己实现的
第3题，用heap比类qsort效率更稳定 |
|
A****e
发帖数: 310 | 5 是因为qsort的worst case是O(n^2)？
我想面试的时候碰到是不是应该都说一说，看他们喜欢哪种再去实现哪种啦～ |
|
p*****p
发帖数: 379 | 6 The array is not sorted so not possible to get that in linear time
qsort can do that in amortized O(n) but not worst case |
|
d*****y
发帖数: 1365 | 7 拍完序以后,先计算a(1,n) = x_n -x_1, 这是最大的差值,所以直接选中.a(1,n)选中以
后,再计算a(1,n-1)和a(2,n),把这两个存到max heap里面.然后挑选出两者中间最大的
那个,假定是a(2,n),那就把a(2,n)pop出来,再把左邻a(2,n-1)和下邻a(3,n)算出来存进
max heap.....一共进行n次这样的操作,得到差值里面最大的前N个数,如果这前N个数是
连续的,就返回true.所以整个操作是n log n.
这个讨论是假定这些差值都不相等,如果相等的话,复杂度能最坏到O(n^2).但是如果考
虑到,上面在判断出现不连续的差值的时候就可以直接跳过下面的操作返回false. 所以
平均复杂度是 n log n. 就像qsort那样.
nlogn |
|
h**o
发帖数: 548 | 8 喔？ 那用了递归的qsort就不算in place了？ |
|
f*****n
发帖数: 224 | 9 1. 换成数组
2. qsort(),然后自己编一个函数比较大小 |
|
f*****n
发帖数: 224 | 10 1. 换成数组
2. qsort(),然后自己编一个函数比较大小 |
|
f*****n
发帖数: 224 | 11 1. 换成数组
2. qsort(),然后自己编一个函数比较大小 |
|
s********u
发帖数: 1109 | 12 不sort的话，你重复的字母不会到一起去啊。因为他不允许用其他数据结构记录重复的
字母，所以只能先排序再做啦。反正只要用in place的sort方式就行了，比如者qsort
，heapsort。 |
|
s********u
发帖数: 1109 | 13 没有，这个太细节了吧。大不了我用c的qsort，这个总明确了。总之量级肯定是nlogn
。只问了我总的，就是O(n^2)，好像没有更优的了。
就是没跳过重复的，脑子卡住了，悔啊。。 |
|
r**********g
发帖数: 22734 | 14 跟我老板组员说不过去啊。说实话我已经是放水了。几个三哥都明显刷过题的，半小时
写完qsort + dfs + bfs。虽然一看就是icc包装出来的，但是起码还是练过的。这个跟
帮忙不帮忙两回事，我觉得是态度问题。当年我中国老板招我，明知会帮忙，俺也是熬
夜做题一个月，面试的时候跟一个毛子苦战一小时的dp。
我发帖只是很失望，想帮忙都帮不了，底线总要有吧…… |
|
r**********g
发帖数: 22734 | 15 我不觉得new grad写了10年程序有什么奇怪，如果你觉得奇怪只能说你孤陋寡闻。我看
到写这样的只会觉得是牛人，至少应该电面一下，最多发现是骗子5分钟挂断，如果真
是扎克那样的高手呢？有的人总觉得看到牛逼简历就说别人是扯淡，其实扯淡不扯淡，
绝对是面了才知道，简历的用处就是让别人跟你talk。
见的多了，就我这样的初一开始搞信息奥赛，跟我一起搞的，我高中至少就有20个，全
省好几千个，我这样还是进不去冬令营的。很奇怪么？我还见过6岁从apple II basic
开始玩起的。我的第一份兼职工作是大一暑假写flash，以后每年都兼职，到MS毕业7年
了吧？到Ph.D 有11年了吧这么说有啥？
我说了，不要写10年industry experience, 写10年的coding experience。当然你还是
要有金刚钻。但是如果你都会写qsort，谁知道你是初中学的还是昨天学的？
在MSR每年都有high school intern，个个都是搞了4-5年程序的高手，我带过的敢说比
招进来的SDE都要好，三五天整一个app上线那种。一群10年纪的都在搞机器人，每天晚
上都搞。盖子写下棋... 阅读全帖 |
|
c*******y
发帖数: 98 | 16 我觉着这个时间复杂度基本和qsort没区别。少partition一层而已。楼上大牛说的
sorting color是怎么模仿的？
来贴个无脑code。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void print(vector& arr){
for (auto& it : arr) cout << it << ", ";
cout << endl;
}
int main (int argc, char** argv) {
vector arr = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
print(arr);
int i = 0, j = 9;... 阅读全帖 |
|
c*******y
发帖数: 98 | 17 比如你自己写个qsort，自己跑1 2 3 4 5没问题，case多了就可能有些错了。正常。 |
|
l*******i
发帖数: 57 | 18
不是一码事。我说的是靠技术吃饭的码农领域。你说的是富二代，不属于这里讨论的范
围。
一个人连qsort都写不好，然后拿了offer，你让另一个把leetcode刷爆了但店面挂掉的
人怎么想？ |
|
y****9
发帖数: 252 | 19 我觉得呢个问题吾差咯，甘最残暴方式就O(n^2) 循环一次，如果吾考虑空间，你可以
Hashing。如果排序 + 循环 就O(nlogn) + O(n), 再进一步你可以问埋OOP：
class SomeCollection where T : IComparable
{
private List items;
private void Sort()
{
T item1;
T item2;
if(item1.CompareTo(item2) < 0)
{
//
}
}
}
距唔一定要识得算法情况下，问下given a Comparator, how to write a Sort
仲简单既题目就qsort啦，问问语言特性，譬如Lamda Expression
查使你有无打算卑我一个机会试下呢？ |
|
m***y
发帖数: 14763 | 20 这主要是硬件原因。Qsort的内循环很容易在硬件上实现，软硬的速度之差就是天壤之
别了。
就事论事，这道题，老汉能找到的标准答案都是deque，不是说它明显比用别的数据结
构好很多，而是deque在很多平台上要不有专门硬件实现，你可以调asm或者native
function,要不有专门的优化过的库。
就stackoverflow的那个链结，下面有人讨论如何用banker's queue,就是用两个stack
来模拟deque。看起来绕圈子，但是在只提供stack的硬件上，这样还是比咱自己写的软
件deque快的多。 |
|
k***g
发帖数: 166 | 21 C有qsort的，当然，同意面试不用C，那不是自己找麻烦么
++ |
|
k***g
发帖数: 166 | 22 C有qsort的，当然，同意面试不用C，那不是自己找麻烦么
++ |
|
k***e
发帖数: 1931 | 23 qsort的partition我还是喜欢算法导论上的做法，拿第一个元素当pivot。反正取哪个
当pivot最优没有定论，面试的时候写成这样面试官也没法反驳。
一般来说partition就两个思路，一个是挖坑，左右两个指针，交替移动，不断挖坑填
坑，这个对两分比较形象，但是对于三分区间（小于，等于，大于）就有点难以理解了
，算法导论上面用的那个partition思路，对付两分三分都比较轻松。 |
|
L******k
发帖数: 395 | 24 Problem Description
-------------------
Your task is to write a command-line program to evaluate a set of
equations, each specified on separate lines. An equation is defined
by:
=
is the left-hand side of the equation and is always a variable
name. A variable name can only be composed of letters from the
alphabet (e.g. for which isalpha(c) is 1). is the right hand
side of the equation and can be composed of variables, unsigned
integers, and the + operator.
Here is one exa... 阅读全帖 |
|
发帖数: 1 | 25 什么时候面的，是在Mountain View面的吗？是SWE吗？你是new graduate还是有工作经
验的啊。
第二题，个人理解是。数组一，排序。用数组二做Index再重新Re order数组一就可以
了好像。
qsort(array1.begin(), array1.end());
for (int i = 0; i < array2.size(); i++) {
out[i] = array1[array2[i]];
}
array1 = out;
另外网上不是说不提倡秒过吗？要么说见过，要么思考推理一下。
电面那题到是挺难的。 |
|
w*******n
发帖数: 4188 | 26 先qsort,再binary search,都是nlogn, 数据多的话比n^2还是快多了. |
|
z********o
发帖数: 4284 | 27 什么GM/director有几个还会写code的，你让他们写个qsort试试看 |
|
|
G******t
发帖数: 1782 | 29 会qsort可以用来折磨来找工的别的码工，赫赫。 |
|
a***n
发帖数: 1616 | 30 http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
第9页算法，递归前面那两行，居然把 k<=p, k>=q 给漏了！
虽然结果依然正确，且不影响主要performance，但明显是个bug嘛:)
void quicksort(Item a[], int l, int r)
{
int i = l-1, j = r, p = l-1, q = r; Item v = a[r];
if (r <= l) return;
for (;;)
{
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
if (a[i] == v) { p++; exch(a[p], a[i]); }
if (v == a[j]) { q--; exch(a[j], a[q]); }
} |
|
k**f
发帖数: 92 | 31 看了那本经典的书，果然是O(N)算法，和qsort长得太象了 |
|
k****f
发帖数: 3794 | 32 char inString[]="ncdosndisoc";
~~ |
|
b*********n
发帖数: 1258 | 33 太帅了，果然就是这个问题
可以讲讲为什么吗？
我一直把char* a和char a[]认为是一样的
为什么这里就不行
难道是因为\0的原因？
谢谢 |
|
k****f
发帖数: 3794 | 34 char*放在不可修改的地方
char[]是可以修改的。一般就在stack，
多来programming版，就会知道的 |
|
|
|
p***o
发帖数: 1252 | 37 C people use qsort and global variables.
C++ people use std::sort and functors. |
|
P********e
发帖数: 2610 | 38 int pstrcmp(const void *p, const void *q)
{ return strcmp((char*)p, (char*)q); }
google qsort |
|
c*****t
发帖数: 1879 | 39 1000 people isn't a lot. No need fansy algorithms, just compare
1 by 1 is enough. If you want something more fansy, then consider
qsort, then do binary search if you are using C. With C++, can use
container. If the set of string is known at compile time,
may consider perfect hash. |
|
|
m******d
发帖数: 414 | 41 之前有人贴出了常见的那个求Maximum repetitive substring的代码，如下：
void MaxDuplicatedSubstring(char *input, char *result)
{
int length = strlen(input);
char **substrings = new char**[length];
for (int i=0; i < length; i++)
substrings[i] = input + i;
qsort(substrings, length, sizeof(char*), (int (*)(const void*, const void*
))strcmp);
int max = 0;
int index = -1;
for (int i=0; i < length - 1; i++)
{
int c = 0;
while (substrings[i][c] && substrings[i+1][c] && substrings[i][c] ==
substrin |
|
H*M
发帖数: 1268 | 42 studying STL now and have a question.
it seems to me that:
1. in STL, if a function is expecting a functor, it is usually ok to use fun
ction pointer; even if it is not ok, you still can use ptr_fun to get an obj
ect;
2. if it is expecting a function pointer, you can not use a functor, like qs
ort.
From what I read, most STL functions are expecting functors. Who can sumariz
e which functions are expecting function pointers only(e.g. qsort)? Or where
can I find such info.? many thanks. |
|
p***o
发帖数: 1252 | 43 嗯，差不多，就是BS在C++ D&E里谈到的原始的template。另外也可以把
函数指针用进去，就像qsort这个C库函数那样。不过用C写费力不讨好，
用C++方便很多。 |
|
d****i
发帖数: 4809 | 44 qsort这个函数的参数中还是有size_t size这样的参数来表示输入array的元素大小，
但是象我一开始举的例子那样没有表示每个元素大小的参数
void function(void *a, int N)
{
int i；
for(i=0;i
printf("%a",a[i]);
}
这样做是错的，因为void pointer不可以被dereferencing,必须cast成相应的类型才可
以，在没有传入size_t size的情况下怎么做呢？（假设不能用Macro） |
|
X****r
发帖数: 3557 | 45 int mystrcmp(const void * str1, const void * str2)
{
return strcmp(*(const char* const*)str1, *(const char* const*)str2);
}
doesn |
|
|
e**********n
发帖数: 359 | 47 Can you just use *(char **)str1 and *(char **)str2 ? |
|
X****r
发帖数: 3557 | 48 Yes, in this case they are the same in result.
But generally speaking, const should be used wherever applicable
to help prevent programming errors. |
|
c*******9
发帖数: 6411 | 49 Xentar,
could you explain why the correct function is :
int mystrcmp(const void * str1, const void * str2)
{
return strcmp(*(const char* const*)str1, *(const char* const*)str2);
}
and not:
nt mystrcmp(const void * str1, const void * str2)
{
return strcmp( (const char*)str1, (const char*)str2 ) ;
}
The array elements here are pointer to char*?
Thanks for the help! |
|
|
