d*****c
发帖数: 605 | 1 最后的onsite一家小公司。。。等回来散尽家财发包子上面经。
update：
14包子已发，没发到的不好意思啦，谢谢你们bless。。。。在等结果。因为签了nda所
以我就报个别家面经吧。
1. strstr，一个string很长，一个很短。
2. 继续第一题，除去所有短string之后组成的string的anagram
3.radix sort
再次感谢大家bless。 |
|
s********u
发帖数: 1109 | 2 http://www.careercup.com/question?id=5673258271637504
Find the latest version of released software. For e.g1. 2 and 2.2.. latest
is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
as string in above format.
一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
int/double/
下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
每一位都要做一次快排，也就是O(knlogn)
另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一
位只要O(n)，总共O(kn)。但坏处是，比如其中一位是很大的数，那么开的空间就要很
大，其实t... 阅读全帖 |
|
p*****2
发帖数: 21240 | 3 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 4 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
a********9
发帖数: 129 | 5 之前稍微收集了一下
glassdoor
===================
edit distance
level traverse tree(高频）
1) Calculate the square root of a double（高频）
2) Given n intervals [si, fi], find the maximum number of overlapping
intervals.
3) Print all the paths from root to every leaf in a binary tree.
4) Print the sum of all the numbers at every vertical level in a binary tree
5) Given a set of n jobs with [start time, end time, cost] find a subset so
that no 2 jobs overlap and the cost is maximum ?
6) Given 1 trillion messages ... 阅读全帖 |
|
m*********1
发帖数: 204 | 6 我前面发过一道题了，就是String 找repeat特征那道，要求算法复杂度为O(n)，第二
题也是超级难。我都放上来。注意我的面试是SDE intern职位
第一题是一个口音极其重的烙印，几乎听不懂，还好是算法考试，要是纯聊天更完蛋。
题目如下：
1.有一种String,是把一个更短的String重复n次而构成的，那个更短的String长度至少为
2，输入一个String写代码返回T或者F
例子：
"abcabcabc" Ture 因为它把abc重复3次构成
"bcdbcdbcde" False 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" False 因为它不是某一个String重复
"aaaaaaaaaa" False 重复的短String长度应至少为2（这里不能看做aa重复5次)
要求算法复杂度为O(n)
public boolean isMultiple(String s){
}
这道题因为我开了一个单独贴了，就不在这里讨论了
第二个45分钟面试，是另外一个烙印，这个烙印的口音更重，更听不懂，但... 阅读全帖 |
|
j*d
发帖数: 96 | 7 第二题 用radix sort为什么不行， 是因为空间开销太大吗？ |
|
l****r
发帖数: 118 | 8 准备FLG面试的话下面有哪些章节需要看吗？
shortest paths
maximum flow
radix sorts
tries
substring search
regular expressions
data compression
reductions
linear programming
intractability
谢指点。 |
|
S***A
发帖数: 133 | 9 我觉得counting sort也可以啊，要是数很多的话用radix sort也行啊。
：这个题我做了，我开始也说的是heap，然后要求提高，你应该问他similarity如何定
义，他会告诉你是(1-100)，然后他期待的其实是类似桶排序的。
…… |
|
l********1
发帖数: 24 | 10 恩 我就是提到 bucket sort和radix sort后，面试官好像觉得还不错，我就继续说了。 |
|
d****n
发帖数: 397 | 11 leetcode， maximum gap problem。
看了鸽笼原理的解法，真是叹服。
不过仔细想想，还是有点radix sort，bucket sort的影子。 |
|
P*******L
发帖数: 2637 | 12 这题无非就是先用一个 O(n) time 的排序算法，然后找最大的 gap。
排序算法可以用 bucket sort/radix sort/spaghetti sort。
鸽笼原理没有在这里用到。 |
|
d****n
发帖数: 397 | 13 ….那我把每个数转化为二进制，然后用32Xn 的radix sort为什么过不了oj，理论上也
是O（n）time，O（n）space。
也不是bucket sort就一定行。对bucket size也有要求。
我也不是想不到bucket sort。 |
|
d****n
发帖数: 397 | 14 一开始试过radix sort，过不了oj。然后想了很长时间，google了下，看到鸽笼原理的
解法。
就是感叹下思想巧妙。学CS的人牛逼，不知道为什么反响会这么大，有些人回复也没有
什么
好语气。
不用鸽笼原理，有其他巧妙解法说出来就是，不想说去投conference也行，没有必要感
觉别人都是
傻逼。
不过我也是少见多怪了。我专业不是CS，数学物理里面的技巧见多了也就不觉得感叹了，
看到这个觉得新鲜感叹了一下。可能CS科班出身的不觉得有什么。都习以为常了。 |
|
t*****a
发帖数: 106 | 15 radix sorting 就可以了。2^32也就是10位数，worst case 10n也是线性时间吧 |
|
S*******C
发帖数: 822 | 16 好方法，DNA序列本质是四进制数字，用radix为4的BigInteger作为key也可以啊 |
|
m*****n
发帖数: 2152 | 17 hash + radix。
烙印太tm的黑了。 |
|
y*****e
发帖数: 712 | 18 这题没见过的话很难30分钟做出来吧。就是做过leetcode那题，还得再写一个radix
sort!!! |
|
y*****e
发帖数: 712 | 19 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。 |
|
|
m*****n
发帖数: 2152 | 21 hash + radix。
烙印太tm的黑了。 |
|
y*****e
发帖数: 712 | 22 这题没见过的话很难30分钟做出来吧。就是做过leetcode那题，还得再写一个radix
sort!!! |
|
y*****e
发帖数: 712 | 23 天这个花的内存太大了吧。。。为啥不能用radix sort？也是扫一遍出结果。。。 |
|
|
c******n
发帖数: 4965 | 25 不对啊，我再想了下， “流”（stream) 根本就没有size /length 的概念， 是
infinite 的， 还扯什么O(N). 如果有截止， 那你用radix 本身的4^10 的size 都要
遍历， 如果input size 比4^10 小很多，那还叫什么O(N)
anyway, 作为一个讨论倒是出了很多可以学习的地方， 纠结题本身已经没有什么意义
了， 尤其是这样一个烙印聚居的地方 |
|
r********3
发帖数: 24 | 26 这个是先给定两个string a1, string a2,先判断是否长度相等，如果相等用radix
sort, time 复杂度 O(n*k),
n 是a1 长度，k=26，假设只有26个小写字母得话。
然后以排好序的作为一个key，放到hashtable里， 这样应该是O（n） |
|
r******d
发帖数: 308 | 27 好像可以不用string长度
思路
Step1 把每个string用radix 的思路转换一下。 例如babab可以转换成a2b3(a出现2次b
出现3次)
Step2 将所有string放到一个hush table里。key 是上步转换后的string.value是list
。如果有conflict 就插入list尾端
Step3 遍历一遍所有string 打印结果 |
|
|
b********6
发帖数: 35437 | 29 用radix sort怎么样O(n)，读出来O(n), 排序O(n)，写回去O(n)
其实n log n已经够了吧，如果这个矩阵只有一行，就是数组排序，n log n就不错了。 |
|
|
s**********g
发帖数: 14942 | 31 你这个完全得看application啊
time vs space tradeoff
search一般来说当然binary search是不错的
但hashset能搞出O(1)来，如果hash function很好的话
sort也要看要求啊
哪怕是algorithm，一般NlogN，但是mergesort和quicksort都有不同的应用
整数的话，甚至可以radix sort搞出O(N)
扯上结构的话，linkedlist就经常不是很好用，因为没有O(1) random access
那arraylist也许会比较方便
或者直接上heap
我觉得这种问题就是看你的理解深度，我不认为能简单一个回答解决，而应该看实际的
tradeoff |
|
c****n
发帖数: 21367 | 32 how about immunization shots and pray for anti-body comes before
virus outbreak? would it make things worse? :)
i did wash hands, and surprisingly, the patient have no other
symptons other than rashes. fever only for about 6 hours.
acyclovir is the main medicine for the patient right now. i am
thinking about use reduced dose as preventitive method
or i just stick with Radix Isatidis... this is the only thing
with me so far... :(
it is so desperate, need to go to see the patient tomorrow...
vala |
|
t*******r
发帖数: 22634 | 33 man。。。小学数学里的 positional notation system 当然需要
默认的 radix，OK? place value。。。最最基本的问题是：what is
the value for this place？ |
|
t*******r
发帖数: 22634 | 34 我觉得这么说，”交换律的应用“是建立在对“手算四则运算”的熟练之上。
但对“交换律的理解”，则是建立在娃版集合论上的吧。
因为“手算四则运算”虽然看起来是对“数”的操作。但是从严格数学的角度，
手算四则运算，直接地是对“数的notation”的操作（具体而言，radix
10 的 positional notation -- 阿拉伯数字）。其正确性是
建立 “数的 notation” 与 “数” 一一对应的基础上的。
但交换律就其本身而言，是对 “数” 而言。并不局限于某一种特定的
“数的 notation”。 |
|
t*******r
发帖数: 22634 | 35 因为（1）这个基于 radix 10 的 place value，（2）搞不出被 N 整除的通解。 |
|
t*******r
发帖数: 22634 | 36 俺刚才要去接娃。。。或者这么说，被 3 整除的概念基础（如果俺没看错的话），就
是:
10 - 3*3 = 1
=> radix 10 的 place value 搞瓢虫式 right shift
但吃饱了撑的搞这个以前，先把基本的，分数换无限循环小数搞清楚再说，虽然那玩意
儿也不是太基本的东东。。。 |
|
t*******r
发帖数: 22634 | 37 分配率对无穷和适用，是公理吧。
不过收敛性的主要不是这个，而是竖式除法你没完全算完的时候，你得到的其实是一个
区间，而不是一个数，而对于这个问题，这个区间的 upper bound 和 lower bound 以
指数的速度互相逼近，所以是指数收敛。radix is 10. |
|
t*******r
发帖数: 22634 | 38 昨晚领导上网搞了张考卷试了一下，俺看了看娃的草稿以及问了问。。。
娃的确不行，所有计算基本都是在按照顺序算。。。而俺在娃面前算给她
看的，大部分题的计算都出现不少随机应变的非顺序计算/重新分解合成。
我观察下来，归根到底还是娃无法在实战中深入理解和灵活应用以下这些
基本概念："order-of-operation" / "set theory" / "(dot) array" /
"modular theory" (go to "next" ring, then change to "opposite"
operation) / "symbol" perception (e.g. negative as "hole")
/ "place value" / "variation" of place value (e.g. hr/min treat
as place value of radix 60) 。。。说白了是数学基础和数学概念差距
还很大。。。
实际的说，俺娃还是以接地气的方式多扑腾扑腾吧。。。不纠结了。。。 |
|
J***A
发帖数: 1511 | 39 OK 明白为何冒似可以直接乘了！
另一种方法，把小九九直接改了， 如7*7=61， 也可以直接算八进制乘法了， 算法和
进位和十进制一样，只是大家都十进制算习惯了。
不过还是觉得推这个对数学没什么帮助......
proof：“in radix 8 place value, 77*100 = 7700”proof by expand place-value
to algebraic ex........ |
|
J***A
发帖数: 1511 | 40 按你这个算法
77*110= 7700 his 770
后两位是70
前三位=77 加7=106…
…7 加7-8=6 进1 ，
7加 1=0 进1，
所以77*110=10670......
幼儿园不用重读了吧：）
谁能教我怎么在这显示加号
proof：“in radix 8 place value, 77*100 = 7700”proof by expand place-value
to algebraic ex........ |
|
t*********1
发帖数: 2852 | 41 请大家帮忙查一篇paper,多谢多谢！
Rapid Fingerprint Analysis of Radix Scutellariae by UFLC–DAD
Journal of Chromatographic Science
如果找到，请帮忙发到g*******[email protected]
多谢！ |
|
r****1
发帖数: 4301 | 42 占星警句（Choice Aphorisms）原文摘选自卡丹(Jerome Cardan 1501—1576)的着作《
Seven segments of Cardan》。卡丹被誉为16世纪的博学者，拥有数学家、物理学家、
医药学家、天文学家、及术士等多个头衔。在他的有生之年，他出版了多达54本着作和
44件手稿，内容涉及了他研究的各个领域。占星警句讲的是星盘分析的一些规则和条文
，按条目的方式列出，分为总论篇、命盘篇、推运篇、医疗篇、择时篇、蚀彗篇、气候
篇、农作篇、实事篇等9部分，论及范围着实广泛。不过，如果以条文的数目来看，命
盘篇是核心部分，共计100条，其它篇的内容相对少很多，可能是与删节有关。
在历史上的顶级占星名家中，还没有Cardan的位置，不知是不是他学识太杂的原因，
很多谈及他的资料均是与数学、人文科学或玄学相关，占星作为玄学，只是他学识中的
一小部分。根据有关资料的判断，占星警句很可能是他汇编成文的，其中有不少条文内
容是值得我们深入思考和借鉴的。
1、A Child is then said to be born when first it breathes in... 阅读全帖 |
|
G*******s
发帖数: 4956 | 43 第六章 论人的堕落、罪恶和刑罚
一．关于堕落
6.1 我们的始祖被撒但的诡计和试探诱惑，吃禁果而犯罪（创3:12；林后11:3）。上
帝既特意要使祂自己得荣耀，就按自己所喜悦的，照祂智慧和圣洁的计划，准许这罪的
发生（罗11:32）。
l 这部分介绍了关于亚当与夏娃堕落的事实。他们是因着上帝至高主权的准许
之下，因撒旦的诱惑而堕落的。有好几项问题尚未回答，也不是我们有限的智力所能回
答的，因此威斯敏斯德的神学家也并没有尝试回答这些问题。这些问题就是：（1）撒
旦（与他的一伙）原来是被造为圣洁与良善的，他们是怎么堕落的？（2）既然人的意
志始终是在占主导地位的倾向与欲望的约束之下（比较 太12:33,35），那么，当时亚
当（亚当的意志一定是正直与圣洁的）与夏娃都有完全公义的性情，他们如何在撒旦的
诱惑下堕落呢？（3）上帝为什么允许撒旦、亚当和夏娃堕落在罪中呢？
l 对于这些时常被问及的问题，我们应该克制，不要勉强回答。一些伟大的神
学家也尝试过解答，却毫无进展。就好比一匹壮马尝试将一辆困在烂泥里的大车拖出来
一样，越是努力，车子却越陷越深。
l ... 阅读全帖 |
|
G*******s
发帖数: 4956 | 44 “威斯敏斯德信条”简释
作者：林集章牧师
翻译：张敏颖
编校：王志勇牧师
注：本书“威斯敏斯德信条”中文译本采用王志勇牧师译文
目录
第一章 论圣经
一．特殊启示的意义和途径
二．圣经的写作与用途
三．确定圣经是上帝之圣言的根据
四．圣经的充分性
五．圣经的明了性
六．圣经的默示性
七．解释圣经的无谬规则
第二章 论上帝和三位一体
一．上帝的属性
二．上帝的位格
第三章 论上帝永远的旨意
一．上帝一般的旨意
二．上帝的预旨与具有理性的受造物的永远命运的关系
三．上帝关于选民的预旨
四．上帝关于被遗弃者的预旨
五．关于预定论教义的讨论与告诫
第四章 论上帝创造之工
一．创造世界之工
二．人的受造
第五章 论上帝护理之工
一．上帝对世界的护理之工
二．护理的次因
三．论上帝的护理与罪恶行为的关系
四．普通与特别护理
第六章 论人的堕落、罪恶和刑罚
一．关于堕落
二．关于重生的结果
三．关于罪的工价
第七章 论上帝与人所立的圣约
一．圣约的必要性
二．行为之约
三．恩典之约
四．圣约与遗命
五．恩典之约在新约与旧约中
第八章 论中保基督
一．基督中保的职分
二．主耶稣基督的位格
三．基... 阅读全帖 |
|
l******t
发帖数: 108 | 45 这个复杂度分析是基于random-access machine (RAM) model的,
可以有无限个随机存储单元, 每个单元可以存放无限大的值 |
|
w****c
发帖数: 2667 | 46 【 以下文字转载自 JobHunting 讨论区 】
发信人: wormcc (虫虫), 信区: JobHunting
标 题: 一道算法题
发信站: BBS 未名空间站 (Sun Feb 17 20:24:30 2013, 美东)
有没有哪位大牛给点思路？Radix tree? Prefix tree?
现有三到五百万的英文词组字典（phrases）。
系统中有大量的用户会输入查询字串，每个查询字串中可能含有零个或多个词组， 现
在，需要实时地匹配查询字串中的所有词组。 |
|
p**i
发帖数: 688 | 47 ☆─────────────────────────────────────☆
jxmg (剑行美国) 于 (Mon Aug 27 20:03:54 2007) 提到:
http://www.apfloat.org/apfloat_java/applet/pi.html
都用100万位，Radix 10，选Chudnovsky，报个数啊。
奇怪，我的电脑算的时候CPU的Load不到75%。为什么不100%呐？
☆─────────────────────────────────────☆
lamborghini (烧玉米杆的Murcielago) 于 (Mon Aug 27 20:11:37 2007) 提到:
C2D T7400:
elapsed time 23.465 sec
final value took 2.965 sec
Total elapsed time 26.432 sec
☆─────────────────────────────────────☆
ZeeGee (猪猪) 于 (Mon Aug 27 20:17:30 2007) 提到 |
|
b******t
发帖数: 965 | 48 http://news.mydrivers.com/1/94/94583.htm
Intel正式发布16款45nm处理器
驱动之家[原创] 作者：上方文Q 编辑：上方文Q 2007-11-12 09:58:21 2279 人阅读
[投递]
就当我们还沉浸在周末的快乐中时，Intel已经正式发布了其首批45nm工艺Penryn核心
处理器，包括一款发烧级桌面型号和15款服务器型号，主流著名型号和笔记本型号则将
在明年一季度推出。
Intel联合创始人之一Gordon Moore称这是近40年来晶体管技术最大的一次进步。新处
理器首次应用了以铪(Hafnium)为基础的High-K金属栅极技术，并在业界首次采用 45nm
工艺制造，从而提高性能、降低功耗。新处理器集成的晶体管数量相比65nm型号增加了
将近一倍，比如四核心高达8.2亿个，但凭借新技术，芯片的核心面积却平均减小了25
％，性能每功耗指标同时提升38％。
此外，Intel还加入了47条新的SSE4指令集，用于视频编码、高清播放、照片处理、HPC
和企业应用，并得到了微软、赛门铁克、Adobe的支持。增强虚拟化技术、Radix |
|
|
p*********e
发帖数: 32207 | 50 builderFactory = org.apfloat.internal.IntBuilderFactory
maxMemoryBlockSize = 201326592
cacheL1Size = 8192
cacheL2Size = 262144
cacheBurst = 32
memoryTreshold = 201326592
sharedMemoryTreshold = 786432
blockSize = 134217728
numberOfProcessors = 8
Calculating pi to 1000000 radix-10 digits
Using up to 8 parallel operations for calculation
Using the Chudnovsky brothers' binary splitting algorithm
100% complete, elapsed time 3.978 seconds
Final value took 0.826 seconds
Total elapsed time 4.852 seconds... 阅读全帖 |
|
