一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3489|回复: 41
收起左侧

[算法题] 想问问大家,你在面试中遇到过leetcode上hard难度或者更难的算法题吗?

[复制链接] |试试Instant~ |关注本帖
zhuli19901106 发表于 2015-7-10 14:54:21 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
如题。
我本科毕业时找过工作,最难只碰见过KMP匹配、快速选择算法。(悲剧的是当时算法底子太差,要么不会,要么写不对)
大家有在实际面试中遇到那种平时刷题都觉得不简单,现场被问更是冷汗直冒的题吗?
stellari 发表于 2015-7-10 21:05:50 | 显示全部楼层
zhuli19901106 发表于 2015-7-10 19:54
终于把"The Skyline Problem"搞定了,这是我所有leetcode题目里耗时最久,出bug最多的一题。
话说最近才发 ...

那是,这道题我可是花了好长时间写出来的,怎么能让你们轻易通过
回复 支持 1 反对 0

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-10 14:56:36 | 显示全部楼层
补充:面试官刻意刁难、强行装X的情况不算在内。
回复 支持 反对

使用道具 举报

love1point 发表于 2015-7-10 16:10:13 | 显示全部楼层
我看的面经里,大家好像都提到,只有在onsite时一些公司会考hard level的题目,比如LRU cache
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-10 19:54:26 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-10 20:04 编辑

终于把"The Skyline Problem"搞定了,这是我所有leetcode题目里耗时最久,出bug最多的一题。
话说最近才发现这题是stelllari出的啊,赞~~@stellari  
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-10 19:56:33 | 显示全部楼层
这题再次用到了map的强大特性:O(log(N))时间完成增、删、改、查、统计个数、求最大、最小。
这题中这些特性全都用到了,堪称量身定做。
回复 支持 反对

使用道具 举报

iker01 发表于 2015-7-10 21:09:50 | 显示全部楼层
同学去onsite有被问到一个比较难的DP问题。最初的题目是CC150里面的Stack of Boxs,之后的followup是箱子如果能转,怎么求最大高度。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-10 22:02:29 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-10 22:09 编辑
iker01 发表于 2015-7-10 21:09
同学去onsite有被问到一个比较难的DP问题。最初的题目是CC150里面的Stack of Boxs,之后的followup是箱子如 ...

因为可以旋转,所以把每个箱子的有三种不同可能,每次DP时也就要求三种对应的最大高度,对吗?
经典的动归,这儿有个同类型的例题。给定条件稍有不同。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1093
http://acm.hdu.edu.cn/showproblem.php?pid=1069
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-10 22:25:06 | 显示全部楼层
love1point 发表于 2015-7-10 16:10
我看的面经里,大家好像都提到,只有在onsite时一些公司会考hard level的题目,比如LRU cache

双向链表的确考验人的细心程度~
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2015-7-11 01:10:30 | 显示全部楼层
stellari 发表于 2015-7-10 21:05
那是,这道题我可是花了好长时间写出来的,怎么能让你们轻易通过

卧槽!你出的!膜拜膜拜。
回复 支持 反对

使用道具 举报

bluestarwing 发表于 2015-7-11 01:42:43 | 显示全部楼层
word ladderII好难啊...
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-11 13:19:14 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-11 14:16 编辑
stellari 发表于 2015-7-10 21:05
那是,这道题我可是花了好长时间写出来的,怎么能让你们轻易通过

话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来,但我想了一个多钟头也没想出O(N^2)的,网上搜了也没有找到平方的解。
有什么比较严谨的办法证明有或者没有吗?难道只能靠脑子想?
更新:刚刚搜了搜论文,说有O(n + k)的解。但是限定条件不同,论文中允许子数组重叠,所以和这个不是一个问题。
再更新:花了俩钟头,终于搞出了O(N * K)的DP解法,怒贴代码~~
  1. // O(k * n) DP with O(n) space, yes!
  2. #include <algorithm>
  3. #include <climits>
  4. using namespace std;

  5. class Solution {
  6. public:
  7.     /**
  8.      * @param nums: A list of integers
  9.      * @param k: An integer denote to find k non-overlapping subarrays
  10.      * @return: An integer denote the sum of max k non-overlapping subarrays
  11.      */
  12.     int maxSubArray(vector<int> nums, int k) {
  13.         vector<int> &a = nums;
  14.         int n = a.size();
  15.         if (k <= 0 || k > n) {
  16.             return 0;
  17.         }
  18.         vector<vector<int> > dp(2, vector<int>(n, 0));
  19.         vector<int> mx(n, 0);
  20.         int i, j;
  21.         int f, nf;
  22.         
  23.         mx[0] = dp[0][0] = a[0];
  24.         for (i = 1; i < n; ++i) {
  25.             dp[0][i] = max(dp[0][i - 1], 0) + a[i];
  26.         }
  27.         mx[0] = dp[0][0];
  28.         for (i = 1; i < n; ++i) {
  29.             mx[i] = max(mx[i - 1], dp[0][i]);
  30.         }
  31.         
  32.         f = 1;
  33.         nf = !f;
  34.         for (i = 1; i < k; ++i) {
  35.             dp[f][i] = dp[nf][i - 1] + a[i];
  36.             for (j = i + 1; j < n; ++j) {
  37.                 dp[f][j] = max(dp[f][j - 1], mx[j - 1]) + a[j];
  38.             }
  39.             mx[i] = dp[f][i];
  40.             for (j = i + 1; j < n; ++j) {
  41.                 mx[j] = max(mx[j - 1], dp[f][j]);
  42.             }
  43.             f = !f;
  44.             nf = !f;
  45.         }
  46.         return mx[n - 1];
  47.     }
  48. };
复制代码
回复 支持 反对

使用道具 举报

会编程的猪先生 发表于 2015-7-11 15:14:29 | 显示全部楼层
stellari 发表于 2015-7-10 21:05
那是,这道题我可是花了好长时间写出来的,怎么能让你们轻易通过

我在13年10月左右面微软OS组,第四面挂在这题。。
回复 支持 反对

使用道具 举报

57656929bb 发表于 2015-7-11 15:33:23 | 显示全部楼层
这题还谁出的。。。。geekforgeek上一百年前的原题。。。。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-11 15:42:50 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-11 15:57 编辑
57656929bb 发表于 2015-7-11 15:33
这题还谁出的。。。。geekforgeek上一百年前的原题。。。。

我说的是leetcode上那题是stellari添加的。。另外,咱能愉快地交谈吗,一百年前geekforgeek还没开张
没说leetcode所有题都是原创,比如LCA问题才刚刚添加,然而别的OJ都见过无数遍了
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-11 17:31:20 | 显示全部楼层
本帖最后由 stellari 于 2015-7-11 17:34 编辑
zhuli19901106 发表于 2015-7-11 13:19
话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来, ...

应该是不存在“确定一个问题可达到的最优复杂度”的一般方法的,否则我们也不需要一道一道地去证明哪些问题是NP-Hard的了。

Maximum Subarray III这题的思路和Sell/Buy Stock IV的思路基本一样。维护两个二维DP数组,分别是:
global[ k ][ i ] -> 子数组0~i中,取k个subarray能达到的最大值。
local[ k ][ i ]  -> 子数组0~i 中,取k个subarray,且第k个subarray一定包含元素 i 时能达到的最大值。

最后你会发现,local和global的状态转移方程都分别依赖于对方。并且每个元素都能在O(1)时间内算出,因此最后总时间是O(N*K)。
回复 支持 反对

使用道具 举报

 楼主| zhuli19901106 发表于 2015-7-11 17:32:44 | 显示全部楼层
stellari 发表于 2015-7-11 17:31
应该是不存在“确定一个问题可达到的最优复杂度”的一般方法的,否则我们也不需要一道一道地去证明哪些问 ...

嗯,就是这样。
局部最优和全局最优交替更新。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-11 17:36:48 | 显示全部楼层
zhuli19901106 发表于 2015-7-11 13:19
话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来, ...

赞,顺便贴一个我的版本:
  1.     int maxSubArray(vector<int> nums, int k) {
  2.         // write your code here
  3.         int N = nums.size();
  4.         vector<vector<int> > local(k+1, vector<int>(N+1, 0));
  5.         vector<vector<int> > global(k+1, vector<int>(N+1, 0));
  6.         
  7.         
  8.         for (int ic = 1; ic <= N; ++ic) {
  9.             for (int ir = 1; ir <= k; ++ir) {
  10.                 local[ir][ic] = max(global[ir-1][ic-1], local[ir][ic-1]) + nums[ic-1];
  11.                 if (ir < ic)
  12.                     global[ir][ic] = max(local[ir][ic], global[ir][ic-1]);
  13.                 else
  14.                     global[ir][ic] = local[ir][ic];
  15.             }
  16.         }
  17.         
  18.         return global[k][N];
  19.     }
复制代码
回复 支持 反对

使用道具 举报

bluesky6 发表于 2015-7-11 19:04:44 | 显示全部楼层
謝謝大家分享
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2015-7-12 04:22:57 | 显示全部楼层
zhuli19901106 发表于 2015-7-11 13:19
话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来, ...

看来leetcode现在是每个账户公开的题目不一样?比如说很早之前,有个同学告诉我leetcode有一道题目是数n里面含有数字为1的总数,我是前天才看到这道题目的。同样,你说的maximum subarray III我也没有看到啊。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 06:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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