Ad
jayeshcp

Search if a value exists in binary search tree (BST)

Search
Algorithms
Logic
import java.util.*;

class Node {
  int value;
  Node left;
  Node right;
  
  public Node(int value) {
    this.value = value;
  }
}


class BST {
  public static boolean search(Node root, int key) {
    if(root == null) {
      return false;
    }
        
    while(root != null) {
      if(root.value == key) {
        return true;
      }
      
      if(root.value > key) {
        root = root.left;
      } else if(root.value < key) {
        root = root.right;
      }
    }
    
    return false;
  }
}
jayeshcp

Test Kumite

This is a test kumite

var getAge = function(today, dob) {
  if(!today || !dob) {
    return null;
  }
  
  var now = new Date(today);
  return now.getYear() - new Date(dob).getYear();
};
jayeshcp

Return Largest Possible Number

Given a list of numbers, return the combination that is largest number.

As output can be large, return the result in String format.

Example:

Input:

[5, 50, 56]

Output:

56550

import java.util.*;

class Solution {
  public static String largestNumber(Integer[] nums) {
    Arrays.sort( nums, new Comparator<Integer>() {
      
      @Override
      public int compare(Integer a, Integer b) {
        String aStr = a.toString();
        String bStr = b.toString();
        
        return (aStr + bStr).compareTo(bStr + aStr) * -1;
      }
      
    } );
    
    String result = "";
    for(Integer num : nums) {
      result += num.toString();
    }
    
    return result;
  }
}
jayeshcp

Find Peak Element

Given array of integer elements, find the index of peak element in O(Log N) time complexity.

A peak element is an element that is greater than its neighbors. Given an input array where num[i] != num[i + 1], find a peak element and return its index. Array may contain multiple peaks, in that case return index of any peak.

Example:

Input:
1 2 3 1

Output:
2

because peak element is 3 and it is at index 2.

import java.util.*;;

class Solution {
  public static int peakIndex(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    int peak = -1;
    
    while(left <= right) {
      if(left == right) {
        peak = left;
        break;
      }
      
      int mid = (left + right) / 2;
      
      if(nums[mid] < nums[mid + 1]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    return peak;
  }
}
jayeshcp

Has duplicates

Write a program to find if given array contains duplicate elements or all elements are unique.
Your function should output true if there are duplicates, false if all elements are unique.

Example:

Input:
1 4 3 2 6 4

Output:
true

Input:
1 4 3 2 6 5

Output:
false

import java.util.*;

class Solution {
  /**
   *  Checks if given array contains duplicate elements.
   *  Complexity: O(N)
   *  @author     Jayesh Chandrapal
   
   *  @param nums integer array of elements
   *  @return     true if duplicate elements are found, false otherwise
   */
  public static boolean hasDuplicates(int[] nums) {
    Set<Integer> set = new HashSet<Integer>();
    
    for(int i = 0, len = nums.length; i < len; i++) {
      if(set.contains(nums[i])) {
        return true;
      } else {
        set.add(nums[i]);
      }
    }
    
    return false;
  }
}
jayeshcp

Matching Brackets

Stacks
Arrays
Data Types

Given an expression string exp, examine whether the pairs and the orders of "{", "}", "(", ")", "[", "]" are correct in exp.

For example, the program should return true for [()]{}{[()()]()} and false for [(]).

Check provided test cases to see expected behaviour for different inputs.

/**
 *  Check if brackets are matching.
 *  Time Complexity: O(N), Space Complexity: O(N)
 *
 *  @author Jayesh Chandrapal
 */
import java.util.*;
import java.lang.*;
import java.io.*;

class MatchingBrackets {
	
  /**
   *  Checks if given input string contains matching brackets.
   *
   * @params str  input string to be checked
   * @returns     boolean value indicating if given string contains matching brackets
   */
  public static boolean isBalanced(String str) {
	    boolean balanced = true;
	    Stack<Character> stack = new Stack<Character>();
	    
	    for(Character c : str.toCharArray()) {
            if(c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if(stack.isEmpty()) {
                    balanced = false;
                    break;
                }
                
                Character top = stack.peek();
                if((c == ')' && top == '(') || (c == '}' && top == '{') || (c == ']' && top == '[')) {
                    stack.pop();
                } else {
                    balanced = false;
                    break;
                }
            }
	    }
	    
	    return balanced && stack.isEmpty();
	}
}
jayeshcp

Power of Two

Write a function that determines if given number is a power of two. A power of two means a number of the form 2^n where n is an integer, i.e. the result of exponentiation with number two as the base and integer n as the exponent. i.e. 1024 is a power of two: it is 2^10.

Example:

power_of_two(4096) # true

power_of_two(333) # false

def power_of_two( n ):
  return n & ( n - 1 ) == 0
jayeshcp

Merge Sort

Implementation of Merge Sort.

  • Time Complexity: O(n log(n))

  • Space Complexity: O(n)

  • Preserves the input order of equal elements in the sorted output.

  • Type of Divide-and-Conquer algorithm.

  • Efficient at handling slow-to-access sequential media.

  • Well-suited for sorting huge amounts of data that does not fit into memory.

  • Wiki Link: Merge Sort

class Sort:

    def merge_sort(self, nums):
        if nums == None: return None

        if len(nums) > 1:
            mid = len(nums) // 2
            lefthalf = nums[:mid]
            righthalf = nums[mid:]

            self.merge_sort(lefthalf)
            self.merge_sort(righthalf)

            i = 0
            j = 0
            k = 0

            while i < len(lefthalf) and j < len(righthalf):
                if lefthalf[i] < righthalf[j]:
                    nums[k] = lefthalf[i]
                    i += 1
                else:
                    nums[k] = righthalf[j]
                    j += 1
                k += 1

            while i < len(lefthalf):
                nums[k] = lefthalf[i]
                i += 1
                k += 1

            while j < len(righthalf):
                nums[k] = righthalf[j]
                j += 1
                k += 1

        return nums
jayeshcp

Insertion Sort

Sorting
Algorithms
Logic

Implementation of Insertion Sort.

  • Time Complexity: Worst case: O(n^2), Best case: O(n)

  • Space Complexity: O(1)

  • Useful when list size is small.

  • only scans as many elements as needed to determine the correct location.

  • More efficient than bubble or selection sort.

  • Efficient for data sets that are already substantially sorted.

  • Requires more writes because the inner loop can require shifting large sections of the sorted portion of the array.

  • Can sort a list as it receives it.

  • Wiki Link: Insertion Sort

class Sort:

    def insertion_sort(self, nums):
        if nums is None:
            return None

        for i in range(1, len(nums)):
            currentvalue = nums[i]
            position = i

            while position > 0 and nums[position - 1] > currentvalue:
                nums[position] = nums[position - 1]
                position -= 1

            nums[position] = currentvalue
        return nums
jayeshcp

Selection Sort

Sorting
Algorithms
Logic

Implementation of Selection Sort.

  • Time Complexity: O(n^2)
  • Space Complexity: O(1)
  • Useful when list size is small
  • Preferable to insertion sort in terms of number of writes (O(n) swaps versus O(n2) swaps), it almost always far exceeds (and never beats) the number of writes that cycle sort makes, as cycle sort is theoretically optimal in the number of writes. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory.
  • Wiki Link: Selection Sort 
class Sort:

    def selection_sort(self, nums):
        if nums == None: return None

        for i in range(0, len(nums) - 1):
            minIndex = i

            for j in range(i + 1, len(nums)):
                if nums[j] < nums[minIndex]:
                    minIndex = j

            nums[i], nums[minIndex] = nums[minIndex], nums[i]
        return nums
jayeshcpvs.jayeshcp

Most frequently appearing number in given array

Example:

Find first most frequently occuring number in given array.

Given input {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2},
output should be 3 as it has highest frequency of occurence.

Note: This solution uses LinkedHashMap to preserve order of entry.

Code
Diff
  • import java.util.*;

/**
  Time Complexity  : O(N)
  Space Complexity : O(N)
*/
class MaxOccurence {
  public static int findMax(int[] nums) {
    return findMaxOccurenceLinkedHashMap(nums);
  }
  
  private static int findMaxOccurenceLinkedHashMap(int[] nums) {
    int maxKey = 0, maxNum = 0;
    
    if(nums.length < 1) return -1;
    if(nums.length == 1) return nums[0];
    
    Map<Integer, Integer> counts = new LinkedHashMap<Integer, Integer>(nums.length);
    
    for(int i = 0, len = nums.length; i < len; i++) {
      if(!counts.containsKey(nums[i])) {
        counts.put(nums[i], 1);
      } else {
        counts.put(nums[i], (counts.get(nums[i]) + 1));
      }
    }
    
    for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {  
      if (entry.getValue() > maxNum) {
        maxKey = entry.getKey();
        maxNum = entry.getValue();
      }  
    }  
    
    return maxKey;
  } 
}
    • import java.util.*;
    • /**
    • Time Complexity : O(N)
    • Space Complexity : O(N)
    • */
    • class MaxOccurence {
    • public static int findMax(int[] nums) {
    • return findMaxOccurenceCountArray(nums);
    • return findMaxOccurenceLinkedHashMap(nums);
    • }
    • private static int findMaxOccurenceCountArray(int[] nums) {
    • int maxNum = 0;
    • int maxCount = 0;
    • private static int findMaxOccurenceLinkedHashMap(int[] nums) {
    • int maxKey = 0, maxNum = 0;
    • if(nums.length < 1) return -1;
    • if(nums.length == 1) return nums[0];
    • int[] counts = new int[nums.length];
    • Map<Integer, Integer> counts = new LinkedHashMap<Integer, Integer>(nums.length);
    • for(int i = 0, len = nums.length; i < len; i++) {
    • counts[nums[i]]++;
    • if(counts[nums[i]] > maxCount) {
    • maxCount = counts[nums[i]];
    • maxNum = nums[i];
    • if(!counts.containsKey(nums[i])) {
    • counts.put(nums[i], 1);
    • } else {
    • counts.put(nums[i], (counts.get(nums[i]) + 1));
    • }
    • }
    • return maxNum;
    • for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
    • if (entry.getValue() > maxNum) {
    • maxKey = entry.getKey();
    • maxNum = entry.getValue();
    • }
    • }
    • return maxKey;
    • }
    • }
jayeshcp

Most frequently appearing number in given array

Example:

Find first most frequently occuring number in given array.

Given input {1, 2, 9, 3, 4, 3, 3, 1, 2, 4, 5, 3, 8, 3, 9, 0, 3, 2},
output should be 3 as it has highest frequency of occurence.

import java.util.*;

/**
  Time Complexity  : O(N)
  Space Complexity : O(N)
*/
class MaxOccurence {
  public static int findMax(int[] nums) {
    return findMaxOccurenceCountArray(nums);
  }
  
  private static int findMaxOccurenceCountArray(int[] nums) {
    int maxNum = 0;
    int maxCount = 0;
    
    if(nums.length < 1) return -1;
    if(nums.length == 1) return nums[0];
    
    int[] counts = new int[nums.length];
    
    for(int i = 0, len = nums.length; i < len; i++) {
      counts[nums[i]]++;
      if(counts[nums[i]] > maxCount) {
        maxCount = counts[nums[i]];
        maxNum = nums[i];
      }
    }
    
    return maxNum;
  } 
}
jayeshcp

HashMap Example

Hashes
Data Structures

Using HashMap in Java.

/* HashMap Example */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
class HashMapDemo
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(1, 1);
		map.put(2, 1);
		map.put(3, 1);
		map.put(4, 1);
		map.put(5, 1);
		map.put(6, 1);
 
		for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
			int key = entry.getKey();
			int value = entry.getValue();
			System.out.println(key + " " + value);
		}
	}
}
jayeshcp

Generate Prime Numbers

Generate prime numbers within a given minimum and maximum.
min and max values should be positive (greater than 0).

import java.util.*;

public class Primes {
  public static List<Integer> generatePrimes(int min, int max) {
    List<Integer> primes = new ArrayList<Integer>();
    boolean isPrime = false;
    
    if((min > max) || min < 0 || max <= 0) {
      return null;
    }           
            
    for(int i = min; i <= max; i++) {
      long endLimit = (long)Math.floor(Math.sqrt(i));
      isPrime = true;
      for(long j = 2; j <= endLimit; j++) {
        if (i % j == 0) {
          isPrime = false;
          break;
        }
      }
    
      if(isPrime) {
        primes.add(i);
      }
    }
    
    return primes;
  }
}
jayeshcp

Balanced Parenthesis

Given a string of open and closed parenthesis output "Balanced" if the parenthesis are balanced or "Unbalanced" otherwise.

A string is balanced if it consists entirely of pairs of opening/closing parenthesis (in that order), none of which mis-nest.

Example input:
(())())

Example output:
Unbalanced

Example input:
(()())

Example output:
Balanced

function balanced_parenthesis(s) {
    if(s == null) return null;
    
    var i = 0,
        startCnt = 0,
        n = s.length;
 
    for(i = 0; i < n; i++) {
        if(s[i] === "(") {
            startCnt += 1;
        } else if(s[i] === ")") {
            startCnt -= 1;
            if(startCnt < 0) {
                break;
            }
        }
    }
 
    if(startCnt !== 0) {
        return 'Unbalanced';
    } else {
        return 'Balanced';
    }
}