Bloom filters

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  6 minutes  |  Kinshuk Chandra

The bloom filter is a data structure designed in 1970. It is similar to a hash table. They are more efficient than a hash table, but they do raise false positives at times. Supported Operations A bloom filter supports super fast lookup and insertion, just like a hash table. So why have this data structure? Pros It is much more space efficient. It takes the space even less than that of the object. [Read More]
cpp  kodeknight  Data Structures  DS  incomplete  hashtable 

AVL Tree : Rotations

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

A tree rotation can be an imtimidating concept at first. You end up in a situation where you’re juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast. I find it helps to block out what’s going on with any of the subtrees which are attached to the nodes you’re fumbling with, but that can be hard. Left Rotation (LL) or Single Left rotation [Read More]
tree  kodeknight  balanced trees  avl 

Sorting in Hungarian Way

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Checked out some videos on youtube. You too have a look:

Quick Sort:

Insertion Sort

Bubble Sort

Shell sort

Merge Sort

kodeknight  sorting  fun 

How to rotate an array?

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

One of the classic problems with array is to perform in-place rotation on the array. For example, if we have an array of integers such as int[]array = new int[]{1, 2, 3, 4, 5, 6} and we want to rotate it around index 2, then the rotated array is {3, 4, 5, 6, 1, 2}. So, how can we rotate an array around a given index? Well here is the algorithm with explanation follows after: [Read More]
kodeknight  array  rotated array 

2 Sum Problem : Given an integer array and a number T, find all unique pairs of (a, b) whose sum is equal to T

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

how to build the hash table in the approach 3. als… Unknown - Feb 3, 2014how to build the hash table in the approach 3. also i think you should check if hash(T-arr[i]) is empty first. This comment has been removed by the author. Hi Jianchen, I think we can use hashmap or we can use element as an index in the array. I think only way hash() is empty when the given array is null or has no element. [Read More]
kodeknight  2Sum  sorting  array  hashtable  pair  unique  sum 

2 Sum Problem : Given an integer array and a number T, find all unique pairs of (a, b) whose sum is equal to T

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x,y in A with x+y=T. Example : Suppose we have an int array = {5, 3, 7, 0, 1, 4, 2} and T = 5. The unique pairs that sum up to 5 are (5, 0) (3, 2) and (1, 4). There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable. [Read More]
kodeknight  2Sum  sorting  array  hashtable  pair  unique  sum