一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1184|回复: 12
收起左侧

补充攒人品

[复制链接] |试试Instant~ |关注本帖
johnnywsd 发表于 2014-11-24 09:41:20 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Pass

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

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

x
电面45分钟。一个数列,对每个数a都可以求出这样一个数f(a)=#(位置排在a后面,且比a大)。要求这些f(a)中的最大值。给充足提示引导到一个o(n^2)(其实是nloglogn)的方法。不要求写代码,下面是大致思路:
1. 如果b>a,b在a后面,则f(b)<f(a), b不在考虑范围内,所以只考虑从头起的一个单调递减的子序列L,L中保存求解需要的数据。
2. 遍历数列,更新L,最后根据L中数据求解。剩下的问题是,要考虑L中保存什么样的数,遍历时更新L中的数据仅用log(length L)时间;用什么方法可以根据这些数据最后在n时间内求f(a)最大值。
3. 讨论复杂度,关键是L的长度。假设给出数列时以这种意义的“均匀”方式给出:数列当前长度为k,第k+1个数大小排在这k+1个数中第i位的概率是1/(k+1). 可以算出L长度的期望是logn(n是数列长度)。所以实际复杂度是nloglogn。

时间有点久了,我当时的答案有点想不起来了,肯定也是有缺陷,但大体思路是上面那样的。如有需要我试着回忆一下。-google 1point3acres
onsite比较简单,http://www.1point3acres.com/bbs/thread-108492-1-1.html

评分

1

查看全部评分

wondermu 发表于 2014-11-25 02:09:30 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
假设原数组是v1,它的拷贝是v2,对v2从大到小排序。那么
i=0;.1point3acres缃
while(v1[i]==v2[i])
    i++;
if i<v1.size()
     return v2[i];
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-11-25 05:10:59 | 显示全部楼层
关注一亩三分地微博:
Warald
wondermu 发表于 2014-11-25 02:09. 鍥磋鎴戜滑@1point 3 acres
假设原数组是v1,它的拷贝是v2,对v2从大到小排序。那么
i=0;
while(v1==v2)

貌似只要v1[0]!=v2[0]就会返回v2[0],能改一下吗?或者说下思路。
回复 支持 反对

使用道具 举报

wondermu 发表于 2014-11-25 06:04:20 | 显示全部楼层
v2[0] 是数组的最大值,对吧。如果v1[0]!=v2[0],说明f(v1[0])=v2[0]
回复 支持 反对

使用道具 举报

wondermu 发表于 2014-11-25 06:04:31 | 显示全部楼层
v2[0] 是数组的最大值,对吧。如果v1[0]!=v2[0],说明f(v1[0])=v2[0]
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

wondermu 发表于 2014-11-25 07:36:56 | 显示全部楼层
对不起,我把题意理解错了,请忽略那个算法
回复 支持 反对

使用道具 举报

ekco 发表于 2014-12-10 04:15:51 | 显示全部楼层
如果b>a,b在a后面,则f(b)<f(a)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个是怎么成立的?
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-10 08:36:04 | 显示全部楼层
这个题的意思是不是:给一个数组,有一个函数,通过这个函数计算每个数的结果,求这些结果中最大的数。是这样么?
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-10 08:40:34 | 显示全部楼层
mm豆 发表于 2015-4-10 08:36
这个题的意思是不是:给一个数组,有一个函数,通过这个函数计算每个数的结果,求这些结果中最大的数。是这 ...

这是surpasser问题吧 不是divide and conquer nlog(n)吗
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-10 09:01:39 | 显示全部楼层
sunfish 发表于 2015-4-10 08:40
这是surpasser问题吧 不是divide and conquer nlog(n)吗

surpasser 是什么问题? 我也不太明白这道题的意思
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-10 09:23:21 | 显示全部楼层
mm豆 发表于 2015-4-10 09:01
surpasser 是什么问题? 我也不太明白这道题的意思

看这个surpasser. visit 1point3acres.com for more.

补充内容 (2015-4-10 09:23):
http://www.fgdsb.com/2015/01/11/maximal-surpasser-count/
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-4-11 02:15:12 | 显示全部楼层
sunfish 发表于 2015-4-10 09:23
看这个surpasser 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2015-4-10 09:23):

十分感谢~~~~~~~~~~
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2015-4-29 07:24:39 | 显示全部楼层
根据 http://www.fgdsb.com/2015/01/11/maximal-surpasser-count/ 写了各Python代码。谢谢 sunfish 的提示
  1. class Item:
  2.     def __init__(self, val):
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.         self.val = val
  4.         self.count = 0. from: 1point3acres.com/bbs


  5. class Solution:

  6.     def __init__(self):
  7.         self._dct = {}.鐣欏璁哄潧-涓浜-涓夊垎鍦

  8.     def get_max_surpasser(self, nums):
  9.         lst = [Item(num) for num in nums]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.         lst_sorted = self._merge_sort(lst)
  11.         max_item = max(lst_sorted, key=lambda x: x.count)
  12.         return max_item.val
  13.         # return [(x.val, x.count) for x in lst_sorted]

  14.     def _merge_sort(self, lst):
  15.         length = len(lst)
  16.         if length <= 1:
  17.             return lst
  18.         mid_idx = length / 2
  19.         left = lst[:mid_idx] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.         right = lst[mid_idx:]
  21.         left_sorted = self._merge_sort(left)
  22.         right_sorted = self._merge_sort(right)
  23.         return self._merge(left_sorted, right_sorted)

  24.     def _merge(self, A, B):
  25.         res = []
  26.         idx_a = 0
  27.         idx_b = 0
  28.         len_a = len(A)
  29.         len_b = len(B)
  30.         while idx_a < len_a and idx_b < len_b:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  31.             a = A[idx_a]
  32.             b = B[idx_b]
  33.             if a.val < b.val:
  34.                 a.count += len_b - idx_b
  35.                 res.append(a)
  36.                 idx_a += 1
  37.             else:
  38.                 res.append(b)
  39.                 idx_b += 1
  40.         if idx_a < len_a:. more info on 1point3acres.com
  41.             res.extend(A[idx_a:])
  42.         if idx_b < len_b:
  43.             res.extend(B[idx_b:])
  44.         return res
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-28 14:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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