M******e
发帖数: 103 | 1 网投。2轮电面. on-site后两天收到电话被拒
第1轮电面 白男
问了排序算法的复杂度和如何根据数据特点设计排序
编程题是那个ransom text. 就是从magazine找组成ransom的字母。Hash table完成
第2轮电面 白男
出了三道编程题
1）shuffling
2) least common ancestor of binary tree
3) 一道判断整数能否被3， 5， 15整除的题，具体什么 忘了
On-site
第1轮 三哥
先问了c++多态性基本问题。
编程题1是检查binary tree是否mirror
编程题2 是输出一个集合的subset (CC150上的题)
编程题3 是LRU (没写code, 只说设计，没时间了)
第2轮 白男manager
先问了20分钟的behavior问题
编程题1是数组中连续数字的最大和(CC150上的题)
编程题2是binary tree的serialize and deserialize
第3轮 白男manager
先问了10分钟的behavior问题
问了一个设计题，关于如何查找一个用户在过去10秒钟内访问网... 阅读全帖 |
|
t****t
发帖数: 6806 | 2 从1,2,3,4,5的均匀随机数发生器里产生的等概率状态数是5^N种. 要生成一个1,2,3,..
.7的均匀随机数发生器, 你需要的状态数一定是7的倍数.
但是对于任何有限的N, 5^N永远不可能被7整除, 所以任何"固定次数"的解必定是错的. |
|
s*******r
发帖数: 2697 | 3 思路是对的，最后一步判断错了
这个题就是在找 10^n-2被19整除的解 解出来是5263157894736842 |
|
S*********g
发帖数: 5298 | 4 10^n -2 可以被19整除,只要n>=17即可 |
|
l*******b
发帖数: 2586 | 5 mxn的格子,共有mn个方格,每个俄罗斯方块都是4个格子,所以? 4 必须整除mn
如果4|m 或者 4|n全部拿1x4的长条填充就好了,
如果2|m && 2|n全部拿2x2的方块填充就好了.
是要求全部的分割方式,还是找到一种就可以? 还是怎样啊? |
|
t****t
发帖数: 6806 | 6 这是个老题我再说一遍:
N次调用rand5()产生的等概率状态数是5^N. 正确产生rand7()需要的等概率状态数必须
是7的倍数. 5^N永远不能被7整除. 所以任何试图用有限次调用rand5()来产生有限个
rand7()的算法, 从数学上都必定是错误的. 正确的算法必定有一个无限循环调用rand5
().
这就好比用5进制写1/7. 如果有人说他有一个写法能用有限位5进制数写出1/7, 你不用
看他的结果就知道他是错的. |
|
L********e
发帖数: 159 | 7 这个不保证有限次实验内实现。rand5在有限次实验中只能产生5的幂种状态，不可能被
7整除从而实习均匀的rand7。最直观有效的方法就是rejec sampling吧。 |
|
j*****y
发帖数: 1071 | 8 确实用 kmp简单，和那个 storm8 的题目一样
pattern = S
source = S + S
找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
return
true, 否则 return false |
|
j*****y
发帖数: 1071 | 9 哈哈，我以为只要 被 4整除就是了，
leap year算错了吧
from wikipedia
if year is divisible by 400 then
is_leap_year
else if year is divisible by 100 then
not_leap_year
else if year is divisible by 4 then
is_leap_year
else
not_leap_year |
|
e******i
发帖数: 106 | 10 是最新的一道题，我题目都没有看懂 >_<|||
题目有点长，有耐心的同学就慢慢看,我有问题的地方我用《 》quote
“Juggle Fest
Description:
Many developers here at Yodle are avid jugglers. To celebrate their prowess
we are organizing a Yodle Open JuggleFest, but we need your help planning it
. There will be thousands of participants split into teams. Each team will
attempt to complete a juggling circuit consisting of several tricks. Each
circuit emphasizes different aspects of juggling, requiring hand to eye
coordination (H), endurance (E) and pizza... 阅读全帖 |
|
r**h
发帖数: 1288 | 11 不知道我有没有理解错了。。是单纯的分解质因数，还是要把一个数表示成两个质数的
乘积？
如果是后者的话我觉得是先用筛法求出从2到N/2中的所有质数，然后对于每个质数判断
N/m是否整除。如果是的话再判断N/m是否是质数
如果是前者我觉得做法也比较类似。从小的质数开始逐个做除法，直到变成1为止 |
|
f*****w
发帖数: 52 | 12 是单纯的分解质因数，我面试的时候还写了判断是否是质数的辅助函数，后来面试完了
才发现不用，就是从2开始看能不能整除，不能了在换下一个数。最后加入到结果的是
肯定都是质数 |
|
d*******3
发帖数: 58 | 13 总共有n!种排列，第二种算法产生的排列数是n^n的，必然有重复，要保证等概率的至
少要有保证n^n 能整除 n!,但这个反例就很多了。。。 |
|
l****i
发帖数: 2772 | 14 报一个迟到的面经，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道更基... 阅读全帖 |
|
s**********r
发帖数: 8153 | 15 这里边 b 不能是int了吧？b是double? float?
b不能被2整除咋整。 |
|
l*****s
发帖数: 774 | 16 第二种方法的话是不是 对于一个数 k，验证它是不是prime number，从 sqrt(k) 往小
的方向循环，一直循环到2，如果中间有可以整除的数字，立即break，这样的复杂度很
大吧。谢谢
不知道二爷是否可以贴个code来看看 |
|
g****o
发帖数: 547 | 17 可以有prime factors大于sqrt(n)，但最多只有一个。
试过所有小于等于sqrt(n)的质数，如果n还没被除为1，说明肯定有一个大于sqrt(n）
的质因子
可以看我上面的代码来理解
你以前没接触过数论的话，这里要用到的知识就是；
如果任何一个小于等于sqrt(n)的质数都不能整除n,那么n是个质数 |
|
k*******t
发帖数: 144 | 18 来自主题: JobHunting版 - 请教一道题 如果input是28, 长除法的余数是[1, 2], 此高位不是被整除，所以直接用[1, 2]map到
"BC". In this case, the result should be "AC". 这个题目的tricky的地方就是最
高位有时要减1,有时不要。问题就是什么情况下要减1,什么情况下不要。继续求解啊。 |
|
s****u
发帖数: 1433 | 19 原因是2x5=10。
所以，只要用10，100，1000，。。。去除这个数，
最后找到余数为1的那个就解决了啦。
----
再一想，只要用(10-a)，(100-a)，。。。去除b最后整除的那个就OK啦 |
|
X******2
发帖数: 5859 | 20 取自若干个公司，名字就不说了，不少题是陈题。
1）用biased coin实现uniform sampling，如何有效实现？
2）一个超大的TABLE（大小在BILLION级别），不知大小内存也放不下，
如何从中随机抽样出百万条记录？
3）有一个数组其中存放整数，有正有负，找出其中连续的和为0的数字。
要求线形算法。
4）2-SUM （数组已经排好序）
5）一个数组，找出最大连续和
6）两维数组（行列均已排序）查找
7）给出一个单词之间未加空格的句子，加空格
8）有很多点，找出离原点最近的K个
9）说明对于任何大于2的素数，P*P-1可以被24整除
10）对LOGISTIC REGRESSION（变量很多）编程求解 |
|
g****o
发帖数: 547 | 21 9）说明对于任何大于2的素数，P*P-1可以被24整除
这个应该是大于3吧 |
|
a******e
发帖数: 710 | 22 那这道题的答案是不是
如果被3整除，都拆成3
如果被3除余1， 拆出来一个4
如果被3除余2， 拆出来一个2？ |
|
n****e
发帖数: 678 | 23 想通了，
5 * (rand5() - 1) + (rand5() - 1);
前面这个系数5是不能随便改的，因为是rand5，所以只有系数为5的时候所生成的书才
是随机的。
这种情况下21是最大的被7整除的数，所以解答是这么给的。
多谢指教！ |
|
s*****r
发帖数: 43070 | 24 感觉不够优化，应该有快速前进地步子。
质数不能被小于平方根的质数整除，1除外。
烙印估计想要个优化的解法。 |
|
w*******e
发帖数: 285 | 25 从1到sqrt(n)扫描，能整除i就输出i和n/i？ |
|
l*****r
发帖数: 2122 | 26 反过来想，原string长度依次除以质数，从小到大。(2，3，5，7，11。。)
能整除的话，接着看是否匹配，不能的话看下一个稍大的质数。直到质数＞n/2。 |
|
x****g
发帖数: 1512 | 27 假设s=S0...Sn-1
我觉得我会选择判定SkSk+1=[Sn-1][S0]位置出的k,
如果k+1能整除整体长度，那么S0...Sk就是当前的pattern,
比较成功的话就一直向前，
如果失败在某一处的话，那么pattern更新为到失败处之后的那个满足条件的k'.
需要思考细节，呵呵。 |
|
l*****r
发帖数: 2122 | 28 反过来想，原string长度依次除以质数，从小到大。(2，3，5，7，11。。)
能整除的话，接着看是否匹配，不能的话看下一个稍大的质数。直到质数＞n/2。 |
|
x****g
发帖数: 1512 | 29 假设s=S0...Sn-1
我觉得我会选择判定SkSk+1=[Sn-1][S0]位置出的k,
如果k+1能整除整体长度，那么S0...Sk就是当前的pattern,
比较成功的话就一直向前，
如果失败在某一处的话，那么pattern更新为到失败处之后的那个满足条件的k'.
需要思考细节，呵呵。 |
|
d********y
发帖数: 2114 | 30 用KMP的next table
1.计算KMP的next table。这个是O(n)
2.如果有重复字符串组成，用输入字符串长度减去next table的最后一个值再减1，得
到重复字串的长度。
3.验证此子串长度大于1，子串最后一个字符和输入字符串最后一个字符相等，字符串
长度可以整除字串长度。
假设计算出的子串长度为p。根据next table的定义，对于0 <= i < i+p <= s.Length
- 1, s[i] = s[i + p]。这就是一个周期函数的表达式。 |
|
w****r
发帖数: 69 | 31 - IMO.IM
P1 Given a matrix of size M*N, containing numbers from 1 ~ M*N. No
duplicates. Find a path from upper left to lower right, such that the
numbers on the path are lexicographically the smallest after being sorted.
P2 Subsequences See http://www.mitbbs.com/article_t/JobHunting/32528491.html
两面答得都还好，第二面写了个变种的binary search，错了一个边界，然后很快就改
过来了。而且自己想到了最优解。不知道为啥挂掉了。
- Palantir
P1 Q1 implement quick sort 秒之
Q2 given N, find the sum of numbers, between 1-n, that are divisible by 3
and 7. Do it i... 阅读全帖 |
|
s******i
发帖数: 236 | 32 https://www.hackerrank.com/challenges/unfriendly-numbers
There is one friendly number and N unfriendly numbers. We want to find how
many numbers are there which exactly divide the friendly number, but does
not divide any of the unfriendly numbers.
Input Format:
The first line of input contains two numbers N and K seperated by spaces. N
is the number of unfriendly numbers, K is the friendly number.
The second line of input contains N space separated unfriendly numbers.
Output Format:
Output the a... 阅读全帖 |
|
M*******a
发帖数: 1633 | 33 就是给个数组A都是正整数，然后一个范围[1,N]，返回[1，N]当中不能被任何A的元素
整除的数字的个数。
就这么简单，怎么做。
什么一个一个除着看的做法就不用说了。 |
|
|
M*******a
发帖数: 1633 | 35 不能被任何A的元素整除
还要公式。。。估计就不是这么做了。 |
|
z******t
发帖数: 59 | 36 的第75道例题。
只能被2, 3, 5整除的数字被称之为丑数Ugly Number。下面的代码是求出按大小顺序第
index个丑数。稍作改动就能打印出前n个丑数，因为之前的丑数都存在数组uglyNums里。
下面是参考代码：
int GetUglyNumber_Solution2(int index) {
if (index <= 0)
return 0;
int[] uglyNums = new int[index];
uglyNums[0] = 1;
int nextUglyIndex = 1;
int index2 = 0;
int index3 = 0;
int index5 = 0;
while (nextUglyIndex < index) {
int min = Math.Min(uglyNums[index2] * 2, uglyNums[index3] * 3);... 阅读全帖 |
|
C********e
发帖数: 492 | 37 现在有一个数N，（0 < N < 10,000)，找到一个最小的正整数S：
满足
1）S的所有数字只有0或者1。
2）S能被N整除。
比如：
输入 25， 输出 100
输入 30， 输出 1110
输入 99， 输出 111111111111111111 |
|
l*****a
发帖数: 14598 | 38 只能先构造可能出现的1/0组合数，然后判断适否可以整除吧
0/1组合数长度从N长度开始，如果没有合适的再加一
每次生成的0/1组合数（基于长度）可以利用前次的结果
还有什么更好的办法吗？ |
|
r*****t
发帖数: 2051 | 39 N是一个很大的正整数——可能到10^15次方，
简单起见，不考虑溢出，或者假设用python
A 是一个array，里面存着一些正整数，up to 1000个
从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？
举个例子：
N = 10
A = [2,4,5]
那么返回4 (1,3,7,9满足条件)
我写的如下，但是面试官不满意，因为N很大的时候内存会溢出
def left(N = 10, A = [2,4,5]):
ones = [1 for i in xrange(N+1)]
ones[0] = 0
for inte in A:
if inte == 1:
return 0
for i in xrange(1,N/inte+1):
ones[i*inte] = 0
return sum(ones) |
|
h****t
发帖数: 69 | 40 如果N很大的话你可以先找1-10000有多少数不能被A中的任何一个数整除的，接着找
10001-20000。。。。 |
|
m**********e
发帖数: 52 | 41 来自主题: JobHunting版 - 一道电面题 求1,000,000内不能被array中的任意数整除的数总共有多少个，比如array = [2,4,9,
10]， 肯定不能用暴力，应该是减减加加 |
|
|
|
l*******i
发帖数: 7 | 44 买买提上好心人推荐的，onsite已挂，发个面经
OA Test2
1.flip 0 or 1
有一串0,1的数组，然后可以取中间任意一段，把0置换为1,1置换为0. 问这样一次置换
之后，这组数组最多还有多少个1.
2. uneaten leaves
给你一个数N,以及一个数组，让你统计在1到N之间，不能被这个数组里的数 整除的数
的个数。
具体内容考古
http://www.1point3acres.com/bbs/thread-136079-1-1.html
第二个问题，我有两个case时间超时没过，也给了电面
skype
Remove nth Node from the end of Node
Find element in rotate array
design a online application for bank account
onsite
round 1. Trapping rain water
写了时间空间O（N），后来要求空间O(1),最后没写完整。面试在一个四周都是墙的小
屋里，一开始就感觉比较压抑。面试官不说话一直玩手机，最后拍走了。
round 2. T... 阅读全帖 |
|
f*******r
发帖数: 976 | 45 Move on吧，希望LZ拿大offer
买买提上好心人推荐的，onsite已挂，发个面经
OA Test2
1.flip 0 or 1
有一串0,1的数组，然后可以取中间任意一段，把0置换为1,1置换为0. 问这样一次置换
之后，这组数组最多还有多少个1.
2. uneaten leaves
给你一个数N,以及一个数组，让你统计在1到N之间，不能被这个数组里的数 整除的数
的个数。
具体内容考古
http://www.1point3acres.com/bbs/thread-136079-1-1.html
第二个问题，我有两个case时间超时没过，也给了电面
skype
Remove nth Node from the end of Node
Find element in rotate array
design a online application for bank account
onsite
round 1. Trapping rain water
写了时间空间O（N），后来要求空间O(1),最后没写完整。面试在一个四周都是墙的小
屋里，一开始就感觉比较压抑。面试官不说话一... 阅读全帖 |
|
r*****s
发帖数: 1815 | 46 我觉得这题，挺简单的。
你说难，只要多想一步，就简单了。说白了不过是说，a，b可以分别写成x^3m和y^3n的
形式，其中m，n不能继续分解成如上形式或为1。
而经过简单替换，(m^2n)和(n^2m)都是整数的三次方，假设将m质因数分解，是q1q2q3.
..qc,n是p1p2p3...pd,则我们知道：m和n的分解中unique质因数一一对应，而且m和n的
分解中每种质因数的出现次数不是1就是2(否则和预处理步骤相悖)
具体考察一个质因数r，它在m里出现t次，在n里出现u次，我们要保证t*2+u和u*2+t都
可以被n整除，且t和u的值域都是1,2
否则就是两个cubic roots无理数相加是不是可能是有理数的问题，我手机实在不能打
了，这里有个链接：http://math.stackexchange.com/questions/437710/cube-roots-dont-sum-up-to-integer
由此可知，对于每一个质因数，要么同时t u都是1，要么同时都是2。
于是可知直觉正确，m和n相等。
于是可知，这两个数有x^3n和y^3n的形式
于是仍然是一道非常简单的题... 阅读全帖 |
|
发帖数: 1 | 47 leetcode 397 原题
除了3以外碰到odd number如果+1能被4整除就+1，不然就-1
或者用recursive夜行
easy级别，电话面试吗？
good luck
safety
string |
|
p**********e
发帖数: 151 | 48 但是这题输入是string，而且最大309位，怎么计算能否被4整除？
递归的话感觉可能会栈溢出，mantain一个stakc或者queue做迭代吗？ |
|
h******k
发帖数: 810 | 49 另外，存二进制，奇偶/加减一/除二/整除四的运算都很简单。 |
|
发帖数: 1 | 50 leetcode 397 原题
除了3以外碰到odd number如果+1能被4整除就+1，不然就-1
或者用recursive夜行
easy级别，电话面试吗？
good luck
safety
string |
|
