q****x
发帖数: 7404 | 1 全是简单的奇偶性分析。
1、70个数字排成一行，除了两头的两个数以外，每个数的3倍都恰好等于它两边的两个
数的和，这一行数的最左边的几个数是这样的：10，1，3，8，21，。。。问：最右边
的一个数是奇数还是偶数？
题不对。1的3倍不等于10和3。
2、学校组织运动会，小明领回自己的运动员号码后，小玲问他：“今天发放的运动员
号码加起来是奇数还是偶数？”小明说：“除开我的号码，把今天发的其它号码加起来
，再减去我的号码恰好是100.”今天发放的运动员号码加起来，到底是奇数还是偶数？
a+b和a-b的奇偶性相同。
3、在黑板上写出三个整数，然后擦去一个换成所剩两数之和，这样继续操作下去，最
后得到88，66，99.问：原来写的三个整数能否是1，3，5？
题不对。擦去一个，替换成剩余两数之和，这样总和始终是偶数。结果不可能是88，66
，99。
4、将888件礼品分给若干个小朋友。问：分到奇数件礼品的小朋友是奇数还是偶数？
显然是偶数。如果是奇数，总和也是奇数。 |
|
c****p
发帖数: 6474 | 2 除了两头的两个数之外，理解上是一共两个数，原题的意思可能是一共四个数。
第3题人家就问的可能不可能。 |
|
a*******o
发帖数: 67 | 3 电面了两轮
第一轮题1 merge sort，SORTING好的两个ARRAY MERGE，问复杂度
题2，一个给定的SORT好的数列，给一个和的值，求返回所有sum是这个数的任意连个数
的值
题3，给一个字符串，求其中第一个只发生一次的字符
然后问了一下HASHTABLE是什么，HASH FUNCTION是什么，如何解决COLLISION
都是挺经典的题，第一题写代码，后面两个都只要谈想法
第二轮题1 abstract 和 interface区别是什么
题2 overloading和overriding区别是什么
题3 equals和==区别是什么，什么是多态
题4 判断两个树是不是identical的，要写代码
onsite
第一轮问什么是generics，什么是factory pattern，又问了abstract class和
interface区别
编程题是给一个棵树的节点增加一个next指针，指向同一层在他右边的那个节点，最右
边的节点的指向null
第二个编程题是关于linux的，我说我没用过linux，他就没问了。
第二轮问什么是给N个FILE，每一个FILE每一行的第... 阅读全帖 |
|
h********g
发帖数: 155 | 4 先考虑如下基本问题：
假定一个数组前N个数是正数，后M个数是负数，如何把M个负数全部移到头部，N个正数
全部移到尾部，同时不改变正数与负数的相对次序？
其实用 N+M 次交换操作就可解决上面问题。因为每次移动一个负数时，你不需要只向
前移一位，而是可以－次移很多位。
比如你有：
３ ２ ５ －１ －２
你可以把２与－１交换，５ 与－２交换得到：
３ －１ －２ ２ ５
再把 ３ 与 －１ 交换
－１ ３ －２ ２ ５
再把 ３ 与 －２ 交换得到
－１ －２ ３ ２ ５
于是移位完成，用了４次交换
于是当 M 能整除 N 时， 用上面的办法其实只交换N次就可以完成了，当M不能整除N时
，你也可以用数学归纳法证明只要M+N次交换就够了。
那么现在你再回过头来看我的算法，就会发现它所需的总操作数最多是：
(l(k-1, k)+1)+(l(k-2,k-1)+2)+(l(k-3, k-2)+3)+...(l(1, 2)+k-1)+(l(0, 1)+k)
其中l(i-1, i)表示第i-1个负数和第i个负数之间所含的正数的个数,
所有的l(i-1, i) 1<=i<=k 的和最多是 N,
所以... 阅读全帖 |
|
G*********t
发帖数: 71 | 5 本人背景：无名学校CS小硕，工作一年在一家无名微型公司, 三低三无人物：资历低，
工资低，水平低、无绿壳，无淫脉，无老婆
中年白淫，语速清晰
面经：
1. 上来要coding 写一个很简单的函数 如果能被5整除输出buzz，能被3整除输出fizz
，同时能被这两个数整除输出舒服fizzbuzz，如果都不能被这两个数整除输出这个数。
2. 给你两个string 是否是anagram，我说两个hastable，然后减少到了一个，面试官
最后提出一个比较有价值的问题。如果想检验这个hastable所有value是否都为0，除了
挨个查之外用C或者C++有没有更快的办法
3. 如何实现priority queue。
三个问题，但是问了很多时间空间效率的问题，同时也问了特别特别多怎么写test
cases，木经验啊，test不咋熟，就在那冥思苦想胡说八道。
从板上的大牛牛们学了很多，所以小的尽微薄之力分享一下下。 |
|
G*********t
发帖数: 71 | 6 本人背景：无名学校CS小硕，工作一年在一家无名微型公司, 三低三无人物：资历低，
工资低，水平低、无绿壳，无淫脉，无老婆
中年白淫，语速清晰
面经：
1. 上来要coding 写一个很简单的函数 如果能被5整除输出buzz，能被3整除输出fizz
，同时能被这两个数整除输出舒服fizzbuzz，如果都不能被这两个数整除输出这个数。
2. 给你两个string 是否是anagram，我说两个hastable，然后减少到了一个，面试官
最后提出一个比较有价值的问题。如果想检验这个hastable所有value是否都为0，除了
挨个查之外用C或者C++有没有更快的办法
3. 如何实现priority queue。
三个问题，但是问了很多时间空间效率的问题，同时也问了特别特别多怎么写test
cases，木经验啊，test不咋熟，就在那冥思苦想胡说八道。
从板上的大牛牛们学了很多，所以小的尽微薄之力分享一下下。 |
|
E*******0
发帖数: 465 | 7 我目前还没有找到一个方法解决这个问题。
我有一些基本的clue供大家参考：
1,如果2*N个数都相等的话，Min(Sum)=2*val;
2,如果2*N个数有一个特别大，其大都很小，Min(sum)=max value;
3,如果2*N个数是[1,2,3,...,N,N+1, ..., 2*N], Min(Sum)=2*N+1=2* average. |
|
c*******d
发帖数: 131 | 8 提供一个想法，我暂时还没想到反例：
假设我们有N个bag来装这2N个数，首先将N个bag全部初始化为0， 用一个max变量实时
记录这N个bag的最大的那个, 将2N个数字从大到小排列，然后按照如下规则将这个2N个
数一个一个装袋：
case 1: 从最大的bag开始search，找到第一个这样的bag：满足这个bag的和加上这个
数不大于现在的max，如果能找到这个bag，就把这个数装到这个bag里面。
case 2： 找不到这样的bag，这说明已经search到最后那个最小的bag了(并且这个也不
满足case1的条件)，如果这样的话，就将现在这个数加入这个bag，并且更新max为这个
bag的值。
example： 25 13 12 7 7 7
bags： 0 0 0， max = 0.
25： 25 0 0, max = 25. (case 2)
13: 25 13 0, max = 25. (case 1)
12: 25 (13,12) 0, max = 25. (case 1)
7: 25 (13,12) 7, max = 25. (case 1)
... 阅读全帖 |
|
n**s
发帖数: 2230 | 9 应该不只这个数。
首先应该是左边个数乘以右边个数。左右两边数组次序不变，还可以交叉。这样要再乘
以交叉的数目。
可以定义为
N(k)=N(x)*N(y)*(number of x and y arrays interleaved) |
|
d****o
发帖数: 1055 | 10 老题，作为题库吧。最近面的。
亚麻:
题1，给定两个二叉排序树，可能结构不同，问是否他们具有完全相同的值。
题2，罗马字符转换为整数。
经验：面试不能急，要先弄清楚题意。
谷歌：
1. 给定n个数，每个数有一个出现得概率，这样就形成了一个分布，根据这个分布，生
成k个数。
2. 有一个很长的DNA串，给定一个短的DNA串，问你短的子串是否出现在长DNA串中。延
伸问题,如果只是找和短串相似的长串中子串怎么办？ 延伸问题二，加入长串太长了，
内存放不下怎么办?
storm8,小公司
1. 在一个排好序的被向右移动过的整数串中查找最小值。
2. 螺旋打印一个矩阵
3. 给定三种颜色，排序。
4. 机器人从一个二维举证左上走到右下，有多少种走法？有障碍怎么办？
职业社交公司
1. 求某数的power |
|
m******d
发帖数: 25 | 11 是不是还可以这样做：
1，2，4，7，12，20，33，54，88，143
从第三个数开始每个数等于前两个数的和加一。这样也可以保证能知道是一个还是两个
瓶子超重。
扩展一下，如果可能有任意个瓶子超重，那么每个数要大于前面所有的数的和。那么2^
n就可以满足。 |
|
m******d
发帖数: 25 | 12 是不是还可以这样做：
1，2，4，7，12，20，33，54，88，143
从第三个数开始每个数等于前两个数的和加一。这样也可以保证能知道是一个还是两个
瓶子超重。
扩展一下，如果可能有任意个瓶子超重，那么每个数要大于前面所有的数的和。那么2^
n就可以满足。 |
|
h*****3
发帖数: 1391 | 13 我糊涂了，0 xor 0 = 1; 1 xor 0 = 1;
怎么会3个0？
还有，如果3个数都一样的，也就是说有2个数的相对位置是完全pair的，那和题目中有
3个数不一样岂不是矛盾了？ |
|
N**n
发帖数: 832 | 14 看hacker's delight，
1，数后缀0的个数
2，右移后缀0个数这么多
3，判断这个数+1是不是2的完全平方数 |
|
f*****e
发帖数: 2992 | 15 有一个数组，先严格递增，后严格递减，最大值位置不知道，给一个数，求这个数在数
组的位置(数组中有多少个数小于这个数)。可能是老题了。 |
|
f***h
发帖数: 8 | 16 从careercup上看到的题目：
There is a game they termed as Mingo. A random generator (like a speaker
standing in a group housie game calls out a number) generates out any number
from 1 to 1000.
There is a 10X10 matrix. A random generator assigns values to each block of
this matrix(within 1 to 1000 obviously).
Whenever, a row or a column or a diagonal is fully filled in this 10x10 from
the numbers called out by the speaker, its called a 'Mingo'.
Write a program that will find first Mingo, then second Mingo... 阅读全帖 |
|
f*********m
发帖数: 726 | 17 能不能这样？
先定义两个index（index1_1, index2_1),每个指向数组头，然后比较移动，每次移动
值小的，直到两个index的和为K。然后，再定义两个index（index1_2, index2_2),每
个指向数组头，用同样的方法每次移动index1_1或 index2_1，也同时移动index1_2或
index2_2。当index1_1或 index2_1指向给定的值时，index1_1或 index2_1指向左边的
第K个数， 记录他。继续移动index1_1或 index2_1，也同时移动index1_2或 index2_2
，当index1_1或 index2_1指向给定的数时，index1_2或 index2_2指向给定的数右边第
K个数。最后比较这两个数与给定书的差值。 |
|
j*******e
发帖数: 1058 | 18 烙印打来电话，接了。感觉paypal里面很混乱，管理超级差，我也开始怀疑paypal能不
能算是ebay一个档次的公司了。ebay感觉都算是tier 2里面的中上，package也是这个
层次吧。为什么呢。烙印居然不知道我2面，还问我是几面，说之前coding过没。也许
是故意藐视我吧。然后开始问问题，都比较顺利。
后来开始coding，就是很简单的sorted array里面，找distinctive integer个数。很
快一个for 循环就写出来了。烙印要求找绝对值的distinctive 个数，想了2个办法，
第一个是绝对值，然后sort，第2个是，把负数变正，然后倒序成一个array，比如，－
5,－3,－1,成5,3,1,再成，1,3,5,然后跟剩下的array做merge。再用刚才写的方法查出
来个数。
最后merge没时间写，烙印就问，可以不可以不用多搞2个array，我说可以。但是就麻
烦些，需要array里面的其他elements需要移位，还有多几个index，烙印还算满意。
最后我犯了一个低级错误，他问，如果传进去int［］，你操作后，改动后，实际的int
［］... 阅读全帖 |
|
e****e
发帖数: 418 | 19
是。
根据不同的类型，写不同的comparator，再把comparator 传进那个最初的算法（最初
的算法是针对数组元素是整数型。）
1. grep + regular expression
2. list或者open address
3. 我用了一个list, 两个list也能解决。
4. 我是用的heap, quick select更好。
：onsite1：
：2. 线性扫一遍
： followup：排序后线性扫一遍？
同意。排序后线性扫一遍还是n平方的时间复杂度。这个followup问题我没有回答出来
，至今也不知到有小于n平方的解法。
：onsite2：
：2. 二分
：3. 不清楚数据模型的角度是啥
是。data model.
：onsite4：
：2. 线性比较一下
followup：排序一下？这个不清楚
是线性比较，我的思路：有两种情况是没有overlap, 有四种情况是overlap,所以只用
看是没有overlap，再取反就行了。
followup, 预处理：按照区间数组里所有的点之间《分段》，计算每段上所重合
interval的个数。当给定区间来... 阅读全帖 |
|
f*****e
发帖数: 2992 | 20 面4.2很简单的:
记每个interval是[Li,Hi]，给定一个interval A=[x1,x2]
找{L1,L2,...,Ln}中小于等于x2的个数，记为n1，
找{H1,H2,...,Hn}中小于等于x1的个数，记为n2。
与A相交的interval个数就是n1-n2
如果对上限和下限排序，然后再二分查找就可以得到n1和n2。
所以是复杂度是O(lgN) |
|
d*****y
发帖数: 1365 | 21 先排序,x1=i.其他位置填零
.当然构建这个矩阵是N^2.但是如下所述,我们只需要算2*N个数就可以了.
问题变成找这个矩阵A的最大的N个值.由于A右上角是最大值,所以维持一个max-heap,最
开始的时候把右上角放在heap.然后每次从这个heap里面娶一个数,就把她的左边和下边
放到heap里面,由于对于每个数,每次最多放两个数去heap. 所以O(n log n)
但是这条题目太难了一点,让我面试的时候做,是打死我也做不出来的. |
|
j******2
发帖数: 362 | 22 哦。
第一问具体是不是这样：
用3个phase:
1. 确定在哪个million——O(n)
2. 确定在哪个thousand，并根据前面和后面的数，确定要找thousand里的第k个数——
O(n/1000)
3. 用partition的方法找出一千个数的第k个数——O(n/1000000)
总的时间复杂度还是O(n)
1B的数还不到整数范围，所以每个phase只要一千个int的counter就行了, partition又
是in-place的，所以总的空间就要1k*4byte=4kb。
第二问我觉得好象挺常见着的，用两个heap做，cc150书里的18.9的原题。不过没说
stream能有多长就是了。
谢谢大师指点哦～～ |
|
d*********g
发帖数: 154 | 23 1. 给一个array，size n, 里面每个数字的range 是 1～n, 输出 duplicates 以及 每
个duplicate出现的次数 要 O(1) 空间
这个题要怎么做到O(1)空间？记录结果至少也需要O(n)空间吧？比如给的数组是A={3,
1, 1, 2, 2}，那需要一个数组来记录每个数出现的频率 freq = {2, 2, 1, 0, 0} 这
样，表示第1个数出现过2次，第二个数出现过2次，以此类推~~ |
|
d*********g
发帖数: 154 | 24 1. 给一个array，size n, 里面每个数字的range 是 1～n, 输出 duplicates 以及 每
个duplicate出现的次数 要 O(1) 空间
这个题要怎么做到O(1)空间？记录结果至少也需要O(n)空间吧？比如给的数组是A={3,
1, 1, 2, 2}，那需要一个数组来记录每个数出现的频率 freq = {2, 2, 1, 0, 0} 这
样，表示第1个数出现过2次，第二个数出现过2次，以此类推~~ |
|
o****d
发帖数: 2835 | 25 cc150有一题是说
把1-n分成大小一样的块 统计每个块里面的数存在于数组中的个数
（假设没有duplicate）
比如每个块是1000个数 但发现之统计出999个数
那么missing的数就在那个块里面
然后再找一遍那个数组就知道了 |
|
f*******t
发帖数: 7549 | 26 我觉得swap不如位运算。
位运算是把N+1个数全读一遍。
swap概率上平均要读(N+1)/4个数，但对每个数，需要做swap操作的概率是N/(N+1)。也
就是说，要进行N/4次swap。swap的cost不止是位运算的4倍吧。 |
|
l****i
发帖数: 2772 | 27 报一个迟到的面经，4月底onsite的，早上8点进，下午4点出，第2天早上9点收到offer。
记得的题目,所有题目都白板写了完整coding：
1. 未排序数组返回第K大 （quick select+median of medians）
2. LCA （带parent节点+不带parent节点）
3. 返回链表的倒数第K个数
4. 反转句子，不反转词
5. 中序+后序构建BST
6. 未排序数组，返回需要最少移动几个数，使这个数组变成排序
例如， [1,3,2] 返回1
[1,3,5,2,7,9,4] 返回2
我白板给的是复杂度O（n^2）的DP解法，就是DP里经典的求最长不降序列。面试官
问为什么选择DP。然后让优化，我解释说，最长不降序列有一个O（nlogn）的算法，需
要占用更多的space，具体的算法，我记得不是很清楚。面试官说有一个求2个数组最大
相似度的算法，是O（nlogn）,可以用来解决这个问题。就是比较[1,2,3]和[1,3,2]的
最大相似度。面试官和我说，这个比较相似度的算法，有人发过paper。
其他还有大概3-4道更基... 阅读全帖 |
|
b********6
发帖数: 97 | 28 我两周前做过，挺简单的。
第一题： leetcode 原题 single number I
第二题： 找出一个矩阵里“平衡数”的总个数
“平衡数”的定义： 这个数所在row之上所有row的数字之和=所在row之
下所有row的数字之和
这个数所在column左边所有col的数字之和
=所在col右边所有col的数字之和
时间 O（mxn） 空间O（m+n） |
|
d**e
发帖数: 6098 | 29 ☆─────────────────────────────────────☆
cybermilu (欲望乡村) 于 (Fri Jun 14 12:36:00 2013, 美东) 提到:
首先声明，我不是学油工专业的，我是码工，但是由于本人学校比较特殊，我认识的所
有中国同学，里面大概有一般都是geophysics, geology and petro engineering的，
从我来美国，我亲眼见证了他们怎么一个个的去的大石油公司，而且并不怎么费力(至
少提前半年锁定offer，而且phd期间summer intern很容易就搞到，实习工资在texas
6k-9k不等，当然这个和他们phd做的项目都是大石油公司sponsor有关)。
毕业后，他们(PHD)大多从事的职位是geophysical scientist, geologist, petro
engineer, reservoir engineer(这个比较例外是一个本科学petro的朋友在从事)，工
资在不同公司待遇不等，Exxon给的最多(Phd 150k+/year)，其次是Shell,BP(120k+)等
... 阅读全帖 |
|
s*********t
发帖数: 52 | 30 你说的查hashtable的个数，因为非空bucket不是连续排列的，所以这个操作的复杂度
是O（M），M是bucket的个数，这个耗时比O（N）还大，我试了一下你说的方法，没有
查剩余数字的个数差，而是数删掉的数字的数量，可以通过大数据，我这里用的是set
，find的复杂度实际上是O(log_n)，也能通过大数据，如果换成unordered_set，会更
快。
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
set myset;
int ret = -INT_MAX;
for (int i = 0; i < num.size(); i++) {
if (myset.find(num[i]) == myset... 阅读全帖 |
|
|
m**********r
发帖数: 27 | 32 小弟问个关于C++ hash map的问题。
今天做leetcode上面4sum这个题，看到有O^2的做法，是用hash_map
int> >存下两数的和sum还有这两个数a,b,这里sum是key， a和b是value，我比较迷惑
的是如果有另外两个数c,d的和跟a,b的和一样，那第一组的两个数a,b是被覆盖掉了还
是形成一个list，把这两组数都存起来？如果是list，那我如何把这两组数读出来呢？
谢谢 |
|
f********a
发帖数: 165 | 33 server连续的接受到yes和no,当我们查询server的时候，返回以前的某一个小时最多的
yes个数。一个一个小时的time slot从server start算起。貌似要考虑多线程。 我想
法是用一个queue,每当接受到一个yes，检查时间，从queue里面pop出超过一个小时的
yes，然后比较这时queue的size和最大个数,如果大就更新最大个数. 我用c++,
multithreading写起来费力，因为查询的时候貌似要stop server？ 那位大侠说说。 |
|
c********e
发帖数: 186 | 34 你觉得这样行不行：
1）删除： Map记录一个元素在heap有的位置，然后相应删除
2）不删除：假设原数组A
一个min heap，一个max heap，一个数组B，B_i表示A_i放在哪个heap里面，0初始值，
1放min heap， 2放max heap。 另外记录min heap和max heap的size，这个size不是
min heap里面的元素的个数，而是里面有效元素即在window里面元素的个数。然后维持
两个heap里面有效元素个数<=1.当一个元素移出window的时候查看在哪个heap，哪个
heap的size就减一。当然挪动一个元素到另外一个heap要更新B和有效size。当extract
min 或者max，如果已无效，则直接remove， 再取下一个。 |
|
d*k
发帖数: 207 | 35 Add my two cents...
mod的那个不容易想啊。我说个更直观的。
随机在数组中找一个数v。然后做类似快排的调整，使得数组中小于v的值都在左侧连续
放置，大于v的值都在右侧，等于v的都在中间。如果只有一个v，返回v。否则若大于v
的个数和小于v的个数必然有一个是3*m和3*m+1，在个数是3*m+1的部分递归查找。
平均时间复杂度O(n)，最坏n*2。
P.S.
Recruiter上周说我的case会送到HC，这两周出结果，求bless啊！！！！！ |
|
l*n
发帖数: 529 | 36 number of conflicting appointments应该是指的跟其他appointment有冲突的个数，
而不是考虑conflicting pair数。interval排序，merge，标记，统计没被merge的个数
，求补就是conflicting的个数吧。 |
|
k******4
发帖数: 94 | 37 1）随机算法，将k个数排序，平均时间klogk，随机选一个数，binary search排序的数
组，如果在其中，继续，否则返回这个数。平均复杂度(k+n/(n-k))logk.
2)将k个数排序，klogk。然后用reservoir sampling。时间是(n+k)logk。 |
|
l***i
发帖数: 1309 | 38 顶这个，好像stanford有一门课专门讲过这个问题，还有一篇paper说这个问题。
limited memory必须扔掉一些数，但是不管扔那个数，之后都可以继续给适当的数使得
扔掉的那个数是median，但是这个数已经被扔掉了。。。 |
|
w*******s
发帖数: 138 | 39 这道题有两种理解方式。当输入是[1, 1]的时候，有两个sequence满足条件，可是他们
都是[1]，所以根据理解的不同，答案可以是1，或者是2。有一种O(nlogn)的方法，不过
是针对答案是2的情形。
首先得将数组中的元素排序，并按数值大小编号，此时我们将原数组变换为新数组，新
数组中的元素值是原数组中数值大小的编号，新数组中的值是从1到n（n为原数组中不同
数值的个数），长度与原数组相同，对于新数组求解等同与对于原数组求解。
举例，原数组是[9,3,6,3]，变换为新数组为[3,1,2,1]
此变换需要排序，故时间复杂度为O(nlogn)
对于此数组（设为A)，我们可以用等同与求LIS的方法来计算个数(DP)，此方法的复杂度
为O(n^2)，DP的状态是对于每一个数组中的元素，我们记录以其为结尾的不同的subseq
uence的个数，设此数组为D。
在求D中每一个元素D[i]的过程中，我们需要对每一个在此元素之前 j < i，并且A[j]
< A[i]的D[j]求和，此操作可以用树状数组（或类似结构）优化为log n，故总时间复杂
度为O(n log n)，空间复杂度为O(n)... 阅读全帖 |
|
s******e
发帖数: 128 | 40 找出一个矩阵里“平衡数”的总个数.“平衡数”的定义： 这个数所在row之上所有row
的数字之和=所在row之下所有row的数字之和, 这个数所在column左边所有col的数字之
和=所在col右边所有col的数字之和
时间 O（mxn） 空间O（m+n）
请问怎么做？ 有个思路是：用四个数组，两个和row有关，一个存之上的row数字和，
一个存之下的row数字和，另两个和col相关，同理。
看不懂， 谁给解释一下？谢 |
|
w*******s
发帖数: 138 | 41 每次从k中选两个数，枚举+,-,*,/四种操作，这样k个数就变成k-1个数了，递归枚举到
只剩下一个数即为结果。 |
|
x****g
发帖数: 1512 | 42 用bit vector其实意义不大。
把数字序列变成bit vector本身就是o(k 单子平均长度)，
而且因为bit vector长度为所有unique单词个数/8
（这个会随着#sentences个数增长，而不是单词平均长度，所以不好。）
s1编号为1，1000000000
s2变好为2.
做OR运算其实有大量无用功发生。完事了你还得统计bit==1的位数...
在做两两比较o(N^2)的目标前提下，你已经有id sequence.
那么简单了事无非就是计算
#1 => #2...#n
#2 => #3...#n
所以你只要对当前的#i建hashset或者dic都行o(#i)单词个数
对于每一个#i+1....#n,无非就是查表计数。o(#s)
最后为o(N^2*k)其中k为单词平均长度。
sentences |
|
b***e
发帖数: 1419 | 43 来自主题: JobHunting版 - 一道面试题 这个题这样出肯定是要找最少的加法操作数。我认为应该是问这个：
分4个数为一组，a, b, c, d。先算b+c，再算a+b+c，再算b+c+d，然后比较两个值。这
样3个加法解决了四个数，解决n个数要3/4*n个加法。但是这只解决了一半的问题：从a
和b开始的解决了，从c和d开始的三连数还没照顾到。那就再做一遍，这次从c开始。两
遍加起来一共是3/2*n个加法。比直观的2*n个加法好。 |
|
s********o
发帖数: 3783 | 44 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数。其实就几行代码，辗转相... 阅读全帖 |
|
s********o
发帖数: 3783 | 45 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样，一模一样的我就不说了。
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数... 阅读全帖 |
|
r*******2
发帖数: 104 | 46 一周之内面了微软两个组，刚刚收到结果双双悲剧，一个组的HR说It's a tough call
，另一个组的HR说very close，不知道是不是套话，总之很沮丧……来版上求问一下大
家问题可能出在哪，并且附上大概的面试过程和coding题目。
第一组：
第1轮：是一个SDE II，看名字像是中东人。coding题目是给定2棵树，判定是否其中一
棵是另一棵的subtree，同时用了DFS和BFS，写完code讨论了几个testcases和复杂度就
结束了。
第2轮：一个白哥Senior Lead，问的题目是一个maze（用2D matrix表示，有的坐标上
有障碍），给定起点和终点，找出从起点到终点的path，还是用的常规的DFS解法，搜
索过程排除有障碍的和访问过的坐标。
第3轮：一个小黑Lead II带去一起lunch，午饭之后问了大概半小时设计题，设计当软
件窗口（比如Word窗口）大小变化的时候每个子图标栏的大小如何变化，大概定义了一
下各个class，挑了其中一个function写了code。
第4轮：一个三哥Principle Lead，先问了一个ASCII和Kanji字... 阅读全帖 |
|
k*******a
发帖数: 772 | 47 因为半颗的个数/2 加上 整颗的个数 = 100 - n/2
所以可以知道整科颗的个数
所以取到整科的概率为 f(n, k) = (100-n/2-k/2)/(100-n/2+k/2)
half |
|
s********0
发帖数: 34 | 48 不好意思 可能没描述清楚
[0,1,0] 有1个‘1’， 2个‘0’， 所以1的个数小于0的个数 不成立
所以题目通俗点讲 就是
如果是1， -1 (0替换成-1）组成的数组的话，就是找出所有子数组的个数，要求子数
组和>= 0 |
|
o***g
发帖数: 2784 | 49 n=4
数组里应该是1-3
1-2一组 3一组，或者1 一组 2-3一组都行
比如选前面这个 1-2应该是2个数，结果是4个，3这个组里是0个数，就将3这组舍弃
1-2这组再分成1一组 2一组
然后，1这组有俩，2这组有俩，先看1这组的话，本来应该是1个数，现在有俩就是1了 |
|
o***g
发帖数: 2784 | 50 这个数组按照题目是一共7个数，我们就知道这里包含的整数是1到6这个区间内的整数
将1到6这个区间分成1到3和4到6两个区间去统计各有多少个数，必然会有一个区间的数
的个数是超过3个的 |
|
