My strategy to solve an algorithmic challenge in 60 mins

Refresher and also a guide for newbies. (Work in progress!)

I have been applying for jobs in different organisations (after 5 years of startups), mostly in other countries than my own. It would be fun and an adventure to explore a new culture.

The time compartments below are not hard and fast. They are an after thought.

Time to solve a problem: 60 mins.

0–10 mins: Mathematics

Use pen and paper extensively to solve the problem for some datasets.

  1. Read the problem carefully and try solving it manually on paper.
  2. Identify the patterns in the data doing so.
  3. Formulate rules for the patterns found, such as — if I see XYZ pattern in data, I would next see ABC.

10–20 mins: Algorithm

Write some pseudo-code. See APPENDIX 1 (cheet sheet).

  1. Think of algorithms you can use to solve the problems.
  2. Think of the data structures you need to create to solve the problem.
  3. At this point, you might have two candidates for data structures that you can use.

20–30 mins: Code

Start writing some code and create a dirty solution.

  1. Figure out how you would read data from file into those structures.
  2. If you had two data structure candidates in the earlier step, choose one that seems to work better.
  3. Apply the algorithms and make it work on simple datasets.

30–40 mins: Fix

Do bug fixes and make it work on all datasets.

40–60 mins: Optimise

We can use the last 20 mins to optimise our solution.

  1. Expect to see timeouts with some datasets or runs out of memory.
  2. Add pre-processing steps to the existing data structures, where the computation is lesser or where the space used is lesser (ex. remove recursion and use queues).
  3. See if you are cracking more datasets.

Hope that leaves you better prepared to solve algorithmic challenges.

APPENDIX 1 (Work in Progress!!!)

Choosing the right data structure, given our algorithm (used in the solution).

Requirement: Algorithms where we traverse in some order inside the graph, such as DFS, BFS, Topological Sort.

Data structure: Graph

A graph consists of two lists — Nodes and Edges (usually ArrayLists)

private List<Vertex<T>> verticies = new ArrayList<Vertex<T>>();
private List<Edge<T>> edges = new ArrayList<Edge<T>>();

Vertex will have a value (indicative of node number) and edge (Edge class) will have two vertices (Vertex class) ‘from’ and ‘to’.

You can add below to a vertex to create a faster access to adjacent edges.

ArrayList<Vertex<T>> neighbours;

or Weak reference it.. ( Reminder: to access a WeakReference object, we use weakref.get() )

ArrayList<WeakReference<Vertex<T>>> neighbours;

If the graph is a tree (or unidirected graph), each vertex can have — parent(/s) and children.

We can HashMap to find Vertex object, given their key/index value and different edges related to the Vertex.

So the Vertex stores some value and also (optionally) various edges associated with it.

Another way to store a Graph is to use a Matrix. Its not often used for large data sets (say, 1024 vertices … is 1MB x (bytes used per Edge)). So maybe we can run it till we are limited to (50K vertices)…