一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1022|回复: 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;
while(v1[i]==v2[i])
    i++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
if 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


  5. class Solution:
  6. . From 1point 3acres bbs
  7.     def __init__(self):
  8.         self._dct = {}.鏈枃鍘熷垱鑷1point3acres璁哄潧

  9.     def get_max_surpasser(self, nums):
  10.         lst = [Item(num) for num in nums]. from: 1point3acres.com/bbs
  11.         lst_sorted = self._merge_sort(lst)
  12.         max_item = max(lst_sorted, key=lambda x: x.count)
  13.         return max_item.val
  14.         # return [(x.val, x.count) for x in lst_sorted]

  15.     def _merge_sort(self, lst):
  16.         length = len(lst)
  17.         if length <= 1:
  18.             return lst
  19.         mid_idx = length / 2. 鍥磋鎴戜滑@1point 3 acres
  20.         left = lst[:mid_idx]
  21.         right = lst[mid_idx:]
  22.         left_sorted = self._merge_sort(left)
  23.         right_sorted = self._merge_sort(right)
  24.         return self._merge(left_sorted, right_sorted). From 1point 3acres bbs
  25. . more info on 1point3acres.com
  26.     def _merge(self, A, B):
  27.         res = []
  28.         idx_a = 0
  29.         idx_b = 0
  30.         len_a = len(A)
  31.         len_b = len(B)
  32.         while idx_a < len_a and idx_b < len_b:
  33.             a = A[idx_a]
  34.             b = B[idx_b]
  35.             if a.val < b.val:
  36.                 a.count += len_b - idx_b. 1point3acres.com/bbs
  37.                 res.append(a)
  38.                 idx_a += 1
  39.             else:
  40.                 res.append(b)
  41.                 idx_b += 1
  42.         if idx_a < len_a:
  43.             res.extend(A[idx_a:])
  44.         if idx_b < len_b:
  45.             res.extend(B[idx_b:])
  46.         return res
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-19 19:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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