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

Yahoo 电面; LC 33. Search in Rotated Sorted Array, follow-up Questions

全局:

2017(1-3月) 码农类General 博士 全职@yahoo - 网上海投 - 技术电面  | | Other | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 类与对象tju 于 2017-1-15 05:51 编辑

今天面了Yahoo,
刚开始给个 , 这个很随意就写出来了。
但是之后的followup 有点问题:
        1. 如果给的数组可能是ascending order, 也可能是 descending order , 问应该怎么做; 我直接想的是, 写一个针对a
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
(2017-1-31 03:12):
发现个错误, 不是电面, 是onsite的。。。 我写错了
之后2~3天就 reject了。  本来想的是拿Yahoo练习一下, 但还是reject了

评分

参与人数 1大米 +20 收起 理由
类与对象tju + 20 感谢分享!

查看全部评分


上一篇:Airbnb 2016.06 店面+两轮skype
下一篇:亚麻_在职_电面
全局:
lela900900 发表于 2017-1-26 22:46
额 你这个情况 如果没有rotate的话,单调递增or递减的 过不去啊
  1. s = Solution()
  2. nums = range(10)
  3. for i in range(10):
  4.     print s.search(nums, i)

  5. print

  6. nums = range(10)[::-1]
  7. for i in range(10):
  8.     print s.search(nums, i)
复制代码
我测试了这两种情况都是对的;因为如果单调无论跳到if check 还是else,都是标准的二分搜索
回复

使用道具 举报

推荐
wantyoulee 2017-2-27 07:25:09 | 只看该作者
全局:
感觉题目挺好的。我写了一个java的版本,但是所有credit归于python版本作业。
  1. /*only consider without duplicate*/
  2. public class SearchInRotatedArray {
  3.         public int search(int[] nums, int target) {
  4.                 if (nums == null || nums.length == 0) {
  5.                         return -1;
  6.                 }
  7.                 int start = 0;
  8.                 int end = nums.length - 1;
  9.                 int mid;
  10.                 boolean isAsc = isAscending(nums);
  11.                 while (start + 1 < end) {
  12.                         mid = start + (end - start) / 2;
  13.                         if (check(isAsc, nums[start], nums[mid])) {/* check mono-tone */
  14.                                 /* always check mono-tune part */
  15.                                 if (isBetween(target, nums[start], nums[mid])) {
  16.                                         end = mid;
  17.                                 } else {
  18.                                         start = mid;
  19.                                 }
  20.                         } else {
  21.                                 if (isBetween(target, nums[end], nums[mid])) {
  22.                                         start = mid;
  23.                                 } else {
  24.                                         end = mid;
  25.                                 }
  26.                         }
  27.                 }
  28.                 if (nums[start] == target) {
  29.                         return start;
  30.                 }
  31.                 if (nums[end] == target) {
  32.                         return end;
  33.                 }
  34.                 return -1;
  35.         }

  36.         private boolean isAscending(int[] nums) {
  37.                 return nums[nums.length - 1] < nums[0];
  38.         }

  39.         private boolean check(boolean isAsc, int a, int b) {
  40.                 if (isAsc) {
  41.                         return a <= b;
  42.                 } else {
  43.                         return a >= b;
  44.                 }
  45.         }

  46.         /* is target in between a and b */
  47.         private boolean isBetween(int target, int a, int b) {
  48.                 return Math.min(a, b) <= target && Math.max(a, b) >= target;
  49.         }

  50.         public static void main(String[] args) {
  51.                 int[] nums = { 5, 4, 3, 2, 1, 9, 8, 7 };
  52.                 int index = new SearchInRotatedArray().search(nums, 8);
  53.                 System.out.println(index);
  54.         }
  55. }
复制代码
回复

使用道具 举报

全局:
laiguojiuhao 发表于 2017-1-18 06:07
如果元素没有重复的话,感觉可以比较第一个元素和最后一个元素,如果第一个比最后一个大,ascending,否则d ...
  1. class Solution(object):
  2.     def search(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: int
  7.         """
  8.         if not nums:
  9.             return -1
  10.    
  11.         def check(a, b, ascending):
  12.             return a > b if ascending else a < b
  13.    
  14.         def inBetween(end1, end2, mid):
  15.             return min(end1, end2) <= mid <= max(end1, end2)
  16.    
  17.         beg, end = 0, len(nums)-1
  18.         ascending = nums[beg] > nums[end]
  19.    
  20.         while beg <= end:
  21.             mid = (beg + end) / 2
  22.             if nums[mid] == target:
  23.                 return mid
  24.             if check(nums[mid], nums[end], ascending):
  25.                 if inBetween(nums[beg], nums[mid], target):
  26.                     end = mid-1
  27.                 else:
  28.                     beg = mid+1
  29.             else:
  30.                 if inBetween(nums[mid], nums[end], target):
  31.                     beg = mid+1
  32.                 else:
  33.                     end = mid-1
  34.         return -1
复制代码
写了一下,能过leetcode的ascending的,descending没有测试
回复

使用道具 举报

🔗
say543 2017-1-13 16:34:58 | 只看该作者
全局:
楼主面什么组的?
回复

使用道具 举报

🔗
 楼主| mycoy 2017-1-14 09:25:06 | 只看该作者
全局:
say543 发表于 2017-1-13 16:34
楼主面什么组的?

应该是search 的一个小team
回复

使用道具 举报

全局:
我觉得没关系吧,不管是直接递增还是递减的数组,代码都适用
回复

使用道具 举报

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

使用道具 举报

🔗
 楼主| mycoy 2017-1-15 06:08:36 | 只看该作者
全局:
类与对象tju 发表于 2017-1-15 05:49
我觉得没关系吧,不管是直接递增还是递减的数组,代码都适用

代码结构是会很相似, 但是肯定不能直接把处理ascending的用到descending上吧。。。
回复

使用道具 举报

全局:
mycoy 发表于 2017-1-15 06:08
代码结构是会很相似, 但是肯定不能直接把处理ascending的用到descending上吧。。。

恩,我感觉是不是就是改一下大小符号就行了,主要就是确定单调区间。但是这个主要是在确定了是递增还是递减的情况下。
回复

使用道具 举报

全局:
mycoy 发表于 2017-1-15 06:08
代码结构是会很相似, 但是肯定不能直接把处理ascending的用到descending上吧。。。

想知道楼主最后是怎么确定是递增还是递减的,通过确定两组3个连续数吗
回复

使用道具 举报

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

使用道具 举报

🔗
 楼主| mycoy 2017-1-15 07:51:10 | 只看该作者
全局:
类与对象tju 发表于 2017-1-15 07:01
想知道楼主最后是怎么确定是递增还是递减的,通过确定两组3个连续数吗

这个还不知道啊;
随便找3个连续的数,应该确定不了吧。
一个长数组可以有很多种rotation的。。。
回复

使用道具 举报

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

本版积分规则

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