详谈如何最大化利用career fair

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1078|回复: 8
收起左侧

空气床 电面挂经

[复制链接] |试试Instant~
我的人缘0
duranneji 发表于 2018-2-24 04:08:06 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩

2018(1-3月) 码农类General 硕士 全职@Airbnb - 内推 - 技术电面  | Fail | 在职跳槽

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

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

x
听口音听不出来是哪儿的人 上来就说先做题 再聊简历

题目是给一个转换规则来转换数字n
n是奇数 n = 3n + 1
n是偶数 n = n / 2
.1point3acres网
最后n总会经过很多次转换到1

问从一到一百万 需要转换次数最多的那个数字需要转换几次. 一亩-三分-地,独家发布
.本文原创自1point3acres论坛
乍一看是DP,但是想了半天,一紧张,总也想不出来,铁定是挂了

求教地里大神这个题怎么做

评分

参与人数 1大米 +2 收起 理由
stingray + 2 给你点个赞!

查看全部评分


上一篇:发个C3 IoT的电面面经,求下一轮!
下一篇:Appfolio SDE Intern 面经
我的人缘0
fallflame 发表于 2018-3-5 00:57:32 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (17)
 
 
0% (0)  踩
感觉我的做法比较简单

共计转换524次,最大的数字 837799
需要1G的内存,运行时间50ms
如果不用内存cache,大概1s多一点


public class MaxConvertTimes {


    @Test
    public void test() {. visit 1point3acres for more.

        fillArray();
        int max = 0;
        int maxi = 0;. visit 1point3acres for more.
        for (int i = 1; i < 1_000_000; i++) {

            if (getTimes(i) > max) {
                max = getTimes(i);. visit 1point3acres for more.
                maxi = i;
            }
        }

        System.out.println(max);
        System.out.println(maxi);. 一亩-三分-地,独家发布
    }

    private int[] times = new int[1_000_000];

    public void fillArray() {
        for (int i = 2; i < 1_000_000; i++) {. 牛人云集,一亩三分地
            getTimes(i);
        }
    }

    public int getTimes(long n) {

        if (n == 1) {.本文原创自1point3acres论坛
            return 0;
        }

        if (n < 1_000_000 && times[(int)n] != 0) {
            return times[(int)n];
        }

        int ans;

        if (n % 2 == 0) {
            ans = 1 + getTimes(n >> 1);
        } else {. from: 1point3acres
            ans = 1 + getTimes(n * 3 + 1);
        }

        if (n < 1_000_000) {. 牛人云集,一亩三分地
            times[(int)n] = ans;
        }

        return ans;
    }.1point3acres网
}
. Waral 博客有更多文章,
回复

使用道具 举报

我的人缘0
chipmonk 发表于 2018-4-23 07:58:15 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
中间n可能会超过1000000吧。比如n = 999999。
回复

使用道具 举报

我的人缘0
kinggarden2001 发表于 2018-2-24 04:52:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (28)
 
 
12% (4)  踩
这明明是个数学题 我在哪看到过 网上有
回复

使用道具 举报

我的人缘0
nicemayi 发表于 2018-3-13 05:51:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (27)
 
 
6% (2)  踩
可以转化为树形问题:node当前值就是转换到的值,node有两个节点,左节点是3n + 1的反函数,右节点是n / 2的反函数,初始root的值就是1,树最终的叶子节点是不能再转换了(再转换就超过一百万了),然后看这棵树的最大深度是多少。
. From 1point 3acres bbs
补充内容 (2018-3-13 06:06):
所以我猜答案是20次?(log2(1000000)= 19.93)

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
nicemayi 发表于 2018-3-13 06:08:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (27)
 
 
6% (2)  踩
nicemayi 发表于 2018-3-13 05:51. 围观我们@1point 3 acres
可以转化为树形问题:node当前值就是转换到的值,node有两个节点,左节点是3n + 1的反函数,右节点是n / 2 ...

sorry没看清题目是要求最大深度而不是最小深度
回复

使用道具 举报

我的人缘0
cptcpt 发表于 2018-4-18 14:15:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (30)
 
 
16% (6)  踩
fallflame 发表于 2018-3-5 00:57. From 1point 3acres bbs
感觉我的做法比较简单

共计转换524次,最大的数字 837799

数组可以开大一点
private int[] times = new int[3_000_000];
回复

使用道具 举报

我的人缘0
stephenchen2016 发表于 2018-4-19 23:54:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
```
public int convert(int n) {
   int count = 0;. from: 1point3acres
   while (n != 1) {
      if (n % 2 == 0) n = 2n;. 1point 3acres 论坛
      else n = 3 * n + 1;
      count++;. 牛人云集,一亩三分地
   }. 围观我们@1point 3 acres
   return count;-google 1point3acres
}
```

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
stephenchen2016 发表于 2018-4-20 00:14:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
stephenchen2016 发表于 2018-4-19 23:54
```
public int convert(int n) {
   int count = 0;

不好意思,表达的不是很清楚,意思是建一个dp[1_000_000 ]的array
每次下来记录一次,比如dp[1] = 0, dp[2] = 1, dp[3] = 7,  dp[4], 然后下一次循环的时候找一下之前有没有做过这个
.本文原创自1point3acres论坛再直接count + dp[n]就可以了。
  public int maxConvert() {
    int[] dp = new int[1_000_000];-google 1point3acres
    int max = 0;. visit 1point3acres for more.
    for (int i = 1; i < 1_000_000; i++) {
      int ans = convert(i, dp);
      dp = ans;. more info on 1point3acres
      max = Math.max(ans, max);
    }. 留学申请论坛-一亩三分地
    return max;
  }

  private int convert(int n, int[] dp) {
    int count = 0;
    while (n != 1) {. more info on 1point3acres
      if (dp[n] != 0) return dp[n] + count;
      if (n % 2 == 0) n /= 2;
      else n = 3 * n + 1;
      count++;
    }
    return count;
  }

补充内容 (2018-4-20 00:18):
加一个条件(n > 0 && n < 1_000_000),防溢出
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-25 03:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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