谷歌New Grad店面

题目如下：

We are given an unsorted array of n distinct elements, and use binary search to find a specific number. How many numbers are guaranteed to be able to be found using binary search in the array?

Given [2, 1, 3, 4, 6, 5] and target = 5, we cannot find 5. Because when the random index is 4, we get element 6, then right pointer will move left, so we’ll lose the opportunity to find target 5.

Given [2, 1, 3, 4, 5, 6] and target = 5, we can find 5. Because wherever the random index picks, we’ll find target at last.

Example 1:

Input: [2, 1, 3, 5, 4, 6]
Output: 2
Explanation: 3 and 6 are the numbers guaranteed to be found.
Example 2:

Input: [1, 2, 3]
Output: 3
Explanation: all the numbers guaranteed to be found.
Example 3:

Input: [3, 2, 1]
Output: 0
Explanation: no numbers guaranteed to be found.

也恭喜一个

Given an array of integers and target value, return the output comprising of 0’s and 1’s such that largest dot product (of input and the output) is equal or less than target value.
Input: [1,2,2,1] target = 4 Output:[0,1,1,0]
Input: [1,2,2,1] target = 3 Output:[1,1,0,0] or [1,0,1,0]
IF there are more than 1 output satisfying, return any one of the possible outputs.
i.e. input.result != target then choose result s.t (target - input.result) is minimum.

应该是 0/1 knapsack

挂在这题了

Given a binary grid where 0 represents water and 1 represents land. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Delete all islands except their borders. A border is land adjacent to water. You may assume all four edges of the grid are surrounded by water.

Example 1:

Input:
[[0, 0, 0, 1, 1, 1],
[0, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]]

Output:
[[0, 0, 0, 1, 1, 1],
[0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1]]
Example 2:

Input:
[[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]]

Output:
[[1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1]]
Example 3:

Input:
[[1, 1, 1, 0, 1, 1, 1],
[1, 1, 1, 0, 1, 1, 1],
[1, 1, 1, 0, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 1, 1, 1]]

Output:
[[1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 0, 1, 1, 1]]

用暴力解法我觉得应该是时间O(nlogn)空间O(1)。如果缩短时间我想到用recursion做，时间O(n),空间O(logn)。
这是我的code，大概逻辑是每次把arr分成左右两边去检查，用min和max动态维护当前的search range，在每一层只检查当前层的mid是不是在search range, 在的话就说明能找到这个点，不在的话说明找不到。我自己写的test case过了，不知道有没有什么case没有考虑到。

def recur(arr, left, right, _min, _max):
    if left>right:
        return 0
    mid = left + (right-left)/2
    nextLevel = recur(arr,left,mid-1,_min,min(_max,arr[mid]))+recur(arr,mid+1,right,max(_min,arr[mid]),_max)
    if arr[mid]>=_min and arr[mid]<=_max:
        return nextLevel+1
    else:
        return nextLevel

def solution (arr):
    return recur(arr, 0, len(arr)-1, min(arr), max(arr))

这道题能不能直接去把上下左右都临近1的1设置为0？时间复杂度O(n), 空间O(k), k是删除岛屿的个数。我不知道这个题能不能优化为空间O(1)

def deleteIsland(arr):
    delete = []
    if len(arr)==0:
        return arr
    for i in range(1,len(arr)-1):
        for j in range(1,len(arr[0])-1):
            if arr[i-1][j]==1 and arr[i+1][j]==1 and arr[i][j-1]==1 and arr[i][j+1]==1:
                delete.append([i,j])
    for cord in delete:
        arr[cord[0]][cord[1]]=0
    return arr

不需要recursion， O(n) 可以解决
从左到右扫一遍，然后从右到左扫一遍即可

参考 Mock 专场第三期

image.jpg1138×1304 290 KB

Google 最全备战合集 也收录了

这题扫两遍即可吧，但设置为0改了matrix就不能判断了
把周围都是1的mark一下，第二遍删除

确实是！谢谢！

感谢告知！

你设置成2 就行了，别用0
可以不用extra space

google new grad還沒開吧 應該是phD new grad?