LinkedIn 电面

下午电面linkedin，题目：

1. given array which is sorted and rota

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

开始rotate的点得位置--> 2 (也就是1得位置)

第一题要注意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;
            
            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 {
                    R = M - 1;
                }
            } else {
                L++;
            }
        }
        return false;
    }

刚才的代码未能正常显示

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.         
   
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]) {
    
21.                     L = M + 1;
    
22.                 } else {
    
23.                     R = M - 1;
    
24.                 }
    
25.             } else {
    
26.                 L++;
    
27.             }
    
28.         }
    
29.         return false;
    
30.     }

复制代码

第二题要注意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. 
   
5.         int L = 0;
   
6.         int R = A.length - 1;
   
7.         
   
8.         if (A[R] > A[L]) // No rotation.
   
9.             return A[L];
   
10. 
    
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.     }

复制代码

1.双调搜索.
2. 同上

第二个问题 开始rotate的点的位置是不是最小值的点？

另外这个面试持续了多长时间？

楼主运气不错，地里有个linkedin的电面比你的难N倍

稍微变化的binary search  
这题不难啊

yzl232 发表于 2014-7-30 22:24
稍微变化的binary search  
这题不难啊

双调的bs 直接写很容易写bug

readman 发表于 2014-7-30 22:27
双调的bs 直接写很容易写bug

leetcode  原题。。。

yzl232 发表于 2014-7-30 22:31
leetcode  原题。。。

啊?> 哪个?

补充内容 (2014-7-30 23:47):
- = 找到了

readman 发表于 2014-7-30 09:39
啊?> 哪个?

补充内容 (2014-7-30 23:47):

请问哪一题啊

wendychueng 发表于 2014-7-31 02:40
请问哪一题啊

rotate array