Median of the two sorted arrays of different sizes

Overall run time complexity should be O(log (m+n)).

int find_kth(int a[], int b[], int size_a, int size_b, int k)
{
     if(size_a > size_b)
          return find_kth(b, a, size_b, size_a, k);
        
     if(size_a == 0)
          return b[k-1];

     if(k ==1)
          return min(a[0], b[0]);

     // K should be less than the size of array  
     int i =  min(size_a, k/2);        
     int j =  min(size_b, k/2); 
 
     if(a[i-1] > b[j-1])
          // Now we need to find only K-j th element
          return find_kth(a, b+j, size_a, size_b -j, k-j);
     else
          return find_kth(a+i, b, size_a-i, size_b,  k-i);
     return -1;
}
 
int  find_median(int a[], int b[], int size_a, int size_b)
{
     int left  =  (size_a + size_b +1)/2;
     int right =  (size_a + size_b +2)/2;
 
     return ((find_kth(a,b, size_a,size_b, left) +
                   find_kth(a,b, size_a,size_b, right))/2);
}

Median of two sorted arrays of same size

Algorithm

  1. If length of both arrays is 1, take average and return the value.
  2. If length of both arrays is 2, then return following value  (max(array1[0], array2[0]) + min(array1[1], array2[1]) )/2
  3. If length is greater than 2, follow steps below
    1. Find median of array1 and array2 individually. Let them be M1 and M2
    2. If M1 == M2 return M1
    3. If M1 < M2 follow step 1 onwards with array1[mid…N] and array2[0, mid-1]
    4. If M2 < M1 follow step 1 onwards with array2[mid…N] and array1[0, mid-1]
int getMedian(int ar1[], int ar2[], int n)
{
    int m1;
    int m2;
 
    if (n == 1)
        return (ar1[0] + ar2[0])/2;
 
    if (n == 2)
        return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
 
    m1 = median(ar1, n);
    m2 = median(ar2, n);

    if (m1 == m2)
        return m1;
 
    /* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */
    if (m1 < m2)
    {
        if (n % 2 == 0)
            //If no. of elements are even, then do not include the middle element in next step
            return getMedian(ar1 + n/2 - 1, ar2, n - n/2 +1);
        else
            //If no. of elements are odd, then include the middle element in next step
            return getMedian(ar1 + n/2, ar2, n - n/2);
    }
 
    /* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
    else
    {
        if (n % 2 == 0)
            return getMedian(ar2 + n/2 - 1, ar1, n - n/2 + 1);
        else
            return getMedian(ar2 + n/2, ar1, n - n/2);
    }
}
 
/* Function to get median of a sorted array */
int median(int arr[], int n)
{
    if (n%2 == 0)
        return (arr[n/2] + arr[n/2-1])/2;
    else
        return arr[n/2];
}

Fixed Point in a given sorted array

Fixed Point in an array is an index i such that arr[i] is equal to i

int binarySearch(int arr[], int low, int high)
{
    if(high >= low)
    {
        int mid = (low + high)/2;

        if(mid == arr[mid])
            return mid;
        if(mid > arr[mid])
            return binarySearch(arr, (mid + 1), high);
        else
            return binarySearch(arr, low, (mid -1));
    }
    return -1;
}

Find index of a peak element

int findPeakUtil(int arr[], int low, int high, int n)
{
    int mid = (low + high)/2;

    if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
            (mid == n-1 || arr[mid+1] <= arr[mid]))
        return mid;

    else if (mid > 0 && arr[mid-1] > arr[mid])
        return findPeakUtil(arr, low, (mid -1), n);

    else return findPeakUtil(arr, (mid + 1), high, n);
}

find minimum element in a sorted and rotated array

Need to handle duplicates also

#include <stdio.h>
 
int min(int x, int y) { return (x < y)? x :y; }
 
int findMin(int arr[], int low, int high)
{
    // incase when array is not rotated 
    if (high < low)  return arr[0];
 
    // If there is only one element left
    if (high == low) return arr[low];
 
    // Find mid
    int mid = (low + high)/2;
 
    // Check if element (mid+1) is minimum element. Consider the cases like {1, 1, 0, 1}
    if (mid < high && arr[mid+1] < arr[mid])
       return arr[mid+1];
 
    // This case causes O(n) time
    if (arr[low] == arr[mid] && arr[high] == arr[mid])
        return min(findMin(arr, low, mid-1), findMin(arr, mid+1, high));
 
    // Check if mid itself is minimum element
    if (mid > low && arr[mid] < arr[mid - 1])
       return arr[mid];
 
    // Decide whether we need to go to left half or right half
    if (arr[high] > arr[mid])
       return findMin(arr, low, mid-1);
    return findMin(arr, mid+1, high);
}

Atoi function in c

ATOI FUNCTION

#include<stdio.h>
#include<stdlib.h>

int main ()
{
    int i;
    char buffer [256];

     printf ("Enter a number: ");
     fgets (buffer, 256, stdin);

     i = atoi (buffer);
     printf ("The value entered is %d.",i);
     return 0;
}

OWN ATOI FUNCTION

#include <stdio.h>
 
// A utility function to check whether x is numeric
bool isNumericChar(char x)
{
    return (x >= '0' && x <= '9')? true: false;
}
 
int myAtoi(char *str)
{
    if (*str == NULL)
       return 0;
    int res = 0;  // Initialize result
    int sign = 1;  // Initialize sign as positive
    int i = 0;  // Initialize index of first digit
 
    if (str[0] == '-')
    {
        sign = -1;
        i++;  // Also update index of first digit
    }
 
    // Iterate through all digits of input string and update result
    for (; str[i] != ''; ++i)
    {
        if (isNumericChar(str[i]) == false)
            return 0;
        res = res*10 + str[i] - '0';
    }

    return sign*res;
}
 
// Driver program to test above function
int main()
{
    char str[] = "-134";
    int val = myAtoi(str);
    printf("%d ", val);
    return 0;
}

Parsing / Reading XML file in Java

Sample XML file

<?xml version="1.0"?>
<students>
    <student>
        <name>John</name>
        <grade>B</grade>
        <age>12</age>
    </student>
    <student>
        <name>Mary</name>
        <grade>A</grade>
        <age>11</age>
    </student>
    <student>
        <name>Simon</name>
        <grade>A</grade>
        <age>18</age>
    </student>
</students>

Java code to parse above XML

import java.io.File;
import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
 
import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
 
public class XMLParser {
 
    public void getAllUserNames(String fileName) {
        try {
            DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
            DocumentBuilder db = dbf.newDocumentBuilder();
            File file = new File(fileName);
            if (file.exists()) {
                Document doc = db.parse(file);
                Element docEle = doc.getDocumentElement();
 
                // Print root element of the document
                System.out.println("Root element of the document: "
                        + docEle.getNodeName());
 
                NodeList studentList = docEle.getElementsByTagName("student");
 
                // Print total student elements in document
                System.out
                        .println("Total students: " + studentList.getLength());
 
                if (studentList != null && studentList.getLength() > 0) {
                    for (int i = 0; i < studentList.getLength(); i++) {
 
                        Node node = studentList.item(i);
 
                        if (node.getNodeType() == Node.ELEMENT_NODE) {
 
                            System.out
                                    .println("=====================");
 
                            Element e = (Element) node;
                            NodeList nodeList = e.getElementsByTagName("name");
                            System.out.println("Name: "
                                    + nodeList.item(0).getChildNodes().item(0)
                                            .getNodeValue());
 
                            nodeList = e.getElementsByTagName("grade");
                            System.out.println("Grade: "
                                    + nodeList.item(0).getChildNodes().item(0)
                                            .getNodeValue());
 
                            nodeList = e.getElementsByTagName("age");
                            System.out.println("Age: "
                                    + nodeList.item(0).getChildNodes().item(0)
                                            .getNodeValue());
                        }
                    }
                } else {
                    System.exit(1);
                }
            }
        } catch (Exception e) {
            System.out.println(e);
        }
    }
    public static void main(String[] args) {
 
        XMLParser parser = new XMLParser();
        parser.getAllUserNames("c:\\test.xml");
    }
}

Few Java snippets

String a = String.valueOf(2);   //integer to numeric string
int i = Integer.parseInt(a); //numeric string to an int

String to Date

SimpleDateFormat format = new SimpleDateFormat( "dd.MM.yyyy" );
Date date = format.parse( myString );

Creating JSON data in Java

import org.json.JSONObject;
...
...
JSONObject json = new JSONObject();
json.put("city", "Mumbai");
json.put("country", "India");
...
String output = json.toString();
...

Java Singleton example

public class SimpleSingleton {
    private static SimpleSingleton singleInstance =  new SimpleSingleton();
 
    //Marking default constructor private
    //to avoid direct instantiation.
    private SimpleSingleton() {
    }
 
    //Get instance for class SimpleSingleton
    public static SimpleSingleton getInstance() {
 
        return singleInstance;
    }
}

Send HTTP request & fetching data using Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
 
public class Main {
    public static void main(String[] args)  {
        try {
            URL my_url = new URL("http://www.xyz.com/");
            BufferedReader br = new BufferedReader(new InputStreamReader(my_url.openStream()));
            String strTemp = "";
            while(null != (strTemp = br.readLine())){
            System.out.println(strTemp);
        }
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }
}

Convert Array to Map in Java

import java.util.Map;
import org.apache.commons.lang.ArrayUtils;
 
public class Main {
 
  public static void main(String[] args) {
    String[][] countries = { { "United States", "New York" }, { "United Kingdom", "London" },
        { "Netherland", "Amsterdam" }, { "Japan", "Tokyo" }, { "France", "Paris" } };
 
    Map countryCapitals = ArrayUtils.toMap(countries);
 
    System.out.println("Capital of Japan is " + countryCapitals.get("Japan"));
    System.out.println("Capital of France is " + countryCapitals.get("France"));
  }
}

HTTP Proxy setting in Java

System.getProperties().put("http.proxyHost", "someProxyURL");
System.getProperties().put("http.proxyPort", "someProxyPort");
System.getProperties().put("http.proxyUser", "someUserName");
System.getProperties().put("http.proxyPassword", "somePassword");

Interpolation search

Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name.

On average the interpolation search makes about log(log(n)) comparisons. In the worst case it can make up to O(n).

In each search step it calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation.

CODE

public int interpolationSearch(int[] Array, int key){

int low = 0;
int high = Array.length – 1;
int mid;

while (Array [low] <= key && Array [high] >= key) {

mid = low + (high – low) / (Array[high] – Array[low]) *( key – Array[low]);

if (Array [mid] < key)
low = mid + 1;
else if (Array [mid] > key)
high = mid – 1;
else
return mid;
}

if (Array [low] == key)
return low;
else
return -1; // Not found
}

Semaphore

It is a variable or abstract data type that is used for controlling access, by multiple processes, to a common resource in a parallel programming or a multi user environment.

Semaphores are a useful tool in the prevention of race conditions.

Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores.