airbnb面试题汇总
給一個flight tickets的list,其中flight ticket包括出發地,到達地,價錢,現在規定最多k個connections,找出從A到B花費最少的path和cost。
.鏈枃鍘熷垱鑷�1point3acres璁哄潧
我是直接BFS做
.鏈枃鍘熷垱鑷�1point3acres璁哄潧
我是直接BFS做
问下BFS的话怎么保存路径呢
for numConnections = 1 to k, keep shortest path from city A to any other city
每一项包括departure, arrival, cost,然后给一个整数k, 表示最多允许k次中转。给定起始地点A,到达地点B, 要求输出从A到B的最小花费,最多k次中转。BFS一层一层扫。
def min_cost(flights, start, end, k):
info = collections.defaultdict(set)
for tour, cost in flights:
st, ed = tour.split("->")
info[st].add((ed, cost))
cur_level = {start: 0}
ans = 0x7FFFFFF
for _ in xrange(k + 1):
next_level = {}
for port, cur_cost in cur_level.iteritems():
for nx, cost in info[port]:
if nx == end:
ans = min(ans, cost + cur_cost)
else:
if nx not in next_level:
next_level[nx] = cost + cur_cost
else:
next_level[nx] = min(next_level[nx], cost + cur_cost)
cur_level = next_level
return ans
///C++: 太丑
typedef pair<string, int> costInfo;
int minCostFlight(const vector<string>& flights, string start, string end, int k) {
unordered_map<string, set<costInfo> > costMap;
unordered_map<string, int> reached[2];
int ans = INT_MAX;
for (auto flight : flights)
auto nx = flight.find("->", 0);
auto comma = flight.find(',', nx + 2);
string st = flight.substr(0, nx);
string ed = flight.substr(nx + 2, comma - nx - 2);
int cost = atoi(flight.substr(comma + 1).c_str());
costMap[st].insert(make_pair(ed, cost));
}
reached[0][start] = 0;
for (int i = 0, j = 0; i <= k; ++i) {
int nxIdx = (j + 1) % 2;
reached[nxIdx].clear();
for (auto st : reached[j]) {
for(auto ed : costMap[st.first]) {
if (ed.first == end) {
ans = min(ans, ed.second + st.second);
} else {
if (!reached[nxIdx].count(ed.first))
reached[nxIdx][ed.first] = ed.second + st.second;
else
reached[nxIdx][ed.first] = min(reached[nxIdx][ed.first], ed.second + st.second);
}
}
}
j = nxIdx;
}
return ans;
}