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, 美东) 提到:
谢谢~~难道我这个真的是小概率?更担心了...哭
☆───... 阅读全帖 |
|