r****o
发帖数: 1950 | 1 你说的稳定性是数据的相对order吗？
我想了一下，quick sort的每次partition后，似乎能保证所有比pivot小的元素们的位
置的相对顺序都不变，但大于等于pivot的元素们的位置的相对顺序有可能变化。
我说的对不对? |
|
d**e
发帖数: 6098 | 2 它这里是说，如果用一个random的pivot，worse case可能是O(n^2)，
而用median of median找到一个好的pivot，需要O(n)，再应用Select找
k-th element，这里主要是花在partition上面，也是O(n)，worse case
也是O(n)，那么 (k-1) smallest/largest elements就在k-th的左/右边. |
|
A*********r
发帖数: 564 | 3 找出问题来了，每个序列找出来的与pivot最接近的数，并不能保证最后得到的数的最
大与最小之差最小。
反例如下
四个序列分别为 { 2， 20}， {10}， {12， 13}， {1，18}
按照你的算法，10是pivot, 分别从取出的数为 2，10，12，18， 窗口大小为16
但是最优的答案应该是窗口大小为10。
你说得这个对于2个序列的情况适用。 |
|
a****s
发帖数: 9 | 4 用quicksort 的idea, 找一个pivot, 然后partition, 扔掉有3n个elements 的
partition, 如果两个partition都有3n个elements, 那么pivot就是要找的element. |
|
b***e
发帖数: 1419 | 5 你这个貌似就是counting sort, 对值域有要求。无法是constant space。比如我最小
的数是
10000000000000，但是数组的长度只有1000000，似乎space要爆。
我感觉这个正解应该是问quick sort，每次抛掉一半(pivot前的长度小于pivot抛后一
半，否则抛前
一半)，最后平均是O(n)。 |
|
g*********s
发帖数: 1782 | 6 struct ball {
int color;
};
int partition(ball A[], int begin, int end, int pivot)
{
int lower = begin - 1;
for ( int k = begin; k <= end; ++ k ) {
if ( A[k].color < pivot ) {
swap(A[k], A[++lower]);
}
}
return lower
} |
|
r******g
发帖数: 13 | 7 3 way partition first puts the duplicated elements in two ends by scanning
once:
1. moving from let to find element not less < p
2. moving from right to find element not greater > p
3. exchange left and right elemnt
4. if (left elment == p) swap it with left end
5. if (right element == p) swap it with right end
=pivot, p, = pivot
my code got
5, 5, 5, 4, 3, 1, 2, 3, 5, 10, 5, 9
put the duplicated elements in the center by exchanging elements in two ends
and those in the center
3, 2, 1, 4, ... 阅读全帖 |
|
f*******t
发帖数: 7549 | 8 怎么那么多循环？我的版本只有一层啊：
void quicksort(int arr[], int left, int right)
{
if(left >= right)
return;
int pivot = arr[right];
int i = left;
for(int j = left; j < right; j++)
{
if(arr[j] < pivot)
{
if(i != j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
++i;
}
}
if(i != right) {
int temp = arr[right];
arr[right] = arr[i];
arr... 阅读全帖 |
|
v***a
发帖数: 365 | 9
Maybe here:
int pivot = 0;
if (d < v[low].length())
pivot = v[low][d]; |
|
d**0
发帖数: 124 | 10 请教一个题目： k个unsorted arrays，假设都是n个元素。怎么样快速求出median？
不能把所有的array拼到一起再做quick selection。
我用类似quick selection的方法使用同一个pivot element在k个arrays里quick
select，再求
方法应该是这样，但是复杂度分析不出来。一个naive的bound是o(kn),但是这样就和拼
到一起做quick select一样。最后猜了一个o(nlogk)但是自己也不是很信服。
请大牛指教，谢谢！ |
|
w**z
发帖数: 8232 | 11 来自主题: JobHunting版 - 问道算法题 It's like the quick sort, pick the pivot. But to handle worst case for
picking the pivot , you need to have the "median of median" thing.
you know about it. |
|
x*******5
发帖数: 152 | 12 这个是我的题库，还有一些题没有coding，比如back of envelop计算，idea思考，等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_... 阅读全帖 |
|
e***l
发帖数: 710 | 13 if (left <= right)
应该是if (arr[left] >= arr[right])
正确性是显然的，左边不大于pivot,右边不小于pivot |
|
j********e
发帖数: 1192 | 14 看明白了。如果pivot选的很倒霉，worst case会到O(N^2)?
一般再用median of median来选pivot，那就麻烦了 |
|
z****e
发帖数: 9 | 15 1st: find the first item that value<0, use it as pivot, start from the next
node to find the sublist with max value, finish until the node reaches the
pivot again. O(n) time cost.
2nd: the first is that at each station, try to get as much gas as possible,
the main idea is to find one station, starting from that station, there is
always gas left when reach one station. if no gas left for one station, then
start from the next station. if the next station if the 1st station, return
with false.
O(N)... 阅读全帖 |
|
b*****u
发帖数: 648 | 16
所谓不稳定是说相等的数字一个被选中pivot后相对于其他几个的位置不定吧
如果数组里没有0，那么添个0进去作pivot 快排一轮还是不稳定的吗？ |
|
b*****u
发帖数: 648 | 17
如果没有重复数字的话可以这么弄：
先用0作pivot， 快排，把k个正数选出来 O(n) 时间
选k/2 作pivot，快排，结果少的那一侧缺数，对其继续选中值，快排，直到区间为0，
O(lgn) |
|
h****n
发帖数: 1093 | 18 第二题应该是O（n）
第三题的O（n）可以这么理解，其实就是快速排序的变形
第一次 随机选择一个pivot，捯饬之后，如果这个pivot的index小于k则从后半部找第k
-index的数，否则找前半部的第k数
每次iteration,on average上问题的规模减半
故有 n/2+n/4+n/8+....+1 = n
也可以用递推式来推 T（n）=T（n/2）+ O(1) |
|
w****x
发帖数: 2483 | 19
大概就是先把起点小于pivot segment的intervals排出在左部, 然后再在那部分
intervals里面排出end point大于pivot interval起点的线段, 这部分线段有共同的
overlap就当已经排好序了 |
|
h*********g
发帖数: 42 | 20 Post for a friend. Do not contact me ...
All these position is in Mainland China.
Please send your resume to m**********[email protected]
Title as "Name - Position Name"
*******************************************************************
Position Separation
*******************************************************************
The Position Principal/Consulting Software Engineer
Position Summary
Reporting to the head of the storage team, the Principal/Consulting Software
Engineer will play a pivotal r... 阅读全帖 |
|
p*****2
发帖数: 21240 | 21 发现两个问题
1. 在step2里，她说return the biggest element on the left. 难道这个不就是
pivot吗？
2. leftEnd = partition(array, left, right, pivot)
leftEnd有可能返回的就是right，这样就死循环了。
大家看看是不是这么回事？ |
|
h********d
发帖数: 13 | 22 谢谢你的建议，我求过好多人帮我推荐，可能我的背景不match吧，都没有回信。
我的经历特别尴尬，国内经济学博士，毕业后随老公来美国，在家呆了一年多带孩子。
工作经验少的可怜。会用Excel， SQL， 用Pivot table分析报表什么的 ，也自学了
Power Pivot，想做Business Analyst/ Business Intelligence/Data Analyst 之类的
，苦于没有这方面的工作经验，投出去的简历都没有回信。不计薪水想做volunteer也
是找不到。以我这种搞不成低不就的经历找起来特别困难。 |
|
b***e
发帖数: 1419 | 23 来自主题: JobHunting版 - G新鲜面经 -- here's a Haskell solution for 1.2
split [] = [];
split (x:xs) =
[([], x, xs)] ++ [ (x:left, pivot, right) | (left, pivot, right) <- split
xs]
up pre [] [] = [pre]
up pre left [] = []
up pre left right =
[ r | (l1, p, r1) <- split right, r <- down (pre ++ [p]) (left ++ l1) r1 ]
down pre [] [] = [pre]
down pre [] right = []
down pre left right =
[ r | (l1, p, r1) <- split left, r <- up (pre ++ [p]) l1 (r1 ++ right) ]
go n = down [] [1..n] []
1
big |
|
s********u
发帖数: 1109 | 24 你是不是放错地方了，应该是
dummy_tail->next = pivot->next;
ListNode* new_head = dummy->next;
pivot_tail->next = NULL;//只有这里需要操作。
delete dummy;
delete pivot;
return new_head;
我用你的代码加这一行就过了测试啊，accepted |
|
p********2
发帖数: 17 | 25 Randomized Quicksort Variants：
Regularly, RANDOMIZED QUICKSORT selects a single pivot element uniformly at
random. In this problem you will analyze two possible modifications to this
choice of pivot.
For an integer parameter k>=1, the HYBRID RANDOMIZED QUICKSORT algorithm
uses regular RANDOMIZED QUICKSORT whenever n>K , but uses I NSERTION S ORT
whenever n<=k . Analyze the expected running time of HYBRID RANDOMIZED Q
UICKSORT in terms of n and k .
Argue that this sorting algorithm runs in O(nk+n... 阅读全帖 |
|
m*z
发帖数: 234 | 26 我们公司去年刚上市，上升趋势稳定，总部在Austin。公司员工绝大部分是白人，极少
印度人，当然中国人也极少，我们部门99个员工就我一中国人。现需急聘Data
Engineer若干。
Austin附近有很多湖，有山有水，是德州为数不多的风景好区。还有各种音乐节，平时
夜晚市区都有大量的live music，被誉为Live Music Capital of the World，是coder
不错的定居点。
有兴趣者请把简历寄到 a***************[email protected]
谢谢你的关注。
Position 1 Data Warehouse Engineer
About the Role:
Data is core to our business and future success. Our Data team is looking
for a Data Warehouse Engineer to play a pivotal role in managing and
distributing data. You will collaborate with a multidis... 阅读全帖 |
|
f********t
发帖数: 6999 | 27 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: onetiemyshoe (onetiemyshoe), 信区: SanFrancisco
标 题: 烙印政客牛B的反华演说 (转载)
发信站: BBS 未名空间站 (Tue Apr 29 14:31:35 2014, 美东)
发信人: onetiemyshoe (onetiemyshoe), 信区: CivilSociety
标 题: 烙印政客牛B的反华演说
发信站: BBS 未名空间站 (Mon Apr 28 22:58:52 2014, 美东)
“TPP & Asia-Pacific Pivot 101..Connecting the Dots.”
https://www.youtube.com/watch?v=InK1e25PkFc
很好的talk, 解释了TPP和Asian Pacific pivot
的日印美心连心反华的关系
@12分钟, 烙印政客开讲。
大致如下:"America needs a junior partner
to control China, through malaika stra... 阅读全帖 |
|
l*********8
发帖数: 4642 | 28 high 是指向数组最后一个元素的后面一个。
比如：
int a[5] = {3,2, 7, 2, 1};
int pivot = 2;
partition(a, a+5, pivot); |
|
w**z
发帖数: 8232 | 29 【 以下文字转载自 Programming 讨论区 】
发信人: wwzz (一辈子当码工), 信区: Programming
标 题: 软软open source .net， 在 linux／mac 上跑
发信站: BBS 未名空间站 (Wed Nov 12 12:55:51 2014, 美东)
http://www.wired.com/2014/11/microsoft-open-sources-net-says-wi
Satya Nadella’s rapid reinvention of Microsoft continues.
In yet another bid to make up lost ground in the long march to the future of
computing, Microsoft is now open sourcing the very foundation of .NET—the
software that millions of developers use to build and operate websites and
o... 阅读全帖 |
|
a******u
发帖数: 69 | 30 Median of median那个方法我没有仔细研究过，面试的时候也没想起来。写随机pivot
的quick select应该也没有太大问题。但他也没让我写哎。anyway，谢谢鼓励
quick select按 median of median的最优解法worst case 是 O(N),你该提下的。如果
让你写就写那个选一个pivot的就行了我觉得你已经答得........ |
|
O********e
发帖数: 48 | 31 A generalized solution:
Suppose you have a master node (or are able to use a consensus protocol to
elect a master from among your servers). The master first queries the
servers for the size of their sets of data, call this n, so that it knows to
look for the k = n/2 largest element.
The master then selects a random server and queries it for a random element
from the elements on that server. The master broadcasts this element to
each server, and each server partitions its elements into those la... 阅读全帖 |
|
l**********0
发帖数: 7 | 32 长期提供Deloitte职位内部推荐机会，地域不限，职位不限，请大家自行在https://
jobs2.deloitte.com/us/en/?icid=top_job-search上搜索详细职位要求,并将Resume以
及职位Requisition code发至[email protected]
/* */ 很抱歉因为工作比较忙很难
每封邮件及站内信都回复。但承诺只要你背景符合并且达到职位最低要求，我一定会尽
力帮大家内推。
General requirements for experienced hire:
1.Prefer at least 2+ years client service experience.
2.Hot skill sets we are looking for are in the following areas: Informatica
suite, Qlikview/Tableau, Big Data/Hadoop, Hyperion HFM/Planning, Pentaho,
Cognos TM1, MS BI stack (SSIS/S... 阅读全帖 |
|
l**********0
发帖数: 7 | 33 长期提供Deloitte职位内部推荐机会，地域不限，职位不限，请大家自行在https://
jobs2.deloitte.com/us/en/?icid=top_job-search上搜索详细职位要求,并将Resume以
及职位Requisition code发至[email protected]/* */ 很抱歉因为工作比较忙很难
每封邮件及站内信都回复。但承诺只要你背景符合并且达到职位最低要求，我一定会尽
力帮大家内推。
General requirements for experienced hire:
1.Prefer at least 2+ years client service experience.
2.Hot skill sets we are looking for are in the following areas: Informatica
suite, Qlikview/Tableau, Big Data/Hadoop, Hyperion HFM/Planning, Pentaho,
Cognos TM1, MS BI stack (SSIS/SS... 阅读全帖 |
|
R*********9
发帖数: 342 | 34 Please send your resume to [email protected]
/* */, I can forward your resume
to recruiter.
Data Analyst - WW Engineering
(ID 309287)
Amazon Corporate LLC
at Engineering - Fulfillment
US, WA, Seattle
Job Description
Amazon is seeking a bright and dynamic Data Analyst to join its Worldwide
Engineering -Advanced Technology Group. WWE –ATG is responsible for
designing new systems in robotics, mechatronics, autonomous vehicles, and
packaging technology for Amazon Fulfillment.
As part of your ... 阅读全帖 |
|
|
l**********0
发帖数: 7 | 36 长期提供Deloitte职位内部推荐机会，地域不限，职位不限，请大家自行在https://
jobs2.deloitte.com/us/en/?icid=top_job-search上搜索详细职位要求,并将Resume以
及职位Requisition code发至[email protected]
/* */ 很抱歉因为工作比较忙很难
每封邮件及站内信都回复。但承诺只要你背景符合并且达到职位最低要求，我一定会尽
力帮大家内推。
General requirements for experienced hire:
1.Prefer at least 2+ years client service experience.
2.Hot skill sets we are looking for are in the following areas: Informatica
suite, Qlikview/Tableau, Big Data/Hadoop, Hyperion HFM/Planning, Pentaho,
Cognos TM1, MS BI stack (SSIS/S... 阅读全帖 |
|
k***e
发帖数: 1931 | 37 qsort的partition我还是喜欢算法导论上的做法，拿第一个元素当pivot。反正取哪个
当pivot最优没有定论，面试的时候写成这样面试官也没法反驳。
一般来说partition就两个思路，一个是挖坑，左右两个指针，交替移动，不断挖坑填
坑，这个对两分比较形象，但是对于三分区间（小于，等于，大于）就有点难以理解了
，算法导论上面用的那个partition思路，对付两分三分都比较轻松。 |
|
t****b
发帖数: 2484 | 38 题刷得太少
是否有等号和循环跳出和返回pivot，pivot+/-1有关
有四种情况 建议楼主总结一下 要不然面试的时候先凭感觉写出来然后test case跪了
就很尴尬了 |
|
h*********n
发帖数: 11319 | 39 “刷的不精”？
刷题就能通过下面这种国女么？
“一轮domain knowledge: 一国女。这个吐一下槽。此interviewer显然早上和人刚吵
完架，进来后面若冰霜，而且面有怒色。在我讲述的过程中，不停地打断我的思路。对
一些明显正确的知识点，问我“is it correct?" or "are you sure?". 我并没有企
望等到什么hint,但我明明on the right tracks的时候，将我打断，想将我扭到别的方
向去。咳，比三哥三姐还狠。”
“要吐槽的是这个女面试官竟然不懂quicksort算法，非得说我中间过程有一个
duplicate的number，是不对的，还说我举的例子是coincident correct, 遇到其他例
子就不行了，我和面试官解释quicksort要找的是pivot的正确位置，中间有一个
duplicate没关系，最后会用pivot replace那个duplicate number，当时还有一个
shadow，这个人在旁边说“我感觉code是对的”，这个女面试官还在纠结，最后我用一
个general case说服了她，结果她竟然... 阅读全帖 |
|
m****s
发帖数: 18160 | 40 【 以下文字转载自 Returnee 讨论区 】
发信人: huataixiang (今天的欢乐，将是明天永恒的回忆), 信区: Returnee
标 题: Some mainland china positions (转载)
发信站: BBS 未名空间站 (Mon May 20 05:18:32 2013, 美东)
发信人: huataixiang (今天的欢乐，将是明天永恒的回忆), 信区: JobHunting
标 题: Some mainland china positions
发信站: BBS 未名空间站 (Mon May 20 05:18:07 2013, 美东)
Post for a friend. Do not contact me ...
All these position is in Mainland China.
Please send your resume to m**********[email protected]
Title as "Name - Position Name"
******************************************... 阅读全帖 |
|
|
发帖数: 1 | 42 你想在北美留学期间获得Coop/Intern的机会么？想进入高薪High Tech行业，而苦于没
有实战经验么？你想拿到项目的实战经验，并提升你所掌握的BI和Big Data的技术和技
能么？ 快来加入BI+Big Data+CRM项目实践吧！
斯坦福IT是北美第一家以求职为导向的专业IT培训学校。导师均为IT领域的顶级专家和
学者，都曾在大公司做管理和技术工作，有着广泛的IT人脉。导师层就职的公司包括微
软，IBM,Oracle,Amazon,Facebook等。学员毕业后全部进入银行，政府，IT顾问公司等
领域，成为IT高薪专才
IT公司BI，大数据及CRM真实项目实践，真实项目交付经验
• 公司网站：http://www.followmedoit.com
• Youtube Channel(斯坦福IT的技术讲座，课堂及求职辅导视频—）：https
://www.youtube.com/channel/UCXT1lD9WEUAEO4KNSZFVniw
• 成功求职同学们（BI， CRM)经验分享（视频）：https://www.... 阅读全帖 |
|
发帖数: 1 | 43 你想在北美留学期间获得Coop/Intern的机会么？想进入高薪High Tech行业，而苦于没
有实战经验么？你想拿到项目的实战经验，并提升你所掌握的BI和Big Data的技术和技
能么？ 快来加入BI+Big Data+CRM项目实践吧！
斯坦福IT是北美第一家以求职为导向的专业IT培训学校。导师均为IT领域的顶级专家和
学者，都曾在大公司做管理和技术工作，有着广泛的IT人脉。导师层就职的公司包括微
软，IBM,Oracle,Amazon,Facebook等。学员毕业后全部进入银行，政府，IT顾问公司等
领域，成为IT高薪专才
IT公司BI，大数据及CRM真实项目实践，真实项目交付经验
• 公司网站：http://www.followmedoit.com
• Youtube Channel(斯坦福IT的技术讲座，课堂及求职辅导视频—）：https
://www.youtube.com/channel/UCXT1lD9WEUAEO4KNSZFVniw
• 成功求职同学们（BI， CRM)经验分享（视频）：https://www.... 阅读全帖 |
|
m***i
发帖数: 84 | 44 Black & Decker PAV1200W 12-Volt Cyclonic-Action Automotive Pivoting-Nose
Handheld Vacuum Cleaner Black & Decker PAV1200W 12-Volt Cyclonic-Action
Automotive Pivoting-Nose Handheld Vacuum Cleaner
$34 |
|
a*****g
发帖数: 19398 | 45 我用 Google Speadsheet 的 pivot report 几年了，
最后的报告从来不需要刷新啊，都是自动更新的啊
不过我还是特意改了格式，重新生成 pivot report，还是不灵光……
filter |
|
a*****g
发帖数: 19398 | 46 pivot report 是这个样的
（图是配合 pivot report 的结果，显示学校几年来学生入学情况）
Filter 是在右边的箭头所指出部分，不过这个案例没有用日期过滤，而是其他过滤。
（我原始说的有日期过滤的例子，因为涉及一些内部信息，不方便截图） |
|
t******l
发帖数: 10908 | 47 两个人吃，一个 pivot 位置 0 到 8，所以 9 种吃法。
三个人吃，上两个 pivot，combination w/ repetition，C(9, 2) + C(9, 1) = 9*8/2
+
9 = 9*5 = 45 种。 |
|
t******l
发帖数: 10908 | 48 对于允许 0 块 pizza 的，你这个 C(10, 2) 的 pivoting modelling 更简单，可以直
接用 combination wo/ repetition。谢谢。
我前面那个是从不允许 0 片 pizza 的 pivoting modelling 外推出来的，我那个会导
致 combination w/ repetition，不如你这个 modelling 好。
C( |
|
t******l
发帖数: 10908 | 49 就用你举例的 “液体在逻辑上可以无限分割” 来说明 monkey's sensory
illusion and cognitive delusion 好了。
“液体在逻辑上可以无限分割” 是基于 “空间在逻辑上可以无限分割”。
而 “空间在逻辑上可以无限分割” 实际上就是 Dedekind cut。而 Dedekind cut 其
背后的 Dedekind continuous 是人为假设的 continuous。
之所以说是该 continuous 是人为的假设，是因为 Dedekind cut 的 cut algorithm (
pivot inserting algorithm -- 该 pivot 这里是一个 irrational number) 本质上是
一个 undecidable problem（类比于 compare identical of any two real numbers
的 problem）。。。而 Dedekind 假设这个 undecidable problem can always get a
decisive answer，也就是人为假设一个 no... 阅读全帖 |
|
|
