[Programming] TIPS TO BE COMPETITIVE

Question 1

There are n webpages (1 ≤ n ≤ 10M). Each webpage i has different page rank r_i. You want to pick top 10 pages with highest page ranks. Which method is more feasible?
(a) Load all n webpages’ page rank to memory, sort, and pick top 10.
(b) Use priority queue data structure (heap).

Question 2

Given a list L of up to 10K integers, you want to frequently ask the value of sum(i, j), i.e. the sum of L[i] + L[i+1] + ... + L[j]. Which data structure should you use?
(a) Simple Array.
(b) Balanced Binary Search Tree.
(c) Hash Table.
(d) Segment Tree.
(e) Suffix Tree.
(f) Simple Array that is pre-processed with Dynamic Programming.

Question 3

You have to compute the ‘shortest path’ between two vertices on a weighted Directed Acyclic Graph (DAG) with |V |, |E| ≤ 100K. Which algorithm(s) can be used?
(a) Dynamic Programming + Topological Sort.
(b) Breadth First Search.
(c) Dijkstra’s.
(d) Bellman Ford’s.
(e) Floyd Warshall’s.

Question 4

Which algorithm is faster (based on its time complexity) for producing a list of the first 10K prime numbers?
(a) Sieve of Eratosthenes.
(b) For each number i ∈ [1 − 10K], test if i is a prime with prime testing function.