l*********8
发帖数: 4642 | 1 赞！
question：
如果strstr是o(N)的，那么调用strstr的简单解法也应该是O(n)的吧？ |
|
C***U
发帖数: 2406 | 2 thanks leetcode!!
I like your website. |
|
w***o
发帖数: 109 | 3 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
，我还真以为自己找到一个好的算法了。 |
|
h****n
发帖数: 1093 | 4 说的很对，写出考虑到所有可能的情况的test case的确很不容易
最近才开始做OJ，收获很大，特别感谢作者能想出那么多test cases出来验证自己的程序
想必是花了挺多时间的 |
|
|
|
i**********e
发帖数: 1145 | 7 small judge 过了而没过 large 肯定是漏了某些状况没测好。
如果你还有当时那个代码，请问可以发一份给我吗？
这样我可以针对更全面的测试来设计 small case 。
interleaving
case |
|
|
l*********8
发帖数: 4642 | 9 赞！
question：
如果strstr是o(N)的，那么调用strstr的简单解法也应该是O(n)的吧？ |
|
C***U
发帖数: 2406 | 10 thanks leetcode!!
I like your website. |
|
l**b
发帖数: 457 | 11 大牛出山的终结，看了好多次，一定要mark一下。 |
|
c********t
发帖数: 5706 | 12 赞研究精神。
这个和OJ上的题不一样吧，似乎还容易些？ |
|
c********t
发帖数: 5706 | 13 这么好的帖子，怎么沉了两年，幸亏有考古者挖了出来。
interleaving
case |
|
j*****g
发帖数: 223 | 14 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
j*****g
发帖数: 223 | 15 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
l*****v
发帖数: 498 | 16 这就是带wildcard的string match。没有*应该不难吧。 |
|
J******8
发帖数: 132 | 17 Not hard at all. But I focused on how to do wildcard matching, missed the
point to do linear lookup in dictionary in that case (binary search not
applicable any more). |
|
n***k
发帖数: 2780 | 18 thanks for your response.
Yes, I guess Trie might be the right solution. however, how can we use Trie
to solve wildcards for lookups?
for example, "com.yahoo.*" should match all nodes like these:
"com.yahoo"
"com.yahoo.finance"
"com.yahoo.sports"
... |
|
g*******s
发帖数: 490 | 19 这个example比较简单，com.yahoo.的所有孩子就是了。。。比较复杂的wildcard search也是可以实现的 |
|
g*********s
发帖数: 1782 | 20 【 以下文字转载自 Programming 讨论区 】
发信人: gandjmitbbs (Nothing), 信区: Programming
标 题: implement a simple regular expression match?
发信站: BBS 未名空间站 (Tue Jan 25 02:30:51 2011, 美东)
the regular expression only includes a-z, '*', and '.'
support:
1. "x*", aka 0 or more continuous 'x'
2. ".", aka wildcard matching any letter.
it seems back-trace is inevitable because of the following ambiguity:
match("b", "b*.") == true;
match("b", "b*") == true; |
|
l*****a
发帖数: 559 | 21 来自主题: JobHunting版 - 问个算法题 如果第一个是wildcard × 的话，需要遍历整个trie，worst case就是trie的节点数，
即O（n） n为节点数。 |
|
|
g*****i
发帖数: 2162 | 23 这链接里是wildcard,楼主的题目是regex,还是不一样.
这题我觉得用递归可能好点,不用递归的话我觉得难点在于一下这些特殊pattern
c*cba (*前后一样),
c*.ba (*后面是"."),
.* (*前面是".")
c*c*.*c* (同一个字符和"."的*连续出现)
谁能给点思路吗? |
|
|
g*****i
发帖数: 2162 | 25 这链接里是wildcard,楼主的题目是regex,还是不一样.
这题我觉得用递归可能好点,不用递归的话我觉得难点在于一下这些特殊pattern
c*cba (*前后一样),
c*.ba (*后面是"."),
.* (*前面是".")
c*c*.*c* (同一个字符和"."的*连续出现)
谁能给点思路吗? |
|
H***e
发帖数: 476 | 26 wildcard是怎么match的？
* match any sequence including empty string
? match exactly one char?
不象regular expression的*, 要跟前面的char有关系， 是这样的吗？
NULL
1, |
|
y******n
发帖数: 47 | 27 周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.
* given a function on sorted dictionary to retrieve word by index,
string getWord(int i), how to i... 阅读全帖 |
|
g*****i
发帖数: 2162 | 28 第一题是celebrity问题,面经了出现过几次了,楼上的就是标准解法.
第二题google下wiki有解释算法,当时我没仔细看.
第三题你google下wildcard match就可以了,递归写法很容易,网上有非递归写法,我没
记住. |
|
r*******g
发帖数: 1335 | 29 hi
考古发现以前题似乎更难一些，不知道是不是错觉
1，从一个string 变到另一个，比如"study"->"world" （字数相等），要求
每次变一个字母，每次改变后的string必须是一个词典里面能查到的英语单词，比如你
不能把study变
成atudy
由于加了个条件，不知道最后讨论出来什么办法更好，似乎还是没有定论？
2， Given an integer, print the closest number to it that is a palindrome
input: 1224
return: 1221.
这个题仔细一想一点都不简单，关键是，最closet的数可能和原来的数完全不一样，怎
么弄？
3， In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of a... 阅读全帖 |
|
r*******g
发帖数: 1335 | 30 hi
考古发现以前题似乎更难一些，不知道是不是错觉
1，从一个string 变到另一个，比如"study"->"world" （字数相等），要求
每次变一个字母，每次改变后的string必须是一个词典里面能查到的英语单词，比如你
不能把study变
成atudy
由于加了个条件，不知道最后讨论出来什么办法更好，似乎还是没有定论？
2， Given an integer, print the closest number to it that is a palindrome
input: 1224
return: 1221.
这个题仔细一想一点都不简单，关键是，最closet的数可能和原来的数完全不一样，怎
么弄？
3， In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of a... 阅读全帖 |
|
|
|
|
|
t****s
发帖数: 1 | 35 a Java version for regex match as below, let me know if there is any issue.
boolean isMatch(String s, String p) throws Exception{
if (p==null || p.length()==0)
return s==null || s.length()==0;
return isMatch(s,p,0,0);
}
boolean isMatch(String s, String p, int is, int ip) throws Exception{
if (ip>=p.length())
return s==null || is>=s.length();
if (ip==p.length()-1 || p.charAt(ip+1)!='*'){
if (p.charAt(ip)=='*')
throw new Exception("illegal");
if (is>=s.lengt... 阅读全帖 |
|
i**********e
发帖数: 1145 | 36 Your code is correct.
It got "Time Limit Exceeded" due to this test case,
s = "aaaaaaaaaaaaab", p = "a*a*a*a*a*a*a*a*a*a*a*a*c"
which happens to Java solution but not C++ solution.
I have updated the test case so that a Java recursive solution could pass.
Sorry about that. |
|
S**I
发帖数: 15689 | 37 ☆─────────────────────────────────────☆
yuhanlin (Yuhan) 于 (Mon Aug 29 00:18:17 2011, 美东) 提到:
周五面完最后一个onsite, 累的惨兮兮的, 好容易爬回家. 不管结果如何, 这段时间找
工作算是告一段落了.
下面把这段时间面试中被问到的题目整理一下, 供大家参考. 我也就不说具体是那些公
司了, 都是很典型的面试题, 到哪里都有可能会被问到.
* implement memcpy? How to improve? how to determine if a system is
32bit or 64bit?
* how is static keyword used in Java?
* a list of intervals, no overlapping and sorted, write a function to
insert an interval into the list and still keep the list sorted and no
overlapping.... 阅读全帖 |
|
h****e
发帖数: 928 | 38 Valid Number按照火鸡的说法，用正则表达式几行就够了。
Next permutation得记得算法，否则是很难的。
我的wildcard match的解答一直都过不了大数据的，最后也放弃了。:( |
|
A*H
发帖数: 127 | 39 是一定code有问题么，还是有可能程序跑得不够快?
wildcard matching 那题，small test 过了，large test 一直timeout, 大家帮忙看
看这个java code有什么问题么? 除了暴力法，还有更快得解法么？
public boolean isMatch(String s, String p) {
return match(s, p, 0, 0);
}
public boolean match(String s1, String s2, int i1, int i2) {
int l1 = s1.length();
int l2 = s2.length();
if (i2 == l2) return i1 == l1;
if (s2.charAt(i2) == '*') {
while (i2
i2++; // find next n... 阅读全帖 |
|
h******8
发帖数: 55 | 40 好像找不出这样的例子。wiki 上的例子是{(a|aa)*b, aaaaaaab}，但是这里我们不用
实现（）和|。 |
|
h******8
发帖数: 55 | 41 好像找不出这样的例子。wiki 上的例子是{(a|aa)*b, aaaaaaab}，但是这里我们不用
实现（）和|。 |
|
c********t
发帖数: 5706 | 42 "aaaaaaab" "*ab" recursion 就是exponentional time吧 |
|
r*****a
发帖数: 421 | 43 用recursive brutal force的算法leetcode通过了small data test，
但是在large data test的时候超时了。
尤其是以下这个例子，自己电脑上都算不出来。
s="bbbababbbbabbbbababbaaabbaababbbaabbbaaaabbbaaaabb"
p="*b********bb*b*bbbbb*ba"
有没有更优化的算法？
贴个java的
public boolean wildcardMatch(String s, String p, int sPos, int pPos) {
if (sPos == s.length()) {
if (pPos == p.length()) // p also used up
return true;
} else if (pPos < p.length() && p.charAt(pPos) == '*') { // current p
is *, rest should all be *
return wild... 阅读全帖 |
|
|
C***U
发帖数: 2406 | 45 有iterative 的算法 可以通过judge large |
|
p*****2
发帖数: 21240 | 46
感觉面试的话recursion或者DP就够了吧？ |
|
|
p*****2
发帖数: 21240 | 48
我的意思是面试的标准不会以leetcode big data能不能pass为标准吧？ |
|
C***U
发帖数: 2406 | 49 恩 这个对哦 看面试官心情 和你和他的缘分
哈哈哈 |
|
p*****2
发帖数: 21240 | 50
其实面试recursion能写到bug free已经挺牛逼的了。好多题我知道最优的面试也不敢
用。自己handle不了更麻烦。 |
|
