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... 阅读全帖 |
|
