Red Black Tree – Insertion

Introduction: Please refer the introduction of RBT here. So, we now know the invariants or properties of RBT which make it rbt :) Insertion of element in RBT or red black tree breaks one of the 4 invariants or properties. So we have to fix it in minimal possible way. To assist us with we have 2 solutions : Flipping the color Right and left rotation Insertion: Insertion begins by adding the node much as binary search tree insertion does and by coloring it red. The insertion of red node can cause red violation so we are going to fix it after...

Read More

Red Black Tree – Deletion

Deletion of a node from a red black tree is very difficult. During insertion we selected the color of a new node as red to make it easier. We forced a red violation and fixed it. Red violations are easy to fix, and we took full advantage of that to produce a truly elegant recursive algorithm. When you want to delete a node, you don’t have the option of choosing its color. If it’s red, that’s good. Red nodes can be removed without any violations....

Read More

Bloom filters

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. So, we don't even worry about what the object is, but we only care about whether we have seen that object or not. So, you may have used something...

Read More

AVL Tree : Deleting a node from AVL Tree

Deleting the node works the same way, when we delete the node, if it upsets the balance, it will have to re-balance. Eg. Consider the t...

Read More

AVL Tree : Rotations

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 Imagine we have this situation: a \ b \ c To fix this, we must perform a left rotation, rooted at A. This is done in the following steps: b becomes...

Read More

Bitonic Sort

http://xlinux.nist.gov/dads/HTML/bitonicSort.h...

Read More

Bidirectional Bubble Sort

http://sanjaal.com/java/198/java-data-structure/java-code-implementation-of-bidirectional-bubble-so...

Read More

Priority Queue based on Sorted Linked Lists

http://chinmaylokesh.wordpress.com/2011/10/16/priority-queue-based-on-sorted-linked-lis...

Read More

Sorting in Hungarian Way

Checked out some videos on youtube. You too have a look: Quick Sort: Insertion Sort Bubble Sort Shell sort Merge Sort...

Read More

How to rotate an array?

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: public void reverseArray(int[] array, int start, int end) { int i; int temp; while (start < end) { temp = array[start]; array[start] = array[end]; array[end]...

Read More

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

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/2sum-problem/. 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...

Read More

Printing "Hello World" to screen without using a single semicolon in C/C++

When I first encountered this question, I thought it was impossible. However, there are ways to do so. I don't know if the solutions are exploitation of c / c++. Anyway, here are the most common solutions: int main() { if (printf("Hello World \n")) { } } Or you can use the while loop like this: int main() { while (printf("Hello World") > 20) { } }If you don't think these codes will work, try them out. They are weird but work well in c / c++. Notice: These don't work in Java. Not sure about other languages, so use them responsibly....

Read More

Construct a full binary tree from a pre-order list of marked nodes

Question: construct a full binary tree from a list of nodes in pre-order. The nodes are marked 'i' if they are inner nodes and are marked 'l' if they are leaf nodes. Example given a list of nodes marked as (i, i, i, l, l, i, l, l, i, l, l), we need to construct a tree from those nodes so that the result looks like this: Notice how all "l" nodes are leaf nodes and "i" nodes are inner nodes? Moreover, since the nodes are given in pre-order,...

Read More

Converting integers less than 100 to words

This is a classic problem in which we're given an integer less than 100 and we have to output the words corresponding to the integer's value. For instance, if input is 90, then the output is "ninety" Moreover, if the input is -99, then the output is "incorrect input" To solve this problem, we should have arrays of unique names such as "one" and "thirteen". The reason is that other integers' names are made up of just those unique names. For example, "nine" is unique name and "ninety" is unique name while "ninety nine" is just made up of "ninety"...

Read More

Find all subsets of a given set OR Find power set of a given set

Problem Write a method that returns all subsets of a set. Example If we're given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the set of all subsets i.e. P(S) we get are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Here is {} is empty set denoted by Φ. If S has n elements in it then P(s) will have 2^n elements.P(S) is also called power set. Solution This can be solved in couple of ways using recursion, backtracking. Method 1 - Using recursion If we have to find...

Read More

Turning a bit off without affecting other bits

Hello and welcome to the second part of "Bit Manipulation Tips & Tricks." If you haven't read the first part yet, here is the link of you. Read it! :) 1. Turning a bit off without affecting other bits Turning a bit off means to change 1 bits (on) to 0 bits (off) and if the bits are already off then they'll stay off. This can be accomplished by using the ~, << and & operators. Here is the genera formula: turnBitOff (int bitString, int bitPosition) { return bitString & ~(1 << bitPosition); } bitString: is the...

Read More

Bit Manipulation Tips and Tricks

In this series, we'll try to compile a list of tips and tricks that are useful for performing bitwise operation. Multiply a number by a power of two using bit left shift Divide a number by a power of two using bit right shift Toggle a specified bit in a bit string without effecting other bits Checking if a bit is on or off without affecting other bits Turning a bit off without affecting other bits C code to check if an integer is a power of 2 or not in a single line Find Position of the only Set Bit C program to count bits set in an...

Read More

Removing a loop in a singly linked list

Problem: Remove a loop from a singly linked list if the list has a loop. Example For example, 1->2->3->4->1 (4 points to the head node 1) should become 1->2->3->4 while 1->2->3->4 should stay the same 1->2->3->4. Solution   The problem has 3 steps : Detect if there is a loop in the list (already solved here) Identify the start of the loop (already discussed here) Delete the loop, which we will discuss here. Please go through 1 and 2. Once you know where the loop starts, it's easy to identify...

Read More

Finding an integer that repeats odd number of times in an array of positive integers

Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity? Solutions Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. Thus, if a number appears a even number of times, it yield a result of 0. For example, given the array {2, 3, 2, 3}, we have...

Read More

Maximum continuous sum subarray problem

Problem You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum. EXAMPLE Input: {2, -8, 3, -2, 4, -10} Output: 5 (i.e., {3, -2, 4}) Solution  Method 1 - Brute force The outer loop picks the beginning element, the inner loop finds the maximum possible sum with first element picked by outer loop and compares this maximum with the overall maximum. Finally return the overall maximum. The time complexity of the Naive method is O(n^2). Method 2 - Divide and conquer 1)...

Read More

Andersson Trees

http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.a...

Read More