Hash Functions

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

Importance of Hash function Why Hash-function matter? Chaining implementation of hashtable We will discuss about hashtable with chain. Insertion in the hashtable is O(1), so does lookup. Invoke hash function and see where is our bucket. Now go to the bucket and traverse the list until we find our element. Suppose we have 100 elements which are inserted in the hash function, then we have Lucky hash function - 1 element per bucket [Read More]
kodeknight  hashtable  hashes 

find four elements in array whose sum equal to a given number X

 Posted on August 30, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

This can be solved efficiently via using HashTables. We can have a hashtable sums sums will store all possible sums of two different elements. For each sum S it returns pair of indexes i and j such that a[i] + a[j] == S and i != j. But initially it’s empty, we’ll populate it on the way. So, this can be done in O(n^2) time. Pseudocode for (int i = 0; i < n; ++i) { // 'sums' hastable holds all possible sums akk + all // where k and l are both less than i for (int j = i + 1; j < n; ++j) { int current = aii + ajj; int rest = X - current; // Now we need to find if there're different numbers k and l // such that akk + all == rest and k < i and l < i // but we have 'sums' hashtable prepared for that if (sumsrestrest ! [Read More]
kodeknight  array  hashtable  sum 

Pathological Data Sets and Universal Hashing Motivation

 Posted on August 11, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

We will go deep inside hash function, where we will find every hash table has its Kryptonite, i.e some pathological data set, which will make it vulnerable. **Note:**To continue on this article, please first read the article - Hash Tables. The Load factor or Load of a hash table It tells us how populated the hash table is.It is denoted by alpha (α) α = (number of objects in the hash table) / (number of buckets in the hash table) [Read More]
kodeknight  hashtable 

Hash Tables

 Posted on August 10, 2013  (Last modified on August 7, 2020)  |  11 minutes  |  Kinshuk Chandra

A hash table is primarily used to keep track of an evolving set of stuff by using a key. It is good for inserting, deleting, and lookups. It is also sometimes referred to as a “dictionary.” They are similar to array in a way, that array gives information at the index very fast, if you know the index. Suppose, your friend names are integer, and you save the number in the array. [Read More]
theory  kodeknight  hashtable  Data Structure 

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 

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 

Vertical Sum of a Binary Tree

 Posted on December 18, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

please explain doubly linked list method in words Anonymous - Apr 6, 2014please explain doubly linked list method in words Added the basic algo for that: 1. Start with the root node and empty double list listNode 2. Add the value of the rootNode to the current listNode 3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively. 4. Similarly for right node Please let me know if I have not explained it properly. [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL 

Vertical Sum of a Binary Tree

 Posted on December 18, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question : Find vertical sum of given binary tree. Example: 1 / \\ 2 3 / \\ / \\ 4 5 6 7 The tree has 5 vertical lines Vertical-1: nodes-4 => vertical sum is 4 Vertical-2: nodes-2 => vertical sum is 2 Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12 Vertical-4: nodes-3 => vertical sum is 3 Vertical-5: nodes-7 => vertical sum is 7 We need to output: 4 2 12 3 7 [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL