《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 777|回复: 8
收起左侧

彭博电面

[复制链接] |试试Instant~ |关注本帖
wadephz 发表于 2017-9-15 07:17:37 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Bloomberg - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
给一个起始数和目标数,只有两个运算(*2和/3),求从起始数到目标数的最短运算步数?解法:用BFS做,把每个数看成一个图上的一个点。

评分

1

查看全部评分

zorrowei 发表于 2017-9-19 07:01:20 | 显示全部楼层
你好!我写了如下BFS code, 做了简单测试都是正确结果
    public int pathBFS(int start, int target) {. Waral 鍗氬鏈夋洿澶氭枃绔,
        if (start == target) {
            return 0; //early termination
        } else if (start == 0) {
            return -1; // from zero, we cannot reach any non-zero number via * 2 or / 3
        } else if (start * target < 0) { // if either start or target is negative, we cannot find such a path
            return -1;
        }
        Node root = new Node(start);
        Map<Integer, Node> map = new HashMap<>();        // check if visited        map.put(start, root);        //queue to BFS traversal visit nodes
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        int countpath = 0;
        while (!q.isEmpty()) {
            
int size = q.size();
            for (int i = 0; i < size; i++) {
                Node cur = q.poll()
;                //find target
                if (cur.val == target) {. 鍥磋鎴戜滑@1point 3 acres
                    
return countpath;
                }                //cur.val == 0, do not move on
               
if (cur.val == 0) {
                    
continue;
                }
               
if (!map.containsKey(cur.val * 2)) {
                    map.put(cur.
val * 2, new Node(cur.val * 2));
                    q.offer(map.get(cur.val * 2));
                }
               
if (!map.containsKey(cur.val / 3)) {
                    map.put(cur.
val / 3, new Node(cur.val / 3));
                    q.offer(map.get(cur.val / 3));
                }
            }
            countpath++
;
        }. more info on 1point3acres.com
        
return countpath;
    }
}


class Node {
    int val;    // left.val = val * 2    Node left;    // right.val = val / 3;    Node right;
    public Node(int val) {
        
this.val = val;
    }
}

回复 支持 0 反对 1

使用道具 举报

fwy4231 发表于 2017-9-15 22:33:03 | 显示全部楼层
求问一下楼主,除3操作出来的是省略余数嘛?是不是还得价格判断出现0的自环情况。。。谢谢!
回复 支持 反对

使用道具 举报

agraynel 发表于 2017-9-19 14:07:05 | 显示全部楼层
zorrowei 发表于 2017-9-19 07:01
你好!我写了如下BFS code, 做了简单测试都是正确结果. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    public int pathBFS(int start, int target) { ...

额。。为什么不直接queue<integer>啊?直接存数字,不需要node吧 。
如果说map是为了减少重复的数字的话,用set吧
回复 支持 反对

使用道具 举报

zorrowei 发表于 2017-9-20 00:36:40 | 显示全部楼层
agraynel 发表于 2017-9-19 14:07
额。。为什么不直接queue啊?直接存数字,不需要node吧 。
如果说map是为了减少重复的数字的话,用set吧

也可以。你的办法更省空间。
回复 支持 反对

使用道具 举报

westcoastboy 发表于 2017-10-2 04:49:58 | 显示全部楼层
agraynel 发表于 2017-9-19 14:07
额。。为什么不直接queue啊?直接存数字,不需要node吧 。
如果说map是为了减少重复的数字的话,用set吧

同意。。。。
回复 支持 反对

使用道具 举报

westcoastboy 发表于 2017-10-2 04:50:25 | 显示全部楼层
zorrowei 发表于 2017-9-20 00:36
也可以。你的办法更省空间。

做了一下,在你的代码基础上,去掉了node,map换成set
回复 支持 反对

使用道具 举报

zorrowei 发表于 2017-10-2 11:38:54 | 显示全部楼层
westcoastboy 发表于 2017-10-2 04:50. from: 1point3acres.com/bbs
做了一下,在你的代码基础上,去掉了node,map换成set

贴下你的code呀!
回复 支持 反对

使用道具 举报

westcoastboy 发表于 2017-10-2 21:54:12 | 显示全部楼层
zorrowei 发表于 2017-10-2 11:38. from: 1point3acres.com/bbs
贴下你的code呀!
  1. public static int pathBFS(int start, int target) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         if (start == target) {
    .1point3acres缃
  3.             return 0;
  4.         } else if (start == 0) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  5.             return -1;. more info on 1point3acres.com
  6.         } else if (start * target < 0) {
  7.             return -1;
  8.         }
  9.         HashSet<Integer> visited = new HashSet<>();
  10.         Queue<Integer> q = new LinkedList<>();
  11.         visited.add(start);
  12.         q.offer(start);
  13.         int count = 0;
  14.         while (!q.isEmpty()) {
  15.             int size = q.size();
  16.             for (int i = 0; i < size; i++) {
  17.                 int cur = q.poll();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.                 if (cur  == target) {
  19.                     return count;
  20.                 }            
  21.                 if (cur == 0) {
  22.                     continue;
  23.                 }
  24.                 if (!visited.contains(cur * 2)) {
  25.                     visited.add(cur * 2);
  26.                     q.offer(cur * 2);
  27.                 }
  28.                 if (!visited.contains(cur / 3)) {
  29.                     visited.add(cur / 3);
  30.                     q.offer(cur / 3);
  31.                 }
  32.             }
  33.             count++;. Waral 鍗氬鏈夋洿澶氭枃绔,
  34.         }
  35.         return count;
  36.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 08:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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