当前在线人数15401
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
一道zenefits面试题
[版面:待字闺中][首篇作者:xujun618] , 2015年09月02日02:25:37 ,2891次阅读,52次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页] [上页][下页][末页] [分页:1 2 3 ]
xujun618
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: xujun618 (o0O0o), 信区: JobHunting
标  题: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 02:25:37 2015, 美东)

A, B两个String
//example
A = XYZ;
A^2 = XXYYZZ;
A^3 = XXXYYYZZZ;

B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh

A^2 是B的subsequence, 所以
return k = 2;

A可能有重复的char, B可能有其他字符, 求k.
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
ItachiUchiha
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: ItachiUchiha (仙人掌), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 03:11:07 2015, 美东)

subsequence不管顺序吗? 那就hashmap统计A中字符的频率,然后统计B中对应字符的
频率,然后频率相除ratio中最小的就是k.   O(n) time + O(n) space
【 在 xujun618 (o0O0o) 的大作中提到: 】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
blaze
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: blaze (狂且), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 03:27:33 2015, 美东)

可以对k进行二分。复杂度O(n*log(n))。

【 在 xujun618 (o0O0o) 的大作中提到: 】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
kkuser
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: kkuser (kkuser!), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 13:55:40 2015, 美东)

String A = "XXZ";
String B = "
XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh";

这样有重复的例子是return 2吗。
       
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
jobhunter123
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: jobhunter123 (jobhunting), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 13:59:33 2015, 美东)

题目就很啰嗦
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 157.]

 
jobhunter123
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: jobhunter123 (jobhunting), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 14:02:57 2015, 美东)

这个怎么算啊?

adhflakjhelXXzzqqkkpoYYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh也是k=2么?
我在中间多加了一个Y
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 157.]

 
lestrois
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: lestrois (lestrois), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 14:06:56 2015, 美东)

抠字符,抠到抠不出为止。O(n*k)


【 在 xujun618 (o0O0o) 的大作中提到: 】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
sza
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: sza (sza), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 14:12:36 2015, 美东)

二分不行吧。二分以后朝哪个方向走呢?

【 在 blaze (狂且) 的大作中提到: 】
: 可以对k进行二分。复杂度O(n*log(n))。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 158.]

 
xujun618
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: xujun618 (o0O0o), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 14:52:18 2015, 美东)

是的
【 在 kkuser (kkuser!) 的大作中提到: 】
: String A = "XXZ";
: String B = "
: XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh";
: 这样有重复的例子是return 2吗。
:        



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
blaze
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: blaze (狂且), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 14:53:28 2015, 美东)

你理解错了。我的意思是对于某一个特定的k,判断B中有没有A^k是一个线性O(n)的问
题。并且k有解则对于所有的i<k,i都有解。所以可以用二分查找来找到k。先看k = 1
有乜解,然后看k = 2, 4, 8, ...一直找到最终的k.  O(n*log(k))。

【 在 sza (sza) 的大作中提到: 】
: 二分不行吧。二分以后朝哪个方向走呢?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
laohuangniu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: laohuangniu (老黄牛), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 16:01:14 2015, 美东)

先找A^3,找到return 3
再找A^2,找到return 2
最后找A,找到return 1?
【 在 xujun618 (o0O0o) 的大作中提到: 】
: A, B两个String
: //example
: A = XYZ;
: A^2 = XXYYZZ;
: A^3 = XXXYYYZZZ;
: B = XXadhflakjhelXXzzqqkkpoYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh
: A^2 是B的subsequence, 所以
: return k = 2;
: A可能有重复的char, B可能有其他字符, 求k.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 147.]

 
xujun618
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: xujun618 (o0O0o), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 16:07:09 2015, 美东)

就是这个意思
【 在 laohuangniu (老黄牛) 的大作中提到: 】
: 先找A^3,找到return 3
: 再找A^2,找到return 2
: 最后找A,找到return 1?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
laohuangniu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: laohuangniu (老黄牛), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 16:16:23 2015, 美东)

A是已知的?还是要自己从B里找?
【 在 xujun618 (o0O0o) 的大作中提到: 】
: 就是这个意思



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 147.]

 
kkuser
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: kkuser (kkuser!), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 16:49:50 2015, 美东)

我的思路:
建立一个一维dp table,大小为A的size;
开始dp表都是0,遇到A中一个元素,查看dp table的对应value和dp[i-1]的value。
如果dp[i -1] 》 dp[i] ,dp[i]++;
都完事了dp[n - 1]就是结果。


【 在 laohuangniu (老黄牛) 的大作中提到: 】
: 先找A^3,找到return 3
: 再找A^2,找到return 2
: 最后找A,找到return 1?




--
※ 修改:·kkuser 於 Sep  2 18:10:02 2015 修改本文·[FROM: 38.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 38.]

 
noregrets
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: noregrets (风满袖), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 17:45:18 2015, 美东)

先把B弄成XXXXYYZZZ, 然后。。。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
noregrets
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: noregrets (风满袖), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 17:58:17 2015, 美东)

0
【 在 jobhunter123 (jobhunting) 的大作中提到: 】
: 这个怎么算啊?
: adhflakjhelXXzzqqkkpoYYYadadfhgakheZafhajkefhlZadhflkejhZfagjhfebhh也是k=2
么?
: 我在中间多加了一个Y



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
xujun618
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: xujun618 (o0O0o), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 18:31:22 2015, 美东)

能具体说说思路吗?
【 在 kkuser (kkuser!) 的大作中提到: 】
: 我的思路:
: 建立一个一维dp table,大小为A的size;
: 开始dp表都是0,遇到A中一个元素,查看dp table的对应value和dp[i-1]的value。
: 如果dp[i -1] 》 dp[i] ,dp[i]++;
: 都完事了dp[n - 1]就是结果。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
laohuangniu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: laohuangniu (老黄牛), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 19:45:53 2015, 美东)

brilliant
【 在 kkuser (kkuser!) 的大作中提到: 】
: 我的思路:
: 建立一个一维dp table,大小为A的size;
: 开始dp表都是0,遇到A中一个元素,查看dp table的对应value和dp[i-1]的value。
: 如果dp[i -1] 》 dp[i] ,dp[i]++;
: 都完事了dp[n - 1]就是结果。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 147.]

 
laohuangniu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 19 ]

发信人: laohuangniu (老黄牛), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 19:48:24 2015, 美东)

俺那种要扫3次,这位网友的是1次
【 在 xujun618 (o0O0o) 的大作中提到: 】
: 能具体说说思路吗?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 147.]

 
meme2
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 20 ]

发信人: meme2 (me too me too), 信区: JobHunting
标  题: Re: 一道zenefits面试题
发信站: BBS 未名空间站 (Wed Sep  2 20:06:27 2015, 美东)

看起来有戏,xyzxyz这种算k=2还是1

【 在 kkuser (kkuser!) 的大作中提到: 】
: 我的思路:
: 建立一个一维dp table,大小为A的size;
: 开始dp表都是0,遇到A中一个元素,查看dp table的对应value和dp[i-1]的value。
: 如果dp[i -1] 》 dp[i] ,dp[i]++;
: 都完事了dp[n - 1]就是结果。




--
☆ 发自 iPhone 买买提 1.22.06
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

[首页] [上页][下页][末页] [分页:1 2 3 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996