h**k
发帖数: 3368 | 1 可以用二分法来确定最大长度x，x应该在区间（1，min(str1_len, str2_len))里。
对于给定长度x，我们可以用O(n)来判断是否在str1和str2中各存在一个长度为x的子串
互为anagram。基本思路是对于str1和str2中的每个可能长度为x的substring，生成
counter array，记录里面每个字符出现的次数。比如baca的counter table就是count[
a]=2, count[b]=1, count[c]=1。然后把array的值存入hash table。这样就能找出互
为anagram的两个子串。
( |
|
j*****g
发帖数: 223 | 2 想出来个新方法，至少看上去挺简单的，不用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... 阅读全帖 |
|
K******g
发帖数: 1870 | 3 isMatch（str1, str2）就是判断str1里从第一个char开始是否和str2 match,如果
match，就return 1，否则0.这个函数很容易写，估计几行就好了。 |
|
B*******1
发帖数: 2454 | 4 你的code的确牛，学习了。
但是我肯定写不出来，改了一下思路，在string前面pack了一个10，再计算，绕过很多
一开始的初始条件
int decodeString(const string &s)
{
if (s.size() == 0) return 0;
string str2 = "10" + s;
const char *str = str2.c_str();
int a = 1, b = 1, c;
str += 2;
while (*str) {
c = 0;
if (*(str-1) == '1' || (*(str-1) == '2' && *str <= '6'))
c += a;
if (*str != '0')
c += b;
a = b;
b = c;
str++;
}
return c;
} |
|
p*****2
发帖数: 21240 | 5 我写了一个，练了练。主要是输出的时候有几个小地方要注意。
def fullJustify(words:Array[String], L:Int)={
process(0)
def process(i:Int):Unit={
val j=getNext(i,0)
if(i
{
printSlice(words.slice(i,j))
process(j)
}
}
def printSlice(words:Array[String]):Unit={
if(words.size==1) {println(words(0));return}
val total=words.map(_.length()).sum
val spaces=... 阅读全帖 |
|
t****a
发帖数: 1212 | 6 这题怎么用greedy来做呢？DP的话是n*m计算量
memoize dp的解
(defn is-match [str1 str2]
(let [str1a (str str1 \a)
str2a (str str2 \a)
n1 (count str1a)
n2 (count str2a)
seq2 (apply concat (repeat n1 (range n2 -1 -1)))
seq1 (mapcat #(repeat n2 %) (range n1 -1 -1))
]
(do
(def is-match-rec
(memoize
(fn [i1 i2]
(let [l1 (- n1 i1)
l2 (- n2 i2)]
(cond (and (== 0 l1) (== 0 l2)) true
(or (=... 阅读全帖 |
|
g*******s
发帖数: 2963 | 7 要求写两个function, signature定义如下。把两个string 合并成一个，再把这个合成
的string还原成两个。string可以包含任意字母任意顺序，另外要求是不允许用额外空
间。比如合并的时候插入新字母或者返回额外变量记录长度什么的。
string serialize(string &str1, string &str2);
void deserialize(string &str， string &str1, string &str2); |
|
d**********x
发帖数: 4083 | 8 我想了一会儿其他可能性，比如说什么异或，rotation之类的
感觉确实是没有多余的空间可以存东西。
所以要么是
1.字符的范围有限制，所以我们可以取一个bit，或者更少的空间做标记什么的
2.考虑到这是个c++函数，可以用很tricky的手段，即先设定字符串的capacity=str1.
length+str2.length，然后resize到str1.length，再把str1和str2的内容填进去。如
果有人想说G不会出这种恶心题目，请参考我的签名档…… |
|
h**o
发帖数: 548 | 9 没见过这题。 我当时这样写的。
请问哪里有真确答案？
int countByte(char* str1, char* str2, char pattern){
int cnt = 0;
char ch;
for (int i = 0; i < 8; i++){
ch = str1<>(8-i);
if (ch ^ pattern==0) cnt++; //^ means XOR
}
return cnt;
}
int countPattern(char* str, char pattern){
if (!str || *str == ‘ |
|
h**o
发帖数: 548 | 10 没见过这题。 我当时这样写的。
请问哪里有真确答案？
int countPattern(char* str, char pattern){
if(!str) return 0;
int sum = 0;
while(!(str+1) && *(str+1)!= 0){
sum += countByte(str, str+1, pattern);
str++;
}
return sum;
}
int countByte(char* str1, char* str2, char pattern){
int cnt = 0;
char ch;
for (int i = 0; i < 8; i++){
ch = str1<> (8-i);
if (ch ^ pattern==0) cnt++;
}
return cnt;
} |
|
b******g
发帖数: 77 | 11 N * LogN 解法
class StrCompare
{
public:
bool operator()( const string& str1, const string& str2 ) const
{
return str1.size() > str2.size();
}
};
class PairFinder
{
public:
void init()
{
m_nProductSize = 0;
}
size_t getProduct() const { return m_nProductSize; }
pair getPair() const { return make_pair( m_csFirst, m_
csSecond ); }
void compute( vector& vctStr )
{
init();
if( vctStr.size() < 2 ) re... 阅读全帖 |
|
i*********n
发帖数: 58 | 12 要求写两个function, signature定义如下。把两个string 合并成一个，再把这个合成
的string还原成两个。string可以包含任意字母任意顺序，另外要求是不允许用额外空
间。比如合并的时候插入新字母或者返回额外变量记录长度什么的。
string serialize(string &str1, string &str2);
void deserialize(string &str， string &str1, string &str2); |
|
u****x
发帖数: 97 | 13 How about this?
return singleDirection(str1, str2) && singleDirection(str2, str1);
singleDirection returns false if the same char in the 1st arg maps to two
different chars in the 2nd arg, which is easy to code. |
|
m*****n
发帖数: 2152 | 14 考官的意思是不是这个：
str1 = "aaab"
str2 = "ab"
reg = "a*b" 而不是 "a.*b"
str1 = "aaabbb"
str2 = "ab"
reg = "a*b*" ? |
|
h****3
发帖数: 89 | 15 public static String bestTime(String tasks, int cooldown){
if(tasks==null || tasks.length()==0 || cooldown<0){
throw new IllegalArgumentException("input not valid");
}
int waitTime = cooldown;
int curRep =0;
StringBuilder res = new StringBuilder();
Stack stack = new Stack();
HashMap map = new HashMap();
PriorityQueue pq = new PriorityQueue(11, new Comparator<... 阅读全帖 |
|
a*****s
发帖数: 1121 | 16 上周五的onsitee，只刷过三道leetcode题目，硬着头皮上了。免得是大数据platform
组SMTS，挂了，不知道谁黑的。
一个俄国小哥：
比较热情， 先问了stack用linklist和array实现的优缺点，然后问了如何用二维数组
存储神经网络，比较耐心的引导类型，最后时间没有了，就只讨论了一下为什么这么做
。俺提出了一些可能的；
印度人：
上来很详细的问了以前的做的东西，HIVE如何转化成TEZ的，TEZ和MAPREDUCE的性能区
别，Slider提交任务需要那三个文件，我说就是三个json文件关于资源请求，可执行文
件等等，半年前作的实在记不清了，他解释说是metainfo.xml， 和两个json文件，俺
就极力说服他，please检查slider的apache JIRA buglist，现在俺还有几个ticket要
解决，他说他会。没让写code
一个国人伯克利小伙子：
随便问了问以前的项目，然后让做题， 给两个string，一个str1，一个str2，找出
str1里所有的str2
出现的第一个位置：比如ababab，ab那么返回数组［0，2，4］。先让写te... 阅读全帖 |
|
f*******r
发帖数: 976 | 17 Move on. 祝LZ早日拿大offer
上周五的onsitee，只刷过三道leetcode题目，硬着头皮上了。免得是大数据platform
组SMTS，挂了，不知道谁黑的。
一个俄国小哥：
比较热情， 先问了stack用linklist和array实现的优缺点，然后问了如何用二维数组
存储神经网络，比较耐心的引导类型，最后时间没有了，就只讨论了一下为什么这么做
。俺提出了一些可能的；
印度人：
上来很详细的问了以前的做的东西，HIVE如何转化成TEZ的，TEZ和MAPREDUCE的性能区
别，Slider提交任务需要那三个文件，我说就是三个json文件关于资源请求，可执行文
件等等，半年前作的实在记不清了，他解释说是metainfo.xml， 和两个json文件，俺
就极力说服他，please检查slider的apache JIRA buglist，现在俺还有几个ticket要
解决，他说他会。没让写code
一个国人伯克利小伙子：
随便问了问以前的项目，然后让做题， 给两个string，一个str1，一个str2，找出
str1里所有的str2
出现的第一个位置：比如ababa... 阅读全帖 |
|
发帖数: 1 | 18 上周面试linkedin的前端，杯具了。反馈说是desgin和coding没做好。我百思不得其解
，想问问大家我的回答到底出了什么问题。
design是倒数第二轮，一个刚刚入职不到一年的小女生主试。
题目是设计一个registration real time map for linkedin. 每当有人注册linked,地
图上就会有一个点闪一下。
我首先问她的第一个问题是期望的效果是什么样的，多久刷屏一下，resolution到多少
，闪的点是不是越大代表注册人数越多。她说1秒钟刷屏一次，resolution到post code
，点的大小代表什么你自己说了算。我就说因为很可能同一地区有可能一秒钟内有多人
注册，所以我就用点的大写代表人数。然后我就开始设计api，我说我期待api返回一个
数组，数组里每个元素是一个json object，包含latitude,longitude和人数，我每个1
秒钟call一次这个api。然后她就说这不行，服务器只返回country code和post code，
并且不能够1秒钟call一次，服务器受不了，最多30秒call一次。于是我就改了一下，... 阅读全帖 |
|
a****s
发帖数: 282 | 19 Top 20 (laatste update: 13:20)
Coureur Team Chassis Laptime Verschil Laps
1 Robert Kubica BMW Sauber F1.07 1:19.556 0
2 Michael Schumacher Ferrari F2007 1:19.929 + 0.373 0
3 Timo Glock Toyota TF107 1:20.031 + 0.475 0
4 Felipe Massa Ferrari F2007 1:20.034 + 0.478 0
5 Sebastian Vettel Toro Rosso STR2 1:20.358 + 0.802 0
6 Sebastien Bourdais Toro Rosso STR2 1:20.368 + 0.812 0
7 Kazuki Nakajima Williams FW29 1:20.413 + 0.857 0
8 Nico Rosberg Williams FW29 1:20.616 + 1.060 0
9 Anthony Davidson Hon |
|
a****s
发帖数: 282 | 20 Top 20 (laatste update: 18:04)
Coureur Team Chassis Laptime Verschil Laps
1 Sebastian Vettel Toro Rosso STR2 1:18.213 100
2 Robert Kubica BMW Sauber F1.07 1:18.410 + 0.197 119
3 Nico Rosberg Williams FW29 1:18.796 + 0.583 97
4 Michael Schumacher Ferrari F2007 1:19.136 + 0.923 58
5 Kazuki Nakajima Williams FW29 1:19.611 + 1.398 76
6 Timo Glock Toyota TF107 1:19.961 + 1.748 59
7 Felipe Massa Ferrari F2007 1:20.000 + 1.787 45
8 Sebastien Bourdais Toro Rosso STR2 1:20.033 + 1.820 87
9 Jarno Trul |
|
c********e
发帖数: 383 | 21 table里面有一个string field. 很长
要做一个query其中一个值我现在是这么搞的
(case when h.exchangereference like '%STR1%' then 'STR1' else (case when h.
exchangereference like '%STR2%' then 'STR2' end) end)
这个string很长，很多东西里面，我要使用nested case clause那得嵌套十几层，最好
能用类似c style case/switch + regex
怎么搞好啊？
谢谢 |
|
g*****g
发帖数: 34805 | 22 应该不同。str1 != str2，但是str1.equals(str2) == true
hashCode应该override了。
进一 |
|
u****s
发帖数: 2186 | 23 public static void main(String [] args)
{
String str1 = "String";
String str2 = "String";
System.out.println(str1 == str2 ? "equal":"not equal");
}
Compile error or runtime error?
What will be printed? equal or not equal? |
|
k*******d
发帖数: 701 | 24 not equal!!!
str1.equal(str2) is true;
str1==str2 is false.
== is a test of address
equal() is a test of value, and it depends on hashCode() |
|
u****s
发帖数: 2186 | 25 String str1 = "string";
String str2 = new String("string");
System.out.println(str1.intern() == str2.intern());
What will be printed?
A. true
B. false |
|
x***i
发帖数: 585 | 26 class被load到memory里。所以有一块是code segment
stack 和 heap 分别是低到高，高到低 分享以大块。
请问 string 字符串 常量 会放在哪里？
String str1 = "abcd";
String str2 = new String("abcd");
按我的理解str1 是放在一块特殊的data segment。
而str2 是放在heap里面，不知这样是否理解准确？ |
|
g**e
发帖数: 6127 | 27 string literal is saved in perm generation.
str2 is in heap like any regular class until str2.intern() is called. |
|
k******p
发帖数: 21 | 28 str1: string pool at perm
str2: heap
str1 != str2 |
|
p*********d
发帖数: 136 | 29 add a few:
?str: backward search
n: find next (after /str or ?str)
o: add new line below
O: add new line above
D: delete to end of line
yy: copy line
p: paste
cw: substitute word
s#str1#str2#: similar to s/str1/str2/ but can have special char in str |
|
p*********d
发帖数: 136 | 30 add a few:
?str: backward search
n: find next (after /str or ?str)
o: add new line below
O: add new line above
D: delete to end of line
yy: copy line
p: paste
cw: substitute word
s#str1#str2#: similar to s/str1/str2/ but can have special char in str |
|
e******d
发帖数: 310 | 31 I want to sort strings using qsort(), and try the following code, but doesn
't work. Could you please help me out. Thank you.
=============================================
#include "stdlib.h"
#include "stdio.h"
#include "string.h"
int mystrcmp(const void * str1, const void * str2)
{
return strcmp( (const char*)str1, (const char*)str2 ) ;
}
int main()
{
int n = 4;
char *pstr[] = {"God", "Bed", "Act", "Cup"};
qsort(pstr, n, sizeof(char*), mystrcmp);
int i = 0;
for(i = 0; |
|
X****r
发帖数: 3557 | 32 int mystrcmp(const void * str1, const void * str2)
{
return strcmp(*(const char* const*)str1, *(const char* const*)str2);
}
doesn |
|
G***y
发帖数: 1082 | 33 多谢多谢！包子奉上。
能不能麻烦把“从头找 matching 然后从尾巴找 matching”的code也写一下？刚开始
学python，需要一些基本知识。matching是用regular expression么？
另外一个问题是如果string里有重复怎么办，比如：
str1='ABBBYYZZ'
str2='ABBBBBYYZZYYZZ'
print difflib.SequenceMatcher(None, str1,str2).get_opcodes()
结果显示：
[('equal', 0, 1, 0, 1),
('insert', 1, 1, 1, 3),
('equal', 1, 8, 3, 10),
('insert', 8, 8, 10, 14)]
但我希望的结果是：
[('equal', 0, ３, 0, ３),
('insert', ３, ３, ４, ９),
('equal', ４, ７, 10, 14)] |
|
t********e
发帖数: 1169 | 34 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
t********e
发帖数: 1169 | 35 【 以下文字转载自 JobHunting 讨论区 】
发信人: mitbbs59 (bEQi), 信区: JobHunting
标 题: 本版1年以内的所有 面经题目，含帖子link [为大家方便]
发信站: BBS 未名空间站 (Fri Jan 29 14:20:44 2010, 美东)
不敢保证全部涵盖，大部分的都在。
我自己找了一遍，大家一起用着都方便。
不过只是含有题目的帖子 我才包含进来了，只分享经验没贴题目的 我都没有包含
进来。
大家复习着方便。
1. 一个sorted interger Array[1...N], 已知范围 1...N+1. 已知一个数字missing。
找该数字。
把原题改为unsorted，找missing数字。 performance。
2. 复制linked list。 已知每个节点有两个pointer，一个指向后一个节点，另一个指向
其他任意一节点。 O(n)时间内，无附加内存，复制该linked list。（存储不连续）
3. 一个party N个人，如果一个人不认识任何其他人，又被任何其他人认识，此人为
celeb... 阅读全帖 |
|
c****p
发帖数: 32 | 36 大部分人只知道const char*指向的位置中的data不能改变,但是不知道char str2[]这
样到底是什么意思。
实际上，C有两种aggregation type，一种是struct，一种就是数组。
比如说，如果我们有
char s[] = {'s','t','r','i'};
那么s就是一个有4个character的buffer，实际上
char s[]={'a','b,'c',0};
跟
char s[]="abc";
是等价的。
定义s的，不是后面那个"abc""string"（那只是operand而已），而是前面的
declaration，并不是说因为可以用指针指向数组，那么数组就可以是指针。
可以看看我copy的这一段：
http://www.codepp.com/default.aspx?g=posts&t=26
可以
我澄 |
|
K******g
发帖数: 1870 | 37 面试的是美国人，英语很好
一上来就问为什么申请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... 阅读全帖 |
|
c*****e
发帖数: 737 | 38 正常的程序员：
int n1, n2;
sscanf (str1,"%d",&n1);
sscanf (str2,"%d",&n2);
sprintf (buffer, "%d", n1 * n2); |
|
c*****e
发帖数: 737 | 39 正常的程序员：
int n1, n2;
sscanf (str1,"%d",&n1);
sscanf (str2,"%d",&n2);
sprintf (buffer, "%d", n1 * n2); |
|
w****o
发帖数: 2260 | 40 能具体的讲讲这个题是什么东西吗？
是不是说给了两个字符串，每个都是代表了一个很长的10进制表示的数？
比如 char str1[] = "23456789009877666555544444"
char str2[] = "346587436598437594375943875943875"
最后求出他们的乘积？ |
|
O******i
发帖数: 269 | 41 if (isScramble(str1+i, str2+(length-i), i)) return true;
这里好像不对，应该有几种情形，象LZ那样的DP转移方程 |
|
x*******6
发帖数: 262 | 42
我自己做的也是peking2一样的算法，遍历str1给str2一个pointer然后比较字符。
用hashtable的话请问如何处理重复字符问题？还有字符的顺序问题但这个应该可以用
sortedmap解决。小弟刚练算法经常问弱问题请莫见怪。。 |
|
x*******6
发帖数: 262 | 43
我自己做的也是peking2一样的算法，遍历str1给str2一个pointer然后比较字符。
用hashtable的话请问如何处理重复字符问题？还有字符的顺序问题但这个应该可以用
sortedmap解决。小弟刚练算法经常问弱问题请莫见怪。。 |
|
u*****3
发帖数: 12 | 44 第一题：如果 str1 ＝ "abc" , str2 ＝ "aaa" bulls 和 cows 分别是多少呢；（1
，2) ?
第二题： 规制是不是类似于黑白棋： 在横向和纵向上，使得两个1之间的连续的2最大
啊？
请问这到道题这么做啊？ |
|
b*****c
发帖数: 1103 | 45 strcmp does not do the trick
A value greater than zero indicates that the first character that does not
match has a greater value in str1 than in str2; And a value less than zero
indicates the opposite |
|
o****d
发帖数: 2835 | 46 you are right, using memory address is default
but the reason for most JDK classes override hashCode() is that, we always
want hashCode() to be "compatible" with equals(); that is, if a.equals(b),
then we want a.hashCode() == b.hashCode()
otherwise, if we have two string instance str1="abc", str2="abc"
then their hash values will be different, which is weird |
|
c*******r
发帖数: 309 | 47 最开始收到hr email说是直接onsite site,后来第二天说是改成了4轮skype interview
. Skype interview之后等了快一周收到hr feedback说全部positive,本来以为能给个
offer.结果hr隔了两天说还要再加三轮skype with senior managers. 上周面了两个人
之后今天说不继续Move forward因为已经有合适candidate。。。。。。
全程感觉我就是备胎.....之间等这么久后来又加面我就感觉应该被当了backup.今天hr
说manager觉得skill set不太match,这个也确实是原因之一吧，在银行it做了一年，
技术都是比较老，本身也不是cs出身，对web service之类的只是学校做过小Project.
已经面了很多公司人很疲惫，到现在一个onsite都没有.....y
面经：
Singleton pattern
String Matching(返回str2在str1中match的所有位置)
电话号码string组合（recursive写完后面试人问iterative的情况如何确定... 阅读全帖 |
|
c*******r
发帖数: 309 | 48 最开始收到hr email说是直接onsite site,后来第二天说是改成了4轮skype interview
. Skype interview之后等了快一周收到hr feedback说全部positive,本来以为能给个
offer.结果hr隔了两天说还要再加三轮skype with senior managers. 上周面了两个人
之后今天说不继续Move forward因为已经有合适candidate。。。。。。
全程感觉我就是备胎.....之间等这么久后来又加面我就感觉应该被当了backup.今天hr
说manager觉得skill set不太match,这个也确实是原因之一吧，在银行it做了一年，
技术都是比较老，本身也不是cs出身，对web service之类的只是学校做过小Project.
已经面了很多公司人很疲惫，到现在一个onsite都没有.....y
面经：
Singleton pattern
String Matching(返回str2在str1中match的所有位置)
电话号码string组合（recursive写完后面试人问iterative的情况如何确定... 阅读全帖 |
|
|
M********n
发帖数: 34 | 50 这样中不，
合并后的str， str[n] n>0 的是str1， str[n] n<0的是str2，
n从0直到end？ |
|
