一亩三分地论坛

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

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

阅后即焚的新鲜店面

[复制链接] |试试Instant~ |关注本帖
Mark6 发表于 2016-5-6 00:17:46 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
前天面的,现在还没消息。发面经攒人品求过呀。店面第一轮,是非常友好的国人小哥,非常耐心的给了很多提示。。如果小哥你也看到这贴了,求给我个加面吧。。非常想去的公司啊。。
第一提,给你你个数组,要你返回数组的最小值的平方是否小于最大值。题目很简单,需要注意的就是最小值的平方可能越界。.鏈枃鍘熷垱鑷1point3acres璁哄潧

佛罗阿噗:如果这个数组不满足第一题中的条件,然后允许你执行“删除数组的第一个元素”的操作,让你返回要执行多少次,也就是删除多少个数组前面的元素后才能满足第一题中的条件。如果删完都不满足,返回-1;这一题小哥反复提示才想出来一个O(n)的做法,然后今天看还有个小bug,哎。。

接着佛罗阿噗:如果可以每次都可以选择删除第一个或者最后一个,问最少要删掉几次。。


.1point3acres缃


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-5-6 03:18):
已挂。
. visit 1point3acres.com for more.
补充内容 (2016-5-6 08:39):
用的https://codepair.hackerrank.com写代码,现在才发现这上面是可以run的。。哎,当时不知道啊。。提醒一下大家。我就奇怪当时小哥怎么说,我们写几个test case来跑一下看看。。然后我用人工给他run了几个

评分

2

查看全部评分

ykwwind 发表于 2016-5-6 01:34:24 | 显示全部楼层
第一问不说了;
第二问从尾巴往前;
第三问第一反应bottom up-DP, 想了下...线段树查最小值啊?
回复 支持 3 反对 0

使用道具 举报

GavinM 发表于 2016-5-6 01:24:35 | 显示全部楼层
问下楼主,第一个佛罗阿噗是从数组尾巴开始往前扫,然后每次记录最大值和最小值,然后求是否满足吗?这样应该是O(n),然后第二个的话,目前只能想到n方的方法,感觉应该有更好的办法- -
回复 支持 反对

使用道具 举报

 楼主| Mark6 发表于 2016-5-6 03:16:58 | 显示全部楼层
GavinM 发表于 2016-5-6 01:24.鐣欏璁哄潧-涓浜-涓夊垎鍦
问下楼主,第一个佛罗阿噗是从数组尾巴开始往前扫,然后每次记录最大值和最小值,然后求是否满足吗?这样应 ...

对,由尾向前扫。。第三问我说的是用dp,dp(i, j)表示i到j的subarray是否满足,然后他接着问是否可以省空间。。。
回复 支持 反对

使用道具 举报

ok123 发表于 2016-5-6 04:45:45 | 显示全部楼层
第二问,是不是题目不对。删除一个元素后,只有三中情况
1. 没有删到max min,关系不变
2. 删了min,第二min的平方更不可能小于max
3. 删了max,min平方更不可能小于第二max
回复 支持 反对

使用道具 举报

 楼主| Mark6 发表于 2016-5-6 04:57:41 | 显示全部楼层
ok123 发表于 2016-5-6 04:45
第二问,是不是题目不对。删除一个元素后,只有三中情况
1. 没有删到max min,关系不变
2. 删了min,第二 ...

元素可以为正,可以为负。
回复 支持 反对

使用道具 举报

 楼主| Mark6 发表于 2016-5-6 04:58:14 | 显示全部楼层
ok123 发表于 2016-5-6 04:45
第二问,是不是题目不对。删除一个元素后,只有三中情况. 1point3acres.com/bbs
1. 没有删到max min,关系不变
2. 删了min,第二 ...

. visit 1point3acres.com for more.元素可以为正,可以为负。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-18 18:50:02 | 显示全部楼层
给的数组是sorted的吗?
回复 支持 反对

使用道具 举报

jackyzhang 发表于 2016-5-18 22:10:33 | 显示全部楼层
请问第二问: 从前往后删和从后往前删的区别是?
我感觉如果不是sorted的话,没有区别啊,因为没法知道max和min会在哪。。。请大家指导
回复 支持 反对

使用道具 举报

 楼主| Mark6 发表于 2016-5-19 04:53:04 | 显示全部楼层
wtcupup 发表于 2016-5-18 18:50
给的数组是sorted的吗?
. 1point3acres.com/bbs
不是。。
回复 支持 反对

使用道具 举报

 楼主| Mark6 发表于 2016-5-19 04:55:37 | 显示全部楼层
jackyzhang 发表于 2016-5-18 22:10
请问第二问: 从前往后删和从后往前删的区别是?
我感觉如果不是sorted的话,没有区别啊,因为没法知道max ...

从前往后是O(n^2),从后往前是O(n)。因为前面不停删除,震荡很大。。而反过来的话,尾部的max和min是不变的,所以可以直接与当前元素作比较,看当前的是否大于max,或者小于min。。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-19 05:26:36 | 显示全部楼层
请问最后一问的DP方程应该怎样写呢?谢谢
回复 支持 反对

使用道具 举报

dg7743 发表于 2016-5-19 10:22:16 | 显示全部楼层
jy_121 发表于 2016-5-19 05:26
请问最后一问的DP方程应该怎样写呢?谢谢

C++代码:
  1. . more info on 1point3acres.com
  2. /*
  3. * Given an array. Check whether 2 power the minimum of the array is larger then the maximum of the array.
  4. * follow up 1: (minTakesFront)     If you can take out the front elements in the array, how many steps it takes to make the rest of the array satisfying the above condition?
  5. * follow up 2: (minTakesBothEnds)  what if you can take out elements from both ends of the arrary? Then what is the minimum steps to find a subarray that satisfying the above condition?
  6. */

  7. #include <iostream>
  8. #include <string>
  9. #include <vector>
  10. #include <algorithm>
  11. #include <limits>

  12. using namespace std;

  13. bool checkPow(const int& minValue, const int& maxValue) {
  14.     errno = 0;-google 1point3acres
  15.     double pow2 = std::pow( minValue, 2 );
  16.     if ( errno == 0 ) {
  17.         //  std::pow succeeded (without overflow) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.         if (pow2 > maxValue) {
  19.             return true;-google 1point3acres
  20.         }
  21.     } else {
  22.         //  some error (probably overflow) with std::pow.
  23.         return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  24.     }   
  25.     return false;. Waral 鍗氬鏈夋洿澶氭枃绔,
  26. }-google 1point3acres

  27. int minTakesFront(const vector<int>& nums) {
  28.         int minValue = numeric_limits<int>::max();
  29.         int maxValue = numeric_limits<int>::min();
  30.         int s = static_cast<int>(nums.size());. 1point 3acres 璁哄潧
  31.         int i = s - 1;-google 1point3acres
  32.         for (; i >= 0 ; --i) {   
  33.                 minValue = min(nums[i], minValue);
  34.                 maxValue = max(nums[i], maxValue);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  35.                 if (!checkPow(minValue, maxValue)) {
  36.                         break;
  37.                 }
  38.         }
  39.         if (i == s - 1) {
  40.                 return -1;
  41.         }
    . 1point 3acres 璁哄潧
  42.         return i + 1;
  43. }

  44. // return minimum steps to make a subarray inside the passed in array such that 2 power the minimum is larger the maximum
  45. // or -1 if there is no such subarray
  46. int minTakesBothEnds(const vector<int>& nums) {
  47.         int s = static_cast<int>(nums.size());. visit 1point3acres.com for more.
  48.         .1point3acres缃
  49.         if (s == 0) {
  50.             return -1;
  51.         }
  52.        
  53.         vector<vector<int>> f(s, vector<int>(s, 0));
  54.         for (int i = 0; i < s; ++i) {
  55.             if (checkPow(nums[i], nums[i])) {
  56.                 f[i][i] = 0;
  57.             } else {
  58.                 f[i][i] = 1;
  59.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  60.         }
  61.        
  62.         for (int i = s - 1; i >= 0; --i) {
  63.                 int minValue = nums[i];
  64.                 int maxValue = nums[i];
  65.                 for (int j = i + 1; j < s; ++j) {
  66.                         minValue = min(nums[j], minValue);
  67.                         maxValue = max(nums[j], maxValue);
  68.                         if (checkPow(minValue, maxValue)) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  69.                                 f[i][j] = 0;
  70.                         } else {
  71.                                 f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;.1point3acres缃
  72.                         }
  73.                 }
  74.         }
  75.         -google 1point3acres
  76.         //if steps equal to size of the array, all elements have been taken out
  77.         if (f[0][s - 1] == s) {. from: 1point3acres.com/bbs
  78.             return -1;
  79.         }
  80.        
  81.         return f[0][s - 1];
  82. }

  83. int main(). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  84. {
  85.   vector<int> test1 = {5};
  86.   vector<int> test2 = {1};. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  87.   vector<int> test3 = {5, 1, 3};
  88.   vector<int> test4 = {1, 1, 1};
  89.   vector<int> test5 = {5, 3, 1};
  90.   vector<int> test6 = {2, 5, 3, 1};
  91.   vector<int> test7 = {-2};
  92.   vector<int> test8 = {1, 5, 3};
  93.   
  94.   cout << "test1 front result : " << minTakesFront(test1) << endl;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  95.   cout << "test2 front result : " << minTakesFront(test2) << endl;
  96.   cout << "test3 front result : " << minTakesFront(test3) << endl;
  97.   cout << "test4 front result : " << minTakesFront(test4) << endl;
  98.   cout << "test5 front result : " << minTakesFront(test5) << endl;
  99.   cout << "test6 front result : " << minTakesFront(test6) << endl;
  100.   cout << "test7 front result : " << minTakesFront(test7) << endl;. 1point 3acres 璁哄潧
  101.   cout << "test8 front result : " << minTakesFront(test8) << endl;
  102.   cout << endl;
  103.   cout << "test1 both result : " << minTakesBothEnds(test1) << endl;. Waral 鍗氬鏈夋洿澶氭枃绔,
  104.   cout << "test2 both result : " << minTakesBothEnds(test2) << endl;
  105.   cout << "test3 both result : " << minTakesBothEnds(test3) << endl;
  106.   cout << "test4 both result : " << minTakesBothEnds(test4) << endl;
  107.   cout << "test5 both result : " << minTakesBothEnds(test5) << endl;. visit 1point3acres.com for more.
  108.   cout << "test6 both result : " << minTakesBothEnds(test6) << endl;.1point3acres缃
  109.   cout << "test7 both result : " << minTakesBothEnds(test7) << endl;
  110.   cout << "test8 both result : " << minTakesBothEnds(test8) << endl;
  111. }. visit 1point3acres.com for more.
复制代码
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-5-19 11:13:47 | 显示全部楼层

谢谢!我一开始还想f = -1时后边怎么累加呢。。
回复 支持 反对

使用道具 举报

zhuhai_ZFC 发表于 2016-7-18 12:53:54 | 显示全部楼层
第一题很简单,从头到尾扫一遍,记录最大最小值,然后比较大小即可。
第二题应该是Min Stack和Max Stack相结合,但是在初始化这两个栈的时候要从数组的末尾向数组的前部扫。但这样的空间复杂度就是O(n)了。
第三题还没有想到,但是应该非DP即Greedy。

补充内容 (2016-7-18 12:57):
顺便问一下,第二题怎么可能出现删完了都不满足的情况?删到最后只有一个元素的时候,他的平方值怎么都比自己大啊。。。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2016-7-18 13:03):
搞错了,原回复+补充都可以忽略不计。。。。
回复 支持 反对

使用道具 举报

sfsttz 发表于 2016-7-18 23:27:53 | 显示全部楼层
第三题有O(n)做法吗? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
排序之后贪心好像是可以到nlgn
1. 把所有数排序 之后试图删除最小值
删除有两个方向,一种会删掉最大的一种不会
2. 如果不会删掉最大的那一种需要的步骤更少,答案找到
3. 否则还有可能走删掉最大的那种,删掉之后清掉排序后数组的头尾 回到3




补充内容 (2016-7-18 23:33):
我说的是错误的 请无视
回复 支持 反对

使用道具 举报

omega094 发表于 2016-7-20 22:45:48 | 显示全部楼层
这个。。。。。。
删除第一个元素的操作次数难道不是直接看数组里面有多少个数是小于 pow(max(arr), 0.5) 呢。。。。。。 =_=#
(假设数组全是正数, 不过如果有负数的话也是一个思路吧。。。稍微处理下就可以。。)

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-7-21 02:58):
Nevermind 我看错了。。。原来是“删除第一个元素”。。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-7-22 09:56:48 | 显示全部楼层
Mark6 发表于 2016-5-6 03:16
对,由尾向前扫。。第三问我说的是用dp,dp(i, j)表示i到j的subarray是否满足,然后他接着问是否可以省空 ...
. 1point3acres.com/bbs
感谢楼主分享 我现在想出来的和您一样~ 要n^2的空间和复杂度? 请问怎么省空间呢?0。0 或者还有复杂度更低的办法吗0.0
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-6 10:31:59 | 显示全部楼层
第三题,对于状态 S(i, j),先检测arr(i, j)其中的最大值和最小值是否满足,如果满足,那么S(i, j) = 0, 如果不满足,那么需要根据S(i, j - 1)和S(i + 1, j)来确定最小值
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-11 23:43:36 | 显示全部楼层
pawprinter 发表于 2016-9-6 10:31
第三题,对于状态 S(i, j),先检测arr(i, j)其中的最大值和最小值是否满足,如果满足,那么S(i, j) = 0, 如 ...

良神准备怎么快速检测 arr(i, j)其中的最大值和最小值是否满足 ? 用BIT?

补充内容 (2016-10-12 00:23):
好像TreeMap就可以。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 19:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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