寄托天下
楼主: bibaboo0
打印 上一主题 下一主题

[编程天地] 刷题咯 [复制链接]

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
46
发表于 2017-2-9 07:16:12 |只看该作者
501. Find Mode in Binary Search Tree
Easy题。我使用dict做的,但是没想到怎么用O(1)的空间实现

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
47
发表于 2017-2-9 07:23:48 |只看该作者
485. Max Consecutive Ones
Easy题,不解释。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
48
发表于 2017-2-9 08:59:14 |只看该作者
475. Heaters
Easy题,第一次击败了百分之99.88的人,也不知道为啥。用了先排序后计算的方法。Naive的方法应该是n方吧。我这样做是nlogn。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
49
发表于 2017-2-9 09:19:20 |只看该作者
448. Find All Numbers Disappeared in an Array
Easy题。看答案看到一种很聪明的做法:
for e in nums:
            nums[abs(e) - 1] = -abs(nums[abs(e) - 1])
        return [i + 1 for i, e in enumerate(nums) if e > 0]

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
50
发表于 2017-2-9 09:42:02 |只看该作者
447. Number of Boomerangs
Easy题。6行python代码解决,有点小开心。至此google easy题全部结束。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
51
发表于 2017-2-9 13:07:02 |只看该作者
33. Search in Rotated Sorted Array 难度Medium 耗时半小时。
经典问题之rotated array

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
52
发表于 2017-2-11 14:09:17 |只看该作者
昨天星期四,面了google intern。
前后两轮,每轮四十五分钟,从中午十二点一直到一点四十五。
第一轮听声音应该是一个白人女生,一开始问了一下项目的事,然后开始出题。给定一个字典,当你输入前几个字符时自动提醒所有可能的单词。我说有两种方式,一种是用prefix字典,另一种是用trie。prefix字典我之前写过,很有信心,但是trie我没写过,虽然我知道trie可能更好,但还是选择了用prefix字典写。写完之后follow up是如果单词有不同的频率,只想返回频率最高的五个怎么办。我一开始想的每得到一个新的就插入排序,然后返回前五个。后来她说如果数据量特别大怎么办,我这才想到可以把除了这五个之外的都抛弃掉。再后来的follow up是如果不是5个是n个,不停的插入删除还要保持最大的n个怎么办,我说可以用heap的数据结构。又问如果允许输入的prefix错一位怎么办,我说遍历搜索整个字典,找出所有跟这个prefix相差一个字符的prefix,输出union中最大的5个单词。总之她问的问题我基本上都能答上,答得好不好是另一回事。主要的问题有两个,一个是trie不熟练,她其实暗示过我可以尝试trie,我没信心就没敢接上。另一个是英语比较烂,说的结结巴巴,卡壳、重复的比较多,这个一定要训练!!

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
53
发表于 2017-2-11 14:18:33 |只看该作者
第二轮运气比较好,遇到一个中国人大哥,大哥直接让我讲中文了。也不废话啰嗦,上来直接就出题。题目是给定一个list of interger,找出其中surpassers的总数。surpasser的定义是对于i,j if i < j and A[i]<A[j], then j is a surpasser of i. 也就是一个pair,后面的数index和值都比前一个大。这个题目brute force的方法很好想,就是一个二重循环,复杂度n方。大哥开始问如何优化,说最优解是nlogn。我想半天没想出来,要大哥提醒。大哥说有两种方法,一种是二叉树插入,还有一种是merge sort的变体。大哥提醒我了之后我还是没想明白,只能再次求教。后来总算明白了merge sort的方法,其实就是分治,分成left right,两边count,再count横跨两边的pair,最后把三个数加起来。知道了算法我就开始写,写的还挺快的,但是中间又出了问题:count横跨两边的pair的时候,我用了一个二层循环,这样一来就不是nlogn了,大哥让我算一下复杂度,我算出来是n方。那么怎么才能nlogn呢?我又卡壳了。在大哥提醒下,我在divide and conquer的时候,一边count 一边排序,这样上层拿到的就是一个有序list,就可以用O(n)的时间计算pair,这样复杂度就nlogn了。大哥开始问我空间复杂度的问题,我说是nlogn。最后大哥说最优的merge sort可以只用O(n)的空间。面试结束。感觉这题比上一题要更难一些,两次思路都没想到,感觉不太妙。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
54
发表于 2017-2-27 15:03:45 |只看该作者
461. Hamming Distance Easy题
python tips: 异或操作 c=x^y

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
55
发表于 2017-2-27 15:04:33 |只看该作者
自从面完谷歌之后,将近二十天没刷题了,准备恢复。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
56
发表于 2017-3-1 02:41:27 |只看该作者
253. Meeting Rooms II 难度Medium
这题之前跟同学讨论过,没想出来方法。今天看了答案,理解了半天,豁然开朗。其实如果脱离了算法、编程这些,如果你就是一个房间管理员,这个其实很好解决,就是根据meeting的先后顺序,先来了就先分配房间,走了房间就空出来,没有空房间了就再开一个新的,就这么简单。如果非要说算法的话应该可以归类为贪心算法吧。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
57
发表于 2017-3-1 03:43:14 |只看该作者
127. Word Ladder 难度medium
一开始超时。后来利用字符串的字母个数限制,将一个维度的复杂度降低到常数级才通过。
for i in xrange(len(w1)):
                    for cha in 'abcdefghijklmnopqrstuvwxyz':
。。。
这个循环大概有上百次,但毕竟还是常数级。再大的常数级都比O(N)要好。这是一个真理。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
58
发表于 2017-3-1 04:32:21 |只看该作者
311. Sparse Matrix Multiplication 难度medium
稀疏矩阵的处理。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
59
发表于 2017-3-1 04:42:52 |只看该作者
28. Implement strStr()
Easy题不解释。

使用道具 举报

Rank: 4

声望
50
寄托币
779
注册时间
2014-10-1
精华
0
帖子
189
60
发表于 2017-3-13 06:34:19 |只看该作者
149. Max Points on a Line
难度 hard
挺难的,写了好久。。三个小时
好久不写了,要多练啊,明天要二面tusimple

使用道具 举报

RE: 刷题咯 [修改]
您需要登录后才可以回帖 登录 | 立即注册

问答
Offer
投票
面经
最新
精华
转发
转发该帖子
刷题咯
https://bbs.gter.net/thread-2062297-1-1.html
复制链接
发送
报offer 祈福 爆照
回顶部