### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# Who is not doing the challenge?

No description
by

## Arman Suleimenov

on 20 April 2015

Report abuse

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

Who is not doing the challenge?
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