algo Learning

Algorithm_questions.md

Q1) For the given sudoku find whether it is valid or invalid? Algo : You need to check for all the constraints of Sudoku : check the sum on each row check the sum on each column check for sum on each box check for duplicate numbers on each row check for duplicate numbers on each column check for duplicate numbers on each box Snippet

      public static boolean isValid(int[][] grid) {
    for (int i = 0; i < 9; i++)
      for (int j = 0; j < 9; j++)
        if (grid[i][j] < 1 || grid[i][j] > 9 
            || !isValid(i, j, grid))
          return false;
    return true; // The solution is valid
  }

  /** Check whether grid[i][j] is valid in the grid */
  public static boolean isValid(int i, int j, int[][] grid) {
    // Check whether grid[i][j] is valid at the i's row
    for (int column = 0; column < 9; column++)
      if (column != j && grid[i][column] == grid[i][j])
        return false;

    // Check whether grid[i][j] is valid at the j's column
    for (int row = 0; row < 9; row++)
      if (row != i && grid[row][j] == grid[i][j])
        return false;

    // Check whether grid[i][j] is valid in the 3 by 3 box
    for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)
      for (int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)
        if (row != i && col != j && grid[row][col] == grid[i][j])
          return false;

    return true; // The current value at grid[i][j] is valid
  }

Q2) Find distance between two words? If two words are not present print -1 Q3) Maze problem?

dynamic_programming.md

Divide a problem into sub problem and store the result and reuse to avoid recomputation. if the solution is not going to be reused don't store, that can't be solved using dynamic programing.

The idea of this is to cache the result and check the cache before computation.

• Overlapping
• Optimal structure

Overlapping

• Momization (Top down) febinocci(5) recursive and store the value.
• Tabulation (bottom up) array[0] array[1] and compute from the bottom to top

learn_about_graph.md

Graph

Graph is non-linear data structure like Tree. Tree and Graph are in the same sector and some time confues too. Though , Tree is also Graph there is a small condition that tree must satisfy. That is, tree must have n - 1 edges for n vertex. Linear data structures are Array , linked list, stack, queue. Order of storing the data is sequential.

Graph has two major type G = (V,E) G = {V,E}

1) Directed

Ordered (a,b) != (b,a)
Example : Website crawler (Google site crawler)
Page A has link to B then B does not have mantatory to link back A.

2) Undirected

UnOrdered {a,b)
Example : Facebook social network connections
Friend A has link to B , it means B has link to A.

Sortest path Algorithm Graph traversal Depth first search Breath first search are some basic idea we can think in graph. Weighted and UnWeighted graph

Inshort : Directed and weighted graph can be default.

Weighted Graph

City roads and stops has Weighted Graph (Edges has KM / Distance)

UnWeighted Graph

Google crawler and Facebook networks are unweighted

leedcode.md

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> holder = new HashMap<>(); // Key : Element, Value : index
        
        for(int i=0;i<nums.length;i++){
            int balance = target - nums[i];
            if(holder.get(balance) != null){
                int[] result = new int[2];
                result[0] = i;
                result[1] = holder.get(balance);
                return result;
            }else{
                holder.put(nums[i],i);
            }            
        }
        return null; 
    }
}