Uber面经分享

今天刚面完Uber， 同学内推，growth组。
一个白人小哥，说话声音很懒散。。。上来就谈简历的事情，问做了什么project，我把自己准备的东西说了一下，花了十分钟，然后他说那我们现在开始做题吧
题目： How to insert a number in

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

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

找到了最大值的位置，解决了target大于最大值或小于最小值的情况。。。
还有当时没来及问出现 3的话是插头还是插尾， 哎。。

自己写了个。。不知道对错。。。import java.util.*;
import java.lang.*;
import java.io.*;

public class rotatedarray{
        public static int position(int[] array, int target)
        {
                if (array[0] < array[array.length - 1])
                        return getresult(array, 0, array.length - 1, target);
                int start = 0;
                int end = array.length - 1;
                while (start < end - 1)
                {
                        int mid = start + (end - start) / 2;
                        if (array[mid] < array[mid + 1] && array[mid] < array[mid - 1])
                        {
                                start = mid;
                                break;
                        }
                        else if (array[mid] > array[start] && array[mid] > array[end])
                                start = mid + 1;
                        else if (array[mid] < array[start] && array[mid] < array[end])
                                end = mid - 1;
                        else if (array[start] < array[end])
                          break;
                }
                if (array[start] > array[end])
                        start = end;
                if (target < array[start] || target > array[start - 1])
                        return start;
                else if (target <= array[array.length - 1])
                        return getresult(array, start, array.length - 1, target);
                else
                        return getresult(array, 0, start - 1, target);
        }

        private static int getresult(int[] nums, int i, int j, int target)
        {
                int start = i;
                int end = j;
                while (start <= end)
                {
                        int mid = start + (end - start) / 2;
                        if (target == nums[mid])
                                return mid;
                        else if (nums[mid] < target)
                                start = mid + 1;
                        else
                                end = mid - 1;
                }
                if (nums[start] <= target)
                        return start + 1;
                return start;
        }

        public static void main(String[] args)
        {
                System.out.println(position(new int[]{5,2,4}, 3));
        }
}

f1371342385 发表于 2015-9-24 07:37
LZ，这题不可能吧，插入数组怎么可能会小于线性。。。LZ，你是不是理解错误了？

这是真的，我也和面试官说过Array插入element一定会O(n)的，但他的意思是只要是O(n)就慢了， 最后我插入还是按O(n)写的。 仔细想下这题如果用O(n)我们直接遍历求解就行了， 那这样就没什么意义了

搜索插入位置应该都是leetcode的原题，但insert in数组，而且时间小于线性，真心不知道怎么弄啊，坐等大神解答

感觉好难啊，得先求出最大值最小值吧

要插入数组不可能快于线性吧...

LZ，这题不可能吧，插入数组怎么可能会小于线性。。。LZ，你是不是理解错误了？

是的。插入就已经O(n).  是有空位吗？

wenqiang88 发表于 2015-9-24 06:40
要插入数组不可能快于线性吧...

我也和他说过这个问题

ab380765597 发表于 2015-9-24 09:53
我也和他说过这个问题

LZ，他是怎么回复你的？