贡献两道的面试题 - 未名空间MITBBS历史存档

a*22011-10-29 07:10

1 楼

1.给定一个数组（包含有重复数），找出所有可能的组合
比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
2.给定字符的三种存储方式: HH, HL, L
现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

s*n2011-10-29 07:10

2 楼

1. DP + hashtable

v*k2011-10-29 07:10

3 楼

第二个不懂

址。

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

B*12011-10-29 07:10

4 楼

1不是直接用那种n个数，就loop 1－》 2^n，看那个bit是1就输出哪个数那样子？
最多搞个hash判断一下重复吧？

【在 s******n 的大作中提到】

: 1. DP + hashtable

s*n2011-10-29 07:10

5 楼

对每个字母从0-count 加进去，然后check下一个字母
char c =KeySet[num];
int count = map.get(c);
recSub(map,stack,KeySet,num+1);
for(int i=0;istack.push(c);
recSub(m,stack,letter,num+1);
}

l*a2011-10-29 07:10

6 楼

why use hashtable
1) sort ==>used for avoid duplication
2) use recursion to get combination

【在 B*******1 的大作中提到】

: 1不是直接用那种n个数，就loop 1－》 2^n，看那个bit是1就输出哪个数那样子？
: 最多搞个hash判断一下重复吧？

B*12011-10-29 07:10

7 楼

otherwise, 1,2,2, may output 1,2 twice?

【在 l*****a 的大作中提到】

: why use hashtable
: 1) sort ==>used for avoid duplication
: 2) use recursion to get combination

S*H2011-10-29 07:10

8 楼

1. sort and count, give count_1, count_2, ..., count_p.
Then the total number is (count_1+1)(count_2+1)...(count_p+1).

址。

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

s*62011-10-29 07:10

9 楼

第二道题目没看明白。

b*t2011-10-29 07:10

10 楼

第二个其实相当于是个哈夫曼编码
不过没看出来有什么玄机就从前往后扫好了扫到包含input的那个index
自然就知道返回哪个了

【在 v*****k 的大作中提到】

: 第二个不懂
:
: 址。

b*t2011-10-29 07:10

11 楼

看来这个题是需要小于O(n)的算法想想看

【在 b******t 的大作中提到】

: 第二个其实相当于是个哈夫曼编码
: 不过没看出来有什么玄机就从前往后扫好了扫到包含input的那个index
: 自然就知道返回哪个了

a*22011-10-29 07:10

12 楼

我当时就是这么做的，backtracking

【在 S*****H 的大作中提到】

: 1. sort and count, give count_1, count_2, ..., count_p.
: Then the total number is (count_1+1)(count_2+1)...(count_p+1).
:
: 址。

a*22011-10-29 07:10

13 楼

对，我也是给了提示才做出来，关键是找特殊的pattern

【在 b******t 的大作中提到】

: 看来这个题是需要小于O(n)的算法想想看

a*22011-10-29 07:10

14 楼

如何用hash判断重复?

【在 B*******1 的大作中提到】

: 1不是直接用那种n个数，就loop 1－》 2^n，看那个bit是1就输出哪个数那样子？
: 最多搞个hash判断一下重复吧？

b*t2011-10-29 07:10

15 楼

每出现一个数a hashmap[a]++;
可以避免sorting

【在 a**********2 的大作中提到】

: 如何用hash判断重复?

b*t2011-10-29 07:10

16 楼

en 往开始的方向前找L L一定是一个结束符
然后就可以了

【在 b******t 的大作中提到】

: 看来这个题是需要小于O(n)的算法想想看

l*a2011-10-29 07:10

17 楼

void GetCombination(int a[],int size,int start,vector &vec)
{
for(int i=start;i<=size-1;i++)
{
if((i!=start)&&(a[i]==a[i-1])) continue;
vec.push_back(a[i]);
PrintCombination(vec);
if(ivec.pop_back();
}
}

【在 B*******1 的大作中提到】

: otherwise, 1,2,2, may output 1,2 twice?

B*12011-10-29 07:10

18 楼

ye. I get it.
Thanks.

【在 l*****a 的大作中提到】

: void GetCombination(int a[],int size,int start,vector &vec)
: {
: for(int i=start;i<=size-1;i++)
: {
: if((i!=start)&&(a[i]==a[i-1])) continue;
: vec.push_back(a[i]);
: PrintCombination(vec);
: if(i: vec.pop_back();
: }

s*e2011-10-29 07:10

19 楼

2nd
int findpos(int[] a, int k){
int p=0;
int i=0;
while(i<=k){
p=i;
if(a[i]=='L')
i++;
else
i+=2;
}
return p;
}

【在 b******t 的大作中提到】

: en 往开始的方向前找L L一定是一个结束符
: 然后就可以了

b*t2011-10-29 07:10

20 楼

你这个O(n)了

【在 s******e 的大作中提到】

: 2nd
: int findpos(int[] a, int k){
: int p=0;
: int i=0;
: while(i<=k){
: p=i;
: if(a[i]=='L')
: i++;
: else
: i+=2;

s*e2011-10-29 07:10

21 楼

what is the better algorithm ?

你这个O(n)了

【在 b******t 的大作中提到】

: 你这个O(n)了

b*t2011-10-29 07:10

22 楼

int findpos(int [] a,int k)
{
int p=k-1;
while(p>=0&& a[p]!='L')
p--;
int i=p+1;
while(i<=k)
{
p=i;
if(a[i]='L')
i++;
else
i+=2;
}
return p;
}

【在 s******e 的大作中提到】

: 2nd
: int findpos(int[] a, int k){
: int p=0;
: int i=0;
: while(i<=k){
: p=i;
: if(a[i]=='L')
: i++;
: else
: i+=2;

s*e2011-10-29 07:10

23 楼

how about this
int findpos(int[] a,int k) {
int p =k-1;
while(p>=0 && a[p]!='L')
p--;
if( (k-p)%2==0)
return k-1;
else
return k;
}

【在 b******t 的大作中提到】

: int findpos(int [] a,int k)
: {
: int p=k-1;
: while(p>=0&& a[p]!='L')
: p--;
: int i=p+1;
: while(i<=k)
: {
: p=i;
: if(a[i]='L')

r*g2011-10-29 07:10

24 楼

这道题的解法能不能详细讲下
貌似你先对a排序了，这样选择的时候就可以避免重复？我觉得上面那个(a1+1)(a2+1)
。。。这样的解法还好些。你这个循环里面不断的recursion，最后还vec.pop_back，
没看明白
谢谢了

【在 l*****a 的大作中提到】

: void GetCombination(int a[],int size,int start,vector &vec)
: {
: for(int i=start;i<=size-1;i++)
: {
: if((i!=start)&&(a[i]==a[i-1])) continue;
: vec.push_back(a[i]);
: PrintCombination(vec);
: if(i: vec.pop_back();
: }

a*22011-10-29 07:10

25 楼

就是这个意思，我当时脑子不转了被提示了半天才想到，真是功力不够

【在 s******e 的大作中提到】

: how about this
: int findpos(int[] a,int k) {
: int p =k-1;
: while(p>=0 && a[p]!='L')
: p--;
: if( (k-p)%2==0)
: return k-1;
: else
: return k;
: }

r*g2011-10-29 07:10

26 楼

睡了一觉起来发现看懂了，收藏这种方法了，我一直都是坚持(1+a1)(1+a2)....或者1-
2^n那种算法。

【在 l*****a 的大作中提到】

: void GetCombination(int a[],int size,int start,vector &vec)
: {
: for(int i=start;i<=size-1;i++)
: {
: if((i!=start)&&(a[i]==a[i-1])) continue;
: vec.push_back(a[i]);
: PrintCombination(vec);
: if(i: vec.pop_back();
: }

s*f2011-10-29 07:10

27 楼

void GetAllComb_(char *str, vector *ret){
static vector vc;
if (!*str){
ret->push_back(string(vc.begin(), vc.end()));
return;
}
char *p = str + 1;
while (*p == *str)
++p;
GetAllComb_(p, ret);
for (int i = 0; i < p - str; ++i){
vc.push_back(*str);
GetAllComb_(p, ret);
}
while (!vc.empty() && vc.back() == *str)
vc.pop_back();
}
void GetAllComb(char *str, vector *ret){
if (!str)
return;
if (!*str){
ret->push_back(string());
return;
}
int len = strlen(str);
sort(str, str + len);
GetAllComb_(str, ret);
}

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

q*x2011-10-29 07:10

28 楼

假设unique value x[i]，每个有k[i]个，变换成选择问题。每个x[i]有k[i]+1种选法。
址。
要点是正确识别变长字符。扫描时记住每个字符的首地址。

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

a*22011-10-29 07:10

29 楼

1.给定一个数组（包含有重复数），找出所有可能的组合
比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
2.给定字符的三种存储方式: HH, HL, L
现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

s*n2011-10-29 07:10

30 楼

1. DP + hashtable

v*k2011-10-29 07:10

31 楼

第二个不懂

址。

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

B*12011-10-29 07:10

32 楼

1不是直接用那种n个数，就loop 1－》 2^n，看那个bit是1就输出哪个数那样子？
最多搞个hash判断一下重复吧？

【在 s******n 的大作中提到】

: 1. DP + hashtable

s*n2011-10-29 07:10

33 楼

对每个字母从0-count 加进去，然后check下一个字母
char c =KeySet[num];
int count = map.get(c);
recSub(map,stack,KeySet,num+1);
for(int i=0;istack.push(c);
recSub(m,stack,letter,num+1);
}

l*a2011-10-29 07:10

34 楼

why use hashtable
1) sort ==>used for avoid duplication
2) use recursion to get combination

【在 B*******1 的大作中提到】

: 1不是直接用那种n个数，就loop 1－》 2^n，看那个bit是1就输出哪个数那样子？
: 最多搞个hash判断一下重复吧？

B*12011-10-29 07:10

35 楼

otherwise, 1,2,2, may output 1,2 twice?

【在 l*****a 的大作中提到】

: why use hashtable
: 1) sort ==>used for avoid duplication
: 2) use recursion to get combination

S*H2011-10-29 07:10

36 楼

1. sort and count, give count_1, count_2, ..., count_p.
Then the total number is (count_1+1)(count_2+1)...(count_p+1).

址。

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

s*62011-10-29 07:10

37 楼

第二道题目没看明白。

b*t2011-10-29 07:10

38 楼

第二个其实相当于是个哈夫曼编码
不过没看出来有什么玄机就从前往后扫好了扫到包含input的那个index
自然就知道返回哪个了

【在 v*****k 的大作中提到】

: 第二个不懂
:
: 址。

b*t2011-10-29 07:10

39 楼

看来这个题是需要小于O(n)的算法想想看

【在 b******t 的大作中提到】

: 第二个其实相当于是个哈夫曼编码
: 不过没看出来有什么玄机就从前往后扫好了扫到包含input的那个index
: 自然就知道返回哪个了

a*22011-10-29 07:10

40 楼

我当时就是这么做的，backtracking

【在 S*****H 的大作中提到】

: 1. sort and count, give count_1, count_2, ..., count_p.
: Then the total number is (count_1+1)(count_2+1)...(count_p+1).
:
: 址。

a*22011-10-29 07:10

41 楼

对，我也是给了提示才做出来，关键是找特殊的pattern

【在 b******t 的大作中提到】

: 看来这个题是需要小于O(n)的算法想想看

a*22011-10-29 07:10

42 楼

如何用hash判断重复?

【在 B*******1 的大作中提到】

: 1不是直接用那种n个数，就loop 1－》 2^n，看那个bit是1就输出哪个数那样子？
: 最多搞个hash判断一下重复吧？

b*t2011-10-29 07:10

43 楼

每出现一个数a hashmap[a]++;
可以避免sorting

【在 a**********2 的大作中提到】

: 如何用hash判断重复?

b*t2011-10-29 07:10

44 楼

en 往开始的方向前找L L一定是一个结束符
然后就可以了

【在 b******t 的大作中提到】

: 看来这个题是需要小于O(n)的算法想想看

l*a2011-10-29 07:10

45 楼

void GetCombination(int a[],int size,int start,vector &vec)
{
for(int i=start;i<=size-1;i++)
{
if((i!=start)&&(a[i]==a[i-1])) continue;
vec.push_back(a[i]);
PrintCombination(vec);
if(ivec.pop_back();
}
}

【在 B*******1 的大作中提到】

: otherwise, 1,2,2, may output 1,2 twice?

B*12011-10-29 07:10

46 楼

ye. I get it.
Thanks.

【在 l*****a 的大作中提到】

: void GetCombination(int a[],int size,int start,vector &vec)
: {
: for(int i=start;i<=size-1;i++)
: {
: if((i!=start)&&(a[i]==a[i-1])) continue;
: vec.push_back(a[i]);
: PrintCombination(vec);
: if(i: vec.pop_back();
: }

s*e2011-10-29 07:10

47 楼

2nd
int findpos(int[] a, int k){
int p=0;
int i=0;
while(i<=k){
p=i;
if(a[i]=='L')
i++;
else
i+=2;
}
return p;
}

【在 b******t 的大作中提到】

: en 往开始的方向前找L L一定是一个结束符
: 然后就可以了

b*t2011-10-29 07:10

48 楼

你这个O(n)了

【在 s******e 的大作中提到】

: 2nd
: int findpos(int[] a, int k){
: int p=0;
: int i=0;
: while(i<=k){
: p=i;
: if(a[i]=='L')
: i++;
: else
: i+=2;

s*e2011-10-29 07:10

49 楼

what is the better algorithm ?

你这个O(n)了

【在 b******t 的大作中提到】

: 你这个O(n)了

b*t2011-10-29 07:10

50 楼

int findpos(int [] a,int k)
{
int p=k-1;
while(p>=0&& a[p]!='L')
p--;
int i=p+1;
while(i<=k)
{
p=i;
if(a[i]='L')
i++;
else
i+=2;
}
return p;
}

【在 s******e 的大作中提到】

: 2nd
: int findpos(int[] a, int k){
: int p=0;
: int i=0;
: while(i<=k){
: p=i;
: if(a[i]=='L')
: i++;
: else
: i+=2;

s*e2011-10-29 07:10

51 楼

how about this
int findpos(int[] a,int k) {
int p =k-1;
while(p>=0 && a[p]!='L')
p--;
if( (k-p)%2==0)
return k-1;
else
return k;
}

【在 b******t 的大作中提到】

: int findpos(int [] a,int k)
: {
: int p=k-1;
: while(p>=0&& a[p]!='L')
: p--;
: int i=p+1;
: while(i<=k)
: {
: p=i;
: if(a[i]='L')

r*g2011-10-29 07:10

52 楼

这道题的解法能不能详细讲下
貌似你先对a排序了，这样选择的时候就可以避免重复？我觉得上面那个(a1+1)(a2+1)
。。。这样的解法还好些。你这个循环里面不断的recursion，最后还vec.pop_back，
没看明白
谢谢了

【在 l*****a 的大作中提到】

: void GetCombination(int a[],int size,int start,vector &vec)
: {
: for(int i=start;i<=size-1;i++)
: {
: if((i!=start)&&(a[i]==a[i-1])) continue;
: vec.push_back(a[i]);
: PrintCombination(vec);
: if(i: vec.pop_back();
: }

a*22011-10-29 07:10

53 楼

就是这个意思，我当时脑子不转了被提示了半天才想到，真是功力不够

【在 s******e 的大作中提到】

: how about this
: int findpos(int[] a,int k) {
: int p =k-1;
: while(p>=0 && a[p]!='L')
: p--;
: if( (k-p)%2==0)
: return k-1;
: else
: return k;
: }

r*g2011-10-29 07:10

54 楼

睡了一觉起来发现看懂了，收藏这种方法了，我一直都是坚持(1+a1)(1+a2)....或者1-
2^n那种算法。

【在 l*****a 的大作中提到】

: void GetCombination(int a[],int size,int start,vector &vec)
: {
: for(int i=start;i<=size-1;i++)
: {
: if((i!=start)&&(a[i]==a[i-1])) continue;
: vec.push_back(a[i]);
: PrintCombination(vec);
: if(i: vec.pop_back();
: }

s*f2011-10-29 07:10

55 楼

void GetAllComb_(char *str, vector *ret){
static vector vc;
if (!*str){
ret->push_back(string(vc.begin(), vc.end()));
return;
}
char *p = str + 1;
while (*p == *str)
++p;
GetAllComb_(p, ret);
for (int i = 0; i < p - str; ++i){
vc.push_back(*str);
GetAllComb_(p, ret);
}
while (!vc.empty() && vc.back() == *str)
vc.pop_back();
}
void GetAllComb(char *str, vector *ret){
if (!str)
return;
if (!*str){
ret->push_back(string());
return;
}
int len = strlen(str);
sort(str, str + len);
GetAllComb_(str, ret);
}

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

q*x2011-10-29 07:10

56 楼

假设unique value x[i]，每个有k[i]个，变换成选择问题。每个x[i]有k[i]+1种选法。
址。
要点是正确识别变长字符。扫描时记住每个字符的首地址。

【在 a**********2 的大作中提到】

: 1.给定一个数组（包含有重复数），找出所有可能的组合
: 比方说1，2，2，那么组合有()，(1),(2),(1,2),(2,2),(1,2,2）
: 2.给定字符的三种存储方式: HH, HL, L
: 现在给定一个包含H和L的长序列和一个数组地址，要求找出这个地址所在字符的首地址。
: i.e. input HLHHHLHHH... 和 6 返回 6 因为 HL|HH|HL|HH|H....
: input HLHHHLHHH... 和 7 返回 6 同样因为HL|HH|HL|HH|H...

x*72011-10-29 07:10

57 楼

没看懂，能解释下思路？printcombination是打印整个vector?

1-

【在 r*******g 的大作中提到】

: 睡了一觉起来发现看懂了，收藏这种方法了，我一直都是坚持(1+a1)(1+a2)....或者1-
: 2^n那种算法。