传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2879|回复: 5
收起左侧

FullTime Google店面

[复制链接] |试试Instant~ |关注本帖
tj474474 发表于 2016-9-24 03:40:13 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
热腾腾的G家全职电面-google 1point3acres
听起来是一个欧洲口音的大哥
先叫我讲了一个project大概扯了5分钟,觉得他也没很注意听. 1point 3acres 璁哄潧
然后就直接贴题目了我就原封不动地贴过来

The Collatz Conjecture states that the sequence of positive integers generated by repeated application of the Collatz function will always pass through 1.

Collatz function f(n) :=
3n + 1 n odd
n/2 n even. 鍥磋鎴戜滑@1point 3 acres

Examples:
1
f(2) = 1
f(3) = 10 => f(10) = 5 => f(5) = 16 => f(16) = 8 => f(8) = 4 => f(4) = 2 => f( 2) = 1

In these examples, the transformation was applied once and seven times, resp.

Q1: Write a function that returns the number of transformations needed to first reach 1.

Q2: Write a function that prints the input value and the number of transformations that maximizes the latter in the range [1 .. N], were N is of the order of one million.

findMax(3) -> “3 -> 7”

Input一定会比0大. more info on 1point3acres.com
. 鍥磋鎴戜滑@1point 3 acres
我第一题就直接写了个recursive function,然后第二题就是用一个Map去存之前出現過的結果有點像是Top Down的DP但是不是用陣列存結果。沒有問複雜度。當下時間緊迫他沒有特別要求我也沒有再想有沒有更加解法了。. 1point3acres.com/bbs

.1point3acres缃
. 1point3acres.com/bbs
补充内容 (2016-10-8 13:02):
过了一周HR打电话来说面试官只给了他很general recommendation
他没有足够的信息作出决定.鏈枃鍘熷垱鑷1point3acres璁哄潧
叫我要加面一轮电面真是跪了。 。 。
我估计是中间犯了一个错. 1point 3acres 璁哄潧
一开始用阵列去memoization 沒有用HashMap

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 462, 订阅: 95
printf_ll 发表于 2016-10-8 01:44:54 | 显示全部楼层
可以用循环来实现,第二问再加一个map来存储出现的结果,不知道写得对不对【java】
  1. HashMap<Integer,Integer> map=new HashMap<>();
  2. private int cal(int n){
  3.                 int res=0;
  4.                 ArrayList<Integer> c=new ArrayList<>();. 1point3acres.com/bbs
  5.                 while(n>1){
  6.                         c.add(n);
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  7.                         if(map.get(n)!=null){
  8.                                 addToMap(c);
  9.                                 return res+map.get(n);
  10.                         }. 1point 3acres 璁哄潧
  11.                         if(n%2==0){
  12.                                 n=n/2;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.                         }else{. From 1point 3acres bbs
  14.                                 n=3*n+1;
  15.                         }
  16.                         res++;
  17.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.                 addToMap(c);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                 return res;
  20.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  21.        
  22.         private void addToMap(ArrayList<Integer>list){
  23.                 int len=list.size();
  24.                 int s=1;
  25.                 if(map.get(list.get(len-1))!=null){
  26.                         s=map.get(list.get(len)-1);
  27.                 }
  28.                 for(int i=len-1;i>=0;i--){
  29.                         map.put(list.get(i), s++);
  30.                 }
  31.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

zyoppy008 发表于 2016-10-4 04:26:10 | 显示全部楼层
第二题干啥。。没太看得懂。。求解释一下。。。
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-4 11:20:29 | 显示全部楼层
就是说写一个function findMax(N).1point3acres缃

这个函式需要返回从1~N
可以让Collatz function得到最大的值的数还有该值
例如 findMax(3)
我们需要看
Collatz(1) = 0
Collatz(2) = 1
Collatz(3) = 7

所以返回的是 "3->7"
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-8 12:58:27 | 显示全部楼层
printf_ll 发表于 2016-10-8 01:44
可以用循环来实现,第二问再加一个map来存储出现的结果,不知道写得对不对【java】

看起来没什么问题 太厉害了-google 1point3acres
再加上一些判断跟纪录max的部分就可以了
我当初还没有用循环
虽然递归写起来比较简单些
但是递归有其缺点
回复 支持 反对

使用道具 举报

jedihy 发表于 2017-2-27 08:34:48 | 显示全部楼层
写了一个python的解法以及followup
  1. class Solution(object):
  2.     def colltaz(self, n):
  3.         ans = 0
  4.         cache = {}
  5.         while n != 1:
  6.             if n % 2 == 0:
  7.                 n = n / 2
  8.             else:
  9.                 n = 3 * n + 1
  10.             cache[n] = cache.get(n, 0) + 1. From 1point 3acres bbs
  11.             ans += 1
  12.         return ans

  13.     # follow up
  14.     def colltazMax(self, n, cache):
  15.         ans = 0
  16.         x = n
  17.         while n != 1:
  18.             if n in cache:
  19.                 return ans + cache[n]. from: 1point3acres.com/bbs
  20. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.             if n % 2 == 0:
  22.                 n = n / 2
  23.             else:
  24.                 n = 3 * n + 1
  25.             ans += 1. visit 1point3acres.com for more.
  26.         cache[x] = ans-google 1point3acres
  27.         return cache[x]

  28.     def findMax(self, n):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  29.         cache = {}
  30.         ans = 0
  31.         for i in range(1, n + 1):
  32.             ans = max(ans, self.colltazMax(i, cache)). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  33.         return "{}->{}".format(n, ans)
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-26 01:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表