矿工跳槽心得

一亩三分地论坛

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

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1597|回复: 16
收起左侧

野的 店面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
leoz0610 发表于 2017-7-31 01:53:37 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩

2017(7-9月) 码农类General 硕士 全职@Uber - 内推 - 技术电面  | Other | 在职跳槽

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

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

x
上周刚面完店面, 给一个json input,列了一个list的intersection。每个intersection有一个list的road。每条road有通向的intersection,cost和名字。求给一个起始intersection和一个终点intersection,找到最短的路径并且打印出来。. more info on 1point3acres
ex.

intersection A: [ {name: "road1", cost: 3, destination: "intersection B"}, {name: "road2", cost: 2, destination: "intersection B"}, {name: "road3", cost: 1, destination: "intersection B"} ]
intersection B: [ {name: "road4", cost: 4, destination: "intersection C"} ]
intersection C: []

最短路径从A到C:road3 -> road4

面试官先问如何把这个json转化成数据结构。楼主选择先建一个intersection class和一个road class,然后再用一个HashMap建一个adjacent list。算法是用dfs去搜索。但是楼主最后始终输出的路径不是最短的一条,不知道最后能不能过。。。. 牛人云集,一亩三分地
.1point3acres网

评分

参与人数 1大米 +30 收起 理由
candy_shmily + 30

查看全部评分


上一篇:两个西格玛 OA
下一篇:阅后即焚 新鲜 店面面经
我的人缘0
wangchengxuan 发表于 2017-7-31 09:45:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
public class UberIntersection {
    public static class Road {
        String name;
.本文原创自1point3acres论坛        int cost;-google 1point3acres
        String end;
        public Road( String name, int cost, String end ) {
            this.name = name;
            this.cost = cost;
            this.end = end;
        }
    }

    public String computeShortestRoad(Map<String, List<Road>> roadMap, String start, String end) {
        Map<String, Map<String, Road>> map = new HashMap<>();
        for( String key : roadMap.keySet() ) {
            if ( !map.containsKey( key ) ) {. 一亩-三分-地,独家发布
                map.put( key, new HashMap<>() );.留学论坛-一亩-三分地
            }. visit 1point3acres for more.
            List<Road> roads = roadMap.get( key );
            Map<String, Road> wantedMap = map.get( key );
            for ( Road road : roads ) {
                if ( !wantedMap.containsKey( road.end ) ) {
                    wantedMap.put( road.end, road );
                }
                if ( road.cost < wantedMap.get( road.end ).cost ) {
                    wantedMap.put( road.end, road );
                }
            }. from: 1point3acres
        }

        return dijkstra(map, start, end);
    }

    public static class Node {
        String name;
        int cost;
        public int getCost() {
            return cost;
        }
        public Node(String name, int cost) {
            this.name = name;
            this.cost = cost;. visit 1point3acres for more.
        }
    }
    private String dijkstra( Map<String, Map<String, Road>> map, String start, String end ) {.本文原创自1point3acres论坛
        String previousNode = "";.1point3acres网
        String res = "";
        Map<String, Integer> hash = new HashMap<>();
        PriorityQueue<Node> pq = new PriorityQueue<>( Comparator.comparingInt( Node::getCost ) );. Waral 博客有更多文章,
        hash.put( start, 0 );
        pq.offer( new Node( "A", 0 ) );

        while ( !pq.isEmpty() ) {
            Node cur = pq.poll();
            if (!previousNode.isEmpty()) {. visit 1point3acres for more.
                res += map.get( previousNode ).get( cur.name ).name + ", ";
            }
            if ( cur.name.equals( end ) ) {
                break;. 牛人云集,一亩三分地
            }
            previousNode = cur.name;

            for( String next: map.get( cur.name ).keySet() ) {
                if ( !hash.containsKey( next ) || hash.get( next ) < hash.get( cur.name ) + map.get( cur.name ).get( next ).cost ) {
                    hash.put( next, hash.get( cur.name ) + map.get( cur.name ).get( next ).cost );
                    pq.add( new Node(next, hash.get( cur.name ) + map.get( cur.name ).get( next ).cost) );. 1point3acres
                }-google 1point3acres
            }
        }
        return res;
    }

    public static void main(String[] args) {
        UberIntersection uberIntersection = new UberIntersection();

        Map<String, List<Road>> map = new HashMap<>();. from: 1point3acres
        map.put( "A", Arrays.asList(  new Road("roda1", 3, "B"), new Road( "road2", 2, "B" ), new Road( "road3", 1, "B" ) ) );
        map.put( "B", Arrays.asList( new Road( "road4", 4, "C" ) ) );
        map.put( "C", new ArrayList<>() );
        System.out.println( uberIntersection.computeShortestRoad( map, "A", "C" ) );
    }
}
回复

使用道具 举报

我的人缘0
endofunctor 发表于 2017-7-31 13:23:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (21)
 
 
4% (1)  踩
用C++的表示哭晕在厕所
回复

使用道具 举报

我的人缘0
endofunctor 发表于 2017-7-31 15:51:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (21)
 
 
4% (1)  踩
试着写了下。。。这题应该是对于每对intersection,取距离最短的road作为edge,然后dijkstra,dijkstra没用堆优化。. visit 1point3acres for more.
假设输入已经parse好了
请面过的老司机指点下用C++面Uber怎么做这种题。。。
  1. vector<string> getPath(unordered_map<string, unordered_map<string, pair<string, int> > >& mp, const string& start, const string& end) {
  2.   unordered_map<string, int> dist;
  3.   unordered_set<string> q;
  4.   for (const auto& p: mp) {
  5.     dist[p.first] = INT_MAX;. 牛人云集,一亩三分地
  6.     q.insert(p.first);.1point3acres网
  7.   }. 1point 3acres 论坛
  8.   dist[start] = 0;
  9.   unordered_map<string, string> previous;
  10.   if (mp.count(start) == 0 || start == end) {. visit 1point3acres for more.
  11.     return {};-google 1point3acres
  12.   }
  13.   while (not q.empty()) {
  14.     string cur;
  15.     int curDist = INT_MAX;
  16.     for (const string& s: q) {
  17.       if (dist[s] < curDist) {
  18.         curDist = dist[s];
  19.         cur = s;
  20.       }. 1point3acres
  21.     }
  22.     for (auto p: mp[cur]) {
  23.       if (dist[p.first]> dist[cur] + p.second.second) {
  24.         dist[p.first] = dist[cur] + p.second.second;. 1point3acres
  25.         previous[p.first] = cur;
  26.       } 来源一亩.三分地论坛.
  27.     }
  28.     q.erase(cur);
  29.   }
  30.   vector<string> res;
  31.   string tmp = end; 来源一亩.三分地论坛.
  32.   while (tmp != start) {
  33.     res.push_back(mp[previous[tmp]][tmp].first);
  34.     tmp = previous[tmp];
  35.   }
  36.   reverse(res.begin(), res.end());
  37.   return res;
  38. }
复制代码
回复

使用道具 举报

我的人缘0
endofunctor 发表于 2017-7-31 16:06:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (21)
 
 
4% (1)  踩
咋不能发帖了。。。
思路大概是,对于每对intersection,选择最短的一条road构造图,然后Dijkstra。(Dijkstra没用堆优化)-google 1point3acres
假设input已经parse好:. 一亩-三分-地,独家发布
  1. vector<string> getPath(unordered_map<string, unordered_map<string, pair<string, int> > >& mp, const string& start, const string& end) {
  2.   unordered_map<string, int> dist;
  3.   unordered_set<string> q;
  4.   for (const auto& p: mp) {
  5.     dist[p.first] = INT_MAX;
  6.     q.insert(p.first);
    . more info on 1point3acres
  7.   }
  8.   dist[start] = 0;
  9.   unordered_map<string, string> previous;
  10.   if (mp.count(start) == 0 || start == end) {
  11.     return {};. 1point3acres
  12.   }
  13.   while (not q.empty()) {. 留学申请论坛-一亩三分地
  14.     string cur;
  15.     int curDist = INT_MAX;
  16.     for (const string& s: q) {
  17.       if (dist[s] < curDist) {
  18.         curDist = dist[s];
  19.         cur = s;
  20.       }
  21.     }
  22.     for (auto p: mp[cur]) {
  23.       if (dist[p.first]> dist[cur] + p.second.second) {
  24.         dist[p.first] = dist[cur] + p.second.second;
  25.         previous[p.first] = cur;.本文原创自1point3acres论坛
  26.       }
  27.     }
  28.     q.erase(cur);
  29.   }
  30.   vector<string> res;
  31.   string tmp = end;
  32.   while (tmp != start) {
  33.     res.push_back(mp[previous[tmp]][tmp].first);
  34.     tmp = previous[tmp];
  35.   }-google 1point3acres
  36.   reverse(res.begin(), res.end());
  37.   return res;
  38. }
复制代码
. Waral 博客有更多文章,
顺便求老司机解答如何用C++写这种题。。。
回复

使用道具 举报

我的人缘0
steveumn 发表于 2017-8-1 03:55:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
弱问一句: "野的"是指哪一家?
回复

使用道具 举报

我的人缘0
endofunctor 发表于 2017-8-1 10:51:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (21)
 
 
4% (1)  踩
endofunctor 发表于 2017-7-31 16:06. visit 1point3acres for more.
咋不能发帖了。。。
思路大概是,对于每对intersection,选择最短的一条road构造图,然后Dijkstra。(Dijk ...
来源一亩.三分地论坛.
发重了。。。求老爷把这一层砍了。。。
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
endofunctor 发表于 2017-8-1 10:51:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (21)
 
 
4% (1)  踩
steveumn 发表于 2017-8-1 03:55
弱问一句: "野的"是指哪一家?
. 一亩-三分-地,独家发布
Uber,凑个字数
回复

使用道具 举报

我的人缘0
juw037 发表于 2017-8-1 14:23:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (9)
 
 
0% (0)  踩
yě dī 字数字数
回复

使用道具 举报

我的人缘0
 楼主| leoz0610 发表于 2017-8-2 15:03:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
wangchengxuan 发表于 2017-7-30 20:45
public class UberIntersection {
    public static class Road {
        String name;

楼主本来想写dijkstra的,被面试官制止,他说实现太复杂,用dfs就好了。。。
回复

使用道具 举报

我的人缘0
 楼主| leoz0610 发表于 2017-8-2 15:03:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
endofunctor 发表于 2017-7-31 02:51
试着写了下。。。这题应该是对于每对intersection,取距离最短的road作为edge,然后dijkstra,dijkstra没用 ...

面试官说用dfs就好。
回复

使用道具 举报

我的人缘0
hwd2000 发表于 2017-8-3 01:21:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
leoz0610 发表于 2017-8-2 15:03
面试官说用dfs就好。
. 留学申请论坛-一亩三分地
我很困惑,为啥不考虑bfs?
回复

使用道具 举报

我的人缘0
 楼主| leoz0610 发表于 2017-8-3 05:02:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
hwd2000 发表于 2017-8-2 12:21. visit 1point3acres for more.
我很困惑,为啥不考虑bfs?

我觉得因为这个是加权的图,bfs不一定能找到最短路径。
回复

使用道具 举报

我的人缘0
f1371342385 发表于 2017-9-13 05:06:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (48)
 
 
12% (7)  踩
最短的不是bfs吗。。。
回复

使用道具 举报

我的人缘0
cx00001 发表于 2017-11-13 13:00:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (51)
 
 
7% (4)  踩
为啥不遍历图 最后取最短呢。。。
回复

使用道具 举报

我的人缘0
ntupenn 发表于 2018-1-24 12:45:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩
bfs加priority queue?
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-7-23 21:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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