y******5
发帖数: 43 | 1 3. bitmap不能处理repeated integer吧。
{1,2,3 |
|
s*********b
发帖数: 815 | 2 巧妙与否要看你的要求哈。如果对空间和预处理没有要求，还是有快速的解法的。
1. 预处理。把棋盘所有状态都找出来。这样查输赢就是O(1)操作了。状态可以用
一个hash值或者bitmap表示，这样要处理的状态占用的空间少一点。
2. 对每一个玩家，每一行，每一列，每一对角线都创建一个计数器。然后每个玩家
再加一“超级”计数器。如果玩家在[x,y]放一棋子，那x那一行的计数器加一，y那一列
的计数器加一。如果x==y或者x==n-y，那么对应对角线的计数器加一。每次加一
后同“超级”计数器比较。如果比超级计数器的值大，那么超级计数器加一。最后只需
要看超级计数器的值是不是N。如果是，那么就算拥有这个计数器的玩家赢了。当然
不要超级计数器也行，只不过这样你就得查询所有的行、列、对角线计数器，于是
复杂度变成O(N)。不过这也比O(N^2)好。 |
|
|
|
d*******l
发帖数: 338 | 5 这是哪个题啊，好象跟这个帖子讨论的不太一样？倒是跟我以前见过的有点像。。
这个帖子的题我觉得bitmap方法就很好了 |
|
f****4
发帖数: 1359 | 6 那个idea只是在连续整数差一个，两个的情况下才比较合适
这里套的话不合适：题目没说char[]放的东西连续
并且要求in-place，那么用bitmap应该也是不合要求的（？？）
如果能放进内存，可以用变形的quicksort来做
Partition好之后
a[0]x a[i+2]>x ..
. a[j]>x
交换 a[j]<=>a[i]; a[j-1]<=>a[i-1]...a[j-k+2]<=>a[i-k+2]
设置j=j-k+1 (重复的元素被交换到了数组尾部，并且不再参与下一次的递归)
继续
最后得到的数组即为无重复数组+尾部所有的重复元素
将重复元素清空即可 |
|
R***i
发帖数: 78 | 7 公司名就不说了
题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
我给了2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of
integers， time O(n), space O(n)。 但面试的人告诉我都不是最优解，有time O(n)
, constant space的解。。。现在都没想明白，大家集思广益吧 |
|
h**********d
发帖数: 4313 | 8 一个bitmap/matrix，往里填色，见career cup |
|
r****l
发帖数: 28 | 9
you mean use one of the element space as a bitmap?
I think it'll work, and we can also reset that element after find out all
missing numbers, thus the array will
remain unchanged.
Cool. |
|
g***s
发帖数: 3811 | 10 Use bitmap as a simple hash map |
|
|
i**********e
发帖数: 1145 | 12 Please note that it's not enough to return only the maximum depth. The
question clearly specifies to return the longest path.
Using DFS is the correct answer. BFS can work too, but requires either:
1) Parent pointer in each node to get the longest path from leaf up to the
root.
2) An extra data structure to record the path from root to leaf, which is
also pushed into the queue.
DFS has a simple solution:
void getLongestPathDFS(Node *root, vector &path,
vector &longestPath) {
if... 阅读全帖 |
|
f**********t
发帖数: 1001 | 13 补充一下。刚才是假设file1非常非常大。如果再小点，可以用hash+bitmap。 |
|
i**********e
发帖数: 1145 | 14 Use bitmap?
Assuming if there's only characters from 'a' - 'z' lowercase, then one 32
bit integer is enough. |
|
y**********u
发帖数: 6366 | 15 bitmap require extra memory space...
normally I guess string could be ascii ...
a |
|
|
i**********e
发帖数: 1145 | 17 1) array trie definition
struct Trie {
// pointer to its 26 children.
// children[i] == NULL means that particular child doesn't exist.
Trie *children[26];
bool end; // marker to indicate if current letter is end of a word.
};
2) linked list trie definition
struct Trie {
// pointer to its first child.
Trie *son;
// pointer to its sibling node.
Trie *next;
};
For 1) -- array trie definition, the insert(const char *s) function is easy
to write. For 2), is a little more tricky to writ... 阅读全帖 |
|
|
r*******g
发帖数: 1335 | 19 Hi, bitmap 的话，难道不是需要43000000位的内存空间，貌似也挺大的。 |
|
r*******g
发帖数: 1335 | 20 这个和binary search什么关系，你们貌似说的两种方法，直接bitmap确实有内存问题。
你貌似在说，每次总是找多的那一半，对多的那一半，再拆分，再找，这样得到的数就
是重复的。貌似这样确实可以。这个是binary search？
我现在和找missing integer的方法搞混了，那个也是这样做，但是每次找少的一半，
而且找到一定程度了就直接对剩下的排序去找missing，不知道我理解对了没有 |
|
j*****j
发帖数: 201 | 21 为什么bitmap空间上更好？Custom ID可能非常大吧？
ID
concern. |
|
s*********6
发帖数: 20 | 22 第一道题目应该还要考虑内存使用的问题。
电话号码如果是10位数，用trie表示，可能需要多到9^10字节的空间。
用push/pop stack，需要的空间更大。
如果限制内存1G或者4G，内存不一定够。
感觉用bitmap比较好。 |
|
s*********6
发帖数: 20 | 23 第一道题目应该还要考虑内存使用的问题。
电话号码如果是10位数，用trie表示，可能需要多到9^10字节的空间。
用push/pop stack，需要的空间更大。
如果限制内存1G或者4G，内存不一定够。
感觉用bitmap比较好。 |
|
f*******t
发帖数: 7549 | 24 如果只是节省内存的话，用bitmap存所有质数 |
|
O******i
发帖数: 269 | 25 或者Bitmap, external sort, map-reduce之类的题？ |
|
j***y
发帖数: 2074 | 26 来自主题: JobHunting版 - 问个算法题
什么是bitmap啊？没听过这样的数据结构？可否稍微详细介绍一些？
我的想法是如果是单个letter的case，打算用类似下面的方法解决：
int c[26] = {0};
char *pIn = strIn;
while (*pIn != 0 && *pIn != ' ') {
++c[*pIn];
++pIn;
}
/* how to sort the array c[26] and remember the original index? */
排序之后怎样知道某个整数对应的是哪个character的count呢？这个还没有想好。请指
教。
如果不是单个letter的case，准备用map解决，可行吗？ |
|
b*****c
发帖数: 1103 | 27 来自主题: JobHunting版 - 问个算法题 bitmap??
用map
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
map |
|
S**I
发帖数: 15689 | 28 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
l*****a
发帖数: 14598 | 29 looks like he want bitmap
1M=1024K=1024*1024byte=1024*1024*8 bit around 10M bits
000
mm
If |
|
b*****k
发帖数: 26 | 30
I told him the bitmap, he said no. |
|
i**********e
发帖数: 1145 | 31 Since in the IntegerSet there could not be duplicates, and 10,000,000 unique
numbers sound like a good candidate for bitmap.
You can represent 8 numbers in 1 byte, with each bit representing if a
number exist in the set or not. Then you can use bit manipulation to extract
each number. Therefore, 10,000,000 requires 1,250,000 bytes =~ 1.19 MB.
I couldn't see why this wouldn't satisfy the constraint, as each operation
is O(1), and it also scales well to the worst case.
The interviewer did hint on ... 阅读全帖 |
|
b***u
发帖数: 12010 | 32 我会弄个bitmap，四位digit有10k，用10k/32+1个unsigned int。每读一个digit把后
四位查下出现没。第几位出现就需要多少时间。 |
|
i**********e
发帖数: 1145 | 33 你思路应该没错，唯一能想到的一个优化就是如 biggu 所说的，用 bitmap 来储存当
hash使用，稍微节省空间一些，但复杂度基本不变。有可能是你说 O(n)，但是没解释
什么是 n 呢？这题你也不知道到何时才能找到重复那四个decimal？除非你能数学证明
出来。 |
|
d********w
发帖数: 363 | 34 coding:
- JOIN: nested join, hash join, sort-merge join
- Number: Fibonacci, prime，随机取文件某一行
- String: strstr, wordcount
- Tree: height, lca, balance tree
- Heap: 查找最大的k个数
- DP: 最大连续子串和
- array: find a key in rotated array, 去除重复字符
- linkedlist: 是否有环，插入结点，删除重复结点
- 递归回溯：变化很多，这方面需要大量练习
知识性：
多线程，mutex/semaphore
java GC
C++ virtual, smart pointer
regex使用
数据库：知道btree, 索引
search engine: 倒排表,拉链，稀疏索引，空间向量模型，tf*idf,
large scale data: hash, consistent hash, bloom filter, bitmap, 外排序，
partition
分布式：CAP理论，gos... 阅读全帖 |
|
d********w
发帖数: 363 | 35 coding:
- JOIN: nested join, hash join, sort-merge join
- Number: Fibonacci, prime，随机取文件某一行
- String: strstr, wordcount
- Tree: height, lca, balance tree
- Heap: 查找最大的k个数
- DP: 最大连续子串和
- array: find a key in rotated array, 去除重复字符
- linkedlist: 是否有环，插入结点，删除重复结点
- 递归回溯：变化很多，这方面需要大量练习
知识性：
多线程，mutex/semaphore
java GC
C++ virtual, smart pointer
regex使用
数据库：知道btree, 索引
search engine: 倒排表,拉链，稀疏索引，空间向量模型，tf*idf,
large scale data: hash, consistent hash, bloom filter, bitmap, 外排序，
partition
分布式：CAP理论，gos... 阅读全帖 |
|
G**********s
发帖数: 70 | 36 此题是 given int array in range [1,N]，find missing integer的变形吧，
in my opinion
扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
gives us O(n+k).
不知道这样做是否妥当和最有呢 |
|
G**********s
发帖数: 70 | 37 此题是 given int array in range [1,N]，find missing integer的变形吧，
in my opinion
扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
gives us O(n+k).
不知道这样做是否妥当和最有呢 |
|
g***i
发帖数: 4272 | 38 两个电话面试，紧挨着，两小时完成的，还挺简单的
1. 两个array 的intersection
（用了个set,直接七八行写完，说了个ok就过了）
2. BST inorder next node
（careercup原题，可惜忘了，写了好久。还有一处有个bug，问我&&逻辑先后，short
circuit问题）
---
1. 10^9个star，亮度为double类型，找出前一千个最亮的
（我一开始说用heap，后来发现不好用，就改了bst，size 1000的，超了就比较最小的
，删除最小的，再插入）
2. 一个动态规划的题目，好像是intro to design & analysis of algorithm上的课后题
3. monochrome bitmap，找出最大的白色矩形。
（卡这了，brutal force也不太会），求教这个咋做 |
|
H***e
发帖数: 476 | 39 "3. monochrome bitmap，找出最大的白色矩形。
（卡这了，brutal force也不太会），求教这个咋做"
这道题电话面试德话，是不是有点过啊？
没见过的话，不知道怎么想出那个答案。。
short |
|
|
w****o
发帖数: 2260 | 41 这个不太好，占用了太多的空间，因为一个 bool 占用的空间和一个 integer是一样的
，通常也是4bytes.就是说一个bool根本就不是一个bit. |
|
R****i
发帖数: 91 | 42 plz try google and check stl |
|
c***7
发帖数: 315 | 43 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
， time O(n), space O(n)。 求time O(n), constant space的解。。。
2.Given P machines, each containing an array of N elements, find the medium
of the array resulted by concatenating all the arrays on the machines. You
cannot move data across machines. |
|
|
|
i*********7
发帖数: 348 | 46 能用额外buffer的话，就建hashtable。其实用Bitmap就够了。。。 |
|
w****x
发帖数: 2483 | 47 "他检查后觉得没有问题，然后问我如果字符串非常长的话怎么办，"
不就是bitmap solution吗, 再长还不是一样算??? 没理解 |
|
|
z*********8
发帖数: 2070 | 49 要统计次数， 而不仅仅是出现与否， bitmap不行吗？ |
|
p*****2
发帖数: 21240 | 50
你这个东西是bitmap吗？长度是不是要＋1呢？ |
|
