h****n
发帖数: 1093 | 1 我记得我写了个暴力的C++版本的strstr也通过了large了，难道你用的是java？ |
|
h*******e
发帖数: 1377 | 2 strstr 实际code 并不是用KMP KMP 只是 next 函数 或者有重复序列出现很多的串有
些作用。。 |
|
a***e
发帖数: 413 | 3 请问这段程序有问题么？能通过OJ。但总觉得似乎太简洁了。。。。。有人被面试的时
候要求当场写KMP么？多谢！
char *strstr(const char *s1, const char *s2) {
const char *a = s1, *b = s2;
while(1)
{
if (!*b) return (char *)s1;
else if (!*a) return NULL;
else if (*a++ != *b++) {a = ++s1; b = s2;}
}
} |
|
a***e
发帖数: 413 | 4 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt
不知道啊，但好像是可以得。我是觉得这种写法很简单， 比起同样的naive matching
char *strStr(const char *haystack, const char *needle) {
// if needle is empty return the full string
if (!*needle) return (char*) haystack;
const char *p1;
const char *p2;
const char *p1_advance = haystack;
for (p2 = &needle[1]; *p2; ++p2) {
p1_advance++; // advance p1_advance M-1 times
}
for (p1 = haystack; *p1_advance; p1_advance++) {
char *p1_old = (char*) p1;
p2 = needle;
while (*p1... 阅读全帖 |
|
a***e
发帖数: 413 | 5 找到一个解释比wiki清楚的source
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.h
下面是根据那个原理写的KMP，这下觉得清楚多了。和正在学习的同学共享一下。。。
。。。顺便多谢各位。。。。
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int pos = kmpSearch(haystack, needle);
if (pos == -1) return nullptr;
else return haystack + pos;
}
static void kmpPreprocess(const char *p, vector &b)
{
int i = 0, j = -1;
b[i] = j;
const int m = strlen(p);
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 6 Are you going to interview candidates soon?
StrStr implementation is much easier to solve compared to wildcard matching.
Although the wildcard matching is a very tricky question, Facebook had asked
this question before:
http://www.mitbbs.com/article_t/JobHunting/31575425.html
If you have taken part in Google Codejam before, you will know how fast
those crazy smart people solve problems within minutes. To solve this
problem using nothing but paper and pencil + without bugs in 20 minutes is
very v... 阅读全帖 |
|
z***e
发帖数: 5393 | 7 上面我对其中一个有疑问，马上又翻了里面一个例子。
题目是给出string s1和s2，问s2能否通过rotate s1得到，比如abc => cab之类的，书
里面的解答如下：
显然作者对programming pearl里面如何O(n)来rotate string一无所知，如果是美国这
边的Interview，fail掉的可能极大（采用programming pearl的方法，首先找s2[0]在
s1中的index比如s1[i]，然后尝试从s1[i]来rotate，如果不对，再找下一个i；而不是
从s1[0...n]全部来试.
这都是小trick，但是最大问题在他的第二种方法“可以用strstr()一次得到结果"----
他不知道strstr是O(n)的么？这样两个方法同样都是O(n*n)，哪来什么“提高空间复杂
度，降低时间复杂度”？这边面试的话，善良的Interviewer会问他strstr的复杂度是
多少，mean一点的一句话不说，下来绝对就涮掉了. |
|
b******g
发帖数: 3616 | 8 也看过不少KMP的讲解，觉得确实是matrix67讲得最清楚。CLRS讲得太生涩。之前刷lc
的strStr()这题是用土办法2 points做的，今天也跟风写了个KMP版的strStr()过了下
lc.
BTW: 今天才发现lc这题的interface改了，以前是返回指针，现在变成返回起始index
了。
vector KMPpreprocessing(char *needle) {
int m = strlen(needle);
// assume j = match[i]: needle[i-j:i] == needle[0:j]
vector match(m,-1);
int j = -1;
for(int i=1; i
while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
if(needle[i]==needle[j+1]) j++;
... 阅读全帖 |
|
w***g
发帖数: 5958 | 9 前面的回复了的除了SSA以外，别的都是不懂装懂，一看就知道有多少水平。竟然还有
人说这个不是c的强项。你这个问题问得挺好，我给你演示一下。源程序叫hello.c，
贴在最后
$ make hello
$ objdump -t hello | grep XXX
00000000004006ec g F .text 00000000000001b1 XXX_TEXT
0000000000601070 g O .data 0000000000000004 XXX_DATA
0000000000400968 g O .rodata 0000000000000001 XXX_RODATA
0000000000601078 g O .bss 0000000000000004 XXX_BSS
$ ./hello
Global:
&XXX_DATA: 0x601070
&XXX_BSS: 0x601078
... 阅读全帖 |
|
s****t
发帖数: 36 | 10 刚刚面完amazon的，facebook的是上周五的，
amazon：
1.找出一组数里面相加起来为y的pair
2.设计一个 parkinglot。
没什么别的问题，基本上30分钟没到就说他没什么问题了，问了他几个问题基本上撑到
40
分钟。时间太短是不是没戏啊？是个印度人。2面。
facebook：
1.implement strstr()
2.如果很多次strstr query，但是base的string不变的话，用什么structure，如果
base string大到内存放不下，那用什么structure。
suffix tree， Btree |
|
f****g
发帖数: 313 | 11 没有一套库函数的strstr()是用ＫＭＰ实现的吧，ｈａｈａ
ＫＭＰ用来处理很长的ｓｔｒｉｎｇ ｍａｔｃｈｉｎｇ的问题，一般的很短的ｓｔｒ
ｉｎｇ
用strstr()就足以了（ＫＭＰ还需要ｐｒｅｐｒｏｃｅｓｓ要找的ｓｔｒｉｎｇ这个也
有开销） :D |
|
r***u
发帖数: 241 | 12
man strstr
char *strstr(const char *haystack, const char *needle); |
|
l*********8
发帖数: 4642 | 13 赞！
question：
如果strstr是o(N)的，那么调用strstr的简单解法也应该是O(n)的吧？ |
|
l*********8
发帖数: 4642 | 14 赞！
question：
如果strstr是o(N)的，那么调用strstr的简单解法也应该是O(n)的吧？ |
|
j*****u
发帖数: 1133 | 15 这个题我觉得书里写的没错
programming pearl作者可能没看过，我也没看过
第二种方法code大概类似这样：
bool CanBeRotated(string s1, string s2)
{
return strstr(s1 + s1, s2);
}
strstr只被call了一次，你自己也说了它是O(n)的 (not for worse case)。
另外，多数公司再中国的hiring bar比美国的都要高(原因很明显)。所以你说“如果是
美国的interview，fail掉可能性极大”。同样的candidate在国内恐怕连海选和笔试都
过不了，连interview机会都没有。 |
|
|
|
k*****y
发帖数: 744 | 18 请问像 s = "abadabadabadeabecd", p = "*ab?c*d"这样的不用递归怎么办？
我也贴一个，大家帮忙看看，谢谢~
===========================
bool isMatch(const char* s, const char* p) {
if(*s == 0) return !hasNonStar(p);
if(*p == 0) return false;
if(*p != '*'){ //case: *p != '*'
while(*s && *p && *p!='*') {
if(*p!='?' && *p!=*s)
return false;
++p; ++s;
}
return isMatch(s, p);
}
else{ // case: *p == '*'
if(!skipStars(s, p)) return false;
... 阅读全帖 |
|
z********c
发帖数: 72 | 19 不知道什么要求。。我直接写的搜索然后优化成DP，他说很好
merge写了，那一场45分钟全部用来搞这个题了。。。。
补充一下电面题把:
F:
1. int strstr (const char *haystack, const char *needle)，要你实现，
bruteforce就行
2. int strstr (const char *haystack[], const char *needle)，意思就是haystack
太长了，然后一个串存不下，变成存个数组里， 把他们concatenate 以后就是
haystack，还是一样的要求，要你实现，不能有额外空间
3. 给一组字符串，按anagram分组，输出
G:
1. 找到ll里最后k个节点，把他们放到前面来
2. 那题在板上说过，一个iterator，有next和hasNext，现在要你加个wrapper，使得
支持peek操作
不少了哥。。。我问了那么多人绝对我写的码比他们都多。。 |
|
J****3
发帖数: 427 | 20 Strstr() using Robin-Karp alg
large case 会有6个过不了。。求大牛帮我看下哪里有问题。
const int base = 26, mod = 997;
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int l_h = strlen(haystack);
int l_n = strlen(needle);
if(l_n > l_h) return NULL;
int h_hash = 0, n_hash = 0;
for(int i = 0; i < l_n; i++){
n_hash = (n_hash*base + needle[i])%mod;
... 阅读全帖 |
|
a***e
发帖数: 413 | 21 最近做leetcode，有的题花很长时间能写出来，但长得很。不知道怎么才能写得简洁一
些,特别是在面试那种时间有限的情况下。多谢大牛分享经验！
比如那道strstr()
char *strStr(char *haystack, char *needle) {
if (haystack==NULL || needle==NULL) return NULL;
char *needleHead = needle;
char *hsHead = haystack;
int hl=0, nl=0;
while(*haystack!=' |
|
f******h
发帖数: 45 | 22 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
l******s
发帖数: 3045 | 23 Yes. O(C(17, 9) *n) is the time complexity, but don't need O(n) to check
validity,
because during the DFS a stack is brought in the parameter list to track
the string's validity. A Hashset result is used to check duplicates.
There are also ways to prune to find the invalidity earlier than removing
all 9 ( chars in each dfs tree, so O(C(17, 9) *n) is only the worst case.
The case you are giving below seems too simple because there are no any
alphabets, and if so, we can do special logic to handl... 阅读全帖 |
|
|
t**8
发帖数: 4527 | 25 凡是靠strstr的都是要看bruteforce 的
bug free 并不容易
FLG 是不会考 strstr 的
备. |
|
h*****f
发帖数: 248 | 26 【 以下文字转载自 JobHunting 讨论区 】
发信人: henrysf (Henry), 信区: JobHunting
标 题: Re: L 电面
发信站: BBS 未名空间站 (Thu Oct 18 01:46:20 2012, 美东)
我写了以下的code, 之后就被拒了, 回信是说别的candidate写得比较好, 我还没看出
问题.
Additional requirements:
- The only operators you need to implement are +, -, *, and /.
However, your implementation should make it relatively easy to
add more operators.
- The calculator should accept floating point numbers and output
floating point numbers (i.e. when the input is 2 3 / the result
is 0.66667).
- ... 阅读全帖 |
|
w****h
发帖数: 152 | 27 感觉我都回答的不好...
1. a linked list, and the last node could point back to any node in the list
. find the node in the list to which the last node points to.
我的方法是iterate the list, mark each node if we pass it, the node that we
are looking for should be the one that we already passed. 但是这样就要在每个
node里加个flag，似乎不太好。
2. find the common words in two sentences.
这个我回答的太土了。我tokenize each words in the sentence, 然后比较这些words
。有啥简单的方法吗？
3. find the specific words in a sentence.
其实就是strstr()?
4. how to remove a cy |
|
x**l
发帖数: 64 | 28 回报本版。以下信息仅供参考。
第一轮：两个engineers，非老印老中，所以口音比较容易听懂
1、在纸上写程序 reverse a decimal number，例如输入123，输出321
trap：如果是8bit char，123的输出位321超过了127，变为负数，所以需要检查输出数
和输入数的符号位是否相同。（用bit xor检查）
2、实现char *strstr(char *sub, char *str)，就是子串匹配，返回匹配的子串地址
或者NULL。
我预先问是否要求用KMP algorithm，对方说不用，就最直接的做法。
里面没什么技巧，注意把代码写规范一些，输入参数检查,边界条件之类的。
3、general question，输入股票代码例如goog，返回股票价格，如何组织数据结构。
我先说hash，对方稍微追问了一下hash的time complexity什么时候最好，最差之类的。
然后我补充了一下还可以用binary search or binary search tree.
4，C的struct和C＋＋的struct的区别 （多4个member funct |
|
s********g
发帖数: 28 | 29 CS方向，希望对大家准备面试有帮助
1. 用stack class来实现queue，具体用几个stack不限。完了以后问怎么实现thread
safety，然后是怎么测试。
2. 实现strstr(str1, str2)，如果str2是str1的子串，返回true，否则返回false。实
现完了以后问如何测试。
3. 给定一个integer array with both positive and negative numbers，return a
contiguous subarray with the largest sum. 我本来想用dynamic programming实现
，但面试官希望按照他的一个更heuristic的思路来解，最后勉强搞定。
4. 给定一个排好序的linked list，删除其中所有的重复元素。比如给定1->2->3->3->
4->4->5，返回1->2->5。给定1->1->1->2->3，返回2->3。看起来简单，一边写一边发
现许多细节需要小心应对，好在最后搞定。
5. 给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3 |
|
t******e
发帖数: 1293 | 30 比如说里面有*和?，*匹配任何字符，?只匹配一个字符
bool strstr(const char * str, const char * pattern);
记得以前有高人说过在某本书的第一章的最后一个例子就是
这个程序。不过，找不到是哪本书了。大家有印象吗？
提示：作者应该是在AT&T Bell Lab呆过的，和K&R, Unix的
作者那帮人一起共事过。 |
|
c******t
发帖数: 27 | 31 I think he is an Indian, a very nice guy.
1. Describe a project you worked lately.
He asked if I know memory flushing when I was giving the answer.
2. 2 sets of numbers, the quickest way to find the intersection.
3. for 2 strings, check if one is a sub-string of the other one (just like
strstr). Write the code and read it aloud to him.
4. for a web game, if you need to find the 10 highest score, how will you
design the interface?
5. You have a directory, it includes some files who have cust |
|
k***g
发帖数: 75 | 32 你的面试题比我难多了啊，我面的他们的基础设施组，问的问题都好简单。总共四个编
程题，atoi，不用sqrt库函数求sqrt，strstr，反转单链表。 |
|
l******o
发帖数: 144 | 33 今天facebook电面，纯编程题，挺简单的，一道是给一个binary tree，按照BFS的方式
打印出来。一道是strstr，还有一道是实现sqrt。
问题就是我的iPhone，断线了5、6次，给interviewer留下了极坏的印象。因此我也变
得比较紧张，说话非常结巴了。我想Facebook是彻底与我无缘了。
我的iPhone很久以前犯过这个毛病，就是老断线，然后重启之后就好了。很长一段时间
没有这个问题了，今天居然在关键时刻又犯了这个毛病。我恨死iPhone了。 |
|
S******a
发帖数: 862 | 34 前几天google的面筋很过瘾。
面过facebook的同学们也出来说说吧！
不胜感谢！
==================================
我碰到的电面题都很简单。
但愿onsite也好运。
[facebook]
1.1. 反转单链表
1.2. 广度优先遍历一颗树
2.1. 实现一个strstr函数
2.2. 输入: phone #
输出: 所有对应的string
eg. 输入: 23, 输出:[ad, ae, af, bd, be, bf, cd, ce, cf]
[google]
1.1. 输入: 一个数独的解(9x9 int 矩阵)
输出: 判断是否是成功的 （判断每一行/一列/3*3矩阵是否是1-9的一个permutation）
2.1. 输入: 两个排好序的数组
输出: 交集和并集
eg. 输入: [1,2,2,3], [1,2,2,2] 输出: [1,2,2] 和 [1,2,2,2,3]
然后，facebook面完2小时--1天给结果，google每轮都等个2周。 |
|
m******9
发帖数: 968 | 35 我想了一下, 这些测试方法, 在软件工程这种课程中确实详细的提到过了. 不过我有一
个困惑就是, 这些方法都比较high level. 很多测试方法都针对比较大型的软件. 如
果我想测试的只是一个小玩意.
比如, 我要测试strstr函数的功能. 我现在能想到的就是测试一些special case, 和一
些边界条件.
测试atoi, 就测试溢出,还有错误的输入,etc
这些套路有时在测试一些具体的function的时候,不是很容易套用. |
|
|
I**********s
发帖数: 441 | 37 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
s*******s
发帖数: 46 | 38 开始走了很多弯路吧，到现在大概7个phone interviews, 2个on-site interviews, 0
个offer.
今天被facebook一轮给拒了－ －，感觉给的题目都挺简单的（strstr, in-place
merge)，我也答得很顺利啊。挺郁闷得
说。
都有点担心更早之前的yahoo面试了。
虽然现在心态摆得很正，如果找不到理想的工作咱就回国，我至少觉得自己回国我也有
另一种过法，而且相信自己的能
力。
今天和朋友吃饭聊到这个问题，不知道是否悲剧是因为一些no-technical的原因。
咳，月末第二个on-site，希望有一个offer吧，虽然这个方向我还要考虑一下。
祝大家早日有好消息～嗯 |
|
b********e
发帖数: 693 | 39 I want to see some function implentation, like
strcpy, strstr, etc
thanks |
|
s*********t
发帖数: 1663 | 40 这是strstr()吧？
算法改成KMP算法，具体细节的去搜索一下吧，忘记了。 |
|
c******t
发帖数: 1500 | 41 strstr函数如果使用KMP的话会不会效率更高呢？
为什么楼主说不需要？ |
|
A********l
发帖数: 184 | 42 网上扔的简历，一周后recruiter来电话约了电话面试。
hiring manager打来电话，问了简历上的问题，比较简单。然后问了一个简单的题目:
如何找出apache weblog中访问最多的几个url。用linux shell如何实现，用java如何实现。
过几天另一个组的hiring manager也来电话，聊了聊，比较开心。
几天后约了onsite，见了10个人，每次两个人。问题都比较简单。
round 1:
hiring manager 1， 聊天，很开心。
round 2:
一个在akamai干了11年的老年软工
2.1 设计course registration的数据库schema
2.2 Fibonacci递归和非递归实现
2.3 三个盒子，一个装的全是白旗子，一个全是黑棋子，一个是混合，但是所有的
label都是错误的，你可以从盒子中draw几个棋子。如何纠正盒子的label，同时保证
draw的次数最少
2.4 两个dice，如何label，使得他们的可以表示01-31中的所有数字
round 3：
两个老年软工:
3.1 聊天
3.2 程序找错，一个计算两个集... 阅读全帖 |
|
K******g
发帖数: 1870 | 43 面试的是美国人，英语很好
一上来就问为什么申请twitter
然后马上coding，实现strstr（）。还没有写完，就问我complexity。我说是O(nm),他
追问一下，什么情况下是exactly O（nm)，我说是当str2不是str1的substring的时候。
写完代码后，就问优化。首先是算法上，我说了KMP，然后要我大概讲一下KMP的思路，
我只记得有个preprocess的过程，把一个string的prefix弄到一个array里去。然后又
问，怎么从程序结构上优化，比如str1非常非常长，我就说分成很多chunks，放到不同
的machine上去跑。他又说，那样会有问题，有可能在分chunks的时候把一个substring
的match打断，问我怎么办。我没有答上来，后来想通了，其实很简单。在分chunk的时
候，把断开的地方的左边和右边一定范围内，再弄一个chunk出来，这样子如果有match
的话，就逃不掉了。
接下来，就是设计问题。许多machine，每个machine上有许多user，每个user有很多
followers，怎么统计每个user的平均foll... 阅读全帖 |
|
d**e
发帖数: 6098 | 44 贴出来看看？
这个跟strstr类似吧？
O(nm)
n = strlen(string)
m = strlen(pattern) |
|
j*****g
发帖数: 223 | 45 I felt my DP solution is the right one. Though I coded it up in about 2
hours (coding is really only 20min, but finding the solution took many
trials and many brain cells).
Anyway, I'm not sure such problems are good interview question candidates.
It's beyond anyone's raw brain power to come up with correct solution from
scratch within given time frame.
My typical interview question is write strstr and using double loop is fine.
Still surprisingly lots of SDE candidates failed w/ that :)
. |
|
j*****g
发帖数: 223 | 46 想出来个新方法，至少看上去挺简单的，不用recursion, 动态规划，suffix tree, 或
脑筋急转弯的算法。
case 1。看看一个普通的pattern string (not edge case):
*str1*str2*str3*
where 1) strN is basically a-z plus '.' 2) assume we've already collapsed
multiple consecutive *'s into a single *.
在这种情况下, 去匹配target string就是一个贪心算法:
start = target;
foreach (strN)
{
new_start = strstr(target + start, strN);
if (new_start == NULL) return false;
start = new_start + len(strN) + 1;
}
return true;
case 2。再看看其他pattern string的情况:
如果pattern string is like... 阅读全帖 |
|
j*****g
发帖数: 223 | 47 Yes.
Since the problem reduces to do a bunch of strstr, so it should be linear to
O(n+m) where n is string length and m is the pattern length.
J |
|
i**********e
发帖数: 1145 | 48 问题背景：
最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
expression match吧。
所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
给个例子，例如
a*b 可以match : ab, aab, aaaaaaaaaaab
写个函数:
bool match(const char *string, const char *pattern)
这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
人很倒霉被问到这题。facebook有问过这题：请参考
http://www.mitbbs.com/article_t/JobHunting/31575425.html
这题其实利用brute force就可以了，算法不难想到，但是要处理很多special case，
非常的棘手。我觉得正常人一般都回遗漏掉很多case，第一次就能写对简直就难如登天
。再加上面试的压力，我觉得没做过这题面试当场第一次就能写对的是神人。
Brute force的算法就是O... 阅读全帖 |
|
D********g
发帖数: 650 | 49 这题如果用strstr的话应该可以greedy。
pseudo code:
bool match(const char *s, const char *pattern)
{
string[] ps = string.split(pattern, '*');
foreach(string p in ps)
{
idx = s.find(p);
if (idx == -1) return false;
s = s.substr(idx + p.length());
}
return true;
} |
|
i**********e
发帖数: 1145 | 50 问题背景：
最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
expression match吧。
所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
给个例子，例如
a*b 可以match : ab, aab, aaaaaaaaaaab
写个函数:
bool match(const char *string, const char *pattern)
这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
人很倒霉被问到这题。facebook有问过这题：请参考
http://www.mitbbs.com/article_t/JobHunting/31575425.html
这题其实利用brute force就可以了，算法不难想到，但是要处理很多special case，
非常的棘手。我觉得正常人一般都回遗漏掉很多case，第一次就能写对简直就难如登天
。再加上面试的压力，我觉得没做过这题面试当场第一次就能写对的是神人。
Brute force的算法就是O... 阅读全帖 |
|
