📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: lithui
跳转到指定楼层
上一主题 下一主题
收起左侧

Pocket Gems 两轮电面面经(有新题)

🔗
frankrenyu 2015-5-21 06:53:18 | 只看该作者
全局:
frankrenyu 发表于 2015-5-21 06:52
根据上面大神未完成的思路,大概想到是不是这个样子?
result[2] = new int[] {num[0], Integer>max};
fo ...

初始化写错了, 应该是Integer.MAX_VALUE
回复

使用道具 举报

🔗
57656929bb 2015-5-21 08:58:30 | 只看该作者
全局:
啊哦卧槽,楼主这题原来是LIS的方法做,LIS里是维持一个递增数组,这题同理,然后因为k=3,就是constant space
回复

使用道具 举报

🔗
57656929bb 2015-5-21 09:04:40 | 只看该作者
全局:
感觉有点傻逼,因为k=3所以是const space以及O(n)时间,但其实是O(nlogk)时间以及O(k**2)空间
回复

使用道具 举报

🔗
calvinq 2015-5-23 05:35:07 | 只看该作者
全局:
我想问个问题...第二题是要返回所有符合这个条件的数...还是只要找到一组就好了?
就像例子中的..只要返回其中一组3个数.就好了么?
回复

使用道具 举报

🔗
 楼主| lithui 2015-5-23 12:47:49 | 只看该作者
全局:
calvinq 发表于 2015-5-23 05:35
我想问个问题...第二题是要返回所有符合这个条件的数...还是只要找到一组就好了?
就像例子中的..只要返回 ...

是的若干组中的一组就好.
回复

使用道具 举报

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

使用道具 举报

🔗
combatant 2015-6-19 09:54:02 | 只看该作者
全局:
用LIS做, 由于K=3, 所以是O(1), LIS本身的时间为O(NlogK), 由于k = 3, 所以是O(N) 不知道这么理解对不对
回复

使用道具 举报

全局:
为啥没有人用两根指针?就跟color sorting一样的方法不行吗?我还没试,试好了贴代码。。。
回复

使用道具 举报

🔗
milanow 2017-7-28 05:36:19 | 只看该作者
全局:
  1. void findIndices(vector<int>& nums, int& a, int& b, int& c){
  2.         int cache1[2] = {0}, cache2[2] = {0};
  3.         int p1 = 0, p2 = 0;
  4.         for(int i = 0; i < nums.size(); ++i){
  5.                 // found sol in cache2;
  6.                 if(p2 != 0 && nums[i] > cache2[1]){
  7.                         a = cache2[0];
  8.                         b = cache2[1];
  9.                         c = nums[i];
  10.                         return;
  11.                 }

  12.                 // compare nums[i] with cache1 elements
  13.                 if(p1 == 0){
  14.                         cache1[p1++] = nums[i];
  15.                 }else if(p1 == 1){
  16.                         if(nums[i] < cache1[0]) cache1[0] = nums[i];
  17.                         else if(nums[i] > cache1[0]){
  18.                                 cache1[p1++] = nums[i];
  19.                         }
  20.                 }else if(p1 == 2){
  21.                         if(nums[i] < cache1[0]){
  22.                                 // find a better candicates, cache2 must be the worst, replace cache2 with cache1, and assign cache1[0] = nums[i]
  23.                                 cache2[0] = cache1[0];
  24.                                 cache2[1] = cache1[1];
  25.                                 p2 = 2;

  26.                                 cache1[0] = nums[i];
  27.                                 p1 = 1;
  28.                         }else if(nums[i] < cache1[1]){
  29.                                 cache1[1] = nums[i];
  30.                         }else if(nums[i] > cache1[1]){
  31.                                 a = cache1[0];
  32.                                 b = cache1[1];
  33.                                 c = nums[i];
  34.                                 return;
  35.                         }
  36.                 }
  37.         }
  38.         cout << "Cannot find a pair" << endl;
  39. }
复制代码


这个算是O(1) Space的解法吧,用了两个array长度为2的cache, cache2保存最好的两个数(第二个数最小), cache1保存最好的一个数(最小),p1,p2分别是两个cache中的元素个数,目前我还没发现什么test case错误。如果有求指正。
回复

使用道具 举报

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

本版积分规则

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