Cheat Sheet For Developers

Recursion   Recursion basically is function calling itself, when you call a function - from another function i.e functionA() calling functionB() or functionC() calling itself, it will create an stack, and the idea of calling functionX() is basically solving the smaller problems or solving the problems with small use case or inputs. Recursion technique is widely used if you want to Break the problem into small usecases and use the result or the output of the usecase to solve the larger problem.  lets take an example - Factorial of the number n! ? the nth factorial would be        n!= n * (n-1)! example  5! = 5 * 4!  Different Algorithms where the recursion is used extensively 1. Divide and Conquer 2. Backtracking 3. Tree Data structure - iteration   Common Steps of recursion    The first step is to identify the Base case , The base case defines the edge case or the smallest part of the problem, beyond which you cannot break...

Difference between substring and subsequence ? substring is continuous, while subsequence is not continuous   1. Longest Palindrome Substring - example -   ababd Approach 1. Brute force -  create all the substring, so create the substring of length 1 , length 2 , length 3, length 4 , and length 5. and then check for the string that has the maximum length .  Time complexity is O(N^3)  2. Decision Tree -    return max(count,          max(longestPalindromic(str, i + 1 , j, 0 ), longestPalindromic(str, i, j - 1 , 0 ))); 3. Dynamic programming using the TABULAR Approach   for d = 0; d < noOfRowSize; d++  // Row major      for i =0, j = d; i < noOfRowsSize, j < noOfColumnsSize ; i++ , j++         if (i == j || d i.e. Diagonal is Zero ) // that means they are equal               DP[i][j] = 1 ...

 Map   - HashMap  - TreeMap  This is the implementation of Red-Black algorithm, the keys are sorted in natural order or the comparator can be provided to sort the elements.   - LinkedHashMap

Terminologies Root node - the topmost element is called the root of the binary tree Leaf Node - the node that does not have any children is the leaf node   Level of Binary Tree -  horizontal distance of Binary Tree -      horizontal distance of the root is 0     horizontal distance of the left child = horizontal distance of its parent minus 1     horizontal distance of the right child = horizontal distance of its parent plus 1  Predecessor -   successor   -  Binary Tree Problems   1. Inorder traversal  (Left root Right) while(root != null){     inorder(root.left)     print(root.data)     inorder(root.right) } 2. Preorder traversal (root Left right ) while(root != null){      print(root.data)      preorder(root.left)     preorder(root.right) } 3. Postorder traversal (Left right root) while(root != null){     postorder(ro...

Sorting algorithm 1. Bubble Sort 2. Insertion Sort 3. Selection Sort  4. Merge Sort 5. Quick Sort Quick Sort - The partition logic of quick sort is very powerful problem solving tool. there are 2 partition logic  1. Horare's Partition Scheme  2. Lomuto's Partition Scheme , This is used for Kth order statistics, example 3rd Highest or Lowest element in the given list.   

  Functional programming First class functions - Functions can be passed as functions or return functions Function Composition - Chained Functional calls Prevent Side effects - Using  Immutability Pure Functions - No Side Effects - Same output for same input Parallelism - Pure function acting on immutable data   1. Immutable data & Pure Functions -  Scala Constructs - Scala uses val keyword to declare the variable, which is immutable declaration.   Pure functions don't read value from the external world, they don't modify the data, instead produce the new value  Java Constructs - Java uses final   keyword to declare the variable reference as Immutable, i.e once the value is assigned to the variable it cannot be reassigned.  Lombok -  https://projectlombok.org/features/val  , val was introduced in lombok that gets replaced to final var Java is the Strict type language, i.e. we need to declare the data type of the v...