f****4
发帖数: 1359 | 1 还有个办法是破坏string2，只要string2有>=4个char，就有32bits，每个bit代表一个
字母；遍历string2剩下字符然后设置string2前26bits。
用这26bits做hashmap，遍历string1
这样就避免了string1 move char
如果string2 size<4; 直接查找即可 |
|
m********l
发帖数: 4394 | 2 昨晚在外面想了个方法
用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++;
} |
|
g***s
发帖数: 3811 | 3 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。 |
|
d*******l
发帖数: 338 | 4 我感觉这个问题可以用grass之前在另一个thread里提到的那个方法，就是
while(s[i] != s[s[i]-'a']) swap(s[i], s[s[i]]);
这里写的比较粗略，没考虑大写字母。相当于把每个字母换到对应的位置上，然后可以
作为hashmap来用。不过这需要string2长度至少是26，而且会破坏string2，不知道是
否符合要求。然后扫一遍string1就可以了。 |
|
i**********e
发帖数: 1145 | 5 我想就是利用两个前后指针扫描，然后首先可以用简单的 linear search 来寻找重复
的。直到后指针与前指针的距离为 26，那也意为着有 26 个连续的空位。这时候就把
后指针指向和之后的所有元素往前移 26位，然后利用最后的 26 空位来当 hash。
也就是 grass 所说的是从 string1 里删除了二十六个重复的字母之后，利用剩下的二十六
个空位来当作hash来用。
这是考虑到 string1 的长度非常长。但是有一个最坏情况就是万一很久都没碰上重复的字母怎么办？抑或是 string1 产生重复的个别字母不超过 string2 的长度？那这基本上就跟 worst case 一样，26*n 的比较次数，那还不如把 string2 排好序，然后做 binary search。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
s*******n
发帖数: 344 | 6 面试题目：
有２个字符串，消除第一个字符串中第二个字符串包含的所有字母。
例如：
string1: helloworld
string2: abcdef
output: hlloworld
面试的时候我说了很笨的办法。因为不许allocate新的空间。
大家帮我说说最好的解法应该是什么？谢谢了 |
|
r*******y
发帖数: 1081 | 7 sort string2 first? then binary search ? |
|
M*****e
发帖数: 568 | 8
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)). |
|
|
S**I
发帖数: 15689 | 10 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
g****c
发帖数: 299 | 11 Basic String Handling Functions
All the string handling functions are prototyped in:
#include
The common functions are described below:
char *stpcpy (const char *dest,const char *src) -- Copy one string into
another.
int strcmp(const char *string1,const char *string2) - Compare string1 and
string2 to determine alphabetic order.
char *strcpy(const char *string1,const char *string2) -- Copy string2 to
stringl.
char *strerror(int errnum) -- Get error message corresponding to specified
er |
|
c***c
发帖数: 21374 | 12 【 以下文字转载自 Programming 讨论区 】
【 原文由 cynic 所发表 】
现在想做这么一个事情
有个个字符串
$string1 | $string2 | $string3 | $string4 | $string5
在$string2 $string3中想进行查找，将含有$keyword的的项目都筛选出来（精确匹配,
不区分字母大小写），保存在一个数组里面，然后逐行打印$string2和string3
如果能用加粗的黑体在打印时候着重表示$keyword，则最好不过了
这个字符串是在一个文本文件里面，都是统一的格式，很多行，因此需要从这个文本文件
（例如abc.txt)中读取以上的字符串信息
打印的时候如果是分页打印，一页打印100个，打完为之，最后一页有几行就打印几
行，应该怎么实现？
特别一点的是，$keyword可能在$string2 和$string3都会出现，为了避免重复，凡是
出现两次的均只按照一次处理，不打印两次
此外，可能有些字符串中 $string1 sting2 string3都完全相同，因此打印的时候
可能会有重复项目，现在希望将所有重复项目剔除 |
|
s*****r
发帖数: 773 | 13 问了三个问题, 直入主题, 简单明了
1 讲你的research, 5分钟就不听了
2 reverse的words in the string, 念code, 还好我写过, 直接念.
3 return true in case you can create String1 using characters from String2
else return false. You are allowed to use characters from String2 only the
number of times it appear.
这个我就说计算第二个string字母出现的次数.
接下来问,
如果是false-bias data set, 就是有一个data set, 里面的大部分string1 and
string2 都return false怎么优化, 如果是true-bias data set, 怎么优化?
第三题, 这题要我写程序发过去, 阿三面试, 很多地方听不懂, 可能挂了. |
|
y*********e
发帖数: 518 | 14 这个题目我能想到的就是Dynamic Programming了。
比较2个bag of chars，可以把它们转化成一种shorten form，which are sorted
alphabets with frequencies.
比如：
AABEDEF -> A2 B1 D1 E2 F1
FFACBDX -> A1 B1 C1 D1 X1 F2
Create, sort and copare two shorten forms would take O(N). Also, find
differences between two shorten forms would take O(logN)。
现在，把2个string各自转化成shorten form。如果是一样的，那么答案就已经出来了。
否则，从string1里面找不存在于string2的字符，把string1截取成若干个小的字符串
。同样地，从string2里面找不存在于string1的字符，把string2截成若干个小的字符
串。这样，我们就有2个字符串数组，比较每一个pair，（这是和本题同样的问题但是
规模小了一些） |
|
P**********c
发帖数: 3417 | 15 根据LZ说的，我觉得是这个意思。
先找到第一个substring A。 从string1的头开始扫，扫到所有的string2的character
都包含为止, count所有string2 character出现的次数。这个可能需要两个hash table
, 一个用来判断是否在string2, 一个用来数个数。
然后从A的头开始一个character一个character的减掉，如果character的count没有变
成0，update length和起始index, 如果某个character的count是0了，就从后面开始补
，一直补到它是1为止，update当前的end index。 |
|
s******0
发帖数: 19 | 16 serialize a binary tree的时候，如果想要serialize的字符恰好是sentinel怎么办？
更难的是，如果想要serialize的正好是分割符怎么办？按照leetcode上的解法，比如
用空格当分隔符，那假设我的key是一个string, 当我deserialize一个字符串：
"string1 string2"的时候我怎么能知道它是"string1" + " string2"还是"string1
" + "string2"呢？ |
|
b******g
发帖数: 1721 | 17 idea：
1.扫一遍string2，把不在string1的字符去掉
2.再扫一遍updated string2，看连起来的substring是否包含string1的所有字符。如
果是，计算长度。保留最短的
第二步有个optimization是一旦出现重复字符，自动取消先前那个，重新算substring。
复杂度是 O（n＊m）where n是string2的长度，m是string1的长度。可以用hash表来优
化判断是否出现。所以复杂度可以是O（n） |
|
H*M
发帖数: 1268 | 18 const char* st = "string1";
char str2[] = "string2"
What is the diff.?
我说是st不能改变"string1", string1是string literal放在data segment str2就可以
改变，string2是放在stack
如果写成char* str = "string1"是不对的.可是MS Studio居然可以通过编译。谁帮我澄
清下我理解有误吗？谢了。 |
|
s****n
发帖数: 1237 | 19 试了一下，如果
char string1[] = "ccc";
RemoveConsecutiveDuplicates(string1); 是可以的。
但是
char *string2 = "aaa";
RemoveConsecutiveDuplicates(string2); 是不行的，虽然complier不会报错，但是
run的时候在s[index]赋值的地方报 Access violation writing location 的错。
所以需要检验这个input到底是char * 还是char []。不过没有想出来怎么检验。 |
|
h*****g
发帖数: 312 | 20 careercup 书上的答案对吗？
Finding if two string are anagrams of each other.
我认为
1.先判断string1 和 string2 长度是否相等
2.然后把string1 的所有字符 用个int[256]的数组过一遍，
3.最后根据string2的字符串，从头到尾，相应地减去int[256]的值，如果遇到int[x]=
=0了就说明不match。
这几步就足够了吧？没必有想书上弄得那么complex吧？
如果我的想法不对，请帮忙给我举一个counterexample.
多谢~ |
|
p*****2
发帖数: 21240 | 21 刚被问到的，答的比较乱，用的recursion解决的。
两个string，string1是个regular string,
string2 contains one or more '*', each '*' represents 1 or more characters
write a function to find the pattern of string2 in string1, return index. |
|
b*******3
发帖数: 109 | 22 贴个java solution O(n m) :
public String minWindow (String originalString, String patternString)
{
List valuePairs = new ArrayList();
int shortestWindowLength = originalString.length();
int shortestHolderIndex = 0;
for (int i=0; i< originalString.length(); i++)
{
if (patternString.indexOf(originalString.charAt(i))>=0)
{
ValuePair valuePair = new ValuePair(originalSt... 阅读全帖 |
|
i***f
发帖数: 10 | 23 Hi,
Today when I try to replace a string in many files, first
I tried to use "sed -e s/STRING1/STRING2/g *" and only found
out the replaced pattern was output to STDOUT. At last I have
to write a script like this:
#/bin/sh
for fn in *
do {
sed -e s/STRING1/STRING2/g $fn > out.tmp
cp -f out.tmp $fn
}
done
rm -f out.tmp
Anyone can suggest to do the same function by using only one
line? |
|
s******0
发帖数: 13782 | 24 10个string 在哪？
是横的
string1 string2 .... string10
还是竖的？
string1
string2
string3
.
.
.
.
string10 |
|
s******0
发帖数: 13782 | 25 10个string 在哪？
是横的
string1 string2 .... string10
还是竖的？
string1
string2
string3
.
.
.
.
string10 |
|
j**z
发帖数: 109 | 26 1. Array, ArrayList and LinkedList pros and cons
2. Binary tree insert & delete a node
3. Think a compiler, what data structure to use to identify if a variable is
out of scope.
{ var a;
var b;
{
var c= 1+b;
}
c= a+b; <== error here, c is out of scope
}
4. string1 = "microsoft" string2="os"
remove every char in s2 from a1. So result is "micrft" |
|
a****u
发帖数: 3 | 27 Phone Interview的时候
1， 找list中间节点。
2， 找string中重复的第一个字符
3， 那个什么10个jar里面有marble，有一个是1.1gram其它都是1gram如何称量最少找出
来那个1。1gram的。
Onsite:
五个人。
组一:
第1人。找树某一节点高度。画园只有add和minus
第2人。integer数组中和最大的sub array。其他都聊天。
组二:
第一人。1，删除string1中所有再string2中出现的字符。 一个N*N矩阵，
2从左往右和从上往下都递增。如何最快找出所有的负数。
3。一个他工作中的问题。 求window浏览器中左边树状结构里面某一 节点
从上往下的高度。注意和树的高度不一样。
这个人面了一小时半。
第二人。
忘了。聊天。自己做的项目相关。
第三人。好像是lead
问了一个如何统计text中出现的单词的次数。聊天。
总体满简单的。可能运气比较好。最终也决定从大俗了。虽然钱不是最多。
靠着小小的脆弱的自尊心一直走到现在。每次在怀疑自己的 |
|
r********t
发帖数: 395 | 28
1. 我当初也是
2。 我当初也面了这道题。就是PIE原题。不过PIE那个方法不大好，用stack更好些
3。MS套题目里面的一道。主要是用bitmap把ascii表里256个东西全都设成0；然后把
string2里的东西设成1，然后再查string1里对应的ascii码。
顺便问一下，amazon被拒了以后多久可以重申？ |
|
f*********5
发帖数: 576 | 29 string1: abcabcd
string2: abcd
1) abcabcd
abcd
intersection: a and d
2) abcabcd
abcd
intersection: ab/cd
...... |
|
y****n
发帖数: 579 | 30 char *string2 = "aaa";
This is a char pointer pointing to a const char array.
No modification is allowed. That is why the error pop up. |
|
g**e
发帖数: 6127 | 31 string encode就是把每个string加上xml tag
STRING1
STRING2
恢复就是parse这个xml了。加'\0'不管用，因为有可能string本身就包含\0 |
|
g***s
发帖数: 3811 | 32 after deleting 26 chars, use these space as a simple hashmap. |
|
|
c******t
发帖数: 391 | 34 So how do we efficiently delete the target letters without additional
storage? |
|
h*********n
发帖数: 11319 | 35 果然要always think of hash first... |
|
w**s
发帖数: 141 | 36 why deleting 26 chars??? Not really understanding... |
|
g**********y
发帖数: 14569 | 37 delete 26个char是什么意思？同不明白。 |
|
s*****y
发帖数: 897 | 38 一个字符8bit，4个字符就有32个bit可以做bitmap hash 26个字符了，这样子可以吗
唯一的就是当第一个字符如果它的bitmap影射到第2个字符，那么在读第2个字符前就会
破坏了第2个字符。 |
|
m********l
发帖数: 4394 | 39 不能用XOR?
helloworld
^aaaaaaaaaa
delete any zero.
^aaaaaaaaaa
...
helloworld
^eeeeeeeeee
delete any zero.
^eeeeeeeeee |
|
d*******l
发帖数: 338 | 40 感觉有点南辕北辙。。相同的字母xor了确实会变成0，但不同的字母xor结果不就乱了
？除非不同的字母的对应的是全0，但这样意义很小，对效率好像也没什么帮助 |
|
m********l
发帖数: 4394 | 41
XOR两次
没仔细读.. 不准用新空间
不过他问题也没说好
output跟string1是同个空间吗?
helloworld 是要变成 hlloworl
多了个d |
|
q******8
发帖数: 848 | 42 第一题，求最短的substring包含所有string2的char的O(N)算法是什么？ |
|
y*******g
发帖数: 6599 | 43 只要求返回第一个吗？
把string2 按* break成list of string 然后按顺序 |
|
f*******t
发帖数: 7549 | 44 使用静态buffer虽然不安全，但不能说就是错的，主要看运行的结果如何使用。像前面
那个程序如果先printf string1再处理并printf string2，就不会有问题。
如果返回的字符串不是立即使用，有两种办法：动态分配空间，和直接修改原字符串。
动态分配空间最大的坏处在于，使用完之后需要手动释放，一旦忘记就会造成内存泄露
。所以建议在调用ToUpper()前分配好空间，将指针传入函数由它修改。
另外用分配在栈上的空间作为buffer，返回一个指针，很可能等不到使用这段内存就被
释放了，程序出现内存错误。
还有就是楼主的代码没有检查数组越界的问题，如果传入的字符串长度超过了1000就会
出问题。 |
|
s******c
发帖数: 99 | 45 在本地的考试中心预约的上机考试。考试有三个部分，1.数学题，2.给出一种新的编程
语言的语法，回答相应问题，3. Programming Test 要求速度和准确性both important
Programming test 答得不好，肯定不行了，把面试题发上来让大家做做。做了3个半小
时，快累死了。
数学题基本上就是脑筋急转弯，举几个例子
1. You have three kinds of magazines, all but two are Times, all but two are
Science, all but two are Nature. How many magazines in total do you have?
2. Only one of the answers is true
A. All of the below are true
B. All answers are true
C. One of the above is true
D. All of the above are true
E. None of the above are true
F... 阅读全帖 |
|
s******c
发帖数: 99 | 46 在本地的考试中心预约的上机考试。考试有三个部分，1.数学题，2.给出一种新的编程
语言的语法，回答相应问题，3. Programming Test 要求速度和准确性both important
Programming test 答得不好，肯定不行了，把面试题发上来让大家做做。做了3个半小
时，快累死了。
数学题基本上就是脑筋急转弯，举几个例子
1. You have three kinds of magazines, all but two are Times, all but two are
Science, all but two are Nature. How many magazines in total do you have?
2. Only one of the answers is true
A. All of the below are true
B. All answers are true
C. One of the above is true
D. All of the above are true
E. None of the above are true
F... 阅读全帖 |
|
e********r
发帖数: 2352 | 47 在本地的考试中心预约的上机考试。考试有三个部分，1.数学题，2.给出一种新的编程
语言的语法，回答相应问题，3. Programming Test 要求速度和准确性both important
Programming test 答得不好，肯定不行了，把面试题发上来让大家做做。做了3个半小
时，快累死了。
数学题基本上就是脑筋急转弯，举几个例子
1. You have three kinds of magazines, all but two are Times, all but two are
Science, all but two are Nature. How many magazines in total do you have?
3 books
2. Only one of the answers is true
A. All of the below are true
B. All answers are true
C. One of the above is true
D. All of the above are true
E. None of the above ar... 阅读全帖 |
|
l*****a
发帖数: 14598 | 48 搞那些怪字符干吗。就是besmile的方法
size1+space+string1
size2+space+string2
size3+space+string3
...
找第一个space,get size1,then get string1.... |
|
w********p
发帖数: 948 | 49 evaluator （String expression)
1。将expression parse 成三块 expr1 operator expr2
2 。如果expr1, expr2 都是数字，return 计算结果。 比如6＊6
3。 不然，如果operator 是乘除的话，parse 来string2里的第一个数字，得到结果
4. 再不然，recursively call for rest expression.
有两个links很好和大家分析。
http://www.strchr.com/expression_evaluator
http://compsci.ca/v3/viewtopic.php?t=21703
把网上的code帖出来，给爱偷懒的同伙。我还没仔细看。
无意中运行了下面的code，并不能handle所有的cases 。个人还是喜欢stack的版本。
不会没关系，学学就会了吗。呵呵， 会了不用还是会忘嘛。
本科compiler课是要用java写一个compiler出来的。还有微积分,还给老师的知识还少
嘛？。。。
/*
* The "ExpressionEv... 阅读全帖 |
|
b******g
发帖数: 1721 | 50 input:
string 1: “A B C”
string 2: “BKKAFFCFBJCAHHBC”
output:
BJCA
目标：
要发现string2里面最短的substring，这个string包含所有的string1里面的字符。
有什么好的算法？ |
|
