Problem<\/h3>\n
The problem is to find the minimum time path for a Tesla car to drive from one charging station\u00a0s<\/em>\u00a0to another charging station\u00a0t<\/em>\u00a0in a Tesla charging station network. The car has a maximum range of 320km, so it needs to charge in intermediate stations. However, each station has a charging speed in\u00a0km\/hr<\/em>, indicating how many more kilometers the car can drive per hour charging, before the car reach the 320km maximum range.<\/p>\n The input is the names of the starting station and the destination station. A header file is provided with a list of charging stations with their names, coordinates, and charging speeds.<\/p>\n The output is a single line in the following format: starting station name, first intermediate station name, charge time in hrs, second intermediate station name, charge time in hrs, \u2026, \u2026, destination station name.<\/p>\n (1) The car starts with a full range of 320km. For example the command\u00a0 The Tesla\u2019s solution is simple: for each charging station a<\/em>, subdivide it into\u00a0m+1<\/em>\u00a0vertices\u00a0(a, 0), (a, 1), \u2026, (a, m)<\/em>, where vertex\u00a0(a, i)<\/em>\u00a0denotes the state that the car is at charging station\u00a0a<\/em>\u00a0and it currently has\u00a0i\/m * 320 km<\/em>\u00a0range. Then, for every vertex\u00a0(a, i)<\/em>, we add an edge to\u00a0(a, i+1)<\/em>\u00a0with the time equal to the corresponding charging time. Also for any points\u00a0(a, i)<\/em>\u00a0and\u00a0(b, j)<\/em>, we add an edge between them if\u00a0(i-j)\/m * 320 km<\/em>\u00a0is greater or equal to the distance between charging station\u00a0a<\/em>\u00a0and\u00a0b<\/em>, and the time of the edge is the corresponding travel time between these two stations. Then we can simply use any shortest path algorithm to find the shortest path between\u00a0(s, m)<\/em>\u00a0and\u00a0(t, 0)<\/em>\u00a0in the new graph and we can get a solution. <\/p>\n The optimal solution is not as trivial as Tesla\u2019s solution. We need to prove several lemmas first.<\/p>\n The proof is trivial.<\/p>\n Proof:<\/strong>\u00a0Assume that there is an optimal solution with non-zero remaining range\u00a0r<\/em>. Let\u00a0a<\/em>\u00a0be the last station the car charged. And let\u00a0r\u2019<\/em>\u00a0be the extra range we gain from the charging in station\u00a0a<\/em>. Now we construct a new solution where everything stays the same, except we charge\u00a0min(r, r\u2019)<\/em>\u00a0less in station\u00a0a<\/em>.<\/p>\n The new solution is a valid solution: before reaching\u00a0a<\/em>\u00a0it is the same as the old solution; after reaching\u00a0a<\/em>\u00a0and charging for the last time, in the new solution the car always has\u00a0min(r, r\u2019)<\/em>\u00a0less range than the old solution. Because we had range\u00a0r<\/em>\u00a0remaining in the old solution, we will always have at least\u00a00<\/em>\u00a0range remaining in the new solution. Thus is is a feasible solution.<\/p>\n The new solution also takes less time than the original solution because\u00a0min(r, r\u2019) > 0<\/em>\u00a0so we save some charging time. Thus it is a contradiction with the assumption that the old solution is an optimal solution. Then we proved Lemma 2 is true.<\/p>\n Proof:<\/strong>\u00a0We will prove this lemma by contradiction. Assume that such optimal solution doesn\u2019t exist. Then all solutions has some intermediate station doesn\u2019t have the property Then let\u2019s consider the solution with lowest number of stations in the output. If multiple such solutions exists, let\u2019s consider the solution with lowest number of intermediate stations without the property.<\/p>\n Let\u2019s consider an optimal solution with lowest number of stations in the output. We will prove that in such a solution, we either fully charge the car, or we charge just enough to reach the next station for every intermediate station.<\/p>\n For every three consecutive stations\u00a0a<\/em>,\u00a0b<\/em>, and\u00a0c<\/em>. We will consider all the cases: (1) We don\u2019t charge at station\u00a0b<\/em>\u00a0at all. (2) We charge less than enough to reach\u00a0c<\/em>. (3) We charge just enough to reach\u00a0c<\/em>. (4) We charge more than enough to reach\u00a0c<\/em>\u00a0but do not fully charge. (5) We fully charge the car.<\/p>\n Case (3) and (5) are two permitted cases in Lemma 3. Case (2) is obviously impossible because we are not able to reach\u00a0c<\/em>\u00a0if we didn\u2019t charge enough in\u00a0b<\/em>. Now all we need is to prove that neither case (1) nor case (4) is impossible.<\/p>\n Case (1): Now assume that we don\u2019t charge at station\u00a0b<\/em>\u00a0at all. Then we can construct a new solution which is the same as the old solution except we skip station\u00a0b<\/em>. Since we didn\u2019t charge at\u00a0b<\/em>\u00a0in the old solution, the car has enough range to travel from\u00a0a<\/em>\u00a0to\u00a0b<\/em>\u00a0and\u00a0c<\/em>\u00a0in the old solution. Therefore the car also has enough range to travel from\u00a0a<\/em>\u00a0to\u00a0c<\/em>\u00a0directly in the new solution. Therefore we found a solution with one less station and it takes at most as much time as the old solution. This is a contradiction with the fact that the old solution is an optimal solution with the lowest number of stations. Therefore we proved that case (1) is impossible for any intermediate station in such solutions.<\/p>\n Case (4): Assume that we charge at station\u00a0b<\/em>\u00a0so that we have more than enough gas to reach\u00a0c<\/em>\u00a0but not fully charge.<\/p>\n Because of Lemma 3 we know that\u00a0c<\/em>\u00a0cannot be the destination, otherwise we will reach the destination with non-zero range, which is a contradiction because we just proved case (1) is impossible. Therefore we know\u00a0c<\/em>\u00a0must be an intermediate station as well. There are 3 sub-cases:<\/p>\n Case (4.1): charging station in\u00a0c<\/em>\u00a0is faster than\u00a0b<\/em>. Because we always charge and we charge more than enough in\u00a0b<\/em>. Therefore we can construct a new solution such that we charge a little bit less in\u00a0b<\/em>\u00a0and a little bit more in\u00a0c<\/em>. Since charging station\u00a0c<\/em>\u00a0is faster, the new solution is better, which is a contradiction.<\/p>\n Case (4.2): charging station in\u00a0c<\/em>\u00a0is slower than\u00a0b<\/em>. Because we don\u2019t fully charge at\u00a0b<\/em>\u00a0and we always charge at\u00a0c<\/em>. We can construct a new solution such that we charge a little bit more in\u00a0b<\/em>\u00a0and we charge a little bit less in\u00a0c<\/em>. Since\u00a0c<\/em>\u00a0is slower, the new solution is better, which is a contradiction.<\/p>\n Case (4.3): charging station in\u00a0c<\/em>\u00a0is as fast as\u00a0b<\/em>. There are 2sub-cases:<\/p>\n Case (4.3.1): we can skip charging station\u00a0b<\/em>\u00a0in the old solution. Then construct a new solution by skipping\u00a0b<\/em>\u00a0and charge more at\u00a0c<\/em>. We spend as much time in charging, spend at most as much time in traveling, but we have one less station in the new solution. It\u2019s a contradiction with the fact that the old solution is an optimal solution with fewest number of stops.<\/p>\n Case (4.3.2): we cannot skip charging station\u00a0b<\/em>\u00a0in the old solution. Then we charge just enough at\u00a0b<\/em>\u00a0to reach\u00a0c<\/em>\u00a0and we charge more at\u00a0c<\/em>. Then we constructed a new solution with the same travel time and the same charging time, and the total number of stations in the output is the same, and we have one less intermediate station without the property, which is a contradiction.<\/p>\n The first step of the algorithm is to handle the special case which we don\u2019t need to charge at all. (Lemma 1)<\/p>\n With these Lemmas, we can construct a polynomial algorithm to find a optimal solution by search only paths where all intermediate station has the property in Lemma 3.<\/p>\n The algorithm has multiple passes of computations.<\/p>\n First, we compute the distance\u00a0d_i,j<\/em>\u00a0between every pair of node.<\/p>\n Second, we find the shortest-time path\u00a0a0_i,j<\/em>\u00a0between every pair of stations such that we start with zero range, and reach the destination with zero range, and we never charge to the full range. By Lemma 3 we know that in this case we always charge just enough to reach the next station, thus we can use Floyd-Warshall algorithm to find all\u00a0a1_i,j<\/em>, using\u00a0d_i,j<\/em>\u00a0and the corresponding charging time as edges.<\/p>\n Third, we find the shortest-time path\u00a0a1_i,j<\/em>\u00a0between every pair of stations such that we start with full range, reach with zero range, and never reach zero range or full range in between. With Lemma 3 we know that there is only two possibilities: (1) the path has length 2 and the distance is the same as the range. (2) for all pats with length > 2, we know that in all intermediate station we can only charge enough to reach the next station, then the next station must has zero range. Then with the fact that we can only reach zero range in the destination we know that this path has length 3. Therefore we can compute all\u00a0a1_i,j<\/em>\u00a0by brute force with\u00a0O(n^3)<\/em>\u00a0complexity.<\/p>\n Fourth, we find the shortest-time path\u00a0a2_i,j<\/em>\u00a0between every pair of stations such that we start with full range, reach with zero range, and never reach full range in between. They can be computed with all\u00a0a1_i,k<\/em>\u00a0and\u00a0a0_k,j<\/em>\u00a0pairs in\u00a0O(n^3)<\/em>\u00a0time.<\/p>\n Fifth, we find the shortest path\u00a0a3_i,j<\/em>\u00a0between every pair of stations such that we start with full range and reach with full range. This can be computed by using a second pass of Floyd-Warshall algorithm, with\u00a0a2_i,j<\/em>\u00a0with charging time and\u00a0d_i,j<\/em>\u00a0with charging time as edges.<\/p>\n Finally, because of Lemma 2, we can , consider all\u00a0a2_s,t<\/em>\u00a0and all\u00a0a3_s,k<\/em>\u00a0and\u00a0a2_k,t<\/em>\u00a0to find the final solution.<\/p>\n Since every pass is\u00a0O(n^3)<\/em>\u00a0time, the final algorithm is O(n^3).<\/p>\n This is my solution in C++. I used macros intensively. It\u2019s generally not a good practice to use macros since it sometimes cause bugs without generating proper compilation errors. However in this particular problem I found macros very useful to beautify the code.<\/p>\n As you can see, even though the proof of this algorithm is very complicated, the actual program is surprisingly simple. The core of the program is only 10 line long, containing 4 passes of\u00a0n^3<\/em>\u00a0loops.An Even Better Algorithm<\/p>\n With the three lemmas we can find a solution even better than the one above.<\/p>\n This solution is a modification of Tesla\u2019s solution. Instead of considering all possible range at every station, we only construct vertices for the full range, the empty range, the ranges such that it is just enough to reach another station, or the remaining range when we arrive the station from another station with full range. Then there are only O(n^2) vertices in this graph.<\/p>\n And then we add edges between stations only when the first vertex of the edge is full range or the second vertex of the edge is zero range. There are at most\u00a02n^2<\/em>\u00a0such edges. And we only add edges among vertices corresponding to a single station only if the second vertex of the edge is the next vertex with higher range comparing to the first vertex of the edge. There are at most\u00a02n^2<\/em>\u00a0such edges. Therefore the total number of edges is at\u00a0O(n^2)<\/em>.<\/p>\n And then we can use Dijkstra algorithm to find the final solution.<\/p>\n The time to add edges is\u00a0O(n^2 log n)<\/em>\u00a0because we need to sort the vertices corresponding to a single station. If we use Dijkstra algorithm with Fibonacci heap, the time complexity to find the shortest path is also\u00a0O(n^2 log n)<\/em>. Therefore, the final time complexity of this algorithm is also\u00a0O(n^2 log n)<\/em>.<\/p>\n Even though this algorithm is faster in complexity and easier to reason about, it is much harder to write the code down because I need to write the Dijkstra algorithm, an\u00a0O(n log n)<\/em>\u00a0sorting algorithm, and a Fibonacci heap. Also in the 303 station network provided by Tesla, this algorithm is not necessarily faster. Therefore I didn\u2019t implement this algorithm.<\/p>\n I didn\u2019t get a job offer in the end. The coding challenge went well. The recruiter submitted my information to the hiring managers of two different teams. And then the asked me where I was from. I said \u201cChina\u201d. Then the recruiter just stopped the interview process abruptly and denied my applications to both teams.<\/p>\n Lessons learned:<\/p>\n (1) Always reveal your ethnicity when applying for jobs. That\u2019s why I have my photo in my homepage. The company is going to know your ethnicity sooner or later. It\u2019s better to get discriminated before the interview starts so you don\u2019t waste time. Also, I believe racism is fundamentally wrong ethically. If a company is practicing racism, you know they are evil and\u00a0it would not be a good company to work for, regardless of your ethnicity.<\/a>\u00a0So reveal your ethnicity is a good way to efficiently avoid evil companies like Tesla.<\/p>\n (2) Never ever work on take-home interview problems. Your time is precious. For every hour you spend on your job application, you need to make sure someone\u00a0at your level<\/strong>\u00a0spend an hour on your application. This is very important to make sure they take your application seriously. 1-to-1 interviews are expensive for companies. Thus they give 1-to-1 interviews only after they review your background and experience, and think there is a good chance they will hire you. However, take-home problem is basically free for them. Their best strategy is to give take home problems to as many people as possible, and only start looking into your background and experience after you finish the problem. It means there is a good chance you will be rejected by something on your resume, even after you spend a long time working on their take-home interview problem.<\/p>\n Anyway, this problem is still my favorite interview problem of all time. There are three reasons.<\/p>\n (1) There are so much depth in this problem. There is an exponential brute force algorithm. There is an approximation algorithm. And we can find two polynomial algorithms if we spent time studying the properties of the optimal solutions. One of the polynomial algorithms is so simple that it just contains four 3D loops.<\/p>\n (2) This problem shows how much better I am comparing to the Tesla people.<\/p>\nAssumptions<\/h5>\n
\n(2) Each charging station has a longitude-latitude coordinate. And the Earth is a sphere of radius 6356.752km.
\n(2) The car travels at a constant speed of 105km\/hr along great circle routes between stations.<\/p>\nExample<\/h5>\n
.\/solution Council_Bluffs_IA Cadillac_MI<\/code> might return:<\/p>\n\nCouncil_Bluffs_IA, Worthington_MN, 1.18646, Albert_Lea_MN, 1.90293, Onalaska_WI,\n0.69868, Mauston_WI, 1.34287, Sheboygan_WI, 1.69072, Cadillac_MI\n<\/code><\/pre>\nTesla\u2019s Solution<\/h5>\n
![\"figure](\"https:\/\/farm8.staticflickr.com\/7808\/40451247803_939c1d3a84_o_d.png\")
Please note that this is an approximate algorithm, which means it just does not return the optimal solution. Since Tesla\u2019s original problem description asked for optimal solution, Tesla\u2019s own solution is technically wrong.Also, even though this algorithm is easy to reason about, it is actually much harder to implement comparing to my optimal solution. You will see how simple my code is in a moment.<\/p>\n<\/code><\/pre>\nA Polynomial Solution<\/h3>\n
Lemma 1: If the distance between\u00a0s<\/em>\u00a0and\u00a0t<\/em>\u00a0is greater than the maximum range, the best solution always contain charging time greater than zero. Otherwise, the best solution is to go from\u00a0s<\/em>\u00a0to\u00a0t<\/em>\u00a0directly.<\/h5>\n
Lemma 2: In the optimal solution, we always reach the destination with the zero remaining range.<\/h5>\n
![\"figure](\"https:\/\/farm8.staticflickr.com\/7886\/46693580534_450bbefe4a_o_d.png\")
<\/p>\nLemma 3: There always exists an optimal solution where every intermediate station\u00a0b<\/em>\u00a0has the following property: we always charge the car at\u00a0b<\/em>, and we either fully charge the car, or we charge just enough to reach the next station.<\/h5>\n
![\"figure](\"https:\/\/farm8.staticflickr.com\/7802\/40451247753_bd7930dd6f_o_d.png\")
<\/p>\n![\"figure](\"https:\/\/farm8.staticflickr.com\/7904\/46693580454_3eb40abe21_o_d.png\")
<\/p>\n![\"figure](\"https:\/\/farm8.staticflickr.com\/7891\/40451247703_6d986de198_o_d.png\")
<\/p>\n<\/p>\n<\/p>\nAlgorithm<\/h4>\n
![\"figure](\"https:\/\/farm8.staticflickr.com\/7925\/46693580434_aa30898992_m_d.jpg\")
<\/p>\n![\"figure](\"https:\/\/farm8.staticflickr.com\/7919\/46693580404_b12b1edb0b_o_d.png\")
<\/p>\n![\"figure](\"https:\/\/farm8.staticflickr.com\/7818\/46693580384_5637c646c9_m_d.jpg\")
<\/p>\n![\"figure](\"https:\/\/farm8.staticflickr.com\/7843\/40451247653_6b9f58ce82_o_d.png\")
<\/p>\nMy Program<\/h4>\n
Aftermath of the Interview<\/h3>\n
\n#include "network.h"\n#include \n\n#define N 303\n#define G 320.\n#define V 105.\n#define L 4\n#define INF 67108864.\n#define R 6356.752\n#define SQ(x) ((x)*(x))\n#define d2r(x) (x\/180.*3.14159265358979323846264338327950288419716939937510)\n\n#define LOOP(x,y) for(int x=0;x<y;++x)\n#define LOOP(x) LOOP(x,N)\n#define LOOP1 LOOP(i)\n#define LOOP2 LOOP1 LOOP(j)\n#define LOOP3 LOOP(k) LOOP2\n#define RELAX(x,y,u,v) if(y<x){x=y;u=v;}\n\nusing namespace std;\n\nstring sn, tn;\nint s,t;\ndouble a[L][N][N], d[N][N], g[N];\nint A[L][N][N];\n\nbool input(int argc, char** argv) {\n if (argc != 3) return false;\n sn = argv[1];\n tn = argv[2];\n \n s = t = 0;\n while (s < network.size() && network[s].name != sn) ++s;\n while (t < network.size() && network[t].name != tn) ++t; if (s >= network.size() || t >= network.size()) return false;\n \n return true;\n}\n\nstring output(int l, int i, int j) {\n if (i == j) return "";\n if (l == 0) {\n if (A[l][i][j] < 0)\n return " " + to_string(d[i][j]*g[i]\/V) + " " + network[j].name;\n return output(0, i, A[l][i][j]) + output(0, A[l][i][j], j);\n }\n if (l == 1)\n return " " + network[A[l][i][j]].name + " "\n + to_string((d[i][A[l][i][j]]+d[A[l][i][j]][j]-G) * g[A[l][i][j]] \/ V)\n + " " + network[j].name;\n if (l == 2)\n return output(1, i, A[l][i][j]) + output(0, A[l][i][j], j);\n if (A[l][i][j] == -1)\n return output(2, i, j) + " " + to_string(g[j]\/V);\n if (A[l][i][j] == -2)\n return " " + network[j].name + " " + to_string(d[i][j] * g[j] \/ V);\n return output(3, i, A[l][i][j]) + output(3, A[l][i][j], j);\n}\n\nint main(int argc, char** argv)\n{\n if (!input(argc, argv)) {\n cout << "Error: requires initial and final supercharger names" << endl; return -1; } LOOP1 g[i] = V \/ network[i].rate; LOOP2 d[i][j] = R*2.*asin(sqrt(SQ(sin(d2r((network[i].lat-network[j].lat)\/2.))) + cos(d2r(network[i].lat))*cos(d2r(network[j].lat)) * SQ(sin(d2r((network[i].lon-network[j].lon)\/2.))))); LOOP2 if (d[i][j] > G) d[i][j] = INF;\n if (d[s][t] <= G) {\n cout << sn + " " + tn << endl; return 0; } LOOP(l,L) LOOP2 a[l][i][j] = INF; LOOP(l,L) LOOP2 A[l][i][j] = -1; LOOP2 a[0][i][j] = d[i][j] * (g[i]+1.); LOOP3 RELAX(a[0][i][j], a[0][i][k] + a[0][k][j], A[0][i][j], k); LOOP3 if (d[i][k] + d[k][j] >= G)\n RELAX(a[1][i][j], G + (d[i][k]+d[k][j]-G)*(g[k]+1.), A[1][i][j], k);\n \n LOOP3 RELAX(a[2][i][j], a[1][i][k] + a[0][k][j], A[2][i][j], k);\n \n LOOP2 a[3][i][j] = a[2][i][j] + g[j] * G;\n LOOP2 RELAX(a[3][i][j], d[i][j] * (1. + g[j]), A[3][i][j], -2);\n LOOP3 RELAX(a[3][i][j], a[3][i][k] + a[3][k][j], A[3][i][j], k);\n \n int m = INF, M = -1;\n LOOP1 RELAX(m, a[3][s][i] + a[2][i][t], M, i);\n if (M < 0)\n cout << "No path exists." << endl;\n else\n cout << sn + output(3, s, M) + output(2, M, t) << endl;\n \n return 0;\n}\n<\/code><\/pre>\n