Programming Bits

Running Median Using Heap (Java): Our goal is to find median of the elements as they come. So first we should know what is a median. Median: Sort the elements and 1. middle element is the median in case number of elements is odd 2. Or (middle element + (middle + 1)th element)/2 is median Example 1: Input: 10,2,3,4,5 Sort :  2,3,4,5,10 Because number of elements are odd 5/2=2 Example 2: Input: 1,10,2,3,4,5 Sort :  1,2,3,4,5,10 Because number of elements are even, so  (n/2th element + n/2+1th element)/2 = (3+4)/2 = 3.5

Bounding Rank of Fibonacci Heap to lgn: Before understanding the concept see below notations, tree(H)=number of nodes in the root list in below Fibonacci Heap Example rank(x)=number of children it has rank(H)=max rank(x)  Note: Black nodes are marked nodes (when one of its children is deleted it is marked if it is not already marked). We have following operation in Fibonacci Heap: Insert - O(1) Union - O(1) Decrease Key - O(1) Delete-Min - O(Rank(H)) = O(lgn) Delete - O(Rank(H)) = O(lgn) In this blog we will see how the rank is bounded to be lgn . So some assumptions I have made that you know at a time we cannot delete >1 child of any node. And after deleting child of a node we make it as Marked Node  if it is not marked already. Some Background; Merge Operation: We do merge operation when we do delete minimum. Merge operation is when rank of two nodes is same, we merge them as making minimum of them as root node and o...

UDP: Contrary to TCP, UDP is connection less and unreliable protocol. Connection less means before sending data we do not establish the connection between server and client, we just send the data right away. This protocol is unreliable because when the data do not reach the destination, this protocol will not let the sender know about it. Then obviously one question arises : Then why we have such protocol ? The answer is very simple, there are certain situation where we use UDP because of its speed. In Telecommunication: As UDP is very fast, we just want the voice to reach and little bit of data loss do not hamper the call. In DNS UDP is used. In transmitting multicast packets. The below code simulation shows how UDP server and client work.. Client sends some alphabets to server and server returns them in sorted order. UDP Server Code: import java.io.IOException; import java.net.*; import java.util.Arrays; public class UDPServer { public static void main(S...

TCP: Transport control protocol is transport layer protocol in TCP/IP model. It is connection oriented and reliable protocol. It guarantees packet transmission between process to process. Connection oriented means that for transmission before starting connection is established and then data is transmitted, that is the reason reliability comes into the picture. So below is typical abstract diagram for TCP protocol, please note this picture just shows the overall functionality of the entire process not the specifics, for more information please click here . TCP Handshaking Process The TCP Server Code in java is given below: This is a demo program which will take sort alphabets sent from client program. import java.net.*; import java.util.Arrays; import java.io.*; public class TCPServer{ private ServerSocket serverSocket; public TCPServer(int port) throws IOException { serverSocket = new ServerSocket(port); // setting port number @server ...

What is auto commit in mysql:  When we run DML query in mysql for example we have insert any value into table or update value in table, after each DML statement mysql auto commits the changes by default, that means we cannot rollback the changes we have made. This is called auto commit functionality. To prevent that we can stop this "auto commit " in mysql in following ways: Permanent Turing off of auto commit: Open /etc/mysql/my.cnf file in linux environment using sudo privileges as: $> sudo gedit /etc/mysql/my.cnf  and type the following lines in bottom of the file and save it. [ client ] init-command = 'set autocommit=0' then restart mysql using following command: $> sudo service mysql restart

We have “post order” and “in order” of binary search tree. We have to construct the Binary Tree with this information. First we should know that there is unique Binary Tree with one PostOrder and InOrder. So below I am explaining how to construct the Binary Tree: PostOrder   Traversal : {D, E, B, F, C, A} InOrder  Traversal : {D, B, E, A, F, C} If we have PostOrder then last element will be root. If  PostOrder  traversal is :           {D, E, B, F, C, A} then ‘A’ will be root. We will search ‘A’ in  InOrder  traversal we got it @ index 3. Whatever present from 0-2 will be present in left sub tree of Root Node ‘A’ and from index 4-5 will be present in right sub tree of A as follows. After first step And now we will check for second last element from  postOrder  that is ‘C’ We will check ‘C’ in InOrder array, and ‘C’ is present at last location that means ‘F’ will be its left child as follows...

Suppose we have one array: 4, 5, 6, 7, 1, 2,1,, 4, 5, 3, 6, 7, 10, 1, 2, 3, 4 And  k=4,  that means we have to find the sub array which has all the elements 1, 2, 3, 4 and the array length should be minimum. Intuition:  First we will just find the index till where we can get all the numbers then we will proceed to minimize the size of the sub-array. So as we can see till index  9  we can get all the desired numbers. Then we will try to minimize this length. And by minimizing means we can get another sub array which is minimum as in this case which is: 1,2,3,4 at last in the array. So we go ahead using this method we can get the minimum sub array having 1 to k numbers. Code in Java: public class NumbersfromOnetoK { public static void main(String[] args) { NumbersfromOnetoK m = new NumbersfromOnetoK(); int[] arr={ 4, 5, 6, 1, 7, 1, 2, 4, 5, 3, 6, 7, 10, 1, 2, 3, 4 };  int k=4; m.findSubArrayWith_1_to_K_Numbers()...