一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 998|回复: 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。

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

评分

1

查看全部评分

wondermu 发表于 2014-11-25 02:09:30 | 显示全部楼层
假设原数组是v1,它的拷贝是v2,对v2从大到小排序。那么
i=0;. visit 1point3acres.com for more.
while(v1[i]==v2[i])
    i++;
-google 1point3acresif i<v1.size()
     return v2[i];
回复 支持 反对

使用道具 举报

 楼主| johnnywsd 发表于 2014-11-25 05:10:59 | 显示全部楼层
wondermu 发表于 2014-11-25 02:09 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
假设原数组是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]
回复 支持 反对

使用道具 举报

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

补充内容 (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. 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]. 鍥磋鎴戜滑@1point 3 acres

  14.     def _merge_sort(self, lst):
  15.         length = len(lst)
  16.         if length <= 1:
  17.             return lst. visit 1point3acres.com for more.
  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. . more info on 1point3acres.com
  25.     def _merge(self, A, B):
  26.         res = []
  27.         idx_a = 0
  28.         idx_b = 0
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  29.         len_a = len(A). 鍥磋鎴戜滑@1point 3 acres
  30.         len_b = len(B)
  31.         while idx_a < len_a and idx_b < len_b:
  32.             a = A[idx_a]
  33.             b = B[idx_b]
  34.             if a.val < b.val:
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                 a.count += len_b - idx_b
  36.                 res.append(a)
  37.                 idx_a += 1.1point3acres缃
  38.             else:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  39.                 res.append(b)
  40.                 idx_b += 1
  41.         if idx_a < len_a:
  42.             res.extend(A[idx_a:])
  43.         if idx_b < len_b:
  44.             res.extend(B[idx_b:])
  45.         return res. visit 1point3acres.com for more.
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 12:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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