m***g
发帖数: 90 | 1 这个频度为何是 O(n3)?
(1) x=1;
(2) for(i=1;i<=n;i++)
(3) for(j=1;j<=i;j++)
(4) for(k=1;k<=j;k++)
(5) x++;
该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关
系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以
从内层循环向外层分析语句(5)的执行次数：
3)被执行 1+2+..+n 次，4)被执行 1+(1+2)+..+(1+..n)，怎么算x被执行n3?
谢谢！ |
|
g*********s
发帖数: 1782 | 2 是1~N吧？这样数组长度为N，取值范围也是N，然后用grass那个把A[i]放在A[A[i]]的
技巧。 |
|
i**d
发帖数: 357 | 3
你这个greedy的取值条件不对。
应该是首先按照结束时间排序，然后greedy的每次取最早结束的presentation.
并且remove有overlap的presentation
按照这个例子应该首先排序成
[0,2],[3,7],[3,12],[8,15],[14,15]
首先取 [0,2]
然后取 [3,7] 并remove有overlap的[3,12]
最后取 [8,15], 并remove掉[14,15]
结果就是[0,2],[3,7],[8,15] |
|
c****p
发帖数: 6474 | 4 key值取负，然后放到maxheap里，实际上不就成了minheap了么。
取值的时候再变回来。 |
|
w******g
发帖数: 313 | 5 我有个问题。。在b表里，j的可能取值都被列到表头上了，那在b表就不存在j这个变量
了吧？ |
|
n*******w
发帖数: 687 | 6 跑了随机1000个元素的例子，取值范围为0-99。结果不对。
问题可能在于，得到一个sequence在hashmap里会残留下一些entry，导致接下来处理重
复元素出错。
比如残留的entry里有两个sequence [0 10] [6 12]。hashmap里会存在4个entry [0,11
] [10, 11] [6,7] [12 7]。如果下一个元素是11。合并两个sequence，得到长度为19
的sequence。其实不存在。
问题在于[12,7]是以12结尾的长度为7的序列。而以后访问的时候并不知道，把它当做
12开始长度为7的序列。而残留的entry里有很多这样的sequence，导致整个结果不对。 |
|
g*****k
发帖数: 623 | 7 来自主题: JobHunting版 - 一道G家题 楼主原题中说数的取值范围是0到M,
"range over M" |
|
x****1
发帖数: 118 | 8 Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
得住的说吧。废话不说，直接上题：
Phone screen：
先问了10道左右的小题，都是概念性的。
包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
有没有多线程，怎么实现。
最后还有5分钟结束的时候，给留了两道coding题，让我明早之前发给他。
一个就是binary search，不用多说了。
另外一个就是如何查找rotated sorted array (这也是很常见的题，因为面试官讲的是
cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）... 阅读全帖 |
|
i**********e
发帖数: 1145 | 9 >>第一题是 bool isOverlap(int a, int b, int c, int d)参数取值范围0~6代表星期
几。a 到b是一个区间，c到d是一个区间，查看有没有overlap，要考虑跨周末的情况。
这题我也被问到了，只不过我的不用考虑跨周末的情况。
如果不用考虑跨周末，直接 return min(b,d) - max(a,c) > 0 就行了，因为如果相交
的话，其中一个终点必须包括在另一个区间。
如果要考虑跨周末的话，也就是当起点大于终点的状况：【2,1】 --> 指的是星期三到
星期二，那么把起点减掉 7，这样就能保证起点永远小于或者等于终点了，然后再用回
之前的方法。
不知道 lz 的方法是不是这样？怎样还有更巧妙的 trick，可以不用 >, < 来做？
另外要加个强 bless！
的地方。
不是很
但也没找出什
session，项目中 |
|
m**q
发帖数: 189 | 10 题目中说明了，index是 0~n-1,value是1~n-1，
所以a[0]的值一定在1~n-1,你说的情况不会出现。
不过这是这道题的一个很强的限制条件。如果value
的范围是0~n-1，那么检查cycle的方法不能用于
解这题，因为会有local cycle的情况，无法保证
找到cycle，就像你说的
index 0 1 2 3 4
value 4 2 2 3 0
dup是2，但是check cycle只能检查到0，4构成的环，
无法找到2这个dup。只是这道题目对取值的限制
保证了这种情况不会发生。 |
|
m**q
发帖数: 189 | 11 那个题的限制条件是 n个数，n-1个取值，所以可以用
check cycle的方法。
这道题不满足上述条件，举个例子：
index 0 1 2 3 4
value 4 2 2 3 0
min是0，max是4，max-min=4
check cycle的方法只能找到 0，4两个元素
构成的环，无法发现2是dup |
|
l****5
发帖数: 60 | 12 n个obeject排序，
object有int和string两个域，知道int部分的取值范围，
排序只考虑int域的值，
要求时间o(n)，空间o(1)
求指点，谢谢 |
|
K*****k
发帖数: 430 | 13 看去都是Java的，很容易改为C++
但是Java对null进行引用取值也是有问题的吧？反正C/C++的基本就是segmentation
fault. |
|
n*******w
发帖数: 687 | 14 不还是那样做么。
假设a不可以等于b。这个无关紧要，只影响dp的下标，不影响dp的使用。
1）把0到N分成3部分。
那么第三部分b的取值可能性有哪些。b可以取2到N。假设b=j，第三部分为j-N
2）剩下0到j，要分成2部分。
2）是1）的subproblem，所以可以dp。
recurrence是
D（i, k） = min {D(j, k-1) + f(j, i)}
k-1=
D（i，k）意思是把0到i分成k部分。
这个题是要得到D（N，3）。需要3N的空间，复杂度O(N)。
b, |
|
u*****3
发帖数: 12 | 15 Count winning possibilities of a modified tic-tac-toe game. Given N*M,
board, count all possible winning positions for K pieces in the row(
horizontal, diagonal, vertical)?
不太明白题目的意思； 例如K的取值范围： 好像不同的K的答案不一样啊？ 有没有谁
想过这题； 谢谢！ |
|
r******r
发帖数: 700 | 16 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 17 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
S****h
发帖数: 115 | 18 这个是DP问题，觉得光凭说不是很容易理解。不过DP从来只要知道怎么从sub optimal
solution得到最优解就好了。试试~
问题：N个鸡蛋，H层高楼，最少需要多少次trial可能确定safe floor?
Let S(n,h) be the minimum required number of trials for the conditon:
n eggs and h uncertain floor (不确定是否safe的楼层数，不是总的楼层高度)
假设此次试验在 x 层， x ∈ [1 ..h],并不是绝对楼层数，而是h个不确定的楼层中的
某一层。测试结果分为两种情况：
1. 鸡蛋打碎
s(n,h) = 1 + s(n-1, x -1);
2.鸡蛋完好无损
s(n,h) = 1 + s(n, h - x);
考虑到所有可能的x的取值[1..h]
s(n, h) = 1 + min{ max {s(n-1, x-1), s(n, h-x)}} x ∈ [1..h]
然后base case
s(n,h) = 1 //h == 1 只有一层，无论几个鸡蛋
= h /... 阅读全帖 |
|
h****e
发帖数: 928 | 19 二爷有时间的话发一段code吧，我不理解如何在知道4,8以及它们的
子树的取值范围以后处理2,7,9的。 |
|
h****e
发帖数: 928 | 20 这样的题目一般要先问清楚字符的取值范围。不过从效率的角度来说
一般面试的人都会希望看到你的解法。HashMap之类的总给人不简洁的
感觉，会打折扣。
题目做到后面的改进就是简洁清晰。精华区里小尾羊的经验帖子就做过
这样的总结。
, |
|
t****a
发帖数: 1212 | 21 这是个数学题诶
假定用XY = {[x1,y1],...,[xi,yi],...[xn,yn]} 表示各个人的位置
求[x0,y0] = argmin{\sum(f(x0,yo))} = argmin{\sum(dist([xi,yi],[x0,y0]))}
目标函数是关于x0,y0的二次函数，可以对它求关于x0,y0的偏导数，最小值发生在两个
偏导数都等于0
解这个方程组可以得到x0, y0的取值 |
|
t****a
发帖数: 1212 | 22 这是多年前的一篇牛文。一家之言，仅供参考。
通天塔导游
(译注：圣经记载：在远古的时候，人类都使用一种语言，全世界的人决定一起造一座
通天的塔，就是巴别塔，后来被上帝知道了，上帝就让人们使用不同的语言，这个塔就
没能造起来。 巴别塔不建自毁，与其说上帝的分化将人类的语言复杂化，不如说是人
类自身心灵和谐不再的分崩离析。之所以后来有了翻译，不仅是为了加强人类之间的交
流，更寄达了一种愿望，希望能以此消除人际的隔阂，获求来自心灵的和谐及慰藉。真
正的译者，把握血脉，抚平创痕，通传天籁，开启心门。)
这是我写的旋风式的编程语言简介—我本来为亚马逊开发者杂志本月的期刊写的，但是
发现我写的东西没法…见人。
首先，我偶尔一不小心口出脏话，或者对上帝不恭的话，所以对很官方很正式的亚马逊
上发表是不合适的; 所以我就把它塞到我的博客里了，我的博客反正没人看的。除了你
以外。是的，只有你会看，你好啊。
其次，这是一项进行中的工程，现在只是东打一耙西搞一下，还没有精加工过的。又一
个把它写到博客里的很大的理由。不需要很好，或很完整。就是我今天想说的一些话。
请随便！
我的旋风式简介会讲C，C++，Lis... 阅读全帖 |
|
f*******4
发帖数: 64 | 23 如果基于比较的方法可以做到可以O(m*n), 那么对任意m*n个元素排序，只需要对young
进行(m*n)lgm的堆排序。
固定m的取值，相当于总排序时间为O(N) |
|
Q*******e
发帖数: 939 | 24 不行, 比如8bit
数值表示-128~127
如果你取值绝对值 -(-128) = 128
放在8bit里面如何判断? |
|
t****a
发帖数: 1212 | 25 sudoku solver如果用recusion的话，会在函数中多次call自己对吧？因为某个格子有
多种可能取值，那就要call多次, 也就是
solver(X) = solver(X1) or solver(X2) or ... or solver(Xn) 这里用X表示sudoku
的状况，solver函数返回T or F。
简单起见我就写了个fib，也是一样，fib(n) = fib(n-1) + fib(n-2)，可以把这种计
算用map函数来实现，再将map换成pmap就并行啦。程序里有个if来控制生成的thread个
数，生成太多就糟了，刚才试过，不加控制生成太多thread会直接挂掉。
其实map-reduce的map灵感也就来自lisp的map。
回到sudoku，这个并行要难一些，因为它是个有回溯的过程，map出的有些子函数很早
结束有些晚结束，所以用相同的逻辑并行效率不好。如果用个全局变量来估算当前的
thread个数并据此判断用map还是pmap会好一些。
不得不说这样的实现实在很丑陋... 如果有人能把lazy evaluation的思路加进去，把
recusi... 阅读全帖 |
|
A*****i
发帖数: 3587 | 26 vector只能用迭代来取值和删除值，和arraylist还是不一样的
确实C++没有这种实现，不过可以用hash+vector来做
或者arraylist怎么来的应该都知道，同样的方法在C++里面做一个就可以 |
|
b****g
发帖数: 192 | 27 多谢！
但是你给的这个例子里，要求每个元素的取值是0到k。 |
|
l*****3
发帖数: 32 | 28 int board[8][8] each value in the matrix represents a character. 1-9 number
represents all whites and 11-19 represents all blacks.
Given a pawn at (x,y) print all possible moves. Assume whites are index 0
and blacks are at index 7.
请教这个题怎么做啊, 不了解国际象棋的规则. 这里1-9代表白色什么意思啊, 白方有
16个6种棋子, 不知道这个大小是9的取值范围怎么理解. 还有移动卒需要考虑后果吗,
比如卒子被吃掉之类的. 看的稀里糊涂的. |
|
d*******y
发帖数: 27 | 29 每个元素是unsigned并且取值范围一定小于数组的长度吗？ |
|
r**a
发帖数: 31 | 30 你的方法实现起来简单，当m和n有一个很小时非常实用
更通用的做法是解一个线性方程组(mod 2意义下的)，一共有m*n个方程和m*n个未知数
，每个未知数表示这个灯泡是否需要变化，每个方程表示一个灯泡的情况。举例来说，
设2*2的灯泡的情况是
V00 V01
V10 V11
这里Vij取值为0或1，表示灯泡一开始亮或灭。有方程组
X00 + X01 + X10 = V00
X00 + X01 + X11 = V01
X00 + X10 + X11 = V10
X01 + X10 + X11 = V11
在mod 2意义下解这个方程组就可以了。用直接的高斯消元法，复杂度是O((m*n)^3)。
因为这里方程组的系数非常有规律，实际上好像有更快的做法。 |
|
l*n
发帖数: 529 | 31 好像明白你的意思，是在利用字符只有10这一点吗？只算小写字母有26个，每个需要5
个bit，10个数一共是50个bit，比64要小。这样long的取值能比10个小写字母的范围大
。但是一旦加入数字或者大写字母就还是会有collision了。
如果是你说的256为底，需要8个bit，直接对应10字符的话，需要一共80bit，超过long
的64了吧？longlong 是128bit么？那的确是一个longlong一个串了。
unordered_ |
|
x*******9
发帖数: 138 | 32 数组长度为N，把整个数组分为K段。这里取 K=sqrt(N)。
一段子数组我们用[st, end]来表示。
我们要统计每段子数组[st...x]的取值。
例如，[1, 2, 3]。sum([1]) = 1, sum([1, 2]) = 3, sum([1, 2, 3]) = 6。 然后排
序累加，使得类似“这一段子数组在和大于3有多少个”的Query的时间复杂度为O(log(
K))。
然后遍历数组，通过预处理好的子数组序列进行计算。
预计时间复杂度为O(n * sqrt(n) * log(n))。
比O(n^2)要好一点。不过比较难写。。。=。= |
|
a********m
发帖数: 15480 | 33 是。俺是说没有branching开销。虚函数开销在多一次取值，主要效率问题是在cache。 |
|
z***y
发帖数: 73 | 34 祝福lz！
1.相当于每次产生一个bit，运行k次，保证2^k >= n，如果超过n就重新运算，否则就
返回；
2.可以用一个stack吧，碰到*/操作立马计算，完了以后再处理一下剩下的+ -；
3.用hash table吧。如果对象都只是一个字符，那么char table[256]即可。遍历相等
的串，把相等的元素设置成同样的值。然后遍历不等的串，取值出来比较即可。 |
|
l*******0
发帖数: 95 | 35 我上面的solution有个假设: A中元素的取值范围是非负的，也就是大于或者等于0. 如
果感兴趣，你可以试着自己改一下程序，让它能够handle包括负数的情况。
另外，这个题现场不会做也没啥，的确要花些时间想想。 |
|
b*********e
发帖数: 26 | 36 int f[n][100]
第一维是数组里的数，第二维是那个数的取值，f[i][j]是第i个数取j(0
的cost
转移方程很恶心如果k很大的话
如果k==1的话
f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i-1][j+1])+ |A[i]-j|
最后输出f[N-1][]里最小的元素即可 |
|
r*g
发帖数: 186 | 37
觉得再咋地也得O(n)吧
任意数组求是否重复, 基于比较的最优复杂度是O(nlog(n))
这里有了取值限制 在[1, n] 可以优化到O(n) |
|
I******g
发帖数: 38 | 38 来自主题: JobHunting版 - h1b状态 这两个**打的还真是让人好猜啊。。。这两位基本上是固定的啊。。。
一位是固定的，另一位取值范围是3选一。。。
：） |
|
c*****m
发帖数: 271 | 39 第四题的题意是：n+1个数的取值范围是1到n，但是其中只有一个重复的数字，且这个
数字可以重复多次么？如果是这样的话，给定的二分法不行吧。
2 |
|
d*******l
发帖数: 338 | 40 数组有n个元素的话，m可能的取值只能是0到n，把空间划分成n+2个区间统计一下原数
组落在各个区间的元素个数就能依次尝试了 |
|
c***G
发帖数: 88 | 41
满足
建议你可以先想想++i;到底是怎么做的，我觉得至少有以下几步：
1. 从mem取值到寄存器
2. 在寄存器上进行计算
3. 寄存器的值写回到mem。
如果我没记错的话，G问的那个sequence是可能的。
我觉得两道题思路差不多，可是G这道复杂太多了。
满足 |
|
D***0
发帖数: 138 | 42 【 以下文字转载自 Java 讨论区 】
发信人: DK100 (dark knight), 信区: Java
标 题: java多线程问题请教
发信站: BBS 未名空间站 (Tue Jan 5 12:34:03 2016, 美东)
操作比较简单，就是有个cache，当cache miss时从数据库取值，同时更新cache。这里
的key是由两部分组成的，一个int和一个interface，函数输入是这两个。问题是在多
线程下如何synchronize。 我想是用concurrentHashMap当cache
Type是一个interface
一开始想用下面这个Key来做map的key，但是后来觉得不对，这也是想请教的一个地方
class Key {
public int a;
public Type t;
public Key(int a, Type t){...}
public int hashCode() {...}
public boolean equals(Key k) {... }
}
List f(int a, Type t) {
... 阅读全帖 |
|
w*******d
发帖数: 59 | 43 这似乎不是一个什么很准确的概率分布，简单的话可以近似成negative binomial
distribution，准确一些其实是markov chain的hitting time，相当于一些geometric
distribution的和。
假如我们把[0,1]区间等分成100个小区间，然后假设雨点一定是准确落到某个小区间里
【来近似均匀分布】，那么每个小区间是否被雨点落到就是一个bernoulli分布，概率
是0.01，问题就是在雨点砸到全部100个小区间之前我们需要砸多少次。假如每个小区
间是否被砸到是独立的，那么这就是一个negative binomial，不过这个假设是错的，
而且近似的结果非常的loose，期望在几千左右。
换一个角度，我们考虑被覆盖区域长度的变化。按照近似这个长度只能取值0, 0.01, 0
.02, ..., 1，而且每次都只能从前一个值往后一个值跳跃。那么我们的问题是需要多
少次，这个markov chain可以移动到1。假设我们当前在x，也就是说有x的长度已经被
覆盖了，那么下一次雨点落下来不增加覆盖长度的概率就是x，而增加0.01的概率是1 -
x... 阅读全帖 |
|
t******i
发帖数: 483 | 44 1.一个计数器Counter，取值0-50
2.Counter每1/50秒自增1，如果超过50则保持50不变
3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
大概就是这么个意思。欢迎批评指正。 |
|
发帖数: 1 | 45 已经很久远了, 记不大清了
1. 给一个int流, 取值在0-1000, 求running中位数
2. Trie树, 通配符匹配
3. Design Facebook 图片相关的, 包含CDN, haystack
4. 倒排索引 |
|
|
k****r
发帖数: 807 | 47 不知为什么， 感觉这种情况似乎用condition更合适：
class BoundedBuffer {
final Lock lock = new ReentrantLock();//锁对象
final Condition notFull = lock.newCondition();//写线程条件
final Condition notEmpty = lock.newCondition();//读线程条件
final Object[] items = new Object[100];//缓存队列
int putptr/*写索引*/, takeptr/*读索引*/, count/*队列中存在的数据个数*/;
public void put(Object x) throws InterruptedException {
lock.lock();
try {
while (count == items.length)//如果队列满了
notFull.await();//... 阅读全帖 |
|
y*******w
发帖数: 5917 | 48 这是另外一个好笑的东西，其取值非常可笑，好像一定是要保房价的一半，我说我家的
破玩意儿全部加起来也没几个钱，丫说这个是捆绑的，无法把它去掉的。
搞得我那几年整天想像自己家房子烧掉我大发一笔。 |
|
y**s
发帖数: 323 | 49 OB说已经是上限了 1cm~1.5cm就是轻度脑室扩张了 可是我看做B超测量的时候取值也有
点偏差 只要医生取点的时候稍微宽泛一点就超1cm啦...
下周去复查 版上的姐妹有遇到过这样的问题吗?
现在挺担心宝宝的 心情一直不太好 到底什么原因造成的呢?
查了些资料 看的反而心情更糟 有没有妈妈和我类似情况但宝宝很健康完全没问题的? |
|
c*******u
发帖数: 12899 | 50 ☆─────────────────────────────────────☆
yxrs (yxrs) 于 (Sat Aug 4 12:18:24 2012, 美东) 提到:
OB说已经是上限了 1cm~1.5cm就是轻度脑室扩张了 可是我看做B超测量的时候取值也有
点偏差 只要医生取点的时候稍微宽泛一点就超1cm啦...
下周去复查 版上的姐妹有遇到过这样的问题吗?
现在挺担心宝宝的 心情一直不太好 到底什么原因造成的呢?
查了些资料 看的反而心情更糟 有没有妈妈和我类似情况但宝宝很健康完全没问题的?
☆─────────────────────────────────────☆
sbalaxigense (美丽人生) 于 (Sat Aug 4 12:21:51 2012, 美东) 提到:
不太懂，bless宝宝。
☆─────────────────────────────────────☆
yxrs (yxrs) 于 (Sat Aug 4 12:48:28 2012, 美东) 提到:
谢谢~~难道我这个真的是小概率?更担心了...哭
☆───... 阅读全帖 |
|
