c*****o
发帖数: 178 | 1 在glassdoor上看到一道题目：
Given a file of unknown size, devise an algorithm to give equal probability
randomization to choosing a single line given a one line buffer space.
请教思路？ |
|
|
z******s
发帖数: 8 | 3 昨天去某公司面试 Software Engineer碰到的最后一道题：
有一种新语言，只能做三种操作。
X=0; 给变量赋值为0；
X++; 递增
LOOP（x）{。。} 给定一个变量值就循环X次，循环block可以嵌套定义的三种操作。
题目是给定B，求A=B-1。
想了很久还是没有想出来。。大家可以帮忙看看有什么思路吗？ |
|
s*****r
发帖数: 773 | 4 版面上的一道题目, 出现了好多次, 但是找不到大家的讨论了
类似这样的
there are lot of log files, how to find the most common string in the files. |
|
L*******o
发帖数: 895 | 5 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这
两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都
出现了两次。请写程序找出这个只出现一次的数字。
我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们
从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字
，因为那些出现两次的数字全部在异或中抵消掉了。
我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个
只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办
法就是分别求出这两个只出现一次的数字了。
从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数
字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字
肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中
至少就有一位为1。我们在结果数字中找到第一个 |
|
c****s
发帖数: 241 | 6 听来的一道c++题，大家看看
class A{
public A(int t){};
};
void f1(A a){...}
void f2(A& a) {...}
void f3(const A& a) {...}
下面的函数调用，哪些能工作，哪些不能，为什么？
f1(5);
f2(5);
f3(5); |
|
f*********6
发帖数: 6 | 7 一道面试的题目。
老师给的题目就是这样的，哪位大牛能给些提示呀！！ |
|
c******g
发帖数: 71 | 8 申请summer intern，今天被面到其中一道题：n locations, 知道两两之间的距离，问
经过所有locations，而且仅经过一次的最短距离怎么走。我做得很马虎。
这貌似就是著名的travelling salesman问题。哪位大侠出来说说有什么简单高效的算
法？ |
|
M*****y
发帖数: 666 | 9 【 以下文字转载自 Quant 讨论区 】
发信人: MsPiggy (coconut), 信区: Quant
标 题: 一道关于两倍年龄的题目
发信站: BBS 未名空间站 (Thu Mar 11 19:32:14 2010, 美东)
有没有高手来说说这道题怎么讨论？
两个人，A,B. A的年龄比Ｂ大。
For what length of time in their lives will A's age be twice B's age? (此处
的年龄说的是 truncated integer age). 还有一个assumption是两个人都可以无限地
活下去。
假设不限定具体的年龄数，该如何讨论这道题目呢？多谢！
我自己觉得无论Ａ，Ｂ多少岁，这个问题的答案始终是１年
不知道对不对，有什么合理的讨论方法 |
|
|
l*******n
发帖数: 14 | 11 昨天的电面，开始还不错，问了很多C++的东西，virtual function, overloading之类
的，然后就是两道算法题，第一道是很常规的链表处理题，很快搞定并写程序，第二道
题题目比较长，他先给我解释说google在搜索完成显示结果的时候会生成快视图 （也
就是把含有搜索关键字的部分显示一下）。现在搜索三个词，比如“hello”,"world",
"goodbye", 搜索完成之后会有三个array，每一个array都存放着三个词在一篇文章里
的位置。写一个函数，返回两个值，代表文章中的两个位置，在这两个位置之间，“
hello”,"world", "goodbye"至少各出现一次，而且要求这两个位置之间的距离尽可能
短。那位大哥光阐述这道题就用了5分钟。。。我听的有点晕，不过迅速明白了题的意
思，但是到最后也没能给出他认为的最优答案，看看哪位达人有思路？？？？ |
|
j**l
发帖数: 2911 | 12 由此想到，即使是很简单的题目，要在面试时候发挥好也不是那么容易，需要多练。
首先面试官会有一些特殊要求，比如这题的只许用一重循环。通常情况下大家都习惯用
两重循环，第一重找到单词开头，第二重跳过整个单词。PIE书里头反转字符串中的每
个单词那个例程，就用了两重循环。
另外如果没有想到问题的实质是检测脉冲，可能会走弯路。程序对开头有没有空格，结
尾有没有空格，以及全部是空格，全部是非空格这些情况都要能涵盖到。
程序是否简洁也很重要。比如用到的flag个数是否可以减少。比如你可以用到两个flag
,一个表示单词刚开始，一个表示在扫描整个单词的所有字符。但后者不是必需的，而
且容易让程序变复杂，容易出错。
对简单题，时间要求和bug free的要求是很严格的
其实，面试并不一定是用难题来考倒人。简单题一样可以考察面试者的基本功。如果看
了大量的难题，结果面试的时候却栽在简单题上，是很可惜的。
其实大家看了那么多难题名题，也决不能忽视对简单题的练习。或许大家还真应该希望碰上的都是见过的难题名题。当碰到一道看去很简单的问题，不可窃喜和掉以轻心，一定要注意有没有什么附加限制，有没有什么陷阱，尽量快 |
|
b******v
发帖数: 1493 | 13 我amazon一面时就遇到这样的情况
一道很简单的题，怎样判断两个BST是否相同
结果我给了判断inorder traversal和preorder traversal是否相同的解法，并coding
用掉了面试大部分的时间
其实只需要用递归判断当前节点，左子树，右子树是否相同就可以了
好在他们还是给了我二面的机会，希望我不会再次搞砸
flag |
|
j**l
发帖数: 2911 | 14 三江口内，风浪不息，铁索连舟，如履平地。
这是小尾羊同学Google最终面的一道经典题目
核心思想就是，先合后分。
先平凡复制整个链表，不考虑random指针。
充分利用random指针和next指针，把原始链表和复制的链表这两个链表关联起来。传说
中有两种连接法：一种是串成长度为2倍的新链表(类似一串珍珠)，另一种是两个平行
但竖直方向对应节点相连的链表（类似横着的梯子)
不管哪种连法，都可以方便的给random指针赋值了。
然后不要忘记把两个链表的关联断开，成为两个一样的独立链表。 |
|
r****o
发帖数: 1950 | 15 同问。
还有一道题是对这个matrix排序，用什么算法最好? |
|
a***9
发帖数: 364 | 16 这个做法是错的～
发信人: amoi9 (amoi), 信区: JobHunting
标 题: Re: 问一道google面试题(from careercup)
发信站: BBS 未名空间站 (Sun Apr 11 22:34:54 2010, 美东)
Thanks for back up.. |
|
f*******r
发帖数: 1086 | 17 今天看了一道DP题目，自己写了一个函数，请大家看看是否有问题:
题目：
A sequence of numbers is called a zig-zag sequence if the differences betwee
n successive numbers strictly alternate between positive and negative. The f
irst difference (if one exists) may be either positive or negative. A sequen
ce with fewer than two elements is trivially a zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3
,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1
,7,4,5,5 are n |
|
|
s*********s
发帖数: 318 | 19 想起来类似的一道题。如要已经有sharp和rectangle这两个类，如何加入正方形？ |
|
s*********e
发帖数: 36 | 20 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
外，主要集中
在data structure, database design。快结束时候问的一道题发散出新问题，让我想
了之后
尽快发信给他。一个open question在这里求大家帮忙啦！
题目：
问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
答：用hash table做 blahblah
问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
作。可能
整个工作过程的某个时段这台机器得到的url set跟另一台机器得到的url set不一样，
我们又不希
望重复劳动。怎么办？
答：这100台机器不是联机了吗，把url的hash table存在global 的file system里，每
台机
器都对这个global的hash table操作
问：如果不允许存在global的file system里呢？每台机器可以send information给其
他机
器，可以接收information，但不能专门reque |
|
s*********e
发帖数: 36 | 21 这是一位网友的回答，我觉得很好就贴出来分享了，用consistent hash来做。
寄信人: duduhao (dudu)
标 题: Re: 在线紧急求助一道system design面试题，面经内附
发信站: 未名空间 (Wed Jun 23 01:16:45 2010)
来 源: 24.17.
Hi Shiningfree
Just saw your post. I can help you on this
Your answer is workable, but it is not optimized, so the hiring manager
follow up with you today. I will give you some of my ideas, hope it is
helpful to you.
There is a kind of data structure called consistent hashing, you can google
or wiki it. it is the critical data structure can be |
|
p******n
发帖数: 32 | 22 来自主题: JobHunting版 - 再来一道题 一些面经那个帖子里的一道题
一个数组有k个不同数字,假设k是常数，如何O(n) time, O(1)space排序 |
|
e**c
发帖数: 195 | 23 面试中被问到一道brain teaser，给了十分钟时间，没有做出来。Interviewer告诉我，十分钟做不出来很正常，他只是想看一下我做题的思路。回来之后，在网上搜了很久，没有找到，想和诸位大侠讨论一下：
背景：地球的北极点有一个空军基地，有无穷架飞机。所有飞机的配置一模一样。每一架飞机携带的汽油恰好能供飞机沿一条经线从北极点飞到南极点。如果两架飞机相遇，每一架飞机都可以在空中把自己的一部分或者全部汽油给另外一架飞机。
要求：设计一个策略，使一架飞机能够从北极点沿西经90度经线飞至南极点，然后沿东经90度经线返回北极点。也就是说，这架飞机的轨迹是一个完整的大圆。此策略必须满足以下条件：
(1)所有加油的飞机也必须返回北极点；
(2)要求用到的飞机最少。 |
|
A*******1
发帖数: 985 | 24 电话interview，最后一道题砸了。
Given two int array A and B, the length is very large, how to find all the
common numbers in these two arrays with time complexity o(n). |
|
f*******e
发帖数: 1161 | 25 一道编程题：给一个board和字典，找到所有words
求高人提示解题思路！ |
|
r***8
发帖数: 86 | 26 玩笑了，是我想出的一道面试题，肯定早有人想出过这种题。 |
|
b******y
发帖数: 660 | 27 前段时间看到一道Google Intern的题目，没想出来具体怎么做，所以上来请教一下各
位大侠，请不吝赐教。
意思大概是这样的：
一群人要清算相互之间的欠款，要写check给对方。问能不能找出一种还钱的方法，以
至于每个人只要写一张check.
譬如说
A欠B 10刀，
B欠C 10刀，
B欠D 10刀，
D欠C 20刀，
原本B要写两张check的，一张给C,一张给D，
跟好的方法是B只写一张20刀的check给C,而D写一张10刀的check给C
要设计一个算法判断是否存在有这种只写一张check的解。 |
|
i*******n
发帖数: 79 | 28 以前面试时候被问到过这样一道题,纠结至今不知道怎么回答,诚心请教各位.
题目如下:
你对油画有权威的鉴赏力,你认为一幅画可以卖多少钱,它就值多少钱.现在有100幅画,
分别放在
100个房间中,你需要一个一个房间的看,才知道每一幅画的价格,在走入房间前,你对这
些画每幅的
估价没有任何信息.
在看了画之后,你首先要对这一幅画进行估价,然后必须做出决定:买,或者不买.看完所
有的画后,
你将付钱买你已经决定要买的画,但是,这些画的买入价格是你估的所有100幅画的平均
价.
请问你该采取什么样的strategy,才能保证最大化的利润? (也就是说,什么时候你就决
定买,什么
时候就决定不买?)
注意:1.你的估价师诚实的,也就是说你不能认为一幅画可以卖1000刀但却故意说它只值
900刀.
2. 这些画是随机放在房中的,不是说按从贵到便宜,或从便宜到贵摆放(不过也有这种可
能,随机放
的).
我的纠结点就是,当你走进个新房间,面对幅新画时,你完全不能估计到它是在所有画的
均价之上,
还是之下...(除了最后一幅)
这题纠结我好几个月了.....
谢谢各位!!! |
|
b******y
发帖数: 660 | 29 是careercup 上面amazon的一道题
http://www.careercup.com/question?id=3214677
Finds whether nodes u and v have a path in between them in O(1) time
用adjacency matrix可以实现；
Finds whether there is a path of length k between u and v in O(k)
这个不是很明白。
careercup上面也没讨论清楚。 |
|
d***8
发帖数: 1552 | 30 能展开说说吗？
怎么存储链表里的data和next指针？
another list 是作什么用的？
多谢！
这是一道面试题。他让我周末作完发给他。 |
|
o******y
发帖数: 13 | 31 consider the process of stepping from integer x to integer y along the
integer points of the straight line. The length of each step must be non-
negative and can be one bigger than, equal to, or one smaller than the
length of the previous step.
What is the minimum number of steps in order to get from x to y? the length
of both the first and the last step must be 1.
INPUT:
the input begins with a line containing the number of test cases - n. Each
test case that follows consists of a line with two... 阅读全帖 |
|
P********l
发帖数: 452 | 32 觉得这道题更象在考楼主的人品，除非楼主就是搞这个的。google一下real time
system scheduling。从第一道题开始，可以延伸到很多优化技术。不要信口开河就好
。 |
|
h***n
发帖数: 276 | 33 很常见的一道题，
N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。
算法比较好描述：先两两比较找出最大的数，然后在找和最大的数曾经比较过的数中最
大的数为第二大的数。我的问题是怎么写代码？谢谢！ |
|
|
i**********e
发帖数: 1145 | 35 最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
我想到一个利用堆的解法，可以达到 O(k log min(m, n)).
但看网上 google 要求的最优解法好... 阅读全帖 |
|
|
d**f
发帖数: 264 | 37 这是是不是类似google的一道面试题，怎么去design google suggestion? |
|
v****x
发帖数: 14 | 38 一道题目，衍生3道小题目。
在面试官的引导下倒是回答正确的。但是用的时间太长。
主要是面试的时候基本无法思考。 |
|
i**j
发帖数: 20 | 39 面试一家maufacturer的global sourcing职位，有一道面试题不会，请大家帮我看看。谢谢！
Sales:
month 1 2 3 4 5 6 7 8 9 10 11 12
Y06 1000 1000 1500 1500 1500 1500 2000 2000 2000 1500 1000 1000
Y07 2000 200 2000 2000 2500 500 2500 3000 3000 2000 2000 500
Y08 2500 2500 3000 3000 3000 3000 3500 4000 4000
Please calculate monthly order quantity f... 阅读全帖 |
|
c********l
发帖数: 8138 | 40 某公司的笔试，具体名称我就不说了，有这样一道题目
你是在公司已经工作5年的VP，最近你们公司有很多新招进来的fresh grads。
今天，已经晚上9点了，你仍然在office里面奋战。正在这时候，你抬头，
看到楼层不远的地方，有一位新来的fresh grad A 同学正因为压力太大而伏在案上啜泣
这时候，你会
A.当作什么事都没发生
B.告诉A的直接上司，希望他能够给予A心理上的辅导
C.自己走到A旁边，询问什么原因
D.因为自己和A不熟，所以找一个和A比较熟的同事B，让B过去安慰安慰A
E.其它（请注明）
问题1：从A到E的选项中，你最应该做的是什么？为什么？
问题2：从A到E的选项中，你最不应该做的是什么？为什么？ |
|
j**f
发帖数: 7403 | 41 我认为，应该C，就算不熟，也可以问问，能帮忙的帮，不帮忙的心里记住
想想以后怎么帮，或者怎么避免，或者找人暗暗的帮。
我认为，最不应该选B，相当于小报告了。如果B处理不当，那个员工会更惨的。
某公司的笔试，具体名称我就不说了，有这样一道题目
你是在公司已经工作5年的VP，最近你们公司有很多新招进来的fresh grads。
今天，已经晚上9点了，你仍然在office里面奋战。正在这时候，你抬头，
看到楼层不远的地方，有一位新来的fresh grad A 同学正因为压力太大而伏在案上啜泣
这时候，你会
A.当作什么事都没发生
B.告诉A的直接上司，希望他能够给予A心理上的辅导
C.自己走到A旁边，询问什么原因
D.因为自己和A不熟，所以找一个和A比较熟的同事B，让B过去安慰安慰A
E.其它（请注明）
问题1：从A到E的选项中，你最应该做的是什么？为什么？
问题2：从A到E的选项中，你最不应该做的是什么？为什么？ |
|
f******n
发帖数: 279 | 42 问一道面试题：
int array a[n] with all element 0<=a[i]<=1000,find the subarray with
the largest sum that is <= max and output the starting and ending index of
this subarray and the sum. If there is more than one such subarray ,
output the one with smallest starting index.
请问这个算最快？ |
|
U*******L
发帖数: 94 | 43 面试的一道问题
给定一种概率发生器，出1的概率是p,出0的概率是1-p
如果我们需要一个概率都是1/2的概率发生器，该怎么做？
如果是1/n的，怎么做？
1/2的做出来了
1/n的做着做着就乱了
求问 |
|
g**********y
发帖数: 14569 | 44 A/G都问的一道：Find kth smallest number in union of two sorted arrays
好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
public int get(int[] a, int[] b, int k) {
int lower = Math.max(0, k-b.length-1);
int upper = Math.min(a.length-1, k-1);
int i = (lower + upper) / 2;
return get(a, b, k, lower, i, upper);
}
private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
int j = k - i - 2;
... 阅读全帖 |
|
j**l
发帖数: 2911 | 45 可以化归为这样一道题：
设计一个有序的数据结构，最初里头有自然数1到n这n个元素，
随后这些元素可以被删除，但剩下元素仍然保持有序。
要求实现方法GetKthElement(int k)和RemoveKthElemenet(int k)，使得它们在任意时
刻都不超过O(lgN), N为当前的元素个数, 1 <= k <= N
感觉要结合BST之类 |
|
d*******l
发帖数: 338 | 46 我记得POJ上有一道一模一样的题，是典型的线段树/树状数组的题，线段树可以做到
nlogn，树状数组nlog^2n。我应该A掉了，方法就是用线段树维护一个区间内还剩下的
点的个数。 |
|
i**********e
发帖数: 1145 | 47 来自主题: JobHunting版 - 一道G家题 这题到底是一个还是两个序列？
发信人: absolute100 (绝对100度), 信区: JobHunting
标 题: Re: 一道G家题
发信站: BBS 未名空间站 (Thu Jul 21 18:38:53 2011, 美东)
给一个有序的M到M+N的序列，找不在这个序列中的数。要去lgn |
|
b*f
发帖数: 212 | 48 考，还真是这里的一道题。
有人做过么？
求比穷举法好一点方法就行，
非常感谢！ |
|
k*j
发帖数: 153 | 49 最近碰到一道题，一个large file，一行是一个单词，
too
who
but
beer
给定一个单词，如何得出alphabetical排序里的下个单词。比如beer的下一个是but。
假使file可以fit into memory.
大家有什么好方法？有人提示用bst 或者hash? |
|
k*j
发帖数: 153 | 50 careercup那本书上一道题。
10.3 Given two lines on a Cartesian plane, determine whether the two lines
would intersect.
书里是用slope来做。
return abs(line1.slope-line2.slope)>esp || abs(line1.yintercept - line2.
yintercept) < esp
但明显这没有考虑slope infinite的情况。所以不是很好的solution.
想问问这题有没有更general的解法呢？多谢！ |
|
