google nyc onsite

今天去谷歌nyc office面试了，总体来说运气不错，遇到了两个国人，题目也不怎么难，而且不知为何没有问到system design。。。不管怎样，希望最后能有offer，祝大家同样有好offer！
我用的python，大家不要鄙视我


答案我就不详细写了，大家肯定都知道

1. 白人。
1.1 问一个数组里面最长的连续的递增数列的长度
1.2 如果是一个tree，不一定是binary tree，的最长的连续递增的序列的长度
     这一问我是用recursive dfs做的，然后被要求用iterative 做一下。

2. 白人。求两个整数的二进制有多少个不同的位数。。。
我说直接xor 然后用python 里bin 函数转化成字符串，数有几位是‘1’。。

后续要求：
2.1 不让用转化成字符串。

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

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

如抛物线。给定单调增的x的数组输入，要求输出单调增的y。
大概做法是从两端开始考虑，结果数组里填f(x)，要注意区分抛物线（比如）开口向上向下的情况。期间还指导了我如何写出漂亮的程序结构，比如loop里少用些if条件。
我感觉这兄弟给我放水了，而且看着很亲切。之后留了几分钟我们用中文聊天的，我说听你有南方口音？结果竟是一个城市的，小兄弟比我还小2届，说了两句家乡话，痛快！

第二题的思路应该就是 把两个是 做 xor 操作 然后 查找结果里面 1的 个数吧? 如果用 暴力法 一个 一个的  1<< 可能有有个bug 就是 如果是一个负数， 那么最左边的那位永远是 1， 那就无线循环了， 书上有一个解法就是 不停地 n  =  (n-1) & n, 直到n为 0， 复杂度就是 k (k是 1的 个数)

1

1. class Solution(object):
   
2.     def lengthOfLIS(self, nums):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :rtype: int
   
6.         """
   
7.         size = len(nums)
   
8.         dp = []
   
9.         for x in range(size):
   
10.             low, high = 0, len(dp) - 1
    
11.             while low <= high:
    
12.                 mid = (low + high) / 2
    
13.                 if dp[mid] >= nums[x]:
    
14.                     high = mid - 1
    
15.                 else:
    
16.                     low = mid + 1
    
17.             if low >= len(dp):
    
18.                 dp.append(nums[x])
    
19.             else:
    
20.                 dp[low] = nums[x]
    
21.         return len(dp)

复制代码

楼主能讲讲这一题吗

uess number，好像是以前的题？我没做过，还好跟leetcode上那个predict winner（或之类名字）的题很相似。
给定一个范围，我要猜一个这个范围内的数字，每猜一个数，我要支付这个数字相同的钱，每次我猜之后，他的回答是大了，或者小了。问最后我最少付多少钱可以一定猜到这个数。
注意的是他的回答可能是变化的，只要不违反他之前的回答。
我设了一个dp 2D array，然后跟leetcode 做法predict winner相似。总而言之是我和他都要取对自己最有利的下一步


是不是才对的那个数字不收钱，
如果收钱，而且每次都对自己有利的，那最少的情况就是直接才那个数字啊，

可能是我题目理解错了，楼主你说说吗？谢谢

楼主你好！能问下你是在职跳槽吗？想了解下你是大概什么时候投的啊，是general的开发岗吗？

iker01 发表于 2017-7-11 11:03
楼主你好！能问下你是在职跳槽吗？想了解下你是大概什么时候投的啊，是general的开发岗吗？

我现在还是博后，按理说不是学生，但专业不对口，也没有公司工作经验，所以不知道是否算是在职跳槽
我是找朋友5月底内推的，后来六月中旬有hr联系我。应该是普通的general的岗位

2.2 怎么更快？可以把这些preprocessing到一个array里，比如我存0~2^16的所有数字的2进制的1的位数在内存里，a xor b之后去这里查每16位的1就是了.

请问Lz，这意思是省去10进制转换成2进制那一步？

jyttwc901231 发表于 2017-7-12 05:27
2.2 怎么更快？可以把这些preprocessing到一个array里，比如我存0~2^16的所有数字的2进制的1的位数在内存里 ...

lz的意思是做index

jyttwc901231 发表于 2017-7-12 05:27
2.2 怎么更快？可以把这些preprocessing到一个array里，比如我存0~2^16的所有数字的2进制的1的位数在内存里 ...

差不多，比如我存0~255（8bit) 整数的二进制的1的个数在数组里，然后a^b = 15，就直接从数组里读，从而省去10进制转化2进制的这一步。

2.4 和cpu缓存有关吧 你缓存太小 miss率高就会降低效率

感觉不难。。。