w**7
发帖数: 71 | 1 面试加州P公司
一面是华人GG
1. 给个数组，给个target, 求找两个数和等于target
然后拓展到找3个数，4个数，分析复杂度
这经典题，没啥说的，hashmap
一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
这个用hashmap存层数和路径长度值，从底层向上遍历
二面是个白人
2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
数组排序
这就是弄个k size 的min-maxheap, 然后先把前0-k-1个元素放到heap里，然后从数组K
位置开始，从heap中取出最小，然后从数组取一个放到heap里，最后O(nlogk)排好
我把方法一说，interviewer感觉可以，说那你写个code发过来吧，然后do you have
any questions。没20分钟就结束了
两面感觉都没啥问题，最后周一就收thank you letter了。有好几次都这样，感觉
technical 题目都没啥问题，两面就悲剧，求经验……move on到麻木了，唉 |
c**y
发帖数: 2282 | 2 现在连playboy都招码工了啊
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
h*********n
发帖数: 11319 | 3 能面palantir的果然都是大牛
便上P面经
组K
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
d*****o
发帖数: 28 | 4 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.
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
R***i
发帖数: 78 | 5 Palantir就是这样。楼主的经历几乎和我当时一模一样。。题都做出来了，但还是挂了
。不过无所谓，后来拿到更好的offer
BTW 华人gg的last name是不是song啊? |
w**7
发帖数: 71 | 6 唉……我那个是Chuang，应该是台湾人了。
感觉面得还不错呢，结果就这么不明不白的挂了
今天follow up Amazon发现给HR的信直接被系统退了，查无此人，打电话，号码无法链
接……唉
【在 R***i 的大作中提到】
: Palantir就是这样。楼主的经历几乎和我当时一模一样。。题都做出来了，但还是挂了
: 。不过无所谓，后来拿到更好的offer
: BTW 华人gg的last name是不是song啊?
|
d*****o
发帖数: 28 | 7 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). |
g******7
发帖数: 1532 | 8 什么是屁公司?
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
m******e
发帖数: 88 | 9 正常，我面了几个月了，大部分自我感觉都很好，结果都没拿到。。。 |
A*********l
发帖数: 2005 | 10 1：
有DP的方法吧。
2：
直觉上感觉，是不是有DP的方法？或者是类似Dijkstra's的算法？（没仔细想，就是直觉）感觉
Dijkstra's比较像，所有到某个节点的path的weight就是这个节点的值。
3：
你的方法不对吧。
假定6个数，k=3，原来的顺序是： 1 5 3 4 2 6
heap 一开始是 1， 5， 3， 把 1 拿出来。
然后heap 是5，3， 4， 把 3 拿出来。
这排序就错了吧？3 排到2 前面去了。
要么我没看懂题或者是没看懂你原来的解法？
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
|
|
w**7
发帖数: 71 | 11 1:求4组的时候确实要DP，问题变成求两个pair, 和为target，时间复杂度O(n^2);我说
Hashmap是两个数的情况
2：用hashmap也是DP啊，把中间的结果存起来, key是层数，value是当前最大值,只是
对于这个三角型，用数组感觉有很多空间浪费掉了，所以我就用hashmap
3：题目要求每个数字距离原本的距离最多为k，我当初是这么理解k的，像滑动窗口一
样，比如a[i]...a[i+k-1],根据你给的例子，5最多移到a[2]的位置。当初也问面试那
人，不过你这样说的意思是d = i+k - i, 也就是说实际窗口size比我多了一个，那我
的heap size+1就OK了，这个是窗口理解问题，本身用heap倒是应该没错.不过多谢提醒
，当初还真没想直接距离等于Index的差，就想着把他们当一个size为k的滑动窗口处理
直觉）感觉
【在 A*********l 的大作中提到】
: 1：
: 有DP的方法吧。
: 2：
: 直觉上感觉，是不是有DP的方法？或者是类似Dijkstra's的算法？（没仔细想，就是直觉）感觉
: Dijkstra's比较像，所有到某个节点的path的weight就是这个节点的值。
: 3：
: 你的方法不对吧。
: 假定6个数，k=3，原来的顺序是： 1 5 3 4 2 6
: heap 一开始是 1， 5， 3， 把 1 拿出来。
: 然后heap 是5，3， 4， 把 3 拿出来。
|
e******0
发帖数: 211 | 12 楼主，第一题用hashmap怎么解
多谢了
好运
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
w**7
发帖数: 71 | 13 大概写个伪代码，差不多就这样
input : a[], target
for(int i = 0; i < a.length; i++)
for(int j = 0; j < a.length; j++)
{
sum = a[i] + a[j];
if(hashmap.find(target-sum))
The four number is a[i], a[j], and the the element with index from
hashmap.getKey(target-sum)
else
if(hashmap.find(sum) == false)
hashmap.insert();
}
【在 e******0 的大作中提到】
: 楼主，第一题用hashmap怎么解
: 多谢了
: 好运
|
b**********r
发帖数: 91 | 14
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
b**********r
发帖数: 91 | 15
use dp, it can be converted to the classical max path problem of squared
matrix, mirror the triangle around the n-th level, but the values at the
nth level should be doubled.
cock tail sort
or smooth sort (but writing smooth sort is too hard for interview)
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
g******0
发帖数: 221 | 16 可不可以讲一下金字塔的题目？ 没看明白。。。
Let me see if I understand the problem:
Let the following be the pyramid.
level 1: n11
level 2: n21 n22
level 3: n31 n32 n33
level 4: n41 n42 n43 n44
...
level n: nn1 nn2 ... nnn
Find a path from n11 to any number in level n, such that the sum of the node
values encountered in the path is minimal.
What i don't understand is what counts as a valid move?
for example, going from n21 to the next level, are n31,n32 the only valid
moves? Is n33 not valid?
请大虾解释一下.谢谢了!
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
s*****y
发帖数: 897 | 17 So you could use the same element in the array more than once?
from
【在 w**7 的大作中提到】
: 大概写个伪代码，差不多就这样
: input : a[], target
: for(int i = 0; i < a.length; i++)
: for(int j = 0; j < a.length; j++)
: {
: sum = a[i] + a[j];
: if(hashmap.find(target-sum))
: The four number is a[i], a[j], and the the element with index from
: hashmap.getKey(target-sum)
: else
|
k***n
发帖数: 11247 | |
m*****k
发帖数: 731 | 19
the
>so the first k elements must be the
>first k elements in the final result???
array: 2 4 1 3
k = 2
【在 d*****o 的大作中提到】
: 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 | 20 array: 2 4 1 3
k = 2
qsort partition:
21 43
count sort:
12 34 |
|
|
j******l
发帖数: 10445 | 21 只能说明楼主对自己的感觉有偏差。
医学上叫：神经性功能失调 |
P********p
发帖数: 1429 | 22 bless
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
a*******y
发帖数: 559 | |
x***n
发帖数: 70 | 24 Q3:qsort的话，每次从数组中取新的节点插入到待sort的数组应该怎么做呢？我想它还
可以用red-
black tree来做吧，这样插入时间复杂度为lgk,和lz的方法一样，整个的时间复杂度仍
为O(nlgk)
另外，counting sort好像不可以吧？并没有说这个数组中存放的是integer啊。
for
qsort.
【在 d*****o 的大作中提到】
: 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.
|
x***n
发帖数: 70 | 25 请问下面这句话怎么理解呢：
The four number is a[i], a[j], and the the element with index from
hashmap.getKey(target-sum)
这样一共不就只有三个数么？
另外下面的insert是做什么的呢？谢谢。
from
【在 w**7 的大作中提到】
: 大概写个伪代码，差不多就这样
: input : a[], target
: for(int i = 0; i < a.length; i++)
: for(int j = 0; j < a.length; j++)
: {
: sum = a[i] + a[j];
: if(hashmap.find(target-sum))
: The four number is a[i], a[j], and the the element with index from
: hashmap.getKey(target-sum)
: else
|
x***n
发帖数: 70 | 26 q1：请问DP应该怎么写呢？非常感谢
for
qsort.
【在 d*****o 的大作中提到】
: 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.
|
w**7
发帖数: 71 | 27 这个可能我代码什么的说的不清楚
对于处理4个数的情况：
思路就是通过两个循环，找到所有的pair(i,j),当然i！=j，这里的Pair就是从数组中
找到的两个数
然后再用之前套用两个数的情况，问题转换成找两个Pair，使得两个Pair的和等于
target.
所以为了防止重复
for(i = 0; i
for( j = i+1; j
pair(i,j) = {a[i], a[j]};
接下来的处理方法跟处理“找两个数，和等于target”一样了。
【在 x***n 的大作中提到】
: 请问下面这句话怎么理解呢：
: The four number is a[i], a[j], and the the element with index from
: hashmap.getKey(target-sum)
: 这样一共不就只有三个数么？
: 另外下面的insert是做什么的呢？谢谢。
:
: from
|
x***n
发帖数: 70 | 28 请问金字塔问题中的路径长度值是什么呢？
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
w**7
发帖数: 71 | 29 首先金字塔的形状大概是这样，有点像杨辉三角
L0: 1
L1: -1 3
L2: 3 2 4
L3: 5 6 7 8
也就是说第i层得第j个元素的child节点是i+1层得第j个和j+1个
hashmap key: <层数，序列号> 比如表示第i层的第j个
value表示从这个节点到底部路径上所有节点的value最大值
对于上面的例子：
开始处理最后一层
(<3, 0>, 5) (<3,1>, 6) (<3,2>, 7) (<3,3>, 8）
然后是L2：
处理<2,0>时，看他的child节点<3,0>,<3,1>取value最大的，6，然后加上自己的3
（<2,0>,9),同样<2,1>看<3,1> <3,2>取value最大的7,加上自己的2（<2,1>, 9)
(<2,2>, 12)
然后处理L1：
略
最后更新到L0，L0的value就是从L0到底部的路径最大值
这其实也是DP，用数组也可以，只是当时觉得三角形里用数组会浪费好多空间，直接
hashmap就是O(n)space
【在 x***n 的大作中提到】
: 请问金字塔问题中的路径长度值是什么呢？
|
d*****o
发帖数: 28 | 30 //Notes: may have bug, just show the ideas
Can not input in Chinese, so write in English -
Q1: code:
for k =3, psedocode: // (O(N^2))
input: A[], S
Arrays.sort(A); // O(NlogN)
for(int i = 0; i < A.length-2; i++) // O(N^2)
{
// set A': A - A[i]
findIt(A[i], S-A[i], A'); // find two element in A -A[i] sum to S -
A[i], O(N)
}
DP solution:
// not exactly the solution, just to decide how many K elements sum to
// a value S
input A[], N, K, S
N- size of the array
K- number of elements to be sumed (k=3,4,...)
S - Sum
// initialize
Table[N][K][S] = ...
for i = N to 0 {
for k = 0 to K {
for s = 0 to S {
if(k == 0)
{
if (s==0) {
table[i][k][s] = 1
} else {
table[i][k][s] = 0
} else if (i == N) {
table[i][k][s] = 0;
} else {
table[i][k][s] = table[i+1][k-1][s-A[p]] + table[i+1][k][s]
}
}
}
}
Result: table[0][K][S]
Q2: DP code
int p[n][n] = ...
int acc[n];
for(int i = 0; i < n; i++)
acc[i] = p[level-1][i];
int len = level-1;
for(int i = level-1; i >=0; i++)
{
for(int j = 0; j < len-1; j++)
acc[i] = Math.min(acc[i] + p[i][j], acc[i] + p[i][j+1]);
len--;
}
result: acc[0] |
|
|
d*****o
发帖数: 28 | 31 Correction:
Q2: DP code
int p[n][n] = ...
int acc[n];
for(int i = 0; i < n; i++)
acc[i] = p[level-1][i];
int len = level-1;
for(int i = level-1; i >=0; i--)
{
for(int j = 0; j < len-1; j++)
acc[i] = Math.min(acc[i] + p[i][j], acc[i] + p[i][j+1]);
len--;
}
result: acc[0] |
x***n
发帖数: 70 | 32 非常感谢。这样算法复杂度为O（n2)对吧 我给想错了，认为是O（n3）了
【在 w**7 的大作中提到】
: 这个可能我代码什么的说的不清楚
: 对于处理4个数的情况：
: 思路就是通过两个循环，找到所有的pair(i,j),当然i！=j，这里的Pair就是从数组中
: 找到的两个数
: 然后再用之前套用两个数的情况，问题转换成找两个Pair，使得两个Pair的和等于
: target.
: 所以为了防止重复
: for(i = 0; i: for( j = i+1; j : pair(i,j) = {a[i], a[j]};
|
x***n
发帖数: 70 | 33 明白了 非常感谢
【在 w**7 的大作中提到】
: 首先金字塔的形状大概是这样，有点像杨辉三角
: L0: 1
: L1: -1 3
: L2: 3 2 4
: L3: 5 6 7 8
: 也就是说第i层得第j个元素的child节点是i+1层得第j个和j+1个
: hashmap key: <层数，序列号> 比如表示第i层的第j个
: value表示从这个节点到底部路径上所有节点的value最大值
: 对于上面的例子：
: 开始处理最后一层
|
x***n
发帖数: 70 | 34 也就是说在这个问题中，有这样一个限制吗：比如从i+1到i层，对i层的某个节点j，它
只能连接i+1层
的child节点（即第j个和第j+1个节点）吗？
【在 w**7 的大作中提到】
: 首先金字塔的形状大概是这样，有点像杨辉三角
: L0: 1
: L1: -1 3
: L2: 3 2 4
: L3: 5 6 7 8
: 也就是说第i层得第j个元素的child节点是i+1层得第j个和j+1个
: hashmap key: <层数，序列号> 比如表示第i层的第j个
: value表示从这个节点到底部路径上所有节点的value最大值
: 对于上面的例子：
: 开始处理最后一层
|
w**7
发帖数: 71 | 35 是的，跟杨辉三角一样
【在 x***n 的大作中提到】
: 也就是说在这个问题中，有这样一个限制吗：比如从i+1到i层，对i层的某个节点j，它
: 只能连接i+1层
: 的child节点（即第j个和第j+1个节点）吗？
|
f*****8
发帖数: 7581 | 36 可能不是你的问题
可能其他有面试的长得好看一点，刚好面试的是个好色的，哈哈。
good luck！！ |
T*x
发帖数: 786 | 37 那你四个数又重复怎么办？
【在 w**7 的大作中提到】
: 这个可能我代码什么的说的不清楚
: 对于处理4个数的情况：
: 思路就是通过两个循环，找到所有的pair(i,j),当然i！=j，这里的Pair就是从数组中
: 找到的两个数
: 然后再用之前套用两个数的情况，问题转换成找两个Pair，使得两个Pair的和等于
: target.
: 所以为了防止重复
: for(i = 0; i: for( j = i+1; j : pair(i,j) = {a[i], a[j]};
|
g******0
发帖数: 221 | 38 很真诚的感叹，你的algorithm好强啊！你一定会有好offer的。
HR说没说句的理由啊？面你的那个美国GG的lastname 是不是B开头的？
【在 w**7 的大作中提到】
: 首先金字塔的形状大概是这样，有点像杨辉三角
: L0: 1
: L1: -1 3
: L2: 3 2 4
: L3: 5 6 7 8
: 也就是说第i层得第j个元素的child节点是i+1层得第j个和j+1个
: hashmap key: <层数，序列号> 比如表示第i层的第j个
: value表示从这个节点到底部路径上所有节点的value最大值
: 对于上面的例子：
: 开始处理最后一层
|
w**7
发帖数: 71 | 39 谢啦，我最近一轮貌似又快被团灭了，这又投了20多个看看新一轮怎么样……
后来我给面我的人发信问了，他说他很suprise, 但是他的feedback肯定是positive的
，HR问了也没说为啥，只说鼓励继续申请……白人GG不是B开头的貌似,不过人不错了，
他们公司起码被拒follow up还是会回邮件的，只是真正为什么被拒，谁也不知道了。
anyway, 继续move on吧
【在 g******0 的大作中提到】
: 很真诚的感叹，你的algorithm好强啊！你一定会有好offer的。
: HR说没说句的理由啊？面你的那个美国GG的lastname 是不是B开头的？
|
m**q
发帖数: 189 | 40 Q3:
Count sort only works when the element values are within
a small range, which is not specified in the original problem.
Thus I think the overall complexity is O(nlgk) instead of O(n).
the
to
【在 d*****o 的大作中提到】
: 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).
|
|
|
m**q
发帖数: 189 | 41 学习了..
【在 w**7 的大作中提到】
: 这个可能我代码什么的说的不清楚
: 对于处理4个数的情况：
: 思路就是通过两个循环，找到所有的pair(i,j),当然i！=j，这里的Pair就是从数组中
: 找到的两个数
: 然后再用之前套用两个数的情况，问题转换成找两个Pair，使得两个Pair的和等于
: target.
: 所以为了防止重复
: for(i = 0; i: for( j = i+1; j : pair(i,j) = {a[i], a[j]};
|
g******0
发帖数: 221 | 42 Q3, 听起来不对啊。Smallest number (assuming sorting in ascending order) is
in the first K elements. The 2nd smallest number is in the first K+1
elements. You were saying "first k elements must be the first k
elements in the final result, ", hmm... i think it's not correct or did
I miss something?
be the
sort to
【在 d*****o 的大作中提到】
: 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).
|
m**q
发帖数: 189 | 43 我理解是这样的，前k小的元素包含在前2k的元素中，因为每个元素的位置和
最终的位置相差不超过k。选择第k个数做partition，把前2k个数分成
1~k, k+1~2k，则partition之后的前k个数就是最终sort之后的前k小
的数，只是这k个数之间现在还没有排序而已。
其中，选择2k个数中的第k个数可以在O(k)解决，partition也是O(k)。
【在 g******0 的大作中提到】
: Q3, 听起来不对啊。Smallest number (assuming sorting in ascending order) is
: in the first K elements. The 2nd smallest number is in the first K+1
: elements. You were saying "first k elements must be the first k
: elements in the final result, ", hmm... i think it's not correct or did
: I miss something?
:
: be the
: sort to
|
s*****d
发帖数: 66 | 44 是说选K个数做pivot么？那么该数也可以是最小的数，你partition晚怎么保证
前k个数就是最终sort之后的前k小?
【在 m**q 的大作中提到】
: 我理解是这样的，前k小的元素包含在前2k的元素中，因为每个元素的位置和
: 最终的位置相差不超过k。选择第k个数做partition，把前2k个数分成
: 1~k, k+1~2k，则partition之后的前k个数就是最终sort之后的前k小
: 的数，只是这k个数之间现在还没有排序而已。
: 其中，选择2k个数中的第k个数可以在O(k)解决，partition也是O(k)。
|
m**q
发帖数: 189 | 45 是先选择前2k个数中的第k小的数，这一步是selection，可以在O(k)内解决；
然后，用这个数做partition，则第1~k-1小的数在它左边，第k+1~2k小的数
在它右边，这个partition也是O(k)。不知道说清楚了没
【在 s*****d 的大作中提到】
: 是说选K个数做pivot么？那么该数也可以是最小的数，你partition晚怎么保证
: 前k个数就是最终sort之后的前k小?
|
r*******g
发帖数: 1335 | 46 一般估计面试官 不希望你用hash，因为需要额外内存开销，金字塔那个题从上到下很
简单。用heap来排序方法思路应该是对的。 |
k*j
发帖数: 153 | 47 想问一下这个partition的过程是in place的吗？还是要另外extra O(n)space
谢谢
【在 m**q 的大作中提到】
: 是先选择前2k个数中的第k小的数，这一步是selection，可以在O(k)内解决；
: 然后，用这个数做partition，则第1~k-1小的数在它左边，第k+1~2k小的数
: 在它右边，这个partition也是O(k)。不知道说清楚了没
|
h*********n
发帖数: 915 | 48 palantir? they are tough.
what's your answer for 3-sum, 4-sum, and k-sum?
【在 w**7 的大作中提到】
: 面试加州P公司
: 一面是华人GG
: 1. 给个数组，给个target, 求找两个数和等于target
: 然后拓展到找3个数，4个数，分析复杂度
: 这经典题，没啥说的，hashmap
: 一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
: 让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
: 这个用hashmap存层数和路径长度值，从底层向上遍历
: 二面是个白人
: 2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
|
m**q
发帖数: 189 | 49 嗯，是in-place的
【在 k*j 的大作中提到】
: 想问一下这个partition的过程是in place的吗？还是要另外extra O(n)space
: 谢谢
|
