g***s
发帖数: 3811 | 1 after deleting 26 chars, use these space as a simple hashmap. |
|
|
c******t
发帖数: 391 | 3 So how do we efficiently delete the target letters without additional
storage? |
|
h*********n
发帖数: 11319 | 4 果然要always think of hash first... |
|
w**s
发帖数: 141 | 5 why deleting 26 chars??? Not really understanding... |
|
g**********y
发帖数: 14569 | 6 delete 26个char是什么意思？同不明白。 |
|
d*******l
发帖数: 338 | 7 我感觉这个问题可以用grass之前在另一个thread里提到的那个方法，就是
while(s[i] != s[s[i]-'a']) swap(s[i], s[s[i]]);
这里写的比较粗略，没考虑大写字母。相当于把每个字母换到对应的位置上，然后可以
作为hashmap来用。不过这需要string2长度至少是26，而且会破坏string2，不知道是
否符合要求。然后扫一遍string1就可以了。 |
|
i**********e
发帖数: 1145 | 8 我想就是利用两个前后指针扫描，然后首先可以用简单的 linear search 来寻找重复
的。直到后指针与前指针的距离为 26，那也意为着有 26 个连续的空位。这时候就把
后指针指向和之后的所有元素往前移 26位，然后利用最后的 26 空位来当 hash。
也就是 grass 所说的是从 string1 里删除了二十六个重复的字母之后，利用剩下的二十六
个空位来当作hash来用。
这是考虑到 string1 的长度非常长。但是有一个最坏情况就是万一很久都没碰上重复的字母怎么办？抑或是 string1 产生重复的个别字母不超过 string2 的长度？那这基本上就跟 worst case 一样，26*n 的比较次数，那还不如把 string2 排好序，然后做 binary search。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
M*****e
发帖数: 568 | 9
Depends the size of the Alphabet, and the length of the second string.
If the alphabet is small (e.g., English char), create a hash table for that
- O(size of alphabet * len_string1). If the second string is small, (e.g.,
1 char), brute force search on the first string - O(len_string1 * len_
string2). If both are large, sort the second string, and go over the first
string while binary look up each char in the sorted second string - O(lg(len
_string2) * (len_string2 + len_string1)). |
|
g***s
发帖数: 3811 | 10 I replied the 2 lou(who mentioned to use sort+binary search to delete
first) and i agreed. (if string2 is very small, scan could be faster
because of binary search overhead)
After enough chars(26 or 52 or 256) are deleted, we can compact it and
use the deleted space.
All we assume is that string1 is very large.
二十六
复的字母怎
么办？抑或是 string1 产生重复的个别字母不超过 string2 的长度？那这基本上就跟
worst
case 一样，26*n 的比较次数，那还不如把 string2 排好序，然后做 binary search。 |
|
s*****y
发帖数: 897 | 11 一个字符8bit，4个字符就有32个bit可以做bitmap hash 26个字符了，这样子可以吗
唯一的就是当第一个字符如果它的bitmap影射到第2个字符，那么在读第2个字符前就会
破坏了第2个字符。 |
|
f****4
发帖数: 1359 | 12 还有个办法是破坏string2，只要string2有>=4个char，就有32bits，每个bit代表一个
字母；遍历string2剩下字符然后设置string2前26bits。
用这26bits做hashmap，遍历string1
这样就避免了string1 move char
如果string2 size<4; 直接查找即可 |
|
m********l
发帖数: 4394 | 13 不能用XOR?
helloworld
^aaaaaaaaaa
delete any zero.
^aaaaaaaaaa
...
helloworld
^eeeeeeeeee
delete any zero.
^eeeeeeeeee |
|
d*******l
发帖数: 338 | 14 感觉有点南辕北辙。。相同的字母xor了确实会变成0，但不同的字母xor结果不就乱了
？除非不同的字母的对应的是全0，但这样意义很小，对效率好像也没什么帮助 |
|
m********l
发帖数: 4394 | 15
XOR两次
没仔细读.. 不准用新空间
不过他问题也没说好
output跟string1是同个空间吗?
helloworld 是要变成 hlloworl
多了个d |
|
m********l
发帖数: 4394 | 16 昨晚在外面想了个方法
用bit encoding.
比如说
0001 = a
0010 = b
0100 = c
1000 = d
0001 0000=e
0010 0000=f
...
用26-bit. (4 bytes)
然后
string2 = (1 <
int i=0;
while(string1[i])
{
if ((1 << (string1[i]-'a')) & string2 == 0) cout << string[i];
i++;
} |
|
f****4
发帖数: 1359 | 17 恩，用string2 做mapping比较方便 |
|
k*j
发帖数: 153 | 18 i think i was asked the same question long time ago when i interviewed with
them
my answer was like:
for two searches, you get something like the following, each is a link, and
they are in order.
search 1: ABCDEF
search 2 : FABEDG
and for each link in the search1, you find its position in search2, and then
calculate the absolute difference of two positions. for example, for link "A", it is
position 0 in search 1, and position 1 in search2. the diff is abs(1-0)=1.
another example, for link "F", i... 阅读全帖 |
|
a****f
发帖数: 944 | 19 【 以下文字转载自 Working 讨论区 】
发信人: abcdef (aa), 信区: Working
标 题: ！！急问： 新工作的开始日期能否推迟？
发信站: BBS 未名空间站 (Tue Jan 17 20:07:56 2012, 美东)
已经定下来是1/30开始，但是由于家庭的一些临时情况我想推迟到2/6开始。offer已经
发了并且我也签字了，offer上面写的是1/30开始。这种情况有没有可能推迟开始日期
？如果可能的话，应该是跟HR说还是跟我未来的老板说？我的工作室在一个研究所，博
士后。
谢谢！ |
|
j*******a
发帖数: 101 | 20 大家说说为何下面的代码输出是CBA?
const char * p = "ABCDEF";
printf("%c%c%c\n", *p, *(p++), *(p++)); |
|
w****x
发帖数: 2483 | 21
没仔细看你程序, 你试试数组就一个string: abcdef 找prefix "abc"能找到就成 |
|
l****p
发帖数: 397 | 22 这段regex的代码是假设必须从字符串的第一个字母开始区配吧，但题中好像没这么要
求。
比如regex("abcdef", "d-f")应该是true，但这个却是false |
|
w****x
发帖数: 2483 | 23 struct NODE
{
vector vecGUID;
NODE* nodes[256];
NODE() { memset(nodes, 0, sizeof(nodes)); }
};
void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
{
if (NULL == pNode)
return;
if (k <= 0)
{
vec = pNode->vecGUID;
return;
}
_inner_get_guid(pNode->nodes[*str], str+1, k-1, vec);
}
vector getGUID(const char* str, NODE* pRoot, int k)
{
vector vecRet;
if (NULL == pRoot || NULL == str || *str == 0 ... 阅读全帖 |
|
j*****y
发帖数: 1071 | 24 来自主题: JobHunting版 - BB 电面 感觉可以分三种大情况
abcdef
1. a, b, c 这组数字和 d , e, f这组数字没有相同的
2. 两组中有一个相同的
3. 两组中 三个数字都相同 |
|
G*******l
发帖数: 19 | 25 不一定要是null pointer，可以用0代表这个节点的data长度是0表示null（如果没有0
长度的value的话），如果有可以用-1，或者随便一个负数应该都行的。。
存到文件不一定是binary，举个例子：
abc
/ \
null abcdef
那在文件里就是 3abc06abcdef |
|
e***s
发帖数: 799 | 26 对不起，我找到反例了，我的做法不正确。
"abcdef" Dictionary： {"abcde","f","ab","cd","ef"}
正确应该返回 "abcde f", 但是下面代码会返回 "ab cd ef" (不是最少单词数）; |
|
b******7
发帖数: 92 | 27 G家问过这样一道位运算题：假设一文本文件中最多存在6种字符(假设就时abcdef)，请
对这些文件进行简单压缩
感觉bug free还是挺难的，当时写的code被找出好几个bug |
|
d*******3
发帖数: 58 | 28 @dingdang2012,你这个不对，LZ的题意是S中是否存在一个子串是T的一个permutation,
garphy的例子：
S串bacde T串cb，应该返回false,你的代码返回true了。
peking2 的两个hashmap+一个counter是正解，时间复杂度O(m+n)
我献丑贴下代码：
bool HasPermuateSubstr(string& S,string& T)
{
int n = S.length();
int m = T.length();
if( n < m || m <=0)return false;
vector findCount(256,0);
vector needCount(256,0);
for(int i = 0;i < m;i++)needCount[T[i]]++;
//initilize the window
int findLen=0;
for(int i = 0;i < m;i++)
{
findCount[S... 阅读全帖 |
|
s********f
发帖数: 510 | 29 如果密码是abcdef
那么以a开头的bucket应该是10个。以b开头的buckt应该是6个，以c开头的是3个，以d
开头的是1个。
如果abcd中间有相同，那么就会出现以a开头的是11个（abca)，13个(abad)， 14个(
abaa),16个(aacd)，17个(aaca),19个(aaad)或者20个(aaaa)
思路是比较清楚，不过算法还要想想。 |
|
w********s
发帖数: 1570 | 30 假设password=abcdef
那么每次给3位x,y,z的话，x只可能在{a,b,c}中，z只可能在{d,e,f}中，
那么根据随机给的可以得出{a,b,c}和{d,e,f}
为了确定顺序，a,b,c有6种排列，d,e,f有6种排列，总共36中可能
对每一种可能做一个bucket，那么每次检验这36个bucket，直到过滤剩下1个bucket，
那个就是password. |
|
w********s
发帖数: 1570 | 31 频率统计法
ABCDEF，每次triplet XYZ
记录X的频率，Y的频率，Z的频率
X可能包含了ABCD，A出现的频率是10/20,B:6/20,C:3/20,D:1/20
ABCD如果都相同，那么就是20
ABCD如果其中2个字母相同，就是16，13，11，9，7，4
3个字母相同，结果是19,14,10,17
都不相同就是10,6,3,1
注意10可能是abbb或者abcd，那么用Y的频率来判断哪种情况。
std::string triplet()
{
static std::string password = "google";
std::set digits;
while (digits.size() < 3)
{
int d = rand() % 6;
digits.insert(d);
}
std::string result;
for (std::set::const_iterator it = digits.begin(); it != digits.end
... 阅读全帖 |
|
w********s
发帖数: 1570 | 32 所有的组合都可以
比如
aaaaaa
abcdef
aabccd
aabbcc
... |
|
g****s
发帖数: 1755 | 33 我来一个不用统计学的Draft吧，只需要知道所有可能组合就可以推出原String：
比如google的所有可能组合一共是13种：{gge,gle,ole,ogl,goe,oge,gog,ool,ggl,oog
, gol,ooe,goo}，把这些组合都放到一个ArrayList里，然后call dfsDecode()就可以
逆推了。
private static void dfsDecode(String head, ArrayList setList,
ArrayList prosStrList) {
// TODO Auto-generated method stub
if(head.length()==6){
prosStrList.add(head);
return;
}
for(int i=0; i
if(head==""){
... 阅读全帖 |
|
m**********w
发帖数: 60 | 34 不一定要一样，比如 abcdefe 和 dcba 就是长度不一样，但连起来是palindorm |
|
b***p
发帖数: 700 | 35 这个行吗？
#!/usr/bin/python
class WordAbbr:
def __init__(self):
pass
def word_abbr(self, word, start, len_abbr):
if len(word) < start + len_abbr:
return False
return word[:start] + word[start+len_abbr:]
def solution(self, word, list_words):
word_len = len(word)
for i in range(word_len - 1):
len_abbr = word_len - i
for j in range(word_len + 1 - len_abbr):
word_abbr = self.word_abbr(word, j, len_abb... 阅读全帖 |
|
b***p
发帖数: 700 | 36 这个行吗？
#!/usr/bin/python
class WordAbbr:
def __init__(self):
pass
def word_abbr(self, word, start, len_abbr):
if len(word) < start + len_abbr:
return False
return word[:start] + word[start+len_abbr:]
def solution(self, word, list_words):
word_len = len(word)
for i in range(word_len - 1):
len_abbr = word_len - i
for j in range(word_len + 1 - len_abbr):
word_abbr = self.word_abbr(word, j, len_abb... 阅读全帖 |
|
y*****i
发帖数: 141 | 37 照着Maxthon的编码解法写了一个：
#include
#include
#include
#include
using namespace std;
bool bool_vec_none(const vector & vec) {
for(auto elem : vec) {
if (elem) {
return false;
}
}
return true;
}
bool bool_vec_all(const vector & vec) {
for(auto elem : vec) {
if (!elem) {
return false;
}
}
return true;
}
string word_abbreviation(string target, vector dict)
{
if (t... 阅读全帖 |
|
|
s*******t
发帖数: 8 | 39 请教各位前辈：
本人刚开始找工作，最近面试了一家生物公司，还算是行业内比较大的公司吧。Onsite
进行了一整天，早上从10点从Hiring Manager（这个位置的直接领导）那里开始聊（大
约半个小时），和组里的人聊。午饭之后，整个下午就是不间断地和不同人（ABCDEF）
谈话，一直到到四点多。
和每个人都单聊到最后一秒钟，有些感觉30min的时间不够用， 然后就被HM领着见下面
的一个人；内容很多，既有专业方向也有职业规划什么的，整个过程个人感觉尽力了，
也不知道效果怎么样。。。
最后临走前再回到HR那里wrap-up的时候，要我发给他3个推荐人联系方式。
本人第一次经历这样的面试。请教在公司里工作的话，Onsite之后 要推荐人一般意味
着什么啊？我的理解是至少没有当场悲剧。。。或者是HM对我下一步还有点兴趣？（这
应该是最后一步了，只有一次onsite）
恳请指教！ |
|
a****w
发帖数: 60 | 40 各位在FLG的PHD码农，有能力去阿里，八里，abcdef里出任副总裁吗？ |
|
m********l
发帖数: 791 | 41 小弟不才，试着回答...
tiny URL 在多machine/Server环境下，如果多个用户同时insert the same URL。如何
处理？谢谢。
不需要特殊处理，来一个long_url就给一个short_url去对应。一个长url对应多个短
url不会对系统和用户造成什么影响
比如两个用户同时insert www.mitbbs.com，生成的url如下：
abcdef -> www.mitbbs.com
123456 -> www.mitbbs.com
两个短url都指向www.mitbbs.com，无所谓
第二个问题：
1.感觉用不用自增ID和做不做consistent hashing没有关系，你用了自增ID也可以用
consistent hashing
2.你的做法可行，无非就是把数据存两份，一个是short2long的mapping，一个是
long2short的mapping。为什么是两份？因为你的mapping方式不能保证long_url和
short_url都在一台server上。
还有另外两个办法：
1) 只存short2long的mapping，来一个lo... 阅读全帖 |
|
a****f
发帖数: 944 | 42 【 以下文字转载自 Maryland 讨论区 】
发信人: abcdef (aa), 信区: Maryland
标 题: 提供古筝和课程，Baltimore
发信站: BBS 未名空间站 (Sun Jul 17 14:16:48 2011, 美东)
有人想学古筝么？我可以提供beginner lessons，价格可以协商。我的目的是以娱乐休
闲为主，收费是次要的。我曾经在学校的China Night上表演过古筝合奏，有兴趣的我
可以把录象的链接发给你。
我自己有一个古筝。你如果暂时没有琴的话，可以到我这里用我的琴来学。古筝非常容
易入门，不用多久你就可以像我一样登台表演，当然如果想表演高水平独奏的话还需要
下一些功夫，但也是可以做到的。
我刚刚从外周搬过来，也希望借此能够交一些朋友。
谢谢。 |
|
g*****0
发帖数: 2998 | 43 租房你难道不要交这些费用？房东活雷锋都把这些费用自己担着 不算在租金里？
要比较就是同样的房子比较 而不是用3000尺sfh的费用跟one bedroom的租金比
[在 abcdef (aa) 的大作中提到：]
:besides utilities, you also have property tax, homeowner insurance, etc.
:You also need to buy some tools to maintain the house, e.g., lawn mower
:in my opinion, owning a home is much more expensive than renting |
|
y****r
发帖数: 120 | 44 感谢各位好心人答复。从发帖到现在，就是时好时坏的。感觉还是胃酸搞的，因为白天
起床后就不太疼，睡觉时疼得厉害，还有饿了也会疼。昨天又急性发作了一下，因为我
也一直没用药想靠自己调节，昨天发现实在调节不过去了只好去看医生，医生用手检查
了上腹部，然后给开了两种药，都是以控制胃酸为主的。昨天吃上后顿时觉得舒服多了
。就是还胀气，总想打嗝，没怎么吃东西胃里就像沉了块石头。奇怪的是这么不舒服居
然还有食欲，有好吃的还需要强烈控制才不会吃超量。
abcdef:
我就是爱暴饮暴食，一去PARTY吃饭就容易吃撑。这两天就小心翼翼，再好吃的都流流
口水而已，不多吃。你可真够能忍的，那么难受了还不做胃镜，我约了下周的胃镜，还
是比较怕死啊。。希望没大事吧，好紧张。。
aohmd：
谢谢啊，已经收藏了。 |
|
|
k**********f
发帖数: 61 | 46 补充一下coupon来源；
1.网上免费订的杂志，爸妈都订一份，不知怎么搞的一下在订了三份，都给送了，baby
talk， parents， parenting 都有。一般订免费杂志需要run 6周最后才能收到第一期
。
2.医生那里，OB每期杂志都会有很多copy的，每周去那里都看到一摞一摞的同一期杂志
。看到了就撕下来吧。：）
3. 这里 或者 ebay买。还是合算的。
趁过期前下了些单子，有些使用amazon coupon的经验，分享一下。
1.之前都是注册一个账户下一个单的，现在一个账户可以多次使用coupon了。
2.$2.00 off 都是pampers的diapers，有时要多刷两次才出来，只要加进当前账户，那
么只要是能适用的diapers就自动减2块。但只适用一箱。
3.$2.00 off 似乎一个账户只能用一次，如果想每个单都省2块那么就再注册一个账户。
3.YJ开头的20% off可以和subscribe使用 最多一单三箱。（如果手头只有YJ开头的，又
不想买coupon的，订3箱相当于半价）
4.YJ开头的20% off只适用一箱。
5.$10 off 只适用于... 阅读全帖 |
|
d*****a
发帖数: 3983 | 47 我学生的妈剖了六次，前面五个都是二子，老六是闺女，终于不生了。
因为他们家孩子名字是ABCDEF排下去的，我说怎么没有继续，
那孩子跟我说医生不让妈妈生了，就美国G了。：（ |
|
K**********i
发帖数: 22099 | 48 我说了，我是猜测。
你给咱说说真实情况？
那好几个OCEF，有个ABCDEF，还有个ACCEF，还有ABOCEF，我操我直接看晕了，你们这
慈善机构太多，名声臭了就随便换个ID，夫妻店接着开，我一个没文化的哪里分辨得出
来啊？
再说，为啥不帮美国的华人儿童，而舍近求远去国内帮？ |
|
h*****s
发帖数: 1654 | 49 你是ABCDEF前员工还是OCEF前员工？
现在在哪个团伙高就？也可以和气龙一样，过来宣传宣传，吃吃人血馒头的人的人血馒头 |
|
h*****s
发帖数: 1654 | 50 你那合集的合集里面，都不止十个帖子，我真看不到
外加不会是把我的雄文拆散了，逐条批？
磊落的做法，应该是和你的一样，把合集链接直接放上
看你的手段，为人真不怎么地。和以前一样，真替OCEF或是ABCDEF着急 |
|
