b******g
发帖数: 3616 | 1 今天正好复习到这题。顺手写了个k-sum的代码，过了LC的3sum和4sum的test。有兴趣帮
着找找有没有没发现的bug。我觉得理解了3sum的算法，并写过4sum以后，这个kSum其
实也就一个小变种，一个葫芦里的药了。由于代码不短，感觉面试的时候还是分成子程
序写比较好，即使时间来不及写完，至少思路能和面试官说清楚。
思路和排板好看点的代码写在自己的复习总结博客里了：
http://bangbingsyb.blogspot.com/2014/11/leetcode-4sum.html
代码：
class Solution {
public:
vector > fourSum(vector &num, int target) {
vector> allSol;
vector sol;
sort(num.begin(),num.end());
kSum(num, 0, num.size()-1, target, 4, sol, allSol);... 阅读全帖 |
|
n******0
发帖数: 61 | 2 google some introduction or read R extesion,
example cited from "An Introduction to the .C Interface to R":
#include
#include
void kernel_smooth(double *x, int *n, double *xpts, int *nxpts,
double *h, double *result)
{
int i, j;
double d, ksum;
for(i=0; i < *nxpts; i++) {
ksum = 0;
for(j=0; j < *n; j++) {
d = xpts[i] - x[j];
ksum += dnorm(d / *h, 0, 1, 0); // see use R function in C code
}
result[i] = ksum / ((*n) * (*h));
}
} |
|
s******y
发帖数: 72 | 3 Phone Interview:
research + coding,
Coding: String Match strstr(); naive way and KMP, write code
Onsite:
一共见了八个人，六个Enginneers， 两个senior manager，给了一个talk。
问了很多research和system相关的问题，以及coding， 记得的问题有
Coding and Language questions:
1) Given a interger array, find a consective subarray with maximal sum
2) 3Sum, without extra space. How to extend to handle KSum?
3) Write a thread safe queue
4) Editing distance, return minimal distance and the operations (remove,
insert, replace) to convert one strin... 阅读全帖 |
|
s******y
发帖数: 72 | 4 Phone Interview:
research + coding,
Coding: String Match strstr(); naive way and KMP, write code
Onsite:
一共见了八个人，六个Enginneers， 两个senior manager，给了一个talk。
问了很多research和system相关的问题，以及coding， 记得的问题有
Coding and Language questions:
1) Given a interger array, find a consective subarray with maximal sum
2) 3Sum, without extra space. How to extend to handle KSum?
3) Write a thread safe queue
4) Editing distance, return minimal distance and the operations (remove,
insert, replace) to convert one strin... 阅读全帖 |
|
s********s
发帖数: 49 | 5 代码好长啊。。。其实有了2sum,3sum的做法很直观吧：先取出一个数，那么只要在剩
下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)就可以了吧。
所以3sum就退化成了2sum, 取出一个数字，这样的数字有N个，所以3sum的算法复杂度
就是O(N^2 )。
注意你排序只需要排一次，后面的工作都是取出一个数字，然后找剩下的两个数字，找
两个数字是2sum用头尾指针线性扫，这里很容易错误的将复杂度算成O(N^2 log N)，这
个是不对的。
可以参考这个总结 http://tech-wonderland.net/blog/summary-of-ksum-problems.html |
|
|
|
w*********e
发帖数: 49 | 8 上点新鲜面经回馈版面
F家phone
中年亚裔，比较注重细节
3sum, 每个元素可用多次
ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
简单方法写了个recursive的
约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
L家
phone
两个老美都挺nice 一个主面一个shadow
第一题lowest common ancestor in binary tree with parent pointer
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
onsite
1.host manager面，国人大叔，主要是些背景和behavior question
2.technical communication，亚裔小哥... 阅读全帖 |
|
w*********e
发帖数: 49 | 9 上点新鲜面经回馈版面
F家phone
中年亚裔，比较注重细节
3sum, 每个元素可用多次
ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
简单方法写了个recursive的
约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
L家
phone
两个老美都挺nice 一个主面一个shadow
第一题lowest common ancestor in binary tree with parent pointer
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
onsite
1.host manager面，国人大叔，主要是些背景和behavior question
2.technical communication，亚裔小哥... 阅读全帖 |
|
y*******6
发帖数: 173 | 10 就是一个大数组里面（unsorted) 要找sum of 最大的k 个数
int kSum (int [] array, int k);
不就是用heap (priorityQueue) keep the biggest k number 吗? 还能有什么更好的
方法吗？ 面试的好像说有，但不说怎么办。 |
|
