s**********o
发帖数: 14359 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: rongxuer (蓉儿), 信区: JobHunting
标 题: 如何秒杀99%的海量数据处理面试题
发信站: BBS 未名空间站 (Thu Apr 5 02:08:57 2012, 美东)
海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的... 阅读全帖 |
|
w*********n
发帖数: 439 | 2 题目： 如果有一个二维数组 （包括两个以上一维数组 Arr1, Arr2, Arr3 ...)， 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array，不能用List等容器。
我的思路是：
1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2． 对每个一维数组中的元素进行从小到大排序，用的是快速排序方法 （quickSort).
3． 把第一个数组和第二个数组比较（我写了compare方法）生成共同元素的新数组，
然后把这个新数组依次和后面的每个数组比较，每次都生成新数组；
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候，在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code？不胜感激。
愿意的留个email吧。有包子 |
|
w*********n
发帖数: 439 | 3 题目： 如果有一个二维数组 （包括两个以上一维数组 Arr1, Arr2, Arr3 ...)， 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array，不能用List等容器。
我的思路是：
1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2． 对每个一维数组中的元素进行从小到大排序，用的是快速排序方法 （quickSort).
3． 把第一个数组和第二个数组比较（我写了compare方法）生成共同元素的新数组，
然后把这个新数组依次和后面的每个数组比较，每次都生成新数组；
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候，在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code？不胜感激。
愿意的留个email吧。有包子 |
|
w*********n
发帖数: 439 | 4 题目： 如果有一个二维数组 （包括两个以上一维数组 Arr1, Arr2, Arr3 ...)， 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array，不能用List等容器。
我的思路是：
1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2． 对每个一维数组中的元素进行从小到大排序，用的是快速排序方法 （quickSort).
3． 把第一个数组和第二个数组比较（我写了compare方法）生成共同元素的新数组，
然后把这个新数组依次和后面的每个数组比较，每次都生成新数组；
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候，在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code？不胜感激。
愿意的留个email吧。有包子 |
|
P****d
发帖数: 137 | 5 这道题本身就有点难懂，我要问了差不多5-10分钟才搞懂题意，输入是一个String
Array，比如{"dog","cat","mouse"}，那么他就有以下六个permutation:
{"dog","cat","mouse"}
{"dog","mouse","cat"}
{"cat","mouse","dog"}
{"cat","dog","mouse"}
{"mouse","dog","cat"}
{"mouse","cat","dog"}
他要你实现serialize 和deseriallize两个方法
其中serialize的方法输入的第一个参数是输入String数组，输出是他的一个
permutation，至于是哪一个permutation，取决于serialize的方法的第二个参数。至
于第二个参数是什么，需要你自己设计
我当时设计的是第二个参数用一个int数组，int数组在每一个位置的数字，代表输入
String Array该位置上的String，在permutation数组中的位置，比如如果输入时{"dog
","cat","mouse"},辅助参数我设计的是{2,1... 阅读全帖 |
|
n**********2
发帖数: 648 | 6 【 以下文字转载自 Programming 讨论区 】
发信人: xykkkk (asdf), 信区: Programming
标 题: 老码农冒死揭开行业黑幕：如何编写无法维护的代码(zz)
发信站: BBS 未名空间站 (Fri Nov 28 13:28:27 2014, 美东)
如何编写无法维护的代码
让自己稳拿铁饭碗 ;-)
– Roedy Green（翻译版略有删节）
简介
永远不要（把自己遇到的问题）归因于（他人的）恶意，这恰恰说明了（你自己的）无
能。 — 拿破仑
为了造福大众，在Java编程领域创造就业机会，兄弟我在此传授大师们的秘籍。这些大
师写的代码极其难以维护，后继者就是想对它做最简单的修改都需要花上数年时间。而
且，如果你能对照秘籍潜心修炼，你甚至可以给自己弄个铁饭碗，因为除了你之外，没
人能维护你写的代码。再而且，如果你能练就秘籍中的全部招式，那么连你自己都无法
维护你的代码了！
（伯乐在线配图）
你不想练功过度走火入魔吧。那就不要让你的代码一眼看去就完全无法维护，只要它实
质上是那样就行了。否则，你的代码就有被重写或重构的风险！
总体原则
Quidquid... 阅读全帖 |
|
a****a
发帖数: 5763 | 7 随着CPU与GPU合并成技术发展的趋势，苹果开发出了OpenCL框架，能够进行高速并行处
理的能力使OpenCL成为了业界标准，被广泛应用。
最近几年，GPU的发展吸引了很多来自科学计算界人士的目光。GPU有稳定的市场推动力
—公众喜闻乐见的电子游戏产生了源源不断的升级GPU的需求—因此比CPU的更新步伐更
快。从技术上讲，GPU本身就是多核架构，高端显卡往往有五百多个核心，即使低端的
集成GPU也有二三十个核心，所以能够通过并行来高效处理成千上万的线程。同时，对
于科学技算中的浮点计算，GPU往往通过硬件加速使其效率比传统CPU更高，因为图形渲
染等工作基本都是浮点计算。
GPGPU浮出水面
早期的GPU只能执行固定的程序，而不开放给程序员编程。随着时代的发展，图像处理
有时需要对着色器进行编程以实现一些特效，因此需要程序员可以使用GPU的汇编语言
写简单的着色程序。这自然对程序员要求过高，所以一些高阶的着色语言又被GPU厂商
开发出来。比如微软和NVIDIA共同开发的Cg语言，就能为顶点和像素编写专门的着色程
序。这类技术虽然面向图形渲染工作者，却吸引了一小簇科学计算研究者的兴趣。... 阅读全帖 |
|
x****k
发帖数: 2932 | 8 如何编写无法维护的代码
让自己稳拿铁饭碗 ;-)
– Roedy Green（翻译版略有删节）
简介
永远不要（把自己遇到的问题）归因于（他人的）恶意，这恰恰说明了（你自己的）无
能。 — 拿破仑
为了造福大众，在Java编程领域创造就业机会，兄弟我在此传授大师们的秘籍。这些大
师写的代码极其难以维护，后继者就是想对它做最简单的修改都需要花上数年时间。而
且，如果你能对照秘籍潜心修炼，你甚至可以给自己弄个铁饭碗，因为除了你之外，没
人能维护你写的代码。再而且，如果你能练就秘籍中的全部招式，那么连你自己都无法
维护你的代码了！
（伯乐在线配图）
你不想练功过度走火入魔吧。那就不要让你的代码一眼看去就完全无法维护，只要它实
质上是那样就行了。否则，你的代码就有被重写或重构的风险！
总体原则
Quidquid latine dictum sit, altum sonatur.
(随便用拉丁文写点啥都会显得高大上。)
想挫败维护代码的程序员，你必须先明白他的思维方式。他接手了你的庞大程序，没有
时间把它全部读一遍，更别说理解它了。他无非是想快速找到修改代码的位置、改代码
、编译，然后就能交差，... 阅读全帖 |
|
i******s
发帖数: 301 | 9 面了一家在SF的SNS公司(非twitter)，一共见了4个人，2 software engineer, 1
senior SE and CTO, 废话不多，下面是on-site面经。
第一个，问了一些基本简历的问题，然后问了一个puzzle，就是那个经典的帽子问题。
1.有一堆人，每人都戴一顶帽子，帽子的颜色不是红色就是绿色，现在所有人都排成一
排，每个人都能看到前面所有人的帽子( 但看不到他后面人的)。现在从最后一个人开
始，每个人必须说出一个颜色：红色或者绿色，不能不说话也不能说除红色、绿色之外
的字句，所有人都能听到这个人的回答。如果报出的颜色和自己所戴帽子的颜色不一致
，该人就得挂掉，否则可以活下来。问：有没有一种方法能使活下来的人尽可能多。
2.现在假设有一堆整数数组，有一个flip函数，接受一个数组下标i为参数，作用是将
数组index 从0到i的元素反转。eg. 假设数组为5, 6, -1, 3, 2, 如果调用flip(3)，
那么就将数组下标0, 1, 2, 3反转，数组变为 3, -1, 6, 5, 2。问：只使用flip函数(
不能直接用swap或数组下标操作[... 阅读全帖 |
|
w**********6
发帖数: 800 | 10 我的思路是用是两个循环
设A数组是输入数组，B数组是输出数组
首先先把A数组的第一位赋给B数组
然后循环
一个大循环重复A数组的每一位
大循环里面套小循环，A数组的每一位都和B数组里面的元素逐个比，如果都没有，就把
他的值赋给B数组
然后A数组都循环了一边，就输出B数组
请教如何只用一个循环？ |
|
h****n
发帖数: 1093 | 11 坊间其实还有一种贪心算法，不过不知道正确性，你可以参考参考
先对数组进行排序，然后用动态规划思想，逐步添加。 O(nlogn)
每次读两个，一共n/2次循环，每次循环中的和计算可以累加
初始化：将最大的两个数分别加入两个新数组。
过程：1.取出原数组中剩余数中的最大数，加入数组和较小的数组，若此时较小数组变
成较大数组，重复1操作，若此时较小数组依然是较小数组，执行操作2。
2.取原数组剩余数中的最小数加入较大数组。
如此直到原数组为空。 |
|
m**q
发帖数: 189 | 12 我觉得第二题是可以O(n)的
可以把原数组的所有波峰波谷分别记录到两个数组a[k],b[k]中，
题目相当于是在把数组a，b分成两段使得两段中的a，b差值和
为最大。
可以先从前向后扫描数组a，b，对于所有index i,计算 b[q]-a[p]
的最大值，存在c[i]中，其中 0<= p <= q <=i；
然后从后向前扫描数组a，b，对于所有index i，计算 b[q]-a[p]
的最大值，存在d[i]中，其中 i<= p <= q <=k-1
然后计算index j使得c[j]+d[k-1-j]最大， 0<= j<= k-1
举个例子:
3 6 8 4 5 7 9 13 15 10 6 2 7 11 8 6
则 k=3
数组a[] = {3, 5, 2}
数组b[] = {8, 15, 11}
数组c[] = {5, 12, 12}
数组d[] = {12, 10, 9}
对应的和分别为 5+10=15, 12+9=21
最大值为21
a，b两个数组的空间可能可以优化掉，
c，d两个数组应该需要一个就够
求大牛们指正 |
|
g*******y
发帖数: 1930 | 13 关于做题目总结一类经验/思想/策略，可能说起来大家觉得比较抽象。我写个我印象比
较深刻的例子吧。
题目1: 一个ring(circular) 数组，找一段连续子数组，使得和最大。
首先第一反应就是利用经典题目max sum subarray，不过这题是环形数组，怎么办？任
意找个地方砍断，那么要找的那段子数组要么是砍断后的一个子段，要么是跨越了砍断
位置。前种情况完全就是应用max sum subarray经典题目，后种情况你怎么找一个数组
一首一尾两段子数组得到最大和？没做过的同学可以打住想想。
答案是，把问题转换为一个等价的补问题，即找一段子数组具有最小和，因为总和一定
，中间某一段有最小和的时候，首尾剩下两段加起来就有最大和了。
好，注意总结这个“转化为等价的补问题”的思路策略。再看一道题:
一个数组，找一段连续的最长的子数组，使得其和小于等于一个给定的值。
如果你把前面那道题的解题思路熟悉掌握了，你可以很快的想到，能不能试试把这个问
题转为等价的补问题:找首尾两段，长度加起来最短，SUM大于等于某个数(剩下的中间
那截自然就是满足题目的最长子数组了)。这样，由于首尾两端都是固定 |
|
S**I
发帖数: 15689 | 14 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Aug 30 00:32:06 2011, 美东) 提到:
Given an array A of positive integers. Convert it to a sorted array with
minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Aug 30 00:37:57 2011, 美东) 提到:
my 2 cents:
允许额外花费O(n)空间么。。。
允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
当前计数器值放入新开的等大... 阅读全帖 |
|
p*****y
发帖数: 1049 | 15 题目是这样的 首先给出一个函数 int * getptr() {int * a[8]; return a;}
这个函数显然是错的，看不懂的就不要往下看了，因为下面更麻烦
然后题目让写出正确的形式。这当然没有问题，但是题目又说必须用C，不能用C++，
这也没有问题。但是题目又变态的要求还要在函数里额外提供一个数组，这个数组存储
的是 ID * 指针。其中struct ID 是一个自定义的结构。这个数组的大小通过一个函数
int num()实现，这个函数只能被getptr()调用。
我很困惑，因为一个函数是不能返回两个变量的。这样就必须在argument里面提供
reference,但是注意reference是不可以的，必须用指针来实现，所以我的interface就是
int * getptr(ID** *ptr_array, int * num_of_array);
第二个变量就是提供数组的尺寸。
我突然想到一个很不可思议的方法，就是能不能保留int* getptr()的形式,然后将额外
的数组与int数组合并成一个统一的int数组，当然需要转化 int a[i]=(int) ID_p... 阅读全帖 |
|
c********g
发帖数: 449 | 16 要求用数组，但为什么对每个1维数组都排队呢？
可以只排序第一个，而后用其他数组的元素来查找第一个数组，根据是否找到来确定是
否有相同的元素，这样效率会高些吧？
假设 你已经做了“
1． 先对的每个一维数组按大小排序（冒泡排序），确保二维数组里面的一维数组是按
元素个数从小到大排列的。”
我来说个思路 看看 行不行：
1. 不需要对每个1维数组都排序，只排序第一个 Array1 并放入 ResultArray。
2.定义flag数组 并令 K=2
3. 用第 K 个数组的每个元素ArrayK2[j]去 折半搜索 ResultArray 找到则标记在
flag【i】=1 ，找不到 则flag【i】=0。
4.根据flag 来压缩ResultArray （去掉flag【i】=0的ResultArray【i】并记录 有效
数据的长度）
5 K=K+1，if （K<=N） goto 2.
6. ResultArray 含有结果（注意压缩后的有效数据的长度） |
|
g*******y
发帖数: 1930 | 17 Dec 05
最近又看到了几道很好的题：
1. 我们知道，从一个数组里找一段(连续的)子数组求最大和，是一道经典的面试题，
方法很简单，只要O(n)的时间。把这个问题变一下，假设是一个循环数组呢？找一个
size<=n的子数组with最大和。
分析，很容易想到第一步，找个地方把循环数组切断，回到了原来的问题，然后在考虑
一下额外的情况。额外的情况就是：有可能最大和的子数组是跨越了切断点的？这种情
况的最大和怎么求呢？一个naive的方法能做到O(n)，但是需要O(n)的空间。巧妙的解
法就是，注意到所有数的和是固定的，考虑切断后的非循环数组，找一段从首开始+一
段从尾开始的两个子数组with最大和，等价于找一段子数组with min sum.
总结，要擅长利用等价性转换问题，从而将新的问题转变为一个已知有好solution的旧
问题。利用已知的经典问题来解决新问题，可以说是面试题目中相当重要的一个技巧
2. largest rectangular problem：问题是这样的，一个N×M的棋盘，上面的数字要么
是1，要么是0，那么要：a）最大的一个正方形全是1填充，b）最大的全是1的矩 |
|
|
b******v
发帖数: 1493 | 19 这道题我有个想法，不过有点复杂
假设给hello上红色，world上绿色，goodbye上蓝色
则那两个位置必定是一红一绿中间夹若干蓝，但没有其他红绿，
或是一红一蓝中间夹若干绿，或是一绿一蓝中间夹若干红。
所以我们可以把三个数组合并成一个大数组并排序O(N*logN)
然后依次遍历这个大数组，并维持如下不变量：
上一个红的位置r，
上一个绿的位置g，
上一个蓝的位置b，
当前最小窗口的起始位置start, end
当扫描到大数组中一个新的元素x时，
(1)x.color = red，
如果x-min(g, b) < end-start，则更新start=min(g, b), end=x
同时更新r=x
(2)x.color = green，类似(1)
(3)x.color = blue，类似(1)
当扫描到大数组最后一个元素，就能打印出最小窗口
算法的复杂度是O(N*logN)，其中N是三个数组的元素个数之和
update: 不用合并成大数组，既然是从小到大依次遍历大数组的元素，
可以用merge sort的想法，每次从三个小数组里取最小元素。
这样，算法复杂度是O(N)。
", |
|
i**********e
发帖数: 1145 | 20 当你传一个数组进去的时候，在函数内得到的只是指向数组第一个位置的一个指针。（
不管你函数定义的是 int *a 或者 int a[]，编译器都直接转换成 int *a）。
所以如果你在函数内利用 sizeof(a) 的话，那得到的永远是 4，也就是指针的 size，
而不是数组的 size。除非你数组内有个 sentinel 值（类似 c string 的 '\0'），不然你必须传数组的长度进函数。
那为什么在定义了 int a[]，然后 sizeof(a) 可以告诉数组的总共 size (in bytes)
呢？因为这里 a 是数组，不是指针。你虽然可以利用 *(a + 3) 来得到 a[3]，但是你
不能像指针一样，可以 a++ 或者 a--。因为数组与指针的特别关系，所以数组也称为
constant pointer。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
s*x
发帖数: 3328 | 21 恭喜.
BTW:sliding window 的那个题目,前面不是有人贴链接了,楼上还有没看懂的? 用线性
结构,单纯的链表或者数组肯定不行,必须用到树形结构.堆可以.问题是这里有两个值,
一个是数组的位置,要保存好更新窗口,一个是数组元素的值,这个好取最大最小.所以就
是一个优先队列了,存的元素是数组元素下标,更新的时候将下标和当前窗口边界比较,
超出的就删除;而优先级用数组元素的值来表示.同时取最大和最小,所以一共需要俩优
先队列,伪码大概是这个样子:
for i from 1 to k 窗口的大小
add i with priority v[i] into PQ1, PQ2
max[i],min[i] 分别从 PQ1, PQ2 根的优先级得到
//上面这步是初始化,当然还要考虑窗口比数组还大的特例
// PQ1, PQ2 一个是按顺序, 一个是按逆序来的, 分别得到最大最小值
for i from k+1 to n 数组长度, 1-based index
add i with priority v[i] into PQ1, PQ2
while PQ1 根的值超出窗... 阅读全帖 |
|
g*********s
发帖数: 1782 | 22 2.现在假设有一堆整数数组，有一个flip函数，接受一个数组下标i为参数，作用是将
数组index 从0到i的元素反转。eg. 假设数组为5, 6, -1, 3, 2, 如果调用flip(3)，
那么就将数组下标0, 1, 2, 3反转，数组变为 3, -1, 6, 5, 2。问：只使用flip函数(
不能直接用swap或数组下标操作[]等对数组进行修改)，来对该数组排序。
void my_swap(int i) // swap element b/w i and i + 1;
{
//let x = A[0..i-1], a = A[i], b = A[i+1]; let x_flip = flip(x);
//we want: x, a, b => x, b, a.
//1) flip(i) , we get a, x_flip, b
//2) flip(i+1), we get b, x, a
//3) flip(i), we get x_flip, b, a
//4) flip(i-1), we get x, b, a.
}
with my_swap defined, we ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 23 恩。这题是trick question，没注意到两个数组相同长度的条件。
可以逻辑证明是正确的，我就随便写写，证明不够严格请多多包涵。
我们这里尝试以逻辑推着找反例，如果逻辑证明有出入那就代表反例必定不存在的。
首先，我们只考虑两个数组和是相同的情况，因为如果不相同那肯定是不一样了。
假设数组 A 得和为 S.
a1 + a2 + ... + an = S
那么，我们考虑其中一个反例，就是把数组 A 的一对数 (ai, aj) 变成 (ai+k, aj-k)：
那么数组 B：
a1 + a2 + ... + (ai + k) + ... (aj - k) + ... + an = S，k 不等于 0.
那么，反例如果存在的话，也就意味着：
数组 B 的平方和等于数组 A 的平方和。
但是 (ai+k)^2 + (aj-k)^2
= ai^2 + aj^2 + 2k*(ai-aj) + 2k^2
> ai^2 + aj^2
因为 k 不可能等于 0，所以 2k^2 就 > 0 了。（如果 k 等于 0 的话就是数组相同的情况了，那就更之前我们的假设有出入）
那么，也就是当把数组 A 的一... 阅读全帖 |
|
f*****e
发帖数: 2992 | 24 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
求这个子数组中的数组是一个连续的序列（不需要排好序）。
例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
为该子数组中，5,7,6,8,4是一个连续的序列。
求算法 |
|
f*****e
发帖数: 2992 | 25 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
求这个子数组中的数组是一个连续的序列（不需要排好序）。
例如，给一个数组[4,5,1,5,7,6,8,4,1]， 最长的满足条件的子数组是[5,7,6,8,4]。因
为该子数组中，5,7,6,8,4是一个连续的序列。
求算法 |
|
g*******n
发帖数: 214 | 26 想到一个算法，O(n^2)不知道行不行：
一个大循环，里面的invariant就是最小的distance就是单个的distance。把这个
distance从数组中删掉，再找到这个distance应该在结果数组中的位置。每次都取最小
值直到这个数组中只剩下一个值。具体来说就是
1.先把distance数组排序，可以得知最小的一个肯定是单个的distance，叫做min。把
这个min从数组中删掉。
2.遍历剩下的值，如果有任意两个值满足min+distanceA=distanceB的话，说明min就说
明distanceB包含了min。那么就删去distanceB。这步做完之后，所有包含min的都被删
掉了。
3.记录第2部被删掉的个数，包括min本身，一共是n个。那么计算C(x,1)+C(length-x,1
)==n中x的值，min就应该在结果数组中从一边开始数，第x-1个没有被赋过值的位置。
4.把剩下的数组作为新的数组，返回到第1步重复。
这样就可以每次得到一个值。具体的实现的话不用用数组，可以用heap来得到最小值。
还有一些细节问题，比如有duplicate： 5+5 和 ... 阅读全帖 |
|
g*******n
发帖数: 214 | 27 想到一个算法，O(n^2)不知道行不行：
一个大循环，里面的invariant就是最小的distance就是单个的distance。把这个
distance从数组中删掉，再找到这个distance应该在结果数组中的位置。每次都取最小
值直到这个数组中只剩下一个值。具体来说就是
1.先把distance数组排序，可以得知最小的一个肯定是单个的distance，叫做min。把
这个min从数组中删掉。
2.遍历剩下的值，如果有任意两个值满足min+distanceA=distanceB的话，说明min就说
明distanceB包含了min。那么就删去distanceB。这步做完之后，所有包含min的都被删
掉了。
3.记录第2部被删掉的个数，包括min本身，一共是n个。那么计算C(x,1)+C(length-x,1
)==n中x的值，min就应该在结果数组中从一边开始数，第x-1个没有被赋过值的位置。
4.把剩下的数组作为新的数组，返回到第1步重复。
这样就可以每次得到一个值。具体的实现的话不用用数组，可以用heap来得到最小值。
还有一些细节问题，比如有duplicate： 5+5 和 ... 阅读全帖 |
|
c**s
发帖数: 159 | 28 转载一个大家共勉。
由于之前Amazon已经发了offer，deadline也快到了，所以不管这次Google on-site结
果如何，都不想再继续折腾，Amazon or Google。求职季到此结束，所以，是时候写点
东西回报地里了。本人NYU-POLY，EE专业，作为一个转行的，感觉自己的求职之路还算
挺顺利，希望自己的经历经验能对各位尤其是非CS的各位有所帮助。
一。
感谢一亩三分地，mitbbs, 米群网（QQ群：320065698，可能满了，但是管理员会清理
，大家可以加加试试，另外米群网也是一个非常不错的求职平台，大家可以通过这个链
接去注册下http://www.meetqun.com/member.php?mod=register&x=12）提供的求职信息，内推信息及面经，当然也得感谢LeetCode和CC150。充分利用上述资源十分必要，而且感觉这些已经足够了。
二。
觉得有必要介绍下自己的准备情况，也算给大家涨点自信。
前面说了我是EE的，所学课程，包括本科的课，都没有什么和计算机相关的。去年暑假
决定开始自学CS，为了毕业好找工作，也就是那时候我才写出了自己第... 阅读全帖 |
|
t********5
发帖数: 522 | 29 很有可能是面试官没看懂，认为你这个不work。
我也看了很久（我本身很水而且很久没写java），因为你最后新建一个数组利用默认值
然后把[0]加一的做法我之前没想到过，所以我看了很久才明白，一开始我也以为你写的
是错的。作为面试官我认为正常情况下如果我看完这段代码没懂我会让candidate解释
清楚一下，弄清楚了之后肯定会让过，没有理由不给过。当然如果面试官没看懂的话（
很有可能）就很容易挂掉你……
另一个方面，你这个做法确实有问题，你不应该更改输入数组，如果你要更改的话更改
后的值应该是一个正确的数组而不是一个partial的数组，比如[9,9] -> [1,0,0]。但
是你的修改后的结果是[0,0]，这个作为工作中的代码是非常危险的，而且极难debug。
按照你的代码，现在你修改了原数组，然后还建立了一个新的数组，这个作为
production的代码后面的人读起来容易confuse，好的代码最好是straightforward and
self-explained。这题我建议你要么修改原数组返回[1,0,0]这种，或者遍历原数组然
后把算过的值放到新数组里面。
当然上面的这一段... 阅读全帖 |
|
f*******g
发帖数: 3 | 30 一次电面，一次onsite，一次followup interview
电面：
Leetcode 原题， Decode Ways
onsite：
共五轮
第一轮，Behavior question，末尾有coding
coding题：有一个包含N个整数的数组，数组里的成员范围都在[0-N]之间，相互
disctinct且已经升序排列，请找出唯一的那个在[0-N]之间但不在这个数组中的整数。
eg. N = 3, [0,1,3]， 输出 2
给了O(logN)的解法，写的时候出了点错误，面试官虽然是烙印，但人很好，给了提示
写对了。
第二轮，两道coding题
第一题：一个包含N个整数的数组，已知里面有超过N/2是负数，要求写一个函数处理这
个数组，让数组的前半部分填满负数(无需保留相对顺序)，后半部分随意。最后返回这
个数组中负数的总数。
给了一个O(N)的算法，暂时没想出更快的。写完代码面试官看看说行，下一题。
第二题：基本上就是leetcode原题，Add and Search Word - Data structure design
很快写完了
第三轮，system design
... 阅读全帖 |
|
f********t
发帖数: 6999 | 31 【 以下文字转载自 JobHunting 讨论区 】
发信人: mudhoof (正在长牙的羊), 信区: JobHunting
标 题: 这么热闹, 我也报Google offer
发信站: BBS 未名空间站 (Tue Feb 23 12:32:47 2010, 美东)
今天刚刚通知的, 特别感谢一起讨论的krone, geniusxsy, hnm, 特别是blaze教了我很
多, 还要特别感谢mitbbs59的总结帖
一起报offer, 好事成三, 大吉大利, 包子分光为止
贴下我的复习材料
题目大全:
http://www.spellscroll.com/viewquestions/?tag=algorithm
http://www.thecareerplus.com/?page=resources&cat=10
http://interviewcyclopedia.blogspot.com/
http://www.doctorinterview.com/A.html
http://toptechnotes.blogspot.com/search/label/algorith... 阅读全帖 |
|
X****r
发帖数: 3557 | 32 C的规则是：某类型的数组可以转化成同类型的指针。多维数组就是数组的数组。
所以你这里array是字符的指针的指针的数组的数组的数组，唯
一可以转化成的就是字符的指针的指针的数组的数组的指针，即
char **(*)[12][12] |
|
f********o
发帖数: 863 | 33 来自主题: Programming版 - 问题请教 第二个文件里的每个word,都要和第一个文件所有的行里所有词遍历一遍。
如果m和n非常大，这个好象快不了吧！
除非排序！但要先加工一下，需要将第一个文件中的所有的word一一取出，放入二维数组或者二维表，第一维放这个word,第二维放word所在的行号。然后将这个表或者数组按第一维排序。
将第二个文件里的word全部一一取出，放入一维数组或表进行排序！
将这两个数组或这两个表进行比较，如果match,就将那个二维数组的行号放入第三个数组中。待全部比较完后，对第三个数组（一维数组）再进行除重计算！
最后根据这个不重复的第三个数组中的行号数据，将第一个文件中的相关行删除！ |
|
h****g
发帖数: 105 | 34 我的理解是这样：
静态数组是局部的，当这个数组所在的函数调用完成了，就会弹栈，你这个静态数组就
不存在了，它被自动回收了。此外静态数组直接被编译器分配好放在栈里，这个大小通
常会有限制，比如在vc编译器里这个限制往往会是1M左右。
而动态数组是new出来的，必须调用delete才会删除，所以如果一个函数如果返回数组
的话，这个数组一半都用动态的。此外动态数组理论上可以扩展到操作系统的整个用户
空间（一般是3G），这个相对而言不用太考虑大小。
因此使用什么样的数组，还是要结合你的应用来考虑。运行时的overflow应该是某些你
没注意到的逻辑错误在运行的时候超出了你申请的空间的大小。 |
|
y**b
发帖数: 10166 | 35 以前读C++ Primer第四版中文版给自己写了个摘录，一搜索“初始化”，发现内容还很
庞杂，贴出来供参考，前面是页号。
042 两种初始化: 直接初始化(), 拷贝初始化=
044 变量初始化：类类型调用默认构造函数，局部内置类型不初始化，全局内置类型初
始化为零。
080 容器元素的值初始化(未指定元素的初始化式时)：类类型调用默认构造函数，内置
类型置零。
097 数组元素的初始化(同变量初始化规则044)：元素为类类型的数组调用默认构造函数
；局部内置数组不初始化，全局内置数组初始化为零。
117 new动态数组元素的初始化：类类型调用默认构造函数，内置类型不初始化，或指定
进行值初始化为零(且只能为零)。
151 new动态对象之初始化：类类型调用默认构造函数，内置类型不初始化，或指定进行
值初始化为任意值。
对提供了默认构造函数的类类型，没有必要进行值初始化, 会自动调用构造函数：
string *p=new string;和string *p=new string();无区别。
对内置类型或未定义默认构造函数的类类型，存在区别：int *p=new int... 阅读全帖 |
|
A*********r
发帖数: 564 | 36 我的意思是新数组的index可以和原来组成这个数的两个index互相转换，这样的话就保
证了在新建立的数组中查找时，可以通过比较原来的坐标，来判断是否重复。。
比如原来数组 N=10， 那么两两相加组成的新数组有100个元素
新数组的 28号元素 就是原来数组的 2号 和 8号 元素而来
如果有另外一个21号元素与28号元素相加为target, 你可以断定原来数组2号元素被重
复利用了，所以不行。。同理81..89号元素也不行。。
不过回想这道题，如果需要sort新数组的话，估计这个方案就不行了，除非再建一个
hashtable。
computing |
|
h**6
发帖数: 4160 | 37 本题可分三步走：
1.把长度为 n 的数组分为 m 段，每段不为空。对应每一种分段法，把第一段全部赋值
为0， 第二段全部赋值为1，……，最后一段全部赋值为 m-1。
2.此时得到升序排列的有重复元素的数组，且 0~m-1 每个元素至少出现一次，使用
next_permutation 函数得到其全排列。
3.根据数组中每一个元素值，把矩阵对应位置元素设置为0，其余为1。
明显，第二、三步都很容易，现在我们看看如何进行第一步，数组分段。
众所周知，把长度为 n 的数组分为 m 段，一共有 C(n-1,m-1) 种方法，其中 C(,) 是
组合数。
1)以数组形式列出所有 n-1 中选 m-1 的组合数，此时得到一个长度为 n-1 的数组，
下标范围为 0~n-2 ，其中有 m-1 个1，其余为0。
2)在数组首尾两端各缩进一格，即位置 -1 和 n-1 处，设置起点和终点。
3)对应每一个组合数，一定能找出一个分段方法与之对应，具体如下：
第一个1与起点的距离为第一段长度，
第二个1与第一个1的距离为第二段长度，
……
第 m-1 个1与第 m-2 个1的距离为第 m-1 段长度，
终点... 阅读全帖 |
|
e****e
发帖数: 418 | 38 一电：
１。给定一个数组，求次大值。
２。给定两个排好序的数组，要求返回一个排好序合并的数组。引申问题，如果数组里
的元素类型不是整数型，可能是String, double, Date...，如何处理？
二电：
１。给一个文件，从中找电话号码。
２。什么是哈希表？解决冲突的方法？
３。分层打印二叉数。
４。二维坐标里n个点，求离原点坐标最近的k个点。
５。面向对象的设计题：停车场。
面对面一：
１。问简历
２。给定一个长度为n整数型数组，看是否满足以下条件，相临数字之差的绝对值，刚
好可以组成 1,2,...,n-1。
例子：2 5 4 6 --> 1, 2, 3 成立。
2 5 4 7 --> 1, 3, 3 不成立。
1 2 3 4 --> 1, 1, 1 不成立。
引申问题：没有相邻数字的条件，可以是任何位置的数字和其他任何位置的数字的差值
的绝对值，其他条件都一样。找个小于n平方的时间复杂度的方法。
面二：
１。问简历
２。求次方，底是个浮点型，指数是整型。
３。面向对象的设计题：从数据模型的角度设计购物网站。主要有哪些类，类里主要有
哪些域，如何... 阅读全帖 |
|
f*****2
发帖数: 10 | 39 M个数放到了N个数组里， 每个数组都是升序，长度不一
找第K个最小的元素
我这是最近面到的。
我首先抛出了找K的经典解法， Selection Algorithm + Median of Medians, 当然它
是针对一个无序的数组。如果每个数组都比K长，我可以取每个数组的前K个，视它为一
个一维无序数组。这个给否了。
我又抛出 Median of Two Sorted Arrays, 分4区，然后抛弃1区的解法， 给否了。
我又抛出海量数据处理Top-K的典型解法， Max-Heap，假如数组非常大。 给否了。
大家有木有好方法， 有一点要注意的是， 分析K相对于数组长度， 解法也许不同。 |
|
z******t
发帖数: 59 | 40 的第8个例题。
这个题目通常有两个解法：
1、在对角线上二分查找。在对角线上找到比指定数字小的最大数，然后用这个数把二
维数组分成4个子数组。目标数字只有可能出现在刚才找到数组的右上子数组或者左下
子数组。接着在这两个子数组中递归查找。
这个思路的代码实现稍微有点复杂，在面试过程中不容易一次性写对。
2、每次拿数组右上角的数字和目标数字比较。如果相等，找到了。如果比目标数字大
，去掉最右边的一列；如果比目标数字小，去掉做上面的一行。接着用同样的思路，在
剩下的数组中继续拿右上角的数字和目标数字比较。
这个思路一旦把思路想清楚，写代码容易很多。这是面试过程中推荐的解法。 |
|
s****t
发帖数: 467 | 41 找工作告一段落，把前一段面试的题目整理一下一起发出来。各个公司的放在一起了，
包括flu亚麻等。有店面也有onsite。
1. LRU cache
2. 一个整数数组，先递增然后递减，也有可能只有递增或者递减。查找某个整数在不
在数组里。
3. 设计Boggle游戏
4. OO design, 用树形结构表示表达式。注意operator要用多态实现。
5. 2 sum，一个元素只能用一次
6. 1）判断一个数组中是否有3个元素和为0，元素可以重用。2）merge k sorted
array。3）稀疏向量的点乘。
7. 一个数组，把非0的元素移动到开头。
8. 1） maximum subarray 2）树里两个节点的最低公共祖先 3）LC subset
9. 设计fb newsfeed
10. 大数相乘
11. 1） 给一段话，再给两个单词，求这两个单词在这段话里的最小距离 2）打印二叉
树（level order遍历）
12. 随机洗牌算法
13. 1）给一个字符串，返回每个字符及其个数。比如：aaabcc-> 3a1b2c 2) 给字符及
其个数，返回原本的字符串 3）media... 阅读全帖 |
|
f*******r
发帖数: 976 | 42 多谢分享，希望你早日拿到大offer
找工作告一段落，把前一段面试的题目整理一下一起发出来。各个公司的放在一起了，
包括flu亚麻等。有店面也有onsite。
1. LRU cache
2. 一个整数数组，先递增然后递减，也有可能只有递增或者递减。查找某个整数在不
在数组里。
3. 设计Boggle游戏
4. OO design, 用树形结构表示表达式。注意operator要用多态实现。
5. 2 sum，一个元素只能用一次
6. 1）判断一个数组中是否有3个元素和为0，元素可以重用。2）merge k sorted
array。3）稀疏向量的点乘。
7. 一个数组，把非0的元素移动到开头。
8. 1） maximum subarray 2）树里两个节点的最低公共祖先 3）LC subset
9. 设计fb newsfeed
10. 大数相乘
11. 1） 给一段话，再给两个单词，求这两个单词在这段话里的最小距离 2）打印二叉
树（level order遍历）
12. 随机洗牌算法
13. 1）给一个字符串，返回每个字符及其个数。比如：aaabcc-> 3a1b2c 2) 给字符及
... 阅读全帖 |
|
发帖数: 1 | 43 参加了一个面试，一道算法题是这样的，我没有做出来，大家帮我看看，我觉得好难。
题目根据回忆是这样的：
发牌人手上有52张扑克牌，在一个初始化好了的数组里面（已经知道牌的点数，J,Q,K
价值是 10，A 比较特殊可以 价值 1，也可以价值 11），发牌人自己能看见数组里牌
的点数和顺序，另外有四个人，发牌人可以把数组里面的牌一张一张的按照数组里的顺
序发给四个人中的任何一个（条件是这个人拿了这张牌后，他手中的牌点数之和小于等
于21），牌必须按照初始化好的数组里面的顺序发，发牌人想把一张牌发给4个人中的
谁就发给谁。发牌人也可以选择丢掉这张牌，不发给任何人。 如果当前4个人，拿了这
张牌，手上点数都大于21，那么发牌人必须把这张牌扔掉。任何人，手上的牌，点数之
和达到21点后，得把手上的所有牌扔掉，算成功达到21点一次，他又可以开始接牌。请
给发牌人设计一种算法（每张牌发给谁，还是丢掉），让4个人产生的21点成功次数总
和最多。 不涉及任何概率的问题，因为数组里的牌是已知的。
输入：数组，52个元素代表52张牌
要求输出：
（1） 整数的一维数组，52个元素，0代表丢掉了... 阅读全帖 |
|
z*********n
发帖数: 1451 | 44
这么理解不完全对
先给你们补充几个基础知识吧:
int a[10];
意义：
a[0] 的类型是int
&a[0]的类型是int *
a 的类型是int[10]，读作"10个int元素的数组"
&a 的类型是int (*)[10]，读作“指向一个有10个int的数组的指针”
值：
a[0] 的值是a中第一个元素的值
&a[0]的值是a中第一个元素的地址
a 的值是a的地址，也等于a中第一个元素地址，规定。
&a 的值是数组a的地址，这个地址（记得我前面小组长的例子）碰巧是a[0]的地址。
所以你说a其实代表a[0]这个不对，这俩类型不一样，只是值碰巧一样。
a永远是这个叫做a的数组，不是只在&a-1中才是这个数组。
关于a-1:
a-1的类型是int *，因为数组名做减法无意义，隐式转化为int *后，减1.就跟你3/2.1
会自动升级成double类似。
另一个基本常识。
int * p
p和p-1之间地址差一个sizeof(int)
char *p
p和p-1之间地址差一个sizeof(char)
数组一样。
int (*p)[10] = &a;
p和p-1之... 阅读全帖 |
|
x**********d
发帖数: 693 | 45 我想把CPU上的一个double数组拷贝靠GPU的complexdouble数组，然后处理完之再把GPU
的complexdouble数组拷贝到CPU的double数组。。
思路就是host的double数组赋值到host的complexdouble数组，然后host的
complexdouble数组memcopy到device的complexdouble数组,and the vice versa。。。
不知道哪里错了。。大神们给看下呗。。感激不尽。。
/////// Host to Device
double *h_data= new double[height*width];
cufftDoubleComplex *h_idata;
h_idata=new cufftDoubleComplex[width * height];
cufftDoubleComplex *d_idata;
cudaMalloc((void**)&d_idata,sizeof(cufftDoubleComplex)*width*height);
for(int i=0;i阅读全帖 |
|
k**g
发帖数: 12 | 46 【 以下文字转载自 JobHunting 讨论区 】
发信人: kbug (feeding roll), 信区: JobHunting
标 题: 请教一个算法问题
发信站: BBS 未名空间站 (Tue Dec 19 16:34:21 2006)
有两个数组，每个数组元素的值代表该元素与前一元素的距离。现求一数组是否是另一
数组的子集。
比如第一个数组为：
0 1 1 7 3 2 1 1 2 1
第二个数组为：
0 5 4
算法应该输出如下结果：
0 1 1 7 3 2 1 1 2 1
0 5 4
第二个数组的pattern 出现在第一个数组的第3个位置（以0为起始地址）， 因为3+2=5
and 1+1+2 =4。 |
|
h****8
发帖数: 599 | 47 Char **array[12][12][12] 三维数组，元素是char**
char ***** p = array; p是5维指针，从数组到指针的转换是可以。所以我认为这个对的
char * (* p) [12][12][12] = array; p是指针，指向一个三维数组，数组元素是char
*,所以错
const char ** p [12][12][12] = array; p是三维数组，元素类型是const char**,我
觉得这里non-const应该不能转换成const,因为是元素而不是指针，所以也错
char (** p) [12][12] = array; p是二维指针，指向一个二维数组，元素类型为char,
很明显连dimension都不对
char ** (* p) [12][12] = array;p是一个指针，指向一个二维数组，元素类型为char
**,与array所指向的数组类型不同 不能赋值
所以只有1是对的我认为。 |
|
c****3
发帖数: 10787 | 48 好像有个简单方法，就是消耗点内存。
简单点用a-b-c-d四个区段说明，按照火车行驶方向，有a-b-c-d, a-b-c, a-b, b-c-d,
b-c, c-d, 这5个可能的区段。这5个区段每个，准备一个数组，有1000张票的空位。
每个数组有个指针，指着剩余票的尾巴。
刚开始所以票都在a-b-c-d数组里，填满这1000个位置，有1000张票。其他数组都是空
的，没有一张票。如果卖掉一张票，就把数组里剩余票尾向前移一位。如果有人买c-d
的票，先找c-d数组里有没有票，如果没有，就从a-b-c-d数组里取走一张票，因为a-b-
c是剩下的空位，把这个空位添加到a-b-c数组里去。 |
|
b***s
发帖数: 242 | 49 我手里有4组数，分别是数组A，数组B，数组C和数组D。
数组A是dependent variable,数组B、C、D都是independent variables
当我把3组自变量同时做回归分析时，B的p-value 是0.47， C的p-value是0.03，D的p-
value是0.57。
但是如果我分别只用一组自变量与数组A做回归分析时，B,C,D数组的p-value都是0.00。
我的问题就是，既然B，C，D都各自分别与A高度相关，那么把B，C，D同时放在一起做
回归的时候，为什么B和D的p value那么大呢？
我是新手，是用EXCEL做的，可能问题很白痴，有没有哪位同学给我解释一下？非常感
谢。 |
|
s*****r
发帖数: 43070 | 50 【 以下文字转载自 JobHunting 讨论区 】
发信人: wsclock (精确), 信区: JobHunting
标 题: F家详细面经，有工作经验被拒(超长慎入)
关键字: facebook,interview
发信站: BBS 未名空间站 (Fri Sep 22 20:45:31 2017, 美东)
简单总结：CS博士，奔5了，申请facebook software engineer，不是headquarter。
onsite后第三天收到据信。估计死在system design上。面试简况如下。详细的在后面。
Screening 和final round头两个都是coding interview，都做到了bug free。题目不
难，即使没刷过题，也容易有思路。唯一不足的是，有一个coding写的代码不是时间复
杂度最低的。虽然后来给出了优化的办法，但是没有时间写优化的代码了。
下一个是system design，感觉不太好。其中一个问题是估计要多少个server，我解答
的时候，最大的失误可能是没有问每秒钟多少个transaction，面试官也没给这个条件
。面试官指出... 阅读全帖 |
|
