一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1512|回复: 16
收起左侧

LinkedIn 电面

[复制链接] |试试Instant~ |关注本帖
Yang_butterfly 发表于 2014-7-30 14:00:37 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Linkedin - 网上海投 - 技术电面 |Other

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

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

x
下午电面linkedin,题目:
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1. given array which is sorted and rotated, find whether a value is in this array or not.
2. follow up: 找到rotate处的index 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
例子: 【6,7,1,2,3,4,5】  
问题1: 找到 5 的位置 --> 6
问题2: 找到开始rotate的点得位置--> 2 (也就是1得位置)-google 1point3acres

评分

1

查看全部评分

readman 发表于 2014-7-30 14:19:15 | 显示全部楼层
1.双调搜索.
2. 同上
回复 支持 反对

使用道具 举报

mkcing 发表于 2014-7-30 14:20:45 | 显示全部楼层
第二个问题 开始rotate的点的位置是不是最小值的点?

另外这个面试持续了多长时间?
回复 支持 反对

使用道具 举报

rengokantai 发表于 2014-7-30 22:06:07 | 显示全部楼层
楼主运气不错,地里有个linkedin的电面比你的难N倍
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-7-30 22:24:18 | 显示全部楼层
稍微变化的binary search  
这题不难啊
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-30 22:27:25 | 显示全部楼层
yzl232 发表于 2014-7-30 22:24. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
稍微变化的binary search  
这题不难啊
.鐣欏璁哄潧-涓浜-涓夊垎鍦
双调的bs 直接写很容易写bug
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-7-30 22:31:10 | 显示全部楼层
readman 发表于 2014-7-30 22:27. From 1point 3acres bbs
双调的bs 直接写很容易写bug

leetcode  原题。。。
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-30 22:39:56 | 显示全部楼层
yzl232 发表于 2014-7-30 22:31. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
leetcode  原题。。。

啊?> 哪个?

补充内容 (2014-7-30 23:47):
- = 找到了
回复 支持 反对

使用道具 举报

wendychueng 发表于 2014-7-31 02:40:08 | 显示全部楼层
readman 发表于 2014-7-30 09:39
啊?> 哪个?
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2014-7-30 23:47):

请问哪一题啊
回复 支持 反对

使用道具 举报

readman 发表于 2014-7-31 08:48:19 | 显示全部楼层

rotate array
回复 支持 反对

使用道具 举报

ilhrx 发表于 2014-7-31 09:50:04 | 显示全部楼层
两种情况, 有duplicate or not
回复 支持 反对

使用道具 举报

 楼主| Yang_butterfly 发表于 2014-7-31 13:22:44 | 显示全部楼层
第二题要注意没有rotate的情况。也就是给你array 【1,2,3,4,5,6,7】找rotate的点
回复 支持 反对

使用道具 举报

tiexiong 发表于 2014-8-1 02:58:38 | 显示全部楼层
第一题要注意Duplicates or not,写之前沟通好就行。我写了一个,是否有Duplicates都可以处理,通过LeetCode.

    public static boolean findSearchInRotatedSortedArray(int[] A, int target) {
        if (A == null || A.length < 1)
            return false;
        
        int L = 0;
        int R = A.length - 1;
        
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] == target)
                return true;. Waral 鍗氬鏈夋洿澶氭枃绔,
            
            if (A[L] < A[M]) {
                if (A[L] <= target && target < A[M]) {
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴                    R = M - 1;
                } else {
                    L = M + 1;
                }
            } else if (A[L] > A[M]){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                if (A[M] < target && target <= A[R]) {
                    L = M + 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                } else {
                    R = M - 1;
                }
            } else {
                L++;
            }. 鍥磋鎴戜滑@1point 3 acres
        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        return false;
    }

回复 支持 反对

使用道具 举报

tiexiong 发表于 2014-8-1 03:03:40 | 显示全部楼层
刚才的代码未能正常显示
  1. public static boolean findSearchInRotatedSortedArray(int[] A, int target) {
  2.         if (A == null || A.length < 1)
  3.             return false;
  4.         
  5.         int L = 0;
  6.         int R = A.length - 1;
  7.         .鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.         while (L <= R) {
  9.             int M = (L + R) / 2;
  10.             if (A[M] == target)
  11.                 return true;
  12.             
  13.             if (A[L] < A[M]) {
  14.                 if (A[L] <= target && target < A[M]) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.                     R = M - 1;
  16.                 } else {
  17.                     L = M + 1;
  18.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.             } else if (A[L] > A[M]){
  20.                 if (A[M] < target && target <= A[R]) {.1point3acres缃
  21.                     L = M + 1;.1point3acres缃
  22.                 } else {
  23.                     R = M - 1;
  24.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.             } else {-google 1point3acres
  26.                 L++;
  27.             }. more info on 1point3acres.com
  28.         }
  29.         return false;
  30.     }
复制代码
回复 支持 反对

使用道具 举报

tiexiong 发表于 2014-8-1 03:08:37 | 显示全部楼层
第二题要注意duplicates,是否rotate,以下是我的code。
  1.     public static int findSmallestElement(int[] A) {
  2.         if (A == null || A.length < 2) // null, empty and one element.
  3.             return 0;

  4.         int L = 0;.1point3acres缃
  5.         int R = A.length - 1;
    . From 1point 3acres bbs
  6.         
  7.         if (A[R] > A[L]) // No rotation.
  8.             return A[L];

  9.         while (L < R) {
  10.             int M = (L + R) / 2;
  11.             if (L == M)
  12.                 return M + 1; // Finally the loop will reach L = M, then A[M + 1] should be the smallest element.
  13.             
  14.             if (A[L] < A[M]) { // Left is smaller than middle, then search the right half array including current middle element.. from: 1point3acres.com/bbs
  15.                 L = M; // Not L = M + 1.
  16.             } else if (A[L] > A[M]) { // Left is greater than middle, then search the left half array including current middle element.
  17.                 R = M; // Not R = M + 1.-google 1point3acres
  18.             } else { // Left is the same as middle, just increment left pointer by one.
  19.                 L++;
  20.             }. more info on 1point3acres.com
  21.         }
  22.         return 0;
  23.     }
复制代码
回复 支持 反对

使用道具 举报

shire1989 发表于 2014-8-1 11:46:40 | 显示全部楼层
你是new grad吗
回复 支持 反对

使用道具 举报

MYcolting 发表于 2014-9-30 11:05:17 | 显示全部楼层
tiexiong 发表于 2014-8-1 03:08
第二题要注意duplicates,是否rotate,以下是我的code。

想确认下我题目理解的对不对,首先是sorted的array,其次是绕着某个pivot转了N次,最后我们也不知道是否rotate过。这样子遍历一遍数组,记录数组最后访问的最大值的index(有duplicates)情况,如果index == 数组length-1,返回0,否则返回index+1, 比如6, 7, 7, 1, 1, 2, 3, 最后访问的最大值7的index是2,这样rotate点位置就是3
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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