#### Transcript of Who is not doing the challenge?

Who is not doing the challenge?

Given head pointer of a linked list, sort linked list (in ascending order) using insertion sort and return new head pointer of the sorted linked list.

Given head node of two linked lists, they amy or may not intersect. If they intersect, then return their intersection point, otherwise return null.

Given a singly linked list, return nth from last node. Return null if 'n' is out-of-bounds.

Given a singly linked list, reverse nodes at even indices.

Given head node of a singly linked list and an integer n, rotate linked list by n.

* Oriented or non-oriented graph.

* n vertices and m edges.

* All weights are non-negative.

* Given the starting vertex s, find the lengths of the shortest path from s to all other vertices.

* Single-source shortest paths problem.

d[v] - the current shortest path length from s to v

Init: d[v] = INF for all v <> s; d[s] = 0;

u[v] - true if visited, false - otherwise

Init: u[v] = false

n iterations

On each iteration: d[v] = min {d[p]} where p: u[p] = false

Relaxation: d[to] <?= (d[v] + len) where len is the distance v -> to

Time complexity:

* n times - find the vertex with the minimum d[v] among O(n) vertices

* m relaxation attempts

* The total time complexity: O(n^2 + m)

**Fail a lot.**

**TopCoder & USACO**

Can we do better?

O(n^2 + m) is optimal for dense graphs where m ~ n^2. The less dense the graph is, the less optimal the complexity is. Everything due to n^2. So our goal is to improve the time to find the vertex with the minimum d[v] while not making the relaxation too much worse.

As a compromise, let’s make both operations O(logn). Then we have O(n*logn + m*logn) = O(m*logn) by using set or priority_queue.

Even if you never use Dijkstra in life, at least you can earn some karma on Quora.

This week my Wed interview hours will be held on Tuesday.

Full transcript