The Union Find problem leads to an understanding of some very interesting data structures.

**References:**

Skip to content
#
datastructures

# Union-Find

# Techniques for Approximate Counting

# An Activity Selection Problem

# Multi-dimensional (axial) data handling in Python

The Union Find problem leads to an understanding of some very interesting data structures.

**References:**

In many scenarios, we can live with approximations in counting.

There are a few techniques in particular which are increasingly being used in online scenarios. Example, services like RedShift, Redis and Spark have in built support for these data structures.

- Hyper Log Log.
- Count Min Sketch.
- Bloom Filters.
- Locality Sensitive Hashing.

**References:**

**Code:**

There is a very interesting problem I recently came across as part of Google’s foobar challenge. The problem is called ‘zombie antidote’.

I wanted to write down some thoughts as I made my way towards solving this problem.

**Thoughts:**

- The problem smells like Dynamic Programming.
- However, there are some challenges in coming up with the DP solution
- How to build up the optimal substructure (aka. recurrence relation) for the problem ?
- How to show overlapping subproblem property ?

- It is useful to look at problems from different perspectives.
- E.g. Can the activity selection problem be formulated as a Graph theory problem ?

**Tips**:

- Refresh basics of Dynamic Programming Algos.
- Especially useful here was understanding the
**cut-rod problem**from Cormen’s algo book

- Especially useful here was understanding the
- Understanding the relationship between the following 3 fundamental algorithmic approaches.
- Dynamic Programming
- Greedy Algorithms
- Graph Theory

- As it turns out, the activity selection problem can indeed be formulated in all of the 3 algo approaches listed above.

**Code:**

**References:**

Recently I was playing around with multi-dimensional data structures in Python.

Some interesting observations:

- Multi-dimensional lists and multi-dimensional arrays are fundamentally handled differently.
- Slicing of multi-dimensional arrays (numpy) need to be carefully considered in regards to shallow copy etc

Some references below for further examination:

**References:**

- http://ilan.schnell-web.net/prog/slicing/
- https://docs.python.org/2/library/copy.html
- http://stackoverflow.com/questions/509211/explain-pythons-slice-notation
- http://cs231n.github.io/python-numpy-tutorial/
- http://www.physics.nyu.edu/pine/pymanual/html/chap3/chap3_arrays.html
- http://www.astro.ufl.edu/~warner/prog/python.html