给最近三部电影排序 - 未名空间MITBBS历史存档

a*x2015-05-27 07:05

1 楼

昨天刚面完的，面的Ads platform,自己的目标达到了，见到了第五个人：manager。
上午10：00到building111，11：30才开始第一个interview，而且第一个上来就是
lunch interview，她先把我带到她office面了45分钟，然后再到25楼吃lunch。问题有
：介绍你的intern,你的最challended的project? 假设你在做一个project，时间不够
，但是requirments又老在变，你怎么办？array和linkedlist的区别，什么情况下选哪
个？coding问的是给一个BST,返回最长的path from root to leaf,code完给test case
.lunch interview也是和她吃的，人很nice，基本不问我啥问题，就是聊天吧，在25楼
吃lunch，风景很不错：）
1:00-2:00,第二个人：为什么转专业？说说你上过的课，哪些你觉得最有意思，说个
不在resume上的project. coding: 给一个数组，去掉duplicate；给数据库的两个表，
一个是ID和person n

s*u2015-05-27 07:05

2 楼

今年夏天要带7岁的儿子回国，不知道应该恰到好处地进行安全教育。

s*e2015-05-27 07:05

3 楼

pitch perfect 2 （PP）>Mad Max (MM) =Ex Machina (EM)
PP，MM和EM都是没有故事的电影。尤其是MM 和 EM，就是种情怀。没有任何给我惊喜的地
方。反而PP坐在影院听唱歌，是种不错的享受。

n*t2015-05-27 07:05

4 楼

多谢分享。
这些behavior问题怎么回答比较好？比如requirements老变，或者deadline快到了，还
有teammate意见不和，和领导意见不和等

case

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

: 昨天刚面完的，面的Ads platform,自己的目标达到了，见到了第五个人：manager。
: 上午10：00到building111，11：30才开始第一个interview，而且第一个上来就是
: lunch interview，她先把我带到她office面了45分钟，然后再到25楼吃lunch。问题有
: ：介绍你的intern,你的最challended的project? 假设你在做一个project，时间不够
: ，但是requirments又老在变，你怎么办？array和linkedlist的区别，什么情况下选哪
: 个？coding问的是给一个BST,返回最长的path from root to leaf,code完给test case
: .lunch interview也是和她吃的，人很nice，基本不问我啥问题，就是聊天吧，在25楼
: 吃lunch，风景很不错：）
: 1:00-2:00,第二个人：为什么转专业？说说你上过的课，哪些你觉得最有意思，说个
: 不在resume上的project. coding: 给一个数组，去掉duplicate；给数据库的两个表，

x*j2015-05-27 07:05

5 楼

应该的，应该的，另外大人看紧一些。

b*e2015-05-27 07:05

6 楼

pp主要是女的都太丑

的地

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

: pitch perfect 2 （PP）>Mad Max (MM) =Ex Machina (EM)
: PP，MM和EM都是没有故事的电影。尤其是MM 和 EM，就是种情怀。没有任何给我惊喜的地
: 方。反而PP坐在影院听唱歌，是种不错的享受。

m*92015-05-27 07:05

7 楼

面的挺不错的，祝福lz顺利拿到offer

s*u2015-05-27 07:05

8 楼

应该如何恰到好处地进行安全教育呢？

s*e2015-05-27 07:05

9 楼

我最喜欢那个德国女的了
戳中了我的G点
按理说MM中的女人该更好看吧
可就是对超模没感觉
不真实

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

: pp主要是女的都太丑
:
: 的地

t*r2015-05-27 07:05

10 楼

面的挺好的！祝福！
是 MS Bellevue 的 Office？谢！

s*u2015-05-27 07:05

11 楼

再问，应该如何恰到好处地进行安全教育呢？

l*e2015-05-27 07:05

12 楼

这个周末决定去把这三个都看一遍，哇哈哈

a*x2015-05-27 07:05

13 楼

结合自身例子吧。对于requirements老变，可以prioritize,先做必须的紧急的，其他
的再慢慢做。。

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

: 多谢分享。
: 这些behavior问题怎么回答比较好？比如requirements老变，或者deadline快到了，还
: 有teammate意见不和，和领导意见不和等
:
: case

e*e2015-05-27 07:05

14 楼

我觉得头一条就是，出门要牵大人手，紧跟大人的脚步，不许乱跑。

t*02015-05-27 07:05

15 楼

pp的歌确实不错

a*x2015-05-27 07:05

16 楼

对，楼好新好高，呵呵

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

: 面的挺好的！祝福！
: 是 MS Bellevue 的 Office？谢！

b*s2015-05-27 07:05

17 楼

就跟他说要跟紧大人，中国人多，容易走失，走丢了，被坏人骗走了，就再回不到家
了。
还有就是不要跟着陌生人走，就是穿着警察的衣服的人也不能走。不吃别人给的食物
，除非妈妈同意的。

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

: 再问，应该如何恰到好处地进行安全教育呢？

x*o2015-05-27 07:05

18 楼

一张票还是三张票？

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

: 这个周末决定去把这三个都看一遍，哇哈哈

c*f2015-05-27 07:05

19 楼

感觉答得很好啊会有Offer的祝福！

s*u2015-05-27 07:05

20 楼

THANKS

h*e2015-05-27 07:05

21 楼

其实只要里面有人，帮忙推开一下门，票都不用。

【在 x****o 的大作中提到】

: 一张票还是三张票？

j*l2015-05-27 07:05

22 楼

BST,返回最长的path from root to leaf
和BST有什么关系？不就是普通二叉树求最大高度？

l*r2015-05-27 07:05

23 楼

这个回不回中国都是要教育的呀，公共场合跟住爸爸妈妈，不合陌生人说话，走，吃东西
回中国要特别小心过马路吧。

d*92015-05-27 07:05

24 楼

这是女观众的排序吧男的估计正好倒过来呵呵

的地

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

: pitch perfect 2 （PP）>Mad Max (MM) =Ex Machina (EM)
: PP，MM和EM都是没有故事的电影。尤其是MM 和 EM，就是种情怀。没有任何给我惊喜的地
: 方。反而PP坐在影院听唱歌，是种不错的享受。

l*a2015-05-27 07:05

25 楼

DP for the last one???
i think we can get it directly with 2 loops
or suffix array/generalized suffix tree

case

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

: 昨天刚面完的，面的Ads platform,自己的目标达到了，见到了第五个人：manager。
: 上午10：00到building111，11：30才开始第一个interview，而且第一个上来就是
: lunch interview，她先把我带到她office面了45分钟，然后再到25楼吃lunch。问题有
: ：介绍你的intern,你的最challended的project? 假设你在做一个project，时间不够
: ，但是requirments又老在变，你怎么办？array和linkedlist的区别，什么情况下选哪
: 个？coding问的是给一个BST,返回最长的path from root to leaf,code完给test case
: .lunch interview也是和她吃的，人很nice，基本不问我啥问题，就是聊天吧，在25楼
: 吃lunch，风景很不错：）
: 1:00-2:00,第二个人：为什么转专业？说说你上过的课，哪些你觉得最有意思，说个
: 不在resume上的project. coding: 给一个数组，去掉duplicate；给数据库的两个表，

w*m2015-05-27 07:05

26 楼

说到过马路，我现在还胆战心惊。我家在一个省会城市，应该不算是管理混乱的地方，
可是好多路口有过马路的斑马线，却没有红绿灯。我抱着娃看着车嗖嗖的开过去，就是
不敢过。

东西

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

: 这个回不回中国都是要教育的呀，公共场合跟住爸爸妈妈，不合陌生人说话，走，吃东西
: 回中国要特别小心过马路吧。

r*e2015-05-27 07:05

27 楼

pp挺好看的啊
青春歌舞片

【在 d**********9 的大作中提到】

: 这是女观众的排序吧男的估计正好倒过来呵呵
:
: 的地

m*g2015-05-27 07:05

28 楼

这个DP应该是最简单直接最符合题目条件的

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

: DP for the last one???
: i think we can get it directly with 2 loops
: or suffix array/generalized suffix tree
:
: case

m*a2015-05-27 07:05

29 楼

最重要的是不要把孩子丢了

b*e2015-05-27 07:05

30 楼

女的太丑啊

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

: pp挺好看的啊
: 青春歌舞片

l*a2015-05-27 07:05

31 楼

assume that f(n-1)=k the number when we have n-1 characters.
then find whether we have more palindrom when we have a[n-1].
but seems that this step is also O(n)

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

: 这个DP应该是最简单直接最符合题目条件的

d*k2015-05-27 07:05

32 楼

赞体力，上次在电影院一口气看两部还是Death Proof和Grindhouse，累呀。

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

: 这个周末决定去把这三个都看一遍，哇哈哈

c*n2015-05-27 07:05

33 楼

palindrome那题怎么用DP做啊？

case

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

: 昨天刚面完的，面的Ads platform,自己的目标达到了，见到了第五个人：manager。
: 上午10：00到building111，11：30才开始第一个interview，而且第一个上来就是
: lunch interview，她先把我带到她office面了45分钟，然后再到25楼吃lunch。问题有
: ：介绍你的intern,你的最challended的project? 假设你在做一个project，时间不够
: ，但是requirments又老在变，你怎么办？array和linkedlist的区别，什么情况下选哪
: 个？coding问的是给一个BST,返回最长的path from root to leaf,code完给test case
: .lunch interview也是和她吃的，人很nice，基本不问我啥问题，就是聊天吧，在25楼
: 吃lunch，风景很不错：）
: 1:00-2:00,第二个人：为什么转专业？说说你上过的课，哪些你觉得最有意思，说个
: 不在resume上的project. coding: 给一个数组，去掉duplicate；给数据库的两个表，

s*e2015-05-27 07:05

34 楼

你看过这三部没有？
我可是买了票
花了三个weekend的
为了看MM还买的16刀的AMC ETX
你能告诉我小时候看过北斗神拳的人这MM有一点点新意吗？
真没什么意思
EM就更扯淡了
男主角性他妈饥渴疯掉了
跟个机器人谈一次话就爱的死去活来
完全没道理
再说机器人这爆发力
有心思“勾引”饥渴男
干死光头男也就是她想不想的事情
比如拿根笔就能戳死他
都是毫无故事，毫无逻辑
还不如看PP

【在 d**********9 的大作中提到】

: 这是女观众的排序吧男的估计正好倒过来呵呵
:
: 的地

a*x2015-05-27 07:05

35 楼

我先给的N^3,问有什么改进? 我第一个念头也是suffix tree，后来马上意识到DP更直
接，也好code

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

: DP for the last one???
: i think we can get it directly with 2 loops
: or suffix array/generalized suffix tree
:
: case

s*e2015-05-27 07:05

36 楼

你这是有多饥渴？

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

: 女的太丑啊

a*x2015-05-27 07:05

37 楼

对，code完后，讨论时说也可以适用于BT。

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

: BST,返回最长的path from root to leaf
: 和BST有什么关系？不就是普通二叉树求最大高度？

b*e2015-05-27 07:05

38 楼

这跟即可有关系么，一群丑女演青春片有毛好看

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

: 你这是有多饥渴？

a*x2015-05-27 07:05

39 楼

L(i,j) = L(i+1,j-1) && (str[i] == str[j] )

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

: palindrome那题怎么用DP做啊？
:
: case

r*e2015-05-27 07:05

40 楼

fat amy很有意思啊
喜感

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

: 这跟即可有关系么，一群丑女演青春片有毛好看

w*m2015-05-27 07:05

41 楼

这个要是是返回max height还是whole path啊?

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

: 对，code完后，讨论时说也可以适用于BT。

z*n2015-05-27 07:05

42 楼

在车上背动看过1，觉得那些人好没表演啊，呵呵
里边两个亚女全是被嘲笑的对象
乐队里那个亚女更是，里边有个情节那个白女吐了一地，然后亚女躺在呕吐物上边玩蝴蝶

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

: 这跟即可有关系么，一群丑女演青春片有毛好看

j*l2015-05-27 07:05

43 楼

最后一题，莫非是先求string的逆，然后求原string和逆string的common substring,
用解决Longest Common Substring的DP方法？

case

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

: 昨天刚面完的，面的Ads platform,自己的目标达到了，见到了第五个人：manager。
: 上午10：00到building111，11：30才开始第一个interview，而且第一个上来就是
: lunch interview，她先把我带到她office面了45分钟，然后再到25楼吃lunch。问题有
: ：介绍你的intern,你的最challended的project? 假设你在做一个project，时间不够
: ，但是requirments又老在变，你怎么办？array和linkedlist的区别，什么情况下选哪
: 个？coding问的是给一个BST,返回最长的path from root to leaf,code完给test case
: .lunch interview也是和她吃的，人很nice，基本不问我啥问题，就是聊天吧，在25楼
: 吃lunch，风景很不错：）
: 1:00-2:00,第二个人：为什么转专业？说说你上过的课，哪些你觉得最有意思，说个
: 不在resume上的project. coding: 给一个数组，去掉duplicate；给数据库的两个表，

s*e2015-05-27 07:05

44 楼

可以听唱歌啊
除了鸡巴
我们还有耳朵和大脑啊

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

: 这跟即可有关系么，一群丑女演青春片有毛好看

j*l2015-05-27 07:05

45 楼

感觉MSFT的招人门槛有降低的趋势阿，难度都没有那么刁钻，长老级的题目少了，就是
考察基本功。

l*e2015-05-27 07:05

46 楼

如果不会太累就是一张
如果看完一个或者两个太累了就分两天去

【在 x****o 的大作中提到】

: 一张票还是三张票？

c*n2015-05-27 07:05

47 楼

多谢指教，用你的思想写了下code,各位看看对不对：
//L[i][j] = L[i+1][j-1] && s[i]==s[j]
public static int findNumberOfPalindrom(String str){
boolean[][] L = new boolean[str.length()][str.length()];
int count=0;
//Init
int i;
for(i=0;iL[i][i]=true;
}
//From substring with length 3 to max length
for(int k = 2;kfor(i=0;iL[i][i+k]=L[i+1][i

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

: L(i,j) = L(i+1,j-1) && (str[i] == str[j] )

j*l2015-05-27 07:05

48 楼

求一个字符串s的最长palindrome, 一般是求s和rev(s)的LCSubString, 用DP
这么说也可以用你的思路直接用DP，不涉及rev(s)
bool L[MAX][MAX] = {false};
int LongestPalindrome(char str[], int N)
{
int length = 1;
for (int i = 0; i < N; i++)
for (int j = 0; j <= i; j++)
L[i][j] = true;
for (int k = 1; k < N; k++)
{
for (int i = 0; i + k < N; i++)
{
L[i][i+k] = L[i+1][i+k-1] && str[i] == str[i+k];

if (L[i][i+k] && (k + 1) > length)
length = k +

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

: 多谢指教，用你的思想写了下code,各位看看对不对：
: //L[i][j] = L[i+1][j-1] && s[i]==s[j]
: public static int findNumberOfPalindrom(String str){
: boolean[][] L = new boolean[str.length()][str.length()];
: int count=0;
: //Init
: int i;
: for(i=0;i: L[i][i]=true;
: }

c*n2015-05-27 07:05

49 楼

恩，看上去代码没什么问题

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

: 求一个字符串s的最长palindrome, 一般是求s和rev(s)的LCSubString, 用DP
: 这么说也可以用你的思路直接用DP，不涉及rev(s)
: bool L[MAX][MAX] = {false};
: int LongestPalindrome(char str[], int N)
: {
: int length = 1;
: for (int i = 0; i < N; i++)
: for (int j = 0; j <= i; j++)
: L[i][j] = true;
: for (int k = 1; k < N; k++)

j*l2015-05-27 07:05

50 楼

用Reverse String + LCSubString的方法
int C[MAX][MAX];
int findNumberOfOddPalindrome(char str[], int N)
{
int count = 0;
for (int i = 0; i <= N; i++)
for (int j = 0; j <= N; j++)
C[i][j] = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (str[i - 1] == str[(N + 1 - j) - 1])
{
C[i][j] = C[i-1][j-1] + 1;
if (C[i][j] > 1 && C[i][j] % 2 == 1)
count++;

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

: 多谢指教，用你的思想写了下code,各位看看对不对：
: //L[i][j] = L[i+1][j-1] && s[i]==s[j]
: public static int findNumberOfPalindrom(String str){
: boolean[][] L = new boolean[str.length()][str.length()];
: int count=0;
: //Init
: int i;
: for(i=0;i: L[i][i]=true;
: }

j*l2015-05-27 07:05

51 楼

总结一下好了。
涉及一个string的palindrome，包括求最长，求所有奇数长，求所有偶数长
可以用以下两种方法
方法一，化归为求string和逆string的LCSubString, 可以用DP, 也可以用suffix tree
方法二，直接用DP, 利用L[i][j] = L[i+1][j-1] && s[i] == s[j]
我们可以规定，当i >= j的时候L[i][j] = true
这样，对特殊情形L[i][i+1]也适用L[i][j] = L[i+1][j-1] && s[i] == s[j]
二重循环的技巧是，
第一重是步长k, palindrome的长度为k+1
第二重是palindrome的起始点i
下面的例子只是找所有长度大于1的奇数
for (int k = 2; k < N; k += 2)
for (i = 0; i < N - k; i++)
如果找所有长度为偶数的呢，那就可以改为
for (int k = 1; k < N; k += 2)
如果找全部长度不为1的呢，那就改为
for (int k = 1; k < N; k++)

l*a2015-05-27 07:05

52 楼

sorry that I am still confused what is the benefit to use the so-called
DP.
did u improved time complexity or saved space?
at least I think that the two dimensions array is definitely useless.
My code is as below,I think it is clear and directly.
count=0;
for(i=1;i<=n-2;i++) //a[i] is the possible central of palindrome
for(k=1;(i-k>=0)&&(i+k<=n-1);k++)
if (a[i-k]==a[i+k]) count++;
else break;
correct me if i am wrong.
thanks very much

tree

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

: 总结一下好了。
: 涉及一个string的palindrome，包括求最长，求所有奇数长，求所有偶数长
: 可以用以下两种方法
: 方法一，化归为求string和逆string的LCSubString, 可以用DP, 也可以用suffix tree
: 方法二，直接用DP, 利用L[i][j] = L[i+1][j-1] && s[i] == s[j]
: 我们可以规定，当i >= j的时候L[i][j] = true
: 这样，对特殊情形L[i][i+1]也适用L[i][j] = L[i+1][j-1] && s[i] == s[j]
: 二重循环的技巧是，
: 第一重是步长k, palindrome的长度为k+1
: 第二重是palindrome的起始点i

l*a2015-05-27 07:05

53 楼

==>说个你最喜欢的DS或algorithm
what does DS mean?

case

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

: 昨天刚面完的，面的Ads platform,自己的目标达到了，见到了第五个人：manager。
: 上午10：00到building111，11：30才开始第一个interview，而且第一个上来就是
: lunch interview，她先把我带到她office面了45分钟，然后再到25楼吃lunch。问题有
: ：介绍你的intern,你的最challended的project? 假设你在做一个project，时间不够
: ，但是requirments又老在变，你怎么办？array和linkedlist的区别，什么情况下选哪
: 个？coding问的是给一个BST,返回最长的path from root to leaf,code完给test case
: .lunch interview也是和她吃的，人很nice，基本不问我啥问题，就是聊天吧，在25楼
: 吃lunch，风景很不错：）
: 1:00-2:00,第二个人：为什么转专业？说说你上过的课，哪些你觉得最有意思，说个
: 不在resume上的project. coding: 给一个数组，去掉duplicate；给数据库的两个表，

j*l2015-05-27 07:05

54 楼

DP may not be the best solution, but it is classic and easy to use to solve
a set of problems including LCSubSequence, LCSubString...
In an interview, you first provide a straight solution that comes to you,
right?

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

: sorry that I am still confused what is the benefit to use the so-called
: DP.
: did u improved time complexity or saved space?
: at least I think that the two dimensions array is definitely useless.
: My code is as below,I think it is clear and directly.
: count=0;
: for(i=1;i<=n-2;i++) //a[i] is the possible central of palindrome
: for(k=1;(i-k>=0)&&(i+k<=n-1);k++)
: if (a[i-k]==a[i+k]) count++;
: else break;

m*g2015-05-27 07:05

55 楼

你的方法一好像是不行的
例如 abcxxxxxxcbaxxxx，这个反过来会找到abc，但是这个不是解
方法二的dp一直都没看懂，也没人解释一下
那个二重循环最简单直接。而且对方限定了不为1的奇数解，感觉就是要那个方法。

tree

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

: 总结一下好了。
: 涉及一个string的palindrome，包括求最长，求所有奇数长，求所有偶数长
: 可以用以下两种方法
: 方法一，化归为求string和逆string的LCSubString, 可以用DP, 也可以用suffix tree
: 方法二，直接用DP, 利用L[i][j] = L[i+1][j-1] && s[i] == s[j]
: 我们可以规定，当i >= j的时候L[i][j] = true
: 这样，对特殊情形L[i][i+1]也适用L[i][j] = L[i+1][j-1] && s[i] == s[j]
: 二重循环的技巧是，
: 第一重是步长k, palindrome的长度为k+1
: 第二重是palindrome的起始点i

c*n2015-05-27 07:05

56 楼

确实，我也觉得reverse + LCSubstring是有问题的
对于这个问题那个二重循环确实更简单一点

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

: 你的方法一好像是不行的
: 例如 abcxxxxxxcbaxxxx，这个反过来会找到abc，但是这个不是解
: 方法二的dp一直都没看懂，也没人解释一下
: 那个二重循环最简单直接。而且对方限定了不为1的奇数解，感觉就是要那个方法。
:
: tree

k*n2015-05-27 07:05

57 楼

re

j*l2015-05-27 07:05

58 楼

方法一DP确实不行，小尾羊说要用suffix tree做。
方法二的那个DP, 暂时没看出有什么问题。
对这道题，二重循环也够用了，DP可能是牛刀

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

: 你的方法一好像是不行的
: 例如 abcxxxxxxcbaxxxx，这个反过来会找到abc，但是这个不是解
: 方法二的dp一直都没看懂，也没人解释一下
: 那个二重循环最简单直接。而且对方限定了不为1的奇数解，感觉就是要那个方法。
:
: tree

c*f2015-05-27 07:05

59 楼

我也觉得你这个是对的，这其实就有DP的思想

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

: sorry that I am still confused what is the benefit to use the so-called
: DP.
: did u improved time complexity or saved space?
: at least I think that the two dimensions array is definitely useless.
: My code is as below,I think it is clear and directly.
: count=0;
: for(i=1;i<=n-2;i++) //a[i] is the possible central of palindrome
: for(k=1;(i-k>=0)&&(i+k<=n-1);k++)
: if (a[i-k]==a[i+k]) count++;
: else break;

z*e2015-05-27 07:05

60 楼

I like your solution, simple, clean, easy to maintain.
yes, DP is common for LCS alike problems. However, this problem, is not the
type for DP. If people try to struggle with DP/Suffix, he is simply waste
time (OK, you will be super if you can do it by DP on whiteboard without ANY
bug within 15 mins).
many ppl like to talk about suffix tree --- can u really code it within 10
mins on whiteboard?

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

: sorry that I am still confused what is the benefit to use the so-called
: DP.
: did u improved time complexity or saved space?
: at least I think that the two dimensions array is definitely useless.
: My code is as below,I think it is clear and directly.
: count=0;
: for(i=1;i<=n-2;i++) //a[i] is the possible central of palindrome
: for(k=1;(i-k>=0)&&(i+k<=n-1);k++)
: if (a[i-k]==a[i+k]) count++;
: else break;

j*l2015-05-27 07:05

61 楼

Data Structure?

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

: ==>说个你最喜欢的DS或algorithm
: what does DS mean?
:
: case

y*i2015-05-27 07:05

62 楼

strictly speaking, the inner loop is DP.

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

: sorry that I am still confused what is the benefit to use the so-called
: DP.
: did u improved time complexity or saved space?
: at least I think that the two dimensions array is definitely useless.
: My code is as below,I think it is clear and directly.
: count=0;
: for(i=1;i<=n-2;i++) //a[i] is the possible central of palindrome
: for(k=1;(i-k>=0)&&(i+k<=n-1);k++)
: if (a[i-k]==a[i+k]) count++;
: else break;

h*k2015-05-27 07:05

63 楼

tree
感觉你这里两重循环写的不对。k固定时，i变化（比如从0到1），你怎么判断新的
substring是不是palindrome? 这里肯定要求判断的时间是O(1)，所以必须利用前一个i
的结果。

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

: 总结一下好了。
: 涉及一个string的palindrome，包括求最长，求所有奇数长，求所有偶数长
: 可以用以下两种方法
: 方法一，化归为求string和逆string的LCSubString, 可以用DP, 也可以用suffix tree
: 方法二，直接用DP, 利用L[i][j] = L[i+1][j-1] && s[i] == s[j]
: 我们可以规定，当i >= j的时候L[i][j] = true
: 这样，对特殊情形L[i][i+1]也适用L[i][j] = L[i+1][j-1] && s[i] == s[j]
: 二重循环的技巧是，
: 第一重是步长k, palindrome的长度为k+1
: 第二重是palindrome的起始点i

r*o2015-05-27 07:05

64 楼

请问求s和rev(s)的LCSubString这个方法是100%正确吗？
如果s="abcdefg1ddadd2gfedcba"，
这个方法是不是会返回abcdefg而不是ddadd?

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

: 求一个字符串s的最长palindrome, 一般是求s和rev(s)的LCSubString, 用DP
: 这么说也可以用你的思路直接用DP，不涉及rev(s)
: bool L[MAX][MAX] = {false};
: int LongestPalindrome(char str[], int N)
: {
: int length = 1;
: for (int i = 0; i < N; i++)
: for (int j = 0; j <= i; j++)
: L[i][j] = true;
: for (int k = 1; k < N; k++)

c*n2015-05-27 07:05

65 楼

不正确，还是用DP

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

: 请问求s和rev(s)的LCSubString这个方法是100%正确吗？
: 如果s="abcdefg1ddadd2gfedcba"，
: 这个方法是不是会返回abcdefg而不是ddadd?

a*y2015-05-27 07:05

66 楼

那个database怎么做？这个看着简单其实不简单啊，你grand parent的孙子之间是
cousin，但是grand grand parent 的孙子以下辈份的在同一辈的都是cousin啊，跨一
个辈分的是second cousin
这个玩意应该是个recursive call。谁能给说下

D*62015-05-27 07:05

67 楼

同问Database的题．
还有，是用SQL?

D*62015-05-27 07:05

68 楼

谁能提示下Binary Tree找最长path怎么做？
是不是先找到height, 然后用height, 递归来找到每个在最长路经上的Node.

s*t2015-05-27 07:05

69 楼

当前树的最长path = max( 所有子树的最长path，根节点的两个最深子树高度和（如果
有两个的话）+1，高度)
递归调用即可

【在 D****6 的大作中提到】

: 谁能提示下Binary Tree找最长path怎么做？
: 是不是先找到height, 然后用height, 递归来找到每个在最长路经上的Node.

D*62015-05-27 07:05

70 楼

不太明白阿，最长path的长度不就是root到最低的leaf node的边数？
还有，这题要的是具体的path, which nodes involved in between?
怎么做啊？

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

: 当前树的最长path = max( 所有子树的最长path，根节点的两个最深子树高度和（如果
: 有两个的话）+1，高度)
: 递归调用即可

D*62015-05-27 07:05

71 楼

你说的这path是树的diameter吧．　但这里好像就是要root到leaf的最长path.

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

: 当前树的最长path = max( 所有子树的最长path，根节点的两个最深子树高度和（如果
: 有两个的话）+1，高度)
: 递归调用即可

a*y2015-05-27 07:05

72 楼

int diameter(node * root,int *height)
{
if (root == null)
{
*height = 0;
return 0;
}
int lh=0;
int rh = 0;
int ldiameter = 0;
int rdiameter = 0;
ldiameter = diameter(root->left, &lh);
rdiameter = diameter(root->right, &rh);
*height = 1+ max(lh,rh);
return max(1+rh+lh,max(ldiameter,rdiameter);

【在 D****6 的大作中提到】

: 谁能提示下Binary Tree找最长path怎么做？
: 是不是先找到height, 然后用height, 递归来找到每个在最长路经上的Node.

a*y2015-05-27 07:05

73 楼

那个database怎么整？谁能给说说？我一直没整出来啊

a*y2015-05-27 07:05

74 楼

BTW:他题目里应该就是height
int height(node * root)
{
if (root == null)
return 0;
return 1 + max(height(root->left), height(root->right));
}

w*12015-05-27 07:05

75 楼

那是不是就先算height, 在用height来递归找具体nodes in the path??

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

: BTW:他题目里应该就是height
: int height(node * root)
: {
: if (root == null)
: return 0;
: return 1 + max(height(root->left), height(root->right));
: }

a*y2015-05-27 07:05

76 楼

哥们，你拿到offer了吗？

f*52015-05-27 07:05

77 楼

你想得太复杂了吧。
我认为就是找grand parent，then all the孙子 of the grand parent

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

: 那个database怎么整？谁能给说说？我一直没整出来啊

l*c2015-05-27 07:05

78 楼

this is a dp problem, time complexity is O(n), space O(n)
your method time is O(n**2) space O(n)

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

: sorry that I am still confused what is the benefit to use the so-called
: DP.
: did u improved time complexity or saved space?
: at least I think that the two dimensions array is definitely useless.
: My code is as below,I think it is clear and directly.
: count=0;
: for(i=1;i<=n-2;i++) //a[i] is the possible central of palindrome
: for(k=1;(i-k>=0)&&(i+k<=n-1);k++)
: if (a[i-k]==a[i+k]) count++;
: else break;

s*l2015-05-27 07:05

79 楼

怎么o(n)？用suffix tree?

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

: this is a dp problem, time complexity is O(n), space O(n)
: your method time is O(n**2) space O(n)

s*l2015-05-27 07:05

80 楼

我想问一下
你这个young tableau 是说这个样子的？
1 2 4 7 8
3 5 6 9
10
还是说就是个m*n的每行和每列都是递增的矩阵？

case

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

: 昨天刚面完的，面的Ads platform,自己的目标达到了，见到了第五个人：manager。
: 上午10：00到building111，11：30才开始第一个interview，而且第一个上来就是
: lunch interview，她先把我带到她office面了45分钟，然后再到25楼吃lunch。问题有
: ：介绍你的intern,你的最challended的project? 假设你在做一个project，时间不够
: ，但是requirments又老在变，你怎么办？array和linkedlist的区别，什么情况下选哪
: 个？coding问的是给一个BST,返回最长的path from root to leaf,code完给test case
: .lunch interview也是和她吃的，人很nice，基本不问我啥问题，就是聊天吧，在25楼
: 吃lunch，风景很不错：）
: 1:00-2:00,第二个人：为什么转专业？说说你上过的课，哪些你觉得最有意思，说个
: 不在resume上的project. coding: 给一个数组，去掉duplicate；给数据库的两个表，