c********p
发帖数: 1969 | 1 返回的是index，这个不能排序吧？排序顺序就乱了。。。
哪个解法最优？ |
|
|
k*******t
发帖数: 144 | 3 可以用先用pair(value, index)， 然后sort pair based on value, 这样也是可以的
，就是比较麻烦点 |
|
|
c********p
发帖数: 1969 | 5 这个有想过但不知道怎么实践。
这个pair，是什么操作，什么数据结构？是自己定义一个wrapper class么？ |
|
k*******t
发帖数: 144 | 6 如果你用c/c++的话 就定义一个struct，里面有两个variable, 一个value, 一个index.
sort时用vector的自带的sort, 不过要自己定义一个comparator。 |
|
|
r*******e
发帖数: 7583 | 8 c++用stl pair就好了..
index. |
|
s*******s
发帖数: 1031 | 9 我的代码：
struct itemRecord {
int index;
int val;
itemRecord(int i, int v): index(i), val(v) {}
};
bool itemRecordLess(itemRecord i1, itemRecord i2) {
return i1.val < i2.val;
}
class Solution {
public:
vector twoSum(vector &numbers, int target) {
vector result;
int n = numbers.size();
vector numRecords;
for(int i=0; i
numRe... 阅读全帖 |
|
|
c********p
发帖数: 1969 | 11 其实这个题用最基本的，每个都试一下，就能通过大oj。
但我不甘心啊。。。 |
|
|
t***a
发帖数: 416 | 13 用个map吧，key是numbers的value, value是numbers的index
这是我前几天写的
class Solution {
public:
vector twoSum(vector &numbers, int target) {
unordered_map index;
for(int i = 0; i < numbers.size(); i++){
auto position = index.find(target - numbers[i]);
if(position != index.end()) { //hit!
vector result;
result.push_back(position->second + 1);
result.push_back(i + 1);
return result;... 阅读全帖 |
|
|
|
g**4
发帖数: 863 | 16 196ms，C++果然是快啊
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > result;
if (num.size() < 4) {
return result;
}
sort(num.begin(),num.end());
for (int j=0;j
int a = num[j];
// 3sum
for (int i=j+1;i
int ... 阅读全帖 |
|
R******1
发帖数: 58 | 17 我之前做的时候是【2500， 4000】，所以很快， 7s左右
刚试了试这个新的range，本来以为是线性增加，时间应该也不不大；
但是，很多target无法满足，就要遍历hash table一次。
【2500， 4000】 用时 7s 命中率1477/1500 绝大多数都很快break了
【0， 1000】 用时 1m56s 命中率445/1000 多于一半要遍历完
建议楼主试试先sort（O（NlogN)), 然后binary search （O（logN)).
2sum.txt ～4MB 所以建设1M个ints
range是【-10000， 10000】， 20000
用hashtable worst case 20000*1M
用sort然后binary search， worst case 1M*log（1M） + 20000*log（1M） ～ 20*1M |
|
m*******0
发帖数: 38 | 18 不是很懂你的意思，里面不会涉及到负数的吧，他是要找出从1～N的数中满足存在两组
不同的数是他们的立方和等于要找的那个数。貌似和2sum有点不一样，就是我们要对所
有1～N都测试一遍？ |
|
m*******0
发帖数: 38 | 19 不是很懂你的意思，里面不会涉及到负数的吧，他是要找出从1～N的数中满足存在两组
不同的数是他们的立方和等于要找的那个数。貌似和2sum有点不一样，就是我们要对所
有1～N都测试一遍？ |
|
A*********c
发帖数: 430 | 20 第一题应该可以优化，在B拷贝完之后可以提前停止，不用copy A剩下的元素到自身。
第二题map的算法是, 排序的算法是
所以说排序算法更好。
对于几sum的问题，2sum和4sum有time-space trade-off 的可能，但3sum 排序是最优
。愚见。 |
|
|
|
j*******t
发帖数: 223 | 23 这不就是2sum么，第一遍扫了放入hashmap，第二遍找hashmap中是否有target - val。
唯一要判断就是是否有值为target / 2。这个在放入hashmap的时候判断下就可以了。 |
|
c**w
发帖数: 1024 | 24 两个公司都挂了，但是还是上个面经。
amz 电面2轮，onsite 5轮，每轮1个小时
电面1： 2sum, 2个stack实现queue
电面2： 实现fixed size的queue， OOD设计题：2个电梯调度的设计
onsite round 1: 在2个等长排序数组中找第k大的元素。
有一个n*n的array，里面的数是1-n^2。找出连续递增的最长序列的长度。方向可以是
上下左右。
比如：
1 3
2 4
最长的递增是3，可以是1->2->4 也可以是1->3->4
round 2： 全behavior，这轮挂了，因为表示了觉得以前的工作没意思。这轮的结
论是没有领导力。所以behavior还是要好好准备。amz很在乎的一点是leadership
principle
round 3: map里面新增一个updateAll(int val1)，调用后，get(key)返回值都是val1
。但是之后如果set(key, val2)后，get(key)返回值是val2.要求所有操作都o(1)。
第二题是count sort变种，不难。
round 4: OOD设计机场调度系统。这轮... 阅读全帖 |
|
h*******8
发帖数: 29 | 25 的确variance很大。我被问了三题，都是leetcode。2sum, generate parentheses 和
parentheses matching。
话说intern面试会不会参考题目难度评分啊？ |
|
m****v
发帖数: 88 | 26 Dropbox:
2sum, 3sum both with duplicates
30分钟写出来了 然后挂了 可能bar比较高
Pinterest:
Map/reduce top 10 ip address
java iterator wrapper (more functions 忘了 反正挺难写的). input is a
original queue iterator
symmetric tree
get the kth element uniformly (swap by 1/k possibiliy) |
|
m****v
发帖数: 88 | 27 Dropbox:
2sum, 3sum both with duplicates
30分钟写出来了 然后挂了 可能bar比较高
Pinterest:
Map/reduce top 10 ip address
java iterator wrapper (more functions 忘了 反正挺难写的). input is a
original queue iterator
symmetric tree
get the kth element uniformly (swap by 1/k possibiliy) |
|
h********g
发帖数: 7 | 28 电面1:
两道SQL题，一个半月前的，实在记不得，不过挺简单，连嵌套都不用
电面2：
2sum，没什么好说的，半个小时完事
onsite：5轮
1.第一题是找出数组中的unique number。第二题是给一个数组和k，如果存在一个数
arr[i]，它的duplication在i-k到i+k之间，则返回true，else false
2.lunch interview，都是那种tell me a time when...的题型
3.一道班上没见过或者被我忽略了的题：给一个matrix[][]，有些位置的值是*，代表
星星，连续的星星算是一个星座，问matrix里有多少星座（单独的星星也算一个星座）
e.g.
**0**0
*00*00
000*00
*00000
上图有三个星座，返回3
4.pair-wise reverse a linked list
input:1->2->3->4->5->null
return: 2->1->4->3->5->null
设计题是设计一个ranking system，用于查找购买次数最多的top k music
5.find the first u... 阅读全帖 |
|
z***g
发帖数: 51 | 29 受到版上版下的xdjm的帮助，希望发个贴感谢一下。报G,T,A, Bloomberg intern面经。
背景不咋地，PhD但是偏理论，什么都做但不精，无实习和实践经历。1月才开始准备，
以为要挂，结果在板上受到不少鼓励和内推机会，坚持到了最后，非常感谢。前些天看
到版上有争论，帮不帮国人，就我自己的经验，我找了不少的人，无论版上下全都无一
例外特别热心，算是超级正能量。
感谢Xiaomeng师兄内推，Zekai师弟，小白和PC的内推，成功拿到G,T,A面试机会。
另外感谢kingse@qualcomm, Joe@akamai，imx@samsung,内推了但是我自己水平不行没
拿到面试，前些天找Google Host match时，多谢luckcatcn和johnkonet帮忙，还有刷
题群里的好兄弟kevin和WELKIN鼓励。
G SDE 2 phone interviews:
第一题：设计一个函数int function(int [] a)， return index of local minima,
local minima is: a[i-1]>a[i]阅读全帖 |
|
r******l
发帖数: 10760 | 30 一个题目，怎么才能知道自己的答案是不是好的呢？比如2sum问题，我用最直接的双重
循环O(n^2)的做法也是accepted。我想任何面试如果你只给个O(n^2)的解法肯定都回挂
掉吧？ |
|
h*d
发帖数: 19309 | 31 我的理解就是2sum可以用夹逼或者hashtable来做 |
|
f*******w
发帖数: 1243 | 32 背景：EE 非名校PhD 无线通信方向，预计夏天毕业，两次实习经历（12年Broadcom，
13年Amazon）
2月的时候发现时间紧迫，开始锁定SDE的目标狂投简历……真正意义上的海投，大大小
小有近百家吧，基本没有找人refer。偶尔在版上看到有人帮忙refer的时候也会问一下
，不过好像都被简历拒了- -
所有面经放上……
Bloomberg:
02/21 电面阿三，没有写具体code，都是说思路
Why bloomberg?
Mention and describe one of your projects. What is your role on this project?
Polymorphism in C++, how to implement virtual functions (vtable), different
types of polymorphisms (dynamic/static).
Two sum (with or without extra memory)
Kth node to the last (Linked List)
Implement m... 阅读全帖 |
|
d********i
发帖数: 582 | 33 题目考的是2sum和3sum。 太简单了，不可能不过啊。。 |
|
l*****a
发帖数: 14598 | 34 你应该出2sum吧
binary search的边界条件有时候会出问题的 |
|
T*******e
发帖数: 4928 | 35 能不能给个2sum的简洁代码？我一直纳闷别人是怎么写的。 |
|
r****s
发帖数: 1025 | 36 here you go, 是不是太复杂了？
public Class TwoSum {
Map searchMap = new HashMap();
public void get2Sum (int[] input, int sum){
for (int i=0; i< input.length; i++) {
searchMap.put(sum-input, i);
}
for (int i=0; i
if (searchMap.containsKey(input[i] && searchMap.get（input[i]!=i)
System.out.println("2sum: "+input[i]+" "+input[searchMap.get(
input[i]));
}
}
} |
|
x******0
发帖数: 1025 | 37 谢谢曾经面过我的国人大哥，都非常nice，只是自己水平还不好
2sum是把 存到hashmap里面。不用两个for loop（虽然都是O(N)）.
上面的例子{４， ４}，sum=8 存(sum - input[0],0)之后，searchMap.containsKey(
input[1])就已经找到答案了，一个for loop就可以了，输出0, 1 |
|
r*******k
发帖数: 1423 | 38 第一个，转化完了，正好是排了序的双向链表
标准2sum的解法
转化最简单的方法，中序遍历，存到一个list里
然后遍历这个list，改left和right指针 |
|
i******s
发帖数: 301 | 39 枚举所有pair, 一共有n*(n-1) / 2个，然后转化为求2sum。重点是去重，可以在pair
里面记录在原来数组的index。所以最好是O(n^2)吧。你的解法应该是O(n^3) |
|
m****t
发帖数: 555 | 40 1,2,7,8, 要求2sum<=9
有(1,2), (1,7), (1,8),(2,7), 不是2个，是4个
贴个简单的解法吧。
int le3Sum(int[] a, int X) {
int count=0;
Arrays.sort(a);
for (int i = 0 ; i <= a.length - 3; i++) {
int j = i+1;
int k = a.length - 1;
while (j < k) {
if (a[j] + a[k] <= X-a[i]) {
count += k-j;
j++;
} else {
k--;
}
}
}
... 阅读全帖 |
|
f*****u
发帖数: 308 | 41 1. 国男
2sum
数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
Merge interval
对我的最后solution表示很满意。
2. 国男
stream of strings like this
"1 34 5 6"
"3 4 5 6 3"
"4 5 6 3 3"
...
每行是一个包含数字的string。去除所有数字完全重复的strings.比如这里的第二和第
三行数字完全相同，可以合并成一个。要求合并所有数字完全重复的strings。
最后表示对我的优化结果不满意。
3. 有点像东南亚或者拉美后裔，英文无口音
Reverse linkedlist
不断要求优化。
4. 欧洲人
写一个小游戏。MxN 的格子上有一条蛇，蛇头可以向前，左，右移动，撞到自己身体任
何部位或者撞到边界就算死。
5. 阿三
有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
timestamp被... 阅读全帖 |
|
r****7
发帖数: 2282 | 42 1的2sum为什么算两个(2,8)pair，而不是一个或者六个？
2个这个我觉得没啥道理 |
|
i******t
发帖数: 798 | 43 en多谢指点
假设2sum
是这个意思吗
prei =-10000;
for(int i =0; i
{
if(prei == A[i])
{
continue;
}
prei = a[i];
prej =-10000;
for(int j =i+1; j
{
if(prej == A[j])
{
continue;
}
prej = a[j];
// do sum test....
}
}
是这个意思吧 |
|
r*******h
发帖数: 315 | 44 差不多，但是前提是数组要排好序，如果排好序，2sum的更好解法是双指针，从两头
skip重复的。 |
|
f*****u
发帖数: 308 | 45 k-sum: 给定一个数组A, A中无重复数字,且都是正整数,k,target是某两个给定数,求A
中所有可能的k个数,其和等于target.也就是2sum,3sum,4sum等等的通解. |
|
y**********u
发帖数: 6366 | 46 我。。。我属于2sum都不会写的人。。。
manager都应该有一定的技术功底，还有视野，我看二爷很适合啊 |
|
d*****1
发帖数: 263 | 47 各位朋友，打扰了。
美国南部的一个大学附近的小公司。
我是公司的第一个国际员工，找老板确认过，可以帮忙申请绿卡，H1B等。（我还没有
开始申。）
老板比较年轻，但是超级能忽悠钱。
手下几个公司，IT部门是刚开始搞。
搞了几个项目都是上千万的funding。因此三两年内是不用担心垮掉。（老板还有
construction company, real estate company等)
现在做的两个项目都是web, app相关。
如果你不是非Flag不去，或者不介意来小地方的话，可以给我发份简历。
anderson.wang24 AT gmail dot com （非 常用邮箱，不保证当天回复）
如果大牛们感兴趣，想来make great impact，我举双手双脚欢迎。LOL
公司不会有版上常见的那种办公室政治。（我努力，呵呵）
来了之后，大家一起努力干，工资待遇福利什么的，我努力帮你跟老板要，只要你好好
干。
老板是标准的资本家心态，只要你能给他带来效益，他不在乎多付你钱。
------------------------------------------------------... 阅读全帖 |
|
d*****1
发帖数: 263 | 48
我不要求数学原理，最简单的做除法，用个while就行。（有点儿小tricky可以speedup
些）
或者你给个hashmap我也认了。
一个老白，就是没有思路。只会用if else。
问题是这样，我提前告诉老白了，题目会很简单， 就像is power of 2.
我都快哭了。真的不能再给他简单了。
后来给出了道2sum，人家直接放弃了。
人还是老板推荐的。面试时老板恰恰就在旁边。
老板本来想要的，被我坚决顶回去了。 |
|
s**a
发帖数: 293 | 49 讲真，lz的要求不算高
正儿八经出来找工作，2SUM都不会做，怎么也不可能招的。。。 |
|
t********5
发帖数: 522 | 50 看第二题2sum 我觉得他们想问的是不是：。。
每次被call写一个log
然后整个log放到一个实时查询系统上面去 查询就是 count(*) 设置查询间隔为[1]分
钟 超过threshold就报警
lol |
|
