谷歌实习电面

去年10月份左右投的简历，然后一直没动静，结果1月初突然有人联系我说要面试，背靠背两轮约在今天早上，然后跪了……
第一轮印度小哥，上来先分别自我介绍了有10分钟，题是能否通过一次交换从第一个string变换到第二个，converse <-> conserve；
以为见过原题可以秒，结果debug了半天……_(:

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

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

问了几个问题他就have a great day了。。。

第一次电面，leetcode刷了才30题不到，跪的妥妥的，还是要多刷题啊……_(:з」∠)_

第二题用递减栈 可以O(N)

oneexy 发表于 2018-2-13 06:16
8 3 9 5 9 4呢，你怎么办

[ 0 (8)]   [0 0 0 0 0 0]

[ 0(8) 1(3)]  [0 0 0 0 0 0]

[2(9) ]  [2,1,0 0 0 0]

[2(9) 3(5)]  [2,1,0 0 0 0]

[2(9) 4(9)]  [2,1,0,1,0,0]

[2(9),4(9), 5(4)] [2,1,0,1,0,0]

def find(nums):
    stack = []
    ans = [0] * len(nums)
    for i in range(len(nums)):
        if stack == [] or nums[i] <= nums[stack[-1]]:
            stack.append(i)
        else:
            while len(stack) > 0 and nums[i] > nums[stack[-1]]:
                idx = stack.pop(-1)
                ans[idx] = i - idx
            stack.append(i)
    return ans
哪里错了吗
请指教

楼主思路的方向应该是对的，但我觉得是用TreeMap来代替priorityQueue因为TreeMap可以保持元素顺序, 以下代码仅供参考:
public int[] countDays(int[] days){
        if(days == null || days.length == 0) return new int[0];
        int length = days.length;
        int[] res = new int[length];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int left = 0;
        int right = 0;
        while(left < length){
                int cur = days[left];
                while(map.higherKey(cur) == null && right < length){
                        map.put(days[right], right);
                        right++;
                }
                if(map.higherKey(cur) != null){
                        int higherIdx = map.get(map.higherKey(cur));
                        res[left] = higherIdx - left;
                }
                map.remove(cur);
                left++;
        }
       
        return res;
}
时间复杂度nlogn

devilnut 发表于 2018-1-31 06:17
第二题用递减栈 可以O(N)

worst case还是nlgn, 因为要全部入栈

第二题扫一遍，O(n)
int n = days.length;
int[] res = new int[n];
int i = 0;
while(i < n - 1){
        int j = i+1;
        if(days[j] > days[i]){
                res[i] = j;
                i++;
        }else{
                while(j < n && days[j] <= days[i]){
                        j++;
                }
                if(j == n) return res;
                for(int k = i; k < j; k++){
                        res[i] = j;
                }
                i = j;
        }
}
return res;

楼主能说下第一题具体怎么变换么？

爱学习的鼠哥 发表于 2018-2-12 11:36
楼主能说下第一题具体怎么变换么？

给一个string，能否通过交换其中的两个char来得到第二个string，仅限一次交换，比如conserve, 交换v和s，可以得到converse，要求返回v和s的index

oneexy 发表于 2018-2-12 10:51
worst case还是nlgn, 因为要全部入栈

如果是01似乎是可以O(n)
判断四种情况 00 01 10 11 就可以
但是我不太明白怎么用hashmap或者stack

请指教

oneexy 发表于 2018-2-12 10:51
worst case还是nlgn, 因为要全部入栈

如果是01似乎是可以 O(n)
判断四种情况 00 01 10 11 就可以
但是我不太明白怎么用hashmap或者stack

请指教

greynut 发表于 2018-2-13 04:26
如果是01似乎是可以 O(n)
判断四种情况 00 01 10 11 就可以
但是我不太明白怎么用hashmap或者stack

1. import java.util.*;
   
2. class solution{
   
3.         public static void main(String[] args) {
   
4.                 int[] in = new int[]{8, 3, 3, 5, 9, 4};
   
5.                 int[] res = find(in);
   
6.                 System.out.println(Arrays.toString(res));
   
7.         }
   
8. 
   
9.         public static int[] find(int[] arr){
   
10.                 int[] res = new int[arr.length];
    
11.                 Queue<Integer[]> heap = new PriorityQueue<>((a,b)->a[0]-b[0]);
    
12.                 for(int i=0; i<arr.length; i++){
    
13.                         while(!heap.isEmpty() && heap.peek()[0] < arr[i]){
    
14.                                 Integer[] pair = heap.poll();
    
15.                                 res[pair[1]] = i - pair[1];
    
16.                         }
    
17.                         heap.add(new Integer[]{arr[i], i});
    
18.                 }
    
19.                 return res;
    
20.         }
    
21. 
    
22. }

复制代码

O(nlgn)解法