Implement Thread Pool
Reference: JavaCodeGreek
Posts
What is merging and masking a bit
Checking a bit is on or off (1 or 0) is called masking. Hint : Use << (left shift) and & operators Setting a bit on in a memory is called merging. Read More
Find a pair of elements with sum k (a+b=k) in unsorted array
class FindAPairWithSumK { static int[] array; // Time complexity : O(n^2). Assuming +ve numbers // n-1 + n-2 + n-3 + .......+ 3 + 2 + 1 = n*(n-1)/2 = (n^2-n)/2 = n^2 static void findPair_bruteForce(int k) { for(int i = 0; i < array.length-1; i++) { for(int j = i+1; j < array.length; j++) { if(array[i] + array[j] == k) { System.out.println("Found pair (" + array[i] + ", " + array[j] + ")"); } } } } static void findPair_dp(int k) { int largest = getMax(); int[] dp = new int[largest + 1]; for(int ...
Find duplicates unsorted array
class PrintDuplicateAndCounts { static int[] array; static int smallest = -1; static int largest = -1; // Time complexity : O(n^2). Assuming +ve numbers static void printDuplicates() { int count; for(int i = 0; i < array.length-1; i++) { if(array[i] > -1) { count = 1; for(int j = i+1; j < array.length; j++) { if(array[i] == array[j]) { count++; array[j] = -1; } ...
Find duplicates and count in sorted array
// Time complexity : O(n) class PrintDuplicateAndCounts { static void printDuplicates(int[] array) { for(int i = 0; i < array.length - 1; i++) { if(array[i] == array[i+1]) { // duplicate found int j = i + 1; while(array[i] == array[j]) { // continue iterating array to count all duplicates of this perticular element j++; } System.out.println(array[i] + " appeared " + (j-i) + " times"); i = j - 1; ...
Find multiple missing elements unsorted in an unsorted array
class FindMultpleMissingElementsInAnArray { int[] array; boolean present[]; int low; int high; void printMissingElements() { // Corner case if(array.length == 0) { System.out.println("Array is empty"); } findLowAndHighElements(); createAndPopulateBooleanArray(); for(int i = 0; i < present.length; i++) { if(present[i] == false) { int missingElement = low + i; System.out.println("Missing element is : " + missingElement); } } }...
Find multiple missing elements in sorted an array
class FindMultpleMissingElementsInAnArray { static int getMissingElement(int[] array) { // Corner case if(array.length == 0) { System.out.println("Array is empty"); return -1; } int sum = 0; for(int i = 0; i < array.length; i++) { sum += array[i]; } int n = array[array.length - 1]; // last element in list int sumOfNNaturalNumbers = n*(n+1)/2; return sumOfNNaturalNumbers - sum; } static void printMissingElements(int[] array) { // Corner case if(array.length == 0) { ...
Find single missing element in sorted an array
class FindSingleMissingElementInAnArray { static int getMissingElement(int[] array) { // Corner case if(array.length == 0) { System.out.println("Array is empty"); return -1; } int sum = 0; for(int i = 0; i < array.length; i++) { sum += array[i]; } int n = array[array.length - 1]; // last element in list int sumOfNNaturalNumbers = n*(n+1)/2; return sumOfNNaturalNumbers - sum; } static void getMissingElement2(int[] array) { // Corner case if(array.length == 0) { ...
Array Operation
class ArrayOperations { int[] array; static int size; void swap(int a, int b) { array[a] = array[a] + array[b]; array[b] = array[a] - array[b]; array[a] = array[a] - array[b]; } void displayArray() { Arrays.stream(array).forEach(num -> System.out.print(num + " ")); System.out.println(); } void displaySortedArray() { for(int i = 0; i <= size; i++) { System.out.print(array[i] + " "); } System.out.println(); } int get(int index) { if(index >= 0 && index < array.length) { return array[index]; ...
Java program for Tower of Hanoi
class TowerOfHanoi { // Time Complexity O(n) and Space Complexity O(1) void tower_recursive(int numberOfDisks, int sourceTower, int additionalTower, int destinationTower) { if(numberOfDisks > 0){ tower_recursive(numberOfDisks - 1, sourceTower, destinationTower, additionalTower); System.out.println("Moving disk from tower " + sourceTower + " to " + destinationTower); tower_recursive(numberOfDisks - 1, additionalTower, sourceTower, destinationTower); } } public static void main (String[] args) { TowerOfHanoi obj = new TowerOfHanoi(); obj.tower_recursive(3, 1, 2, 3); } }
Java program for combination | nCr
class NCR { // Time Complexity O(n) and Space Complexity O(1) int nCr (int n, int r) { // Formula n!/(r!*(n-r)!) int factorialN = factorial(n); int factorialR = factorial(r); int factorialNMinusR = factorial(n-r); return factorialN / (factorialR * factorialNMinusR); } // Time Complexity O(n) and Space Complexity O(n) int nCr_pascalTriangle (int n, int r) { if(r == 0 || n == r) { return 1; } return nCr_pascalTriangle(n-1, r-1) + nCr_pascalTriangle(n-1, r); } // Time Complexity O(n) and Space Complexity O(1) int factorial (int n) { if(n <= 1) { //To return 1st ...
Java program for Fibonacci Series
class FibonacciSeries { int[] dp; // Time Complexity O(2^n) and Space Complexity O(n) int fibonacci_recursive (int n) { if(n <= 1) { //To return 1st and 2nd term return n; } return fibonacci_recursive(n-2) + fibonacci_recursive(n-1); } // Time Complexity O(n) and Space Complexity O(n) int fibonacci_recursive_memoization (int n) { if(n <= 1) { //To return 1st and 2nd term return n; } if(dp[n-2] == -1) { dp[n-2] = fibonacci_recursive(n-2); } if(dp[n-1] == -1) { dp[n-1] = fibonacci_recursive(n-1); ...
Java program for Taylor Series
class TaylorSeries { int powerOfX; int factorialOfN; double result; // Time Complexity O(n) and Space Complexity O(n) double taylor_recursive (int x, int n) { if(x <= 0 || n < 0) { // Corner case return -1; } if(n == 0) { return 1; } double result = taylor_recursive(x, n - 1); powerOfX *= x; factorialOfN *= n; return (double)powerOfX / factorialOfN + result; } // Time Complexity O(n) and Space Complexity O(1) double taylor_iterative (int x, int n) { if(x <= 0 || n < 0) { // Corner case ...
Java program to calculate the power of a number | exponential (m^n)
// Time Complexity O(n) and Space Complexity O(n) int pow_recursive (int m, int n) { if(n == 0) { return 1; } return pow_recursive(m, n - 1) * m; } // Time Complexity O(n/2) and Space Complexity O(n) int pow_recursive_improved(int m, int n) { if(n < 0) { return 0; } if(n == 0) { return 1; } if(n % 2 == 0) { // Even return pow_recursive_improved(m*m, n/2); } return m * pow_recursive(m*m, (n - 1) / 2); } // Time Complexity O(n) and Space Complexity O(1) int pow_iterative(int m, int n) { if(n < 0) { return 0; } if(n == 0) { return 1; } int result = 1; for(int i = 0; i < n; i++) { ...
Write program to calculate factorial of a number
0! = 1 1! = 1 //Time complexity O(n) and Space complexity O(n) int factorial_recursive(int n) { if(n < 0) { return 0; } if(n == 0) { return 1; } return factorial_recursive(n - 1) * n; } //Time complexity O(n) and Space complexity O(1) int factorial_iterative(int n) { if(n < 0) { return 0; } if(n == 0) { return 1; } int result = 1; for(int i = 1; i <= n; i++) { result *= i; } return result; }
Sum of natural numbers
//Time complexity O(n) and Space complexity O(n) int sum_recursive(int n) { if(n == 0) { return 0; } return sum_recursive(n - 1) + n; } //Time complexity O(n) and Space complexity O(1) int sum_iterative(int n) { int sum = 0; for(int i = 1; i <= n; i++) { sum += i; } return sum; } //Time complexity O(1) and Space complexity O(1) int sum_usingFormula(int n) { return n * (n + 1) / 2; }
Types of Recursion
1. Tail Recursion : Function call itself is the last statement. Operations perform at calling time of the recursion. // Time complexity O(n) & Space complexity O(n) void tail_recursion(int n) { if(n > 0) { System.out.print(n + " "); tail_recursion(n - 1); } } // Time complexity O(n) & Space complexity O(1) void tail_recursion_iterative(int n) { System.out.println(); while(n > 0) { System.out.print(n + " "); n--; } } 2. Head Recursion : Function call itself is the first statement. Operations perform at returning time of the recursion. //Time complexity O(n) & Space complexity O(n) void head_recursion(int n) { ...
