Find the rotation count in rotated sorted array

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

**Question : **Find the minimum element in the rotated sorted array. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Solution This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array. [Read More]
ArraySearch  kodeknight  recursion  array  rotated array  count  min  sorted-array 

Random Contraction Algorithm

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

This algorithm was designed by Karger in 1990, as phd student at stanford. This algorithm is used to solve the min cut problem, which is : Input - An undirected graph G = (V,E) , (note that parallel edges are allowed) Goal - Tom compute a cut with fewest number of crossing edges (a min cut) Karger’s Algorithm We will have just one mail loop, and algorithm terminates when only 2 vertices are remaining. [Read More]
Graph  kodeknight  incomplete 

Graph Representations

 Posted on August 24, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

We have already discussed what are graphs here. Now graph can be represented in 2ways: Adjacency matrix  Adjacency list Adjacency Matrix Undirected graph Represent G by a nXn, n being number of vertices 0-1 matrix A, where Aij = 1 for every edge between 2 nodes. Undirected graph with parallel edges Aij = b*1 where b is number of parallel edges between i and j. Weighted Undirected graph [Read More]
Graph  kodeknight  incomplete 

Cuts of Graphs

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

A cut of a graph (V, E) is a partition of a graph into two non-empty sets A and B. Each set contains only the vertices that connect one vertex in the set to another in the set. Meanwhile, there are also edges connecting the vertices from set A to set B and vice versa. For eg. Similarly we have directed graph. Edges, that cross from A, to B are called are crossing edges. [Read More]
Graph  kodeknight  Data Structure 

Integer Multiplication using Karatsuba algorithm

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

Normal Integer method If we consider the integer multiplication, we need 2 integers and output is also integer. Suppose we have to multiply 5678*1234. In the normal way, we will realize following: 5678 X 1234 \------------ 22712 //first number multiply as is i.e. 4\*5678 17034- //2nd time, shift (left) and then multiply the number as 3\*5678 11356-- //shift twice 5678--- //shift thrice \------------ 7006652 ```So, each time we multiply, depending on the digit of the 2nd number, we shift and then multiply. [Read More]
master-method  kodeknight  time complexity  divide and conquer  incomplete  multiplication 

Data Type in Data Structure

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

Before discussing data type in data structure, i am going to describe data, basis of categorization of these data, and advanced categories of data. DATA :- Data can be defined as a value or set of values. These values may represent some observations from an experiment, some figures collected during some surveys, marks obtained by a student in an examination, etc. DATA ITEM :- A data item refers to a single unit of values. [Read More]
kodeknight  Data Structure  data types 

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 

Given a dictionary of word - Group all words into set of anagrams of each other

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

Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets. input: “bat”, “tar”, “xyz” , “tab”, “tar” output:[[“bat”, tab”], [“tar”, rat”],”xyz” ] Anagrams Two words are anagrams if one of them has exactly same characters as that of the another word. Example : Anagram & Nagaram are anagrams (case-insensitive). Approach The simpler logic would be to : [Read More]
kodeknight  Microsoft  String  Amazon  anagrams