I**A 发帖数: 2345 | 1 agree with bitmap..
how to do it with hash? |
|
x****k 发帖数: 2932 | 2 bitmap is a hash without conflict. |
|
d**e 发帖数: 6098 | 3 应该是的。
第一个loop reset bitmap为0
第二个set 对应位置为1
第三个就输出
系数为常数3,算是O(n)吧。 |
|
h**e 发帖数: 13 | 4 输出的时候要遍历整个bitmap (128MB个integer), size大于n,能算作O(n)吗?
迷惑中。。。 |
|
f*********5 发帖数: 576 | 5 can below be considered as O(1) space?
char array or bitmap which can support 256 different situations? |
|
h**k 发帖数: 3368 | 6 时间复杂度的分析不对吧。
所有可能的pair就有O(n^2),难道不需要检查所有的pair?
两个单词的bitmap做 and 操作,虽然很快,也不是O(1),而是O(m)啊
i
corresp
of
The
fo |
|
p********7 发帖数: 549 | 7 bitmap 就可以了,都不用记录次数,2个bit就表示一个整数,0表示没有,1表示出现
一次,多余一次就是2了。
遍历一次之后再遍历第二次,第一个次数是1的就是答案 |
|
v********w 发帖数: 136 | 8 Given a[n]
int *p=&a[n-1];
hashtable(or bitmap) ht;
for i=n-2:-1:0
if ht.contians(a[i])
{if (a[i]==*p) p=0;}
else {p=&a[i];ht.add(a[i]);}
if (p) return *p
else noelementIndicator |
|
A*********r 发帖数: 564 | 9 第一章第二章其实就是那么几道算法,居然旁证博引搞出洋洋洒洒好几页。
举的例子或者某些习题都貌似好老的样子,好不容易撑到第四章了,实在是看不下去了
,眼皮开始打架。。这个行文风格是太学术还是太艺术,怎么理解起来这么费劲,跟
programming interviews exposed相差真远,真的不是题或算法有多难,主要是*****
(可能我英语修炼得还不够?)。。
还是去做题比较有趣,而且不犯困。。
我觉得稍微提炼一下,他的前两章可以这样总结:
(如果我有时间,觉得搞一个programming pearl的精简版,适合没有大量时间去啃这
本古书的人,是不是已经有人这么做了?)
1. Sort given n integers in the range 1..m (n<=m), with each integer appear
at most once.
k-pass algorithm: if the memory is limited, process the maximum inputs
during each pass.
bitmap representation( the in |
|
p********7 发帖数: 549 | 10 先用1bit bitmap,0表示没出现,1表示出现过1次或者以上
然后再根据上面的结果创建一个hashtable表格,里面只包括了出现了1次或者1次以上的数字,这样这个hashtable的大小会小很多。
最后就是一个counting的过程 |
|
f****g 发帖数: 313 | 11 That's a very good solution too: use bitmap to determine the existence of
each
element, and then build a hashtable to count.
上的数字,这样这
个hashtable的大小会小很多。 |
|
k***g 发帖数: 58 | 12 不知道这个bitmap有什么用,原来数组中的数,出现次数肯定大于等于1,跟直接扫描
数组有区别?
上的数字,这
样这个hashtable的大小会小很多。 |
|
g*****e 发帖数: 282 | 13 这个bitmap开销很大。2^32 bits。建ht的过程又要读一遍。这个ht能直接count,还是
类似bucket sort要来好几轮?
我觉得还是类似bucket sort的思路好,每次2^8个buckets,最坏的情况全部数字读4遍
。从space和time的cost均衡一些。
但是我觉得tree不是更好,类似Huffman coding,每个node带一个counter? |
|
K******g 发帖数: 1870 | 14 感觉twitter的面试比较难,二面派了两个人同时面,就像一面一样,反复纠缠细节,使劲的追问那种,弄得我脑子很乱。
面试是上周进行的,基本的东西不说了,整个面试中真正的题目就是下面这道,由于没有答好,面试fail掉了,郁闷了好几天。
a collection of integer,设计data structure,支持delete, insert, getRandom三个操作,尽量做到最优。
我先提出来BST,复杂度分别是O(logn),O(logn),O(n),然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
我就说hashtable,他们就问怎么实现,还说getRandom的复杂度太高了,如果随机产生一个整数,很有可能那个整数在这个collection里不存在,我说那就再产生一个,知道找到为止,面试的人不满意。
然后我还说了bitmap,仍然不满意。中间纠缠了很久,还被问到collection里的整数的range很大,该怎么办之类的。
最后那个面试的人提醒我,考虑hash function。
其实面试的人的最终要求就是三个操作的复杂度都是O(1)... 阅读全帖 |
|
K******g 发帖数: 1870 | 15 感觉twitter的面试比较难,二面派了两个人同时面,就像一面一样,反复纠缠细节,使劲的追问那种,弄得我脑子很乱。
面试是上周进行的,基本的东西不说了,整个面试中真正的题目就是下面这道,由于没有答好,面试fail掉了,郁闷了好几天。
a collection of integer,设计data structure,支持delete, insert, getRandom三个操作,尽量做到最优。
我先提出来BST,复杂度分别是O(logn),O(logn),O(n),然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
我就说hashtable,他们就问怎么实现,还说getRandom的复杂度太高了,如果随机产生一个整数,很有可能那个整数在这个collection里不存在,我说那就再产生一个,知道找到为止,面试的人不满意。
然后我还说了bitmap,仍然不满意。中间纠缠了很久,还被问到collection里的整数的range很大,该怎么办之类的。
最后那个面试的人提醒我,考虑hash function。
其实面试的人的最终要求就是三个操作的复杂度都是O(1)... 阅读全帖 |
|
a********m 发帖数: 15480 | 16 随机数看能不能碰上还有bitmap确实不是好方法。 |
|
x****k 发帖数: 2932 | 17 My 2 cents
用bitmap,每个数占用1bit,0表示没出现或者出现偶数次,1表示奇数次。
O(n) time complexity |
|
l*******o 发帖数: 791 | 18 但是Bitmap到底要申请多大的空间才能合适呢?
如果input是[1,1000000,1000001,10000002,...]怎么办呢?
我觉得还是用map好一点map.规避了申请空间问题上的麻烦,这样好么? |
|
l****i 发帖数: 396 | 19 这个数组里元素的值有范围么?
有的话,我觉得用bitmap。
没有的话,就不知道了。。。等解答 |
|
P********l 发帖数: 452 | 20 We cannot avoid bookmarking the path when the we find a local maximum path.
But we can use bit map to keep track the path rather than using vector of
pointers. The bitmap can be as simple as a long integer, 0 is for left child
and 1 is for right child. The current depth needs to be saved in this case.
traversing the entire tree beforehand.
path |
|
s*****n 发帖数: 5488 | 21 你的brute force是啥。用个bitmap.如果有就bit[1] = 1,otherwise, bit[i] = 0
这个几乎最快了吧。 |
|
r*******l 发帖数: 511 | 22 UTF8解码器
线段overlap
死锁机制
fair streaming sample
最不好的是,忘记可以用bitmap记录sparse data,选择了hashtable.显然不是她想要的
虽然我也是骑驴找马,家里也不等米下锅.还是觉得伤心.
一直抱着哭闹的娃儿复习看书来着.唉.累啊... |
|
s******n 发帖数: 21 | 23 上周二面的onsite, 礼拜五电话被拒, 郁闷了一天。 刚刚看到flydog的帖子, 感觉才
算好些。 从版上受益良多, 现在将整理的面经发一下吧
Phone1:
Behavioral: Your biggest challenge, do you know our product?
Tech: 经典的html里找email的题 (using regex)
找anagram
Deck shuffle algorithm
Two stacks for a queue
Phone2:
N-way merge和时间复杂度 (n-way 和 2-way的比较)
手机输入提示功能 (trie)
两个phone都不难 很快拿到onsite 同时面两个组 onsite发现 A组全是白人 B组全是阿
三 结果被阿三给放倒了...
Onsite1 - 老美 A组manager: 问了问profile, 给了一个oop design的问题 不是常见的
电梯或家具题, 完全是他们所做项目的设计. 这题回答的一般, 最初给的答案不是他想
要的。。。... 阅读全帖 |
|
f****g 发帖数: 313 | 24 电话面试
1st:
1. 讨论我的博士研究项目
2. 如果SNMP agent不能获取数据,或者获取的数据不符合预期,如何诊断该问题?
3。我做过的最有挑战的项目是什么?
4。用邮件写代码,然后讨论我写的代码:
unsigned char * get(int sizeOfArray, int sizeOfRecord);
void release(unsigned char* ptr);
该函数可以实现:
unsigned char ** array = get(5, 10);
snprintf( array[0], 10, “hello world\n”);
snprintf( array[1], 10, “hello again\n”);
5。Java的基本概念
2nd
1。Apache的log file如何找访问量最大的网页 (用linux shell写个小script)
2。如果某网站访问量突然增加,可能是什么情况发生,如何确定各种情况(1。暂时的
Popularity激增 2. DDOS Attack 3. 网站添加新的内容)
3。Java基本概念+设计扑克牌的类
4。读re... 阅读全帖 |
|
f****g 发帖数: 313 | 25 If the data is distributed in a small range, then use bitmap. |
|
l*****v 发帖数: 498 | 26 infinite loop with a bitmap, after all task are outputed, terminate loop. |
|
l**********3 发帖数: 161 | 27 可不可以用一个4G个元素的counter数组,每个数组存一个long,每次access就累加这
个数组。如果query的时候,用min heap做一个linear search,找出n个最多的地址。
如果要优化search的话,用一个什么bitmap记录一段IP range,如果有访问的话,就是
1,否则是0,像个索引,这样可以跳过很多0。
不知道可不可行,大家讨论一下。 |
|
f****g 发帖数: 313 | 28 如果是32-bit的machine话, bitmap的话,需要(2^32 - 1)/2^5 = 2^27
如果available不多的话(相对不available的数),可以用hash table只存available
的数.
lz怎么答得阿:D |
|
l**o 发帖数: 356 | 29 我觉得这本书还是有些基础了再看得好。。。
我感觉书里比较有用的是heap,bitmap,anagram |
|
z****i 发帖数: 102 | 30 I think here we can use bitmap. Support it is one year, each hour is
indicated in a bit. We need 365*24/8 byptes. It is quite small.
Then scan A, set bits. Again, scan B, set conflicts if the bit is set
already.O(N) |
|
C*****n 发帖数: 1872 | 31 俺的答案:
1. bitmap
5. 3^6 - 3*(2^6) + 3
6. XOR 0xFFFFF
列组合了。。。 |
|
|
|
l*******o 发帖数: 791 | 34
我想要一些具体问题举例,比如排除duplicate或者计数之类的具体例子和详细用法,
多谢了 |
|
l*****a 发帖数: 14598 | 35 建议是,自己整理网上看到的相关题目
更容易加深自己的理解 |
|
|
g*******s 发帖数: 490 | 37 对于一个missing number的题目,用xor是最好解法
比如,1,2,3,5,missing number is 4
(0^1^2^3^4^5) ^ (1^2^3^5) = 4
xor 1-n的数,再xor array里面的数给你那个唯一的missing number
但是这招对于2个或以上missing number行不通
所以我们回到addition to find missing number的路上来
sum(1-n) - sum(elements in array) 也可以给你唯一的missing number (potential
overflow problem)
把那个方法generalize到>1个missing number
a1=sum(1-n) - sum(elements in array), a1是missing number的和
a2=sum(1 squre-n squre) - sum (elements squre in array), a2是missing number
的平方和
假设两个missing number是x, y
x+y=a1
x... 阅读全帖 |
|
a******7 发帖数: 106 | 38 can we use bitmap of true of false to indicate ith number is prime or not?
Then 10^7 number only takes 10^7 bits/ (8*1024*1024) = 1.19 MB space. |
|
i**9 发帖数: 351 | 39 头晕,找两个数要算98个平方先,弄个100的array/bitmap,走一遍不更快吗,感觉interviewer
是故意的,
你说东,他偏要给来个西嘿嘿
= |
|
g*******s 发帖数: 490 | 40 那样需要size of 100的bitmap,对方考虑是memory的问题,但是算平方很明显的问题
就是有可能会overflow。
interviewer |
|
g*********s 发帖数: 1782 | 41 能报一下offer吗?
另外两个方法写字符子集:一个递归,一个用bitmap? |
|
H******7 发帖数: 1728 | 42 这题目如何进行BITMAP?没想明白 请指点。
N
就可 |
|
f*********i 发帖数: 197 | 43 刚刚从西雅图回来,飞了整整一天,其实游戏那道题目,bitmap估计是最好的数据结构
了,和大家讨论的一致。
关键的问题是,如何判断是否可以放入board,我提出的方法是最naive的brute force
,就是单纯的比较,没有用DY,因为我当时实在想不起来了。看老印的意思,是可以用
DY来做的。 |
|
E*****R 发帖数: 9 | 44 第一个问题是给了一个很大的文
件(不能完全放入内存),其中每一行存一个整数,要求判断这个文件中的数有没有重
复。
这个可以用bitmap,10^7个整数之需要1.25M内存就可以了。这是Programming Pearls
第一章的例题。 |
|
|
i****c 发帖数: 102 | 46 可以加一个count,记录bitmap中1的个数。
不知道这种情况,是否有不需要额外内存的方法 |
|
x**y 发帖数: 1086 | 47 如果用bitmap的话,complexity应该是多少啊 |
|
C***y 发帖数: 2546 | 48 1. bitmap比较好,当然sort也可以做
这个有个问题就是,可能in-place remove 所用的两个指针所指的位置不能同时装入内
存,这个问题还没想好如何解决
2. 方法很多
a. 全部加起来,看缺多少,就是哪个数
b. 1xor2xor...10000,然后继续xor给的9999个数字
3.
不知道,太开放了,先说集中可能,再跟面试官交流,慢慢讨论吧
duplicate?
法得出缺了哪个数字?
code,不看GDB的trace和应用程序的log,该怎样快速诊断出可能的原因? |
|
C***y 发帖数: 2546 | 49 1.bitmap你可以看看programming pearls的第一章
2.两个话,可以解方程:
x+y+其他9998个数 = 1+...+10000
x^2+y^2+...=1^2+...+10000^2
子? |
|
z**********g 发帖数: 209 | 50 抛砖引玉一下
Some questions:
1. find PI using simulation
monte carlo simulation
2. design a cache (interface, implements different cache strategies)
LRU hashtable + double linked list
3. judge whether two integer arrays are the same after sorting, e.g., {1,2,3
} is the same as {1,3,2}
Any O(n) approach?
bitmap
what if the range of the integers in the arrays are huge?
hashtable
4.
if a tree can be converted to the other by only swaping the labels between s
ibling nodes, then the two trees are considere... 阅读全帖 |
|