回复: 8
跳转到指定楼层
上一主题 下一主题
收起左侧

报一个Jet Karat电面顺便求问一道题最优解

全局:

2018(1-3月) 码农类General 硕士 全职@jet.com - 猎头 - 技术电面  | | Other | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
前几分钟讲一下背景
然后限时20分钟给一段大概150-200行的代码做code review,把问题和解决方案写在代码边上

LZ这里做review过于仔细,comment也写得太细,最后时间不太够,最后有一个大的问题只能说一说,没来得及写

然后给了一道题:
给两个用户访问一个网站各网页的list(有序),求这两个list的最长连续共同序列(也
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
相同,但是在list B里不是连续的

这道题我想了20分钟没想出比暴力解更好的方法,最后无奈之下把暴力解写了,复杂度是M*N,求问版上大神此题有没有比M*N更好的解法





上一篇:软家OTS
下一篇:已经得到人事的邮件通知通过面试,但不发offer说是headcount issues
推荐
cai_lw 2018-3-14 10:20:01 | 只看该作者
全局:
顺便贴个应该符合面试官心意的DP代码好了
  1. class Solution {
  2. public:
  3.     int longestCommonSubstring(string &A, string &B) {
  4.         vector<vector<int>> dp(A.length() + 1, vector<int>(B.length() + 1));
  5.         int ans=0;
  6.         for(int i=0;i<=A.length();i++)dp[i][0]=0;
  7.         for(int i=0;i<=B.length();i++)dp[0][i]=0;
  8.         for(int i=0;i<A.length();i++){
  9.             for(int j=0;j<B.length();j++){
  10.                 if(A[i]==B[j]){
  11.                     ans=max(ans,dp[i][j]+1);
  12.                     dp[i+1][j+1]=dp[i][j]+1;
  13.                 }
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. };
复制代码
回复

使用道具 举报

推荐
cai_lw 2018-3-14 08:02:40 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
hexu8888 2018-2-19 06:42:40 | 只看该作者
全局:
这题用DP才是MN,参考longest substring。不知道你说的暴力是什么样的可以弄到MN。
回复

使用道具 举报

🔗
木铎清 2018-2-21 07:19:59 | 只看该作者
全局:
请问lz这是申请jet什么职位的电面呢
回复

使用道具 举报

🔗
vtiaocao 2018-2-21 07:41:44 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
Liddy_L 2018-2-22 16:08:19 | 只看该作者
全局:
我intuit的oa是这道题。
最优的应该是用dp,m*n的时间,constant的空间(不建二维表,只记录i - 1,j - 1的结果)。
回复

使用道具 举报

🔗
shevchenko777 2018-3-14 07:46:27 | 只看该作者
全局:
Liddy_L 发表于 2018-2-22 16:08
我intuit的oa是这道题。
最优的应该是用dp,m*n的时间,constant的空间(不建二维表,只记录i - 1,j - 1 ...

不建二維表的話,需要一維表然後從后往前掃,是麽?
回复

使用道具 举报

🔗
滚动的西瓜 2018-10-27 10:30:24 | 只看该作者
全局:
cai_lw 发表于 2018-3-14 10:20
顺便贴个应该符合面试官心意的DP代码好了

这里应该要输出的是list,然后其实也可以优化空间吧,2D->1D,经典背包优化
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表