Up to date

import java.util.*; import java.lang.*; import java.io.*; class SinglyLinkedList { private static Node head; private static void create(int[] data) { // create first Node head = new Node(data[0], null); // if only single element if(data.length == 1) { return; } Node last = head; for(int i = 1; i max) { max = temp.getData(); } // move next node temp = temp.getNext(); } return max; } private static int maxRecursive(Node head) { if(head == null) { return Integer.MIN_VALUE; } int max = maxRecursive(head.getNext()); return max > head.getData() ? max : head.getData(); } private static int min() { if(head == null) { return 0; } Node temp = head; int min = Integer.MAX_VALUE; while(temp != null) { if(temp.getData() curr...

 1. Diagonal Matrix :   For this matrix M[row, column] = 0 for all row != column We can store non zero elements in one dimensional array to avoid storing zeros  2. Lower Triangular Matrix :  M[row, column] = 0 for all row < column M[row, column] = non-zero for all row >= column Non zero element count = 1 + 2 + 3 + ..... n = n(n+1)/2 Zero element count = n^2 - n(n+1)/2 = n(n-1)/2 Row Major Formula Column Major Formula 3. Upper Triangular Matrix M[row, column] = 0 for all row > column M[row, column] = non-zero for all row <= column Non zero element count  = 1 + 2 + 3 + ..... n =  n(n+1)/2 Zero element count  = n^2 - n(n+1)/2 =  n(n-1)/2 4. Symmetric Matrix M[row, column] is Symmetric matrix if M[row, column] = M[column, row] To represent it we can either use Lower Triangular Matrix or Upper Triangular Matrix. 5. Tridiagonal Matrix Total number of elements = n + n-1 + n-1 = 3n - 2 Calculate index when represented in 1 D array   6. ...

 TODO

An  anagram  of a  string  is another  string  that contains the same characters, only the order of characters can be different. For example, “abcd” and “dabc” are an  anagram  of each other. class isStringAnagram {     // Asumption : All characters in strings are ASCII codes     static void isAnagram(String str1, String str2) {         if(str1.length() != str2.length()) {             System.out.println(str2 + " is not anagram of " + str1);             return; // early return         }         int[] frequency = new int[128];         for(int i = 0; i < str1.length(); i++) {             frequency[str1.charAt(i)]++;         }         for(int i = 0; i < str1.length(); i++) {             if(...

Using 2 for loops : It is O(n^2) time Find Duplicates in String using hashing . It is O(n) time Find Duplicates in String using bitwise operator

I should be mindful of taking bits. For example if I want to cover all 128 ASCII codes in string then I need 128 bit datatype and long has only 8 bytes (8 bytes * 8 bits) = 64 bits. Hence this method works well if I have string with alphabets only. Let's assume my string contains only small letters. So I just need 26 bits for all 26 letters.  class DuplicatesInString {     // Asumption : All characters are 'a' to 'z'     static void printDuplicates(String str) {         int resultBits = 0;         for(int i = 0; i < str.length(); i++) {             int tempShiftBits = 1; // Assign a byte ; 00000000 00000000 00000000 00000001             // If character is 'd'. ASCII code of 'd' = 100 and shiftCount = 3             int shiftCount = str.charAt(i) - 97;             tempShiftBits = tempShiftBits << s...

 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

// It is O(n) time class DuplicatesInString {     // Asumption : All characters are in ASCII code     static void printDuplicates(String str) {         int[] frequency = new int[128];         for(int i = 0; i < str.length(); i++) {             frequency[str.charAt(i)]++;         }         System.out.println("Printing duplicates : ");         for(int i = 0; i < str.length(); i++) {             char ch = str.charAt(i);             if(frequency[ch] > 1) {                 System.out.println(ch + " appears " + frequency[ch] + " times.");                 frequency[ch] = 0; // To avoid print duplicate result             }           }   ...

  Palindrome A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar. class PalindromeString {     static boolean isPalindrome(String str) {         // 2 variable to traverse from left and right         int i = 0;         int j = str.length() - 1;         while(i < j) {             char c1 = str.charAt(i);             char c2 = str.charAt(j);             // If characters don't match but case may be ignored,             // try converting both characters to uppercase.             // Unfortunately, conversion to uppercase does not work properly             // for the Georgian alphabet, which has strange rules about case     ...

Greeksforgreeks reference import java.util.regex.Pattern; class ReverseWordInGivenString {     static String reverseWords(String str) {         // Specifying the pattern to be searched         Pattern pattern = Pattern.compile("\\s");         // splitting String str with a pattern         // (i.e )splitting the string whenever their         //  is whitespace and store in temp array.         String[] temp = pattern.split(str);         String result = "";            // Iterate over the temp array and store         // the string in reverse order.         for (int i = 0; i < temp.length; i++) {             if (i == temp.length - 1)                 result = temp[i] + result;       ...

class CountWordsConsonantsVowelsInSentence {     // ASCII Codes : A-Z = 65-90, a-z = 97-122, 0-9 = 48-57, Enter = 10, Space = 13, Esc = 27     static void count(String str) {         // Corner case :         if(str == null || str == "") {             System.out.println("Invalid input");             return;         }         System.out.println("Original String is : " + str);         char[] chars = str.toCharArray();         int cCounts = 0;         int vCounts = 0;         int wCounts = 1; // assigning 1 if no space means single word         // Remove leading, trailing and multiple spaces         chars = trim(chars);         for(int i = 0; i < chars.length; i++) {       ...

class ConvertCase {          // ASCII Codes : A-Z = 65-90, a-z = 97-122, 0-9 = 48-57, Enter = 10, Space = 13, Esc = 27     static void convertCase(String str) {         System.out.println("Original String is : " + str);         char[] chars = str.toCharArray();         for(int i = 0; i < chars.length; i++) {             // Convert capital later to small later             if(chars[i] >= 65 && chars[i] <= 90) {                 chars[i] += 32; // 97-65 = 32             } else if(chars[i] >= 'a' && chars[i] <= 'z') {                     chars[i] -= 32; // 97-65 = 32             }         }         System.out.println("Conv...

  ASCII defines 128 characters, which map to the numbers 0–127. Unicode defines (less than) 2 21  characters, which, similarly, map to numbers 0–2 21  (though not all numbers are currently assigned, and some are reserved). Unicode is a superset of ASCII, and the numbers 0–127 have the same meaning in ASCII as they have in Unicode. For example, the number 65 means "Latin capital 'A'". Because Unicode characters don't generally fit into one 8-bit byte, there are numerous ways of storing Unicode characters in byte sequences, such as UTF-32 and UTF-8 .  More about UTF.

 class FindAPaireWithSumKSortedArray {     static int[] array;          // Time complexity : O(n). Assuming +ve numbers     static void findPair(int k) {         int i = 0;         int j = array.length-1;         while(i < j) {             if(array[i] + array[j] == k) {                 System.out.println("Found pair (" + array[i] + ", " + array[j] + ")");                 i++;                 j--;                 continue; // To avoid checking below conditions             } else if(array[i] + array[j] > k) {                 j--;             } else {           ...

 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 ...

 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;                     }     ...

// 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;           ...