Java, NoSQL, SQL, REST API and other scary words

Array Algorithms

Reverse an array or string

Input: 123

Output: 321

1) Initialize start and end indexes (start = 0, end = n-1).

2) In a loop, swap arr[start] with arr[end] and change start and end as follows (start = start +1; end = end – 1)

Given an array A[] and a number x, check for pair in A[] with sum as x

1) Sort the array in non-decreasing order. sort(A, 0, arr_size-1);

2) Initialize two index variables to find the candidate elements in the sorted array.

   (a) Initialize first to the leftmost index: l = 0

  (b) Initialize second  the rightmost index:  r = ar_size-1

3) Loop while l < r.

   (a) If (A[l] + A[r] == sum)  then return 1

   (b) Else if( A[l] + A[r] <  sum )  then l++

   (c) Else r–

4) No candidates in whole array – return 0

/* The main function that implements QuickSort() arr[] –> Array to be sorted, low  –> Starting index, high  –> Ending index */

static void sort(int arr[], int low, int high)

{

    if (low < high)

    {

        /* pi is partitioning index, arr[pi] is now at right place */

        int pi = partition(arr, low, high);

        // Recursively sort elements before partition and after partition

        sort(arr, low, pi-1);  sort(arr, pi+1, high);

    }

}

OR OTHER WAY

1) Initialize Binary Hash Map M[] = {0, 0, …}

2) Do following for each element A[i] in A[]

  (a)     If M[x – A[i]] is set then print the pair (A[i], x – A[i])

  (b)     Set M[A[i]]

static void printpairs(int arr[],int sum)

   {

       // Declares and initializes the whole array as false

       boolean[] binmap = new boolean[MAX];

       for (int i=0; i<arr.length; ++i)

       {

           int temp = sum-arr[i];

           if (temp>=0 && binmap[temp]) // checking for condition

           {

               System.out.println(“sum + ” is (” + arr[i] + “, “+temp+”)”);

           }

           binmap[arr[i]] = true;

       }

   }

Reverse an array without affecting special characters

Input:   str = “a,b$c”

Output:  str = “c,b$a”

Note that $ and , are not moved anywhere, only subsequence “abc” should be reversed

1) Let input string be ‘str[]’ and length of string be ‘n’

2) l = 0, r = n-1

3) While l is smaller than r, do following

  1. a) If str[l] is not an alphabetic character, do l++
  2. b) Else If str[r] is not an alphabetic character, do r–
  3. c) Else swap str[l] and str[r] (call swap(l,r) the values of l and r will be swapped)

How to check that this is an alphabet letter: Character.isLetter(charToCheck)

Given a string, print all possible palindromic partitions

Input:   nitin

Output:  n I t I n , n iti n, nitin

1) Get length (int n = str.length();)

2)     String array List<String> list = new ArrayList<String>(); To Store all palindromic partitions

3)     String array List<String> listForAnyLetter = new ArrayList<String>();  To store current palindromic partition

4)     Go letter by letter to pick all possible ending points for substrings

5)     If substring str[start..i] is palindrome then add the substring to result

6)     Recur for remaining substring, remove substring str[start..i] from current partition

Key method to check if str is palindrome:

private bool isPalindrome(string str, int low, int high)

{

   while (low < high)

   {

       if (str[low] != str[high])

           return false;

       low++;

       high–;

   }

   return true;

}

Count triplets with sum smaller than a given value

Input : arr[] = {-1, 0,5, 50} sum = 55

Output : 1

A Simple Solution is to run three loops to consider all triplets one by one. For every triplet, compare the sums and increment count if triplet sum is smaller than given sum:

for (int i = 0; i < n-2; i++) {

          for (int j = i+1; j < n-1; j++){

              for (int k = j+1; k < n; k++)

                  if (arr[i] + arr[j] + arr[k] < sum)

                      ….

Time complexity of above solution is O(n3). An Efficient Solution can count triplets in O(n2) :

1) Sort the input array in increasing order Arrays.sort(arr);

2) Initialize result as 0.

3) Run a loop from i = 0 to n-2.  An iteration of this loop finds all

  triplets with arr[i] as first element.

  1. a) Initialize other two elements as corner elements of subarray

    arr[i+1..n-1], i.e., j = i+1 and k = n-1

  1. b) Move j and k toward each other until they meet, i.e., while (j < k)

           b-1) if (arr[i] + arr[j] + arr[k] >= sum), then do k–. Else for current i and j, there can (k-j) possible third elements that satisfy the constraint.

            b-2) Else Do ans += (k – j) followed by j++  

Code:

for (int i = 0; i < n – 2; i++)

       {

           // Initialize other two elements as corner elements

           int j = i + 1, k = n – 1;

           while (j < k)

           {

               // If sum of current triplet is more or equal,

               // move right corner to look for smaller values

               if (arr[i] + arr[j] + arr[k] >= sum)

                   k–;

               // Else move left corner

               else

               {

                   // This is important. For current i and j, there

                   // can be total k-j third elements.

                   ans += (k – j);

                   j++;

               }

           }

return ans;

Convert array into Zig-Zag fashion

Input:  arr[] = {4, 3, 7, 8, 6, 2, 1}

Output: arr[] = {3, 7, 4, 8, 2, 6, 1}

A Simple Solution is to first sort the array. After sorting, exclude the first element, swap the remaining elements in pairs. Time complexity is O(nlogn) since we need to sort the array first.

We can convert in O(n) time using an Efficient Approach. The idea is to use modified one pass of bubble sort. Maintain a flag for representing which order(i.e. < or >) currently we need. If the current two elements are not in that order then swap those elements otherwise not.

static int arr[] = new int[]{4, 3, 7, 8, 6, 2, 1};

boolean flag = true;   //The first expected relation is “<“

int temp =0;

   for (int i=0; i<=arr.length-2; i++)

   {

           if (flag)  /* “<” relation expected */

          {

               /* If we have a situation like A > B > C, we get A > B < C by swapping B and C */

               if (arr[i] > arr[i+1])

               {

                   temp  = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp;  // swap

               }   

           }

           else

           {

               /* If we have a situation like A < B < C, we get A < C > B by swapping B and C */

               if (arr[i] < arr[i+1])

               {

                  temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp;  // swap

               }

           }

           flag = !flag;

       }

   }

Generate all possible sorted arrays from alternate elements of two given sorted arrays

Input: A = {10, 15, 25} B = {1, 5, 20, 30}

Output:

 10 20

 10 20 25 30

 10 30

 15 20

 15 20 25 30

 15 30

 25 30

1)    Get length for both: int n = A.length; int m = B.length;

2)    Create third array to store results: int C[] = new int[m + n]; Will print a new raw with result when ready

3)    Add flag – If ‘flag’ is true, then current element is to be included from A otherwise from B. Start with the first element, len = 0

4)    Run generateUtil(A, B, C, 0, 0, m, n, 0, true);

void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n, int len, boolean flag)

   {

       if (flag) // Include valid element from A

       {

            if (len != 0) printArr(C, len + 1); // Print if not empty

        for (int k = i; k < m; k++) // Recur for all elements of A after current index

{

               if (len == 0) //first call

               {

                   C[len] = A[k];

              generateUtil(A, B, C, k + 1, j, m, n, len, !flag); //process B

               }

               else if (A[k] > C[len])

               {

                       C[len + 1] = A[k];

                       generateUtil(A, B, C, k + 1, j, m, n, len + 1, !flag);

               }

           }

       }

       else  //process B

       {

           for (int l = j; l < n; l++)

           {

               if (B[l] > C[len])

               {

                   C[len + 1] = B[l];

                   generateUtil(A, B, C, i, l + 1, m, n, len + 1, !flag);

               }

           }

       }

 }

Pythagorean Triplet in an array

Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2.

Input: arr[] = {3, 1, 4, 6, 5}

Output: True. There is a Pythagorean triplet (3, 4, 5).

A simple solution is to run three loops. We can solve this in O(n2) time by sorting the array first.

1) Do square of every element in input array. This step takes O(n) time. arr[i] = arr[i]*arr[i];

2) Sort the squared array in increasing order. This step takes O(nLogn) time. Arrays.sort(arr);

3) To find a triplet (a, b, c) such that a = b + c, do following.

  1.     Fix ‘a’ as last element of sorted array. for (int i = arr.length()-1; i >= 2; i–)
  2.     Now search for pair (b, c) in subarray between first element and ‘a’. A pair (b, c) with given sum can be found in O(n) time using meet in middle algorithm (second one in this article).

int l = 0; // index of the first element in arr[0..i-1]

           int r = i-1; // index of the last element in arr[0..i-1]

           while (l < r)

           {

               if (arr[l] + arr[r] == arr[i]) return true; // A triplet found

           else if (arr[l] + arr[r] < arr[i]) l++; // Else either move ‘l’ or ‘r’

               else r–;

           }

  1.     If no pair found for current ‘a’, then move ‘a’ one position back and repeat previous step.

Length of the largest subarray with contiguous elements

Input:  arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};

Output: Length of the longest contiguous subarray is 5

  1.     Initialize result  int max_len = 1;
  2.     Initialize min and max for all subarrays starting with I int mn = arr[i], mx = arr[i];
  3.     Create loop to go thru all elements
  4.     Get max and min value as a first element of the loop
  5.     Create another one loop:

// Consider all subarrays starting with i and ending with j

           for (int j = i + 1; j < n; j++)

           {

               // Update min and max in this subarray if needed

               mn = min(mn, arr[j]); mx = max(mx, arr[j]);

               // If current subarray has all contiguous elements

               if ((mx – mn) == j – i)

                max_len = max(max_len, mx – mn + 1);

           }

int min(int x, int y)

{

       return (x < y) ? x : y; //if true – z, if false – y

}

int max(int x, int y)

{

       return (x > y) ? x : y;

}

Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

Input:  arr[] = {1, 3, 6, 10, 11, 15};

Output: 2

Input:  arr[] = {1, 1, 1, 1};

Output: 5

int findSmallest(int arr[])

   {

       int res = 1; // Initialize result

       // Traverse the array and increment ‘res’ if arr[i] is smaller than or equal to ‘res’.

       for (int i = 0; i < arr.length() && arr[i] <= res; i++)

           res = res + arr[i];

       return res;

   }

Smallest subarray with sum greater than a given value

arr[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}

   x = 280

Output: 4

Minimum length subarray is {100, 1, 0, 200}

// Returns length of smallest subarray with sum greater than x. If there is no subarray with given sum, then returns n+1

   static int smallestSubWithSum(int arr[], int n, int x)

   {

       // Initialize current sum and minimum length

       int curr_sum = 0, min_len = n + 1;

       // Initialize starting and ending indexes

       int start = 0, end = 0;

       while (end < n)

       {

           // Keep adding array elements while current sum

           // is smaller than x

           while (curr_sum <= x && end < n)

               curr_sum += arr[end++];

           // If current sum becomes greater than x.

           while (curr_sum > x && start < n)

           {

               // Update minimum length if needed

               if (end – start < min_len)

                   min_len = end – start;

               // remove starting elements

               curr_sum -= arr[start++];

           }

       }

       return min_len;

   }

Stock Buy Sell to Maximize Profit

{100, 180, 260, 310, 40, 535, 695} and we could buy only 1 time

  1. Process all elements
  2. Find the local minima and store it as starting index. If not exists, return. while ((i < n – 1) && (price[i + 1] <= price[i])) i++;
  3. If we reached the end, break as no further solution possible if (i == n – 1)
  4. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index. while ((i < n) && (price[i] >= price[i – 1])) i++;
  5. Update the solution (Increment count of buy sell pairs)
  6. Repeat the above steps if end is not reached.

Reverse an array or string

Input: 123

Output: 321

1) Initialize start and end indexes (start = 0, end = n-1).

2) In a loop, swap arr[start] with arr[end] and change start and end as follows (start = start +1; end = end – 1)

Given an array A[] and a number x, check for pair in A[] with sum as x

1) Sort the array in non-decreasing order. sort(A, 0, arr_size-1);

2) Initialize two index variables to find the candidate elements in the sorted array.

   (a) Initialize first to the leftmost index: l = 0

  (b) Initialize second  the rightmost index:  r = ar_size-1

3) Loop while l < r.

   (a) If (A[l] + A[r] == sum)  then return 1

   (b) Else if( A[l] + A[r] <  sum )  then l++

   (c) Else r–

4) No candidates in whole array – return 0

/* The main function that implements QuickSort() arr[] –> Array to be sorted, low  –> Starting index, high  –> Ending index */

static void sort(int arr[], int low, int high)

{

    if (low < high)

    {

        /* pi is partitioning index, arr[pi] is now at right place */

        int pi = partition(arr, low, high);

        // Recursively sort elements before partition and after partition

        sort(arr, low, pi-1);  sort(arr, pi+1, high);

    }

}

OR OTHER WAY

1) Initialize Binary Hash Map M[] = {0, 0, …}

2) Do following for each element A[i] in A[]

  (a)     If M[x – A[i]] is set then print the pair (A[i], x – A[i])

  (b)     Set M[A[i]]

static void printpairs(int arr[],int sum)

   {

       // Declares and initializes the whole array as false

       boolean[] binmap = new boolean[MAX];

       for (int i=0; i<arr.length; ++i)

       {

           int temp = sum-arr[i];

           if (temp>=0 && binmap[temp]) // checking for condition

           {

               System.out.println(“sum + ” is (” + arr[i] + “, “+temp+”)”);

           }

           binmap[arr[i]] = true;

       }

   }

Reverse an array without affecting special characters

Input:   str = “a,b$c”

Output:  str = “c,b$a”

Note that $ and , are not moved anywhere, only subsequence “abc” should be reversed

1) Let input string be ‘str[]’ and length of string be ‘n’

2) l = 0, r = n-1

3) While l is smaller than r, do following

  1. a) If str[l] is not an alphabetic character, do l++
  2. b) Else If str[r] is not an alphabetic character, do r–
  3. c) Else swap str[l] and str[r] (call swap(l,r) the values of l and r will be swapped)

How to check that this is an alphabet letter: Character.isLetter(charToCheck)

Given a string, print all possible palindromic partitions

Input:   nitin

Output:  n I t I n , n iti n, nitin

1) Get length (int n = str.length();)

2)     String array List<String> list = new ArrayList<String>(); To Store all palindromic partitions

3)     String array List<String> listForAnyLetter = new ArrayList<String>(); /To store current palindromic partition

4)     Go letter by letter to pick all possible ending points for substrings

5)     If substring str[start..i] is palindrome then add the substring to result

6)     Recur for remaining substring, remove substring str[start..i] from current partition

Key method to check if str is palindrome:

private bool isPalindrome(string str, int low, int high)

{

   while (low < high)

   {

       if (str[low] != str[high])

           return false;

       low++;

       high–;

   }

   return true;

}

Count triplets with sum smaller than a given value

Input : arr[] = {-1, 0,5, 50} sum = 55

Output : 1

A Simple Solution is to run three loops to consider all triplets one by one. For every triplet, compare the sums and increment count if triplet sum is smaller than given sum:

for (int i = 0; i < n-2; i++) {

          for (int j = i+1; j < n-1; j++){

              for (int k = j+1; k < n; k++)

                  if (arr[i] + arr[j] + arr[k] < sum)

                      ….

Time complexity of above solution is O(n3). An Efficient Solution can count triplets in O(n2) :

1) Sort the input array in increasing order Arrays.sort(arr);

2) Initialize result as 0.

3) Run a loop from i = 0 to n-2.  An iteration of this loop finds all

  triplets with arr[i] as first element.

  1. a) Initialize other two elements as corner elements of subarray

    arr[i+1..n-1], i.e., j = i+1 and k = n-1

  1. b) Move j and k toward each other until they meet, i.e., while (j < k)

           b-1) if (arr[i] + arr[j] + arr[k] >= sum), then do k–. Else for current i and j, there can (k-j) possible third elements that satisfy the constraint.

            b-2) Else Do ans += (k – j) followed by j++  

Code:

for (int i = 0; i < n – 2; i++)

       {

           // Initialize other two elements as corner elements

           int j = i + 1, k = n – 1;

           while (j < k)

           {

               // If sum of current triplet is more or equal,

               // move right corner to look for smaller values

               if (arr[i] + arr[j] + arr[k] >= sum)

                   k–;

               // Else move left corner

               else

               {

                   // This is important. For current i and j, there

                   // can be total k-j third elements.

                   ans += (k – j);

                   j++;

               }

           }

      return ans;

Convert array into Zig-Zag fashion

Input:  arr[] = {4, 3, 7, 8, 6, 2, 1}

Output: arr[] = {3, 7, 4, 8, 2, 6, 1}

A Simple Solution is to first sort the array. After sorting, exclude the first element, swap the remaining elements in pairs. Time complexity is O(nlogn) since we need to sort the array first.

We can convert in O(n) time using an Efficient Approach. The idea is to use modified one pass of bubble sort. Maintain a flag for representing which order(i.e. < or >) currently we need. If the current two elements are not in that order then swap those elements otherwise not.

static int arr[] = new int[]{4, 3, 7, 8, 6, 2, 1};

boolean flag = true;   //The first expected relation is “<“

int temp =0;

   for (int i=0; i<=arr.length-2; i++)

   {

           if (flag)  /* “<” relation expected */

          {

               /* If we have a situation like A > B > C, we get A > B < C by swapping B and C */

               if (arr[i] > arr[i+1])

               {

                   temp  = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp;  // swap

               }

           }

           else

           {

               /* If we have a situation like A < B < C, we get A < C > B by swapping B and C */

               if (arr[i] < arr[i+1])

               {

                  temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp;  // swap

               }

           }

           flag = !flag;

       }

   }

Generate all possible sorted arrays from alternate elements of two given sorted arrays

Input: A = {10, 15, 25} B = {1, 5, 20, 30}

Output:

 10 20

 10 20 25 30

 10 30

 15 20

 15 20 25 30

 15 30

 25 30

1)    Get length for both: int n = A.length; int m = B.length;

2)    Create third array to store results: int C[] = new int[m + n]; Will print a new raw with result when ready

3)    Add flag – If ‘flag’ is true, then current element is to be included from A otherwise from B. Start with the first element, len = 0

4)    Run generateUtil(A, B, C, 0, 0, m, n, 0, true);

void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n, int len, boolean flag)

   {

       if (flag) // Include valid element from A

       {

            if (len != 0) printArr(C, len + 1); // Print if not empty

        for (int k = i; k < m; k++) // Recur for all elements of A after current index

{

               if (len == 0) //first call

               {

                   C[len] = A[k];

              generateUtil(A, B, C, k + 1, j, m, n, len, !flag); //process B

               }

               else if (A[k] > C[len])

               {

                       C[len + 1] = A[k];

                       generateUtil(A, B, C, k + 1, j, m, n, len + 1, !flag);

               }

           }

       }

       else  //process B

       {

           for (int l = j; l < n; l++)

           {

               if (B[l] > C[len])

               {

                   C[len + 1] = B[l];

                   generateUtil(A, B, C, i, l + 1, m, n, len + 1, !flag);

               }

           }

       }

 }

Pythagorean Triplet in an array

Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2.

Input: arr[] = {3, 1, 4, 6, 5}

Output: True. There is a Pythagorean triplet (3, 4, 5).

A simple solution is to run three loops. We can solve this in O(n2) time by sorting the array first.

1) Do square of every element in input array. This step takes O(n) time. arr[i] = arr[i]*arr[i];

2) Sort the squared array in increasing order. This step takes O(nLogn) time. Arrays.sort(arr);

3) To find a triplet (a, b, c) such that a = b + c, do following.

  1.     Fix ‘a’ as last element of sorted array. for (int i = arr.length()-1; i >= 2; i–)
  2.     Now search for pair (b, c) in subarray between first element and ‘a’. A pair (b, c) with given sum can be found in O(n) time using meet in middle algorithm (second one in this article).

int l = 0; // index of the first element in arr[0..i-1]

           int r = i-1; // index of the last element in arr[0..i-1]

           while (l < r)

           {

               if (arr[l] + arr[r] == arr[i]) return true; // A triplet found

           else if (arr[l] + arr[r] < arr[i]) l++; // Else either move ‘l’ or ‘r’

               else r–;

           }

  1.     If no pair found for current ‘a’, then move ‘a’ one position back and repeat previous step.

Length of the largest subarray with contiguous elements

Input:  arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};

Output: Length of the longest contiguous subarray is 5

  1.     Initialize result  int max_len = 1;
  2.     Initialize min and max for all subarrays starting with I int mn = arr[i], mx = arr[i];
  3.     Create loop to go thru all elements
  4.     Get max and min value as a first element of the loop
  5.     Create another one loop:

// Consider all subarrays starting with i and ending with j

           for (int j = i + 1; j < n; j++)

           {

               // Update min and max in this subarray if needed

               mn = min(mn, arr[j]); mx = max(mx, arr[j]);

               // If current subarray has all contiguous elements

               if ((mx – mn) == j – i)

                max_len = max(max_len, mx – mn + 1);

           }

int min(int x, int y)

{

       return (x < y) ? x : y; //if true – z, if false – y

}

int max(int x, int y)

{

       return (x > y) ? x : y;

}

Find the smallest positive integer value that cannot be represented as sum of any subset of a given array

Input:  arr[] = {1, 3, 6, 10, 11, 15};

Output: 2

Input:  arr[] = {1, 1, 1, 1};

Output: 5

int findSmallest(int arr[])

   {

       int res = 1; // Initialize result

       // Traverse the array and increment ‘res’ if arr[i] is smaller than or equal to ‘res’.

       for (int i = 0; i < arr.length() && arr[i] <= res; i++)

           res = res + arr[i];

       return res;

   }

Smallest subarray with sum greater than a given value

arr[] = {1, 11, 100, 1, 0, 200, 3, 2, 1, 250}

   x = 280

Output: 4

Minimum length subarray is {100, 1, 0, 200}

// Returns length of smallest subarray with sum greater than x. If there is no subarray with given sum, then returns n+1

   static int smallestSubWithSum(int arr[], int n, int x)

   {

       // Initialize current sum and minimum length

       int curr_sum = 0, min_len = n + 1;

       // Initialize starting and ending indexes

       int start = 0, end = 0;

       while (end < n)

       {

           // Keep adding array elements while current sum

           // is smaller than x

           while (curr_sum <= x && end < n)

               curr_sum += arr[end++];

           // If current sum becomes greater than x.

           while (curr_sum > x && start < n)

           {

               // Update minimum length if needed

               if (end – start < min_len)

                   min_len = end – start;

               // remove starting elements

               curr_sum -= arr[start++];

           }

       }

       return min_len;

   }

Stock Buy Sell to Maximize Profit

{100, 180, 260, 310, 40, 535, 695} and we could buy only 1 time

  1. Process all elements
  2. Find the local minima and store it as starting index. If not exists, return. while ((i < n – 1) && (price[i + 1] <= price[i])) i++;
  3. If we reached the end, break as no further solution possible if (i == n – 1)
  4. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index. while ((i < n) && (price[i] >= price[i – 1])) i++;
  5. Update the solution (Increment count of buy sell pairs)
  6. Repeat the above steps if end is not reached.
Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s