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


一亩三分地论坛

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

野的 店面

[复制链接] |试试Instant~ |关注本帖
leoz0610 发表于 2017-7-31 01:53:37 | 显示全部楼层 |阅读模式

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

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

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

x
上周刚面完店面, 给一个json input,列了一个list的intersection。每个intersection有一个list的road。每条road有通向的intersection,cost和名字。求给一个起始intersection和一个终点intersection,找到最短的路径并且打印出来。
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

查看全部评分

wangchengxuan 发表于 2017-7-31 09:45:57 | 显示全部楼层
public class UberIntersection {. visit 1point3acres.com for more.
    public static class Road {
        String name;
        int cost;
        String end;
        public Road( String name, int cost, String end ) {
            this.name = name;
            this.cost = cost;
            this.end = end;
        }.1point3acres缃
    }

    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<>() );.1point3acres缃
            }
            List<Road> roads = roadMap.get( key );. 鍥磋鎴戜滑@1point 3 acres
            Map<String, Road> wantedMap = map.get( key );-google 1point3acres
            for ( Road road : roads ) {
                if ( !wantedMap.containsKey( road.end ) ) {
                    wantedMap.put( road.end, road );.鐣欏璁哄潧-涓浜-涓夊垎鍦
                }. visit 1point3acres.com for more.
                if ( road.cost < wantedMap.get( road.end ).cost ) {. from: 1point3acres.com/bbs
                    wantedMap.put( road.end, road );
                }
            }
        }

        return dijkstra(map, start, end);
    }

    public static class Node {
        String name;
        int cost;
        public int getCost() {
            return cost;
        }. 1point 3acres 璁哄潧
        public Node(String name, int cost) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            this.name = name;
            this.cost = cost; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    }
    private String dijkstra( Map<String, Map<String, Road>> map, String start, String end ) {
        String previousNode = "";
        String res = "";
        Map<String, Integer> hash = new HashMap<>();
        PriorityQueue<Node> pq = new PriorityQueue<>( Comparator.comparingInt( Node::getCost ) );
        hash.put( start, 0 );.1point3acres缃
        pq.offer( new Node( "A", 0 ) );. 鍥磋鎴戜滑@1point 3 acres

        while ( !pq.isEmpty() ) {
            Node cur = pq.poll();.鐣欏璁哄潧-涓浜-涓夊垎鍦
            if (!previousNode.isEmpty()) {
                res += map.get( previousNode ).get( cur.name ).name + ", ";.鏈枃鍘熷垱鑷1point3acres璁哄潧
            }
            if ( cur.name.equals( end ) ) {. 1point 3acres 璁哄潧
                break;
            }
            previousNode = cur.name;. 鍥磋鎴戜滑@1point 3 acres

            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) );
                }
            }
        }
        return res;
    }

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

        Map<String, List<Road>> map = new HashMap<>();
        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" ) );
    }
}
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-7-31 13:23:04 | 显示全部楼层
用C++的表示哭晕在厕所
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-7-31 15:51:58 | 显示全部楼层
试着写了下。。。这题应该是对于每对intersection,取距离最短的road作为edge,然后dijkstra,dijkstra没用堆优化。
假设输入已经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;. From 1point 3acres bbs
  3.   unordered_set<string> q;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.   for (const auto& p: mp) {
  5.     dist[p.first] = INT_MAX;
  6.     q.insert(p.first);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.   }. more info on 1point3acres.com
  8.   dist[start] = 0;-google 1point3acres
  9.   unordered_map<string, string> previous;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  10.   if (mp.count(start) == 0 || start == end) {
  11.     return {};
  12.   }
  13.   while (not q.empty()) {
  14.     string cur;-google 1point3acres
  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) {. 1point3acres.com/bbs
  24.         dist[p.first] = dist[cur] + p.second.second;
  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. }
复制代码
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-7-31 16:06:56 | 显示全部楼层
咋不能发帖了。。。
思路大概是,对于每对intersection,选择最短的一条road构造图,然后Dijkstra。(Dijkstra没用堆优化)
假设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);
  7.   }. 1point3acres.com/bbs
  8.   dist[start] = 0;
  9.   unordered_map<string, string> previous;
  10.   if (mp.count(start) == 0 || start == end) {. 1point3acres.com/bbs
  11.     return {};. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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;. 鍥磋鎴戜滑@1point 3 acres
  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;
  26.       } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  27.     }
  28.     q.erase(cur);
  29.   }
  30.   vector<string> res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. }. from: 1point3acres.com/bbs
复制代码

顺便求老司机解答如何用C++写这种题。。。
回复 支持 反对

使用道具 举报

steveumn 发表于 2017-8-1 03:55:08 | 显示全部楼层
弱问一句: "野的"是指哪一家?
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-8-1 10:51:13 | 显示全部楼层
endofunctor 发表于 2017-7-31 16:06
咋不能发帖了。。。
思路大概是,对于每对intersection,选择最短的一条road构造图,然后Dijkstra。(Dijk ...

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 发重了。。。求老爷把这一层砍了。。。
回复 支持 反对

使用道具 举报

endofunctor 发表于 2017-8-1 10:51:26 | 显示全部楼层
steveumn 发表于 2017-8-1 03:55. more info on 1point3acres.com
弱问一句: "野的"是指哪一家?

Uber,凑个字数
回复 支持 反对

使用道具 举报

juw037 发表于 2017-8-1 14:23:51 | 显示全部楼层
yě dī 字数字数
回复 支持 反对

使用道具 举报

 楼主| leoz0610 发表于 2017-8-2 15:03:25 | 显示全部楼层
wangchengxuan 发表于 2017-7-30 20:45
public class UberIntersection {
    public static class Road {. 鍥磋鎴戜滑@1point 3 acres
        String name;

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

使用道具 举报

 楼主| leoz0610 发表于 2017-8-2 15:03:54 | 显示全部楼层
endofunctor 发表于 2017-7-31 02:51. From 1point 3acres bbs
试着写了下。。。这题应该是对于每对intersection,取距离最短的road作为edge,然后dijkstra,dijkstra没用 ...

面试官说用dfs就好。
回复 支持 反对

使用道具 举报

hwd2000 发表于 2017-8-3 01:21:41 | 显示全部楼层
leoz0610 发表于 2017-8-2 15:03
面试官说用dfs就好。

我很困惑,为啥不考虑bfs?
回复 支持 反对

使用道具 举报

 楼主| leoz0610 发表于 2017-8-3 05:02:29 | 显示全部楼层
hwd2000 发表于 2017-8-2 12:21
我很困惑,为啥不考虑bfs?

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

使用道具 举报

f1371342385 发表于 2017-9-13 05:06:09 | 显示全部楼层
最短的不是bfs吗。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-23 15:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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