BTree in java
Posted on January 5, 2012 (Last modified on August 7, 2020) | 0 minutes | Kinshuk Chandra
BTree in java
Red Black tree
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them “symmetric binary B-trees”, but acquired its modern name in a paper in 1978 by Leo J. Guibas and Robert Sedgewick, due to printing press technology of that time. Unfortunately, they were not able to print the paper in red black ink as was supposed, but the name stayed.
[Read More]
Heap Sort in java
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Heap sort Algorithm
This algorithm assumes understanding of heap - Heap - Introduction. Also, it also uses ExtractMin from Heap.
Algorithm
The essence of heap sort (in-place) is this:
Convert the array to be sorted into a heap. (see BuildHeap, it uses O(n) time) Build the sorted array back to front by repeatedly removing the minimum value in the heap (the value at position 1), putting that value into the sorted array, and rebuilding the heap with one fewer element.
[Read More]
Binary heap : Introduction
http://www.algolist.net/Data_structures/Binary_heap
Heap : Removing the min element using BubbleDown
We are discussing min heap here. Extracting min from the heap is same as insertion in heap that we discussed earlier. In insertion, we used bubbling up (or sifting up) method, but in extract-min we will use bubbling down (or sifting down) method.
Pseudocode:
Copy the last value in the array to the root; Remove last element, decrease heap’s size by 1;(as we are using array) Bubble down root’s value if heap property between the nodes is violated.
[Read More]
Heap : Inserting an element into a heap using BubbleUp
Lets consider the min heap here.
Inserting the key k in the given heap. Consider the heap:
Insert k at the end of the last level
a) If the heap property is not broken you are done. Suppose k = 10. Here 10 is more than 4, hence min-heap property i.e. parent < child is already followed. Hence everything ok.
b)If the heap property is broken, then you have to bubble up the added child until heap property is restored.
[Read More]
Convert array of positive numbers to sorted array
You are given an array of positive integers. Convert it to a sorted array with minimum cost.
Only valid operation are
Decrement -> cost = 1 Delete an element completely from the array -> cost = value of element
For example:
4,3,5,6, -> cost 1 (decrement 4)
10,3,11,12 -> cost 3 (delete 3) Trying out DP
We can make the DP more efficient You don’t need to scan the whole previous column when calculating costs of decrementing.
[Read More]
Implement Add,Subtract,Multiplication,Division Using Bit Manipulation
Addition
This One is Somewhat Logical and the Best also. This will work all kind of Inputs. The Logic Behind the Concept is described breifly here :
Here we use, One’s Complement Operator (~ - Known as Tilda). This is a Unary Operator. The output of “~b” means, One Complement of the value stored in ‘b’. For example, a=10, b=5. Then the ~b=-6. This operator simply works on the binary value of the corresponding Integer.
[Read More]
K – Reverse a linked list
This is one of the questions asked in Microsoft Interview.
Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list.
The following are the constraints given:
If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is You have to retain the memory address of the nodes without modifying it i.
[Read More]
Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .
for(int j=arrIndex/2 ; j < arrIndex;j++) …
shanky - Nov 0, 2014
for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}
This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i
Hi Shanky, you are right. That’s what I have done :)