推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

LinkedIn 电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
下午电面linkedin,题目:
. From 1point 3acres bbs
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】  . 鍥磋鎴戜滑@1point 3 acres
问题1: 找到 5 的位置 --> 6. more info on 1point3acres.com
问题2: 找到开始rotate的点得位置--> 2 (也就是1得位置).鏈枃鍘熷垱鑷1point3acres璁哄潧
. visit 1point3acres.com for more.

评分

1

查看全部评分

readman 发表于 2014-7-30 14:19:15 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
1.双调搜索.
2. 同上
回复 支持 反对

使用道具 举报

mkcing 发表于 2014-7-30 14:20:45 | 显示全部楼层
关注一亩三分地微博:
Warald
第二个问题 开始rotate的点的位置是不是最小值的点?. from: 1point3acres.com/bbs

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

使用道具 举报

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. Waral 鍗氬鏈夋洿澶氭枃绔,
稍微变化的binary search  
这题不难啊

双调的bs 直接写很容易写bug
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-7-30 22:31:10 | 显示全部楼层
readman 发表于 2014-7-30 22:27
. 1point 3acres 璁哄潧双调的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.鏈枃鍘熷垱鑷1point3acres璁哄潧
啊?> 哪个?

补充内容 (2014-7-30 23:47):
.1point3acres缃
请问哪一题啊
回复 支持 反对

使用道具 举报

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;
        .鏈枃鍘熷垱鑷1point3acres璁哄潧
        int L = 0;
        int R = A.length - 1;
        
.鏈枃鍘熷垱鑷1point3acres璁哄潧        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] == target)-google 1point3acres
                return true;
            
            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;
                } else {
. From 1point 3acres bbs                    R = M - 1;
                }
            } else {
                L++;
            }
        }
        return false;. from: 1point3acres.com/bbs
    }

回复 支持 反对

使用道具 举报

tiexiong 发表于 2014-8-1 03:03:40 | 显示全部楼层
刚才的代码未能正常显示
  1. public static boolean findSearchInRotatedSortedArray(int[] A, int target) {. From 1point 3acres bbs
  2.         if (A == null || A.length < 1). Waral 鍗氬鏈夋洿澶氭枃绔,
  3.             return false;
  4.         . 鍥磋鎴戜滑@1point 3 acres
  5.         int L = 0;
  6.         int R = A.length - 1;
  7.         . From 1point 3acres bbs
  8.         while (L <= R) {. visit 1point3acres.com for more.
  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;-google 1point3acres
  16.                 } else {
  17.                     L = M + 1;
  18.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  19.             } else if (A[L] > A[M]){
  20.                 if (A[M] < target && target <= A[R]) {
  21.                     L = M + 1;
  22.                 } else {
  23.                     R = M - 1;
  24.                 }
  25.             } else {
  26.                 L++;
  27.             }
  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. .1point3acres缃
  5.         int L = 0;
  6.         int R = A.length - 1;
  7.         
  8.         if (A[R] > A[L]) // No rotation.
  9.             return A[L];
  10. . from: 1point3acres.com/bbs
  11.         while (L < R) {
  12.             int M = (L + R) / 2;
  13.             if (L == M)
  14.                 return M + 1; // Finally the loop will reach L = M, then A[M + 1] should be the smallest element.
  15.             
  16.             if (A[L] < A[M]) { // Left is smaller than middle, then search the right half array including current middle element.
  17.                 L = M; // Not L = M + 1.
  18.             } else if (A[L] > A[M]) { // Left is greater than middle, then search the left half array including current middle element.
  19.                 R = M; // Not R = M + 1.
  20.             } else { // Left is the same as middle, just increment left pointer by one.
  21.                 L++;
  22.             }
  23.         }
  24.         return 0;
  25.     }
复制代码
回复 支持 反对

使用道具 举报

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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-16 23:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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