Posts

Important Graph Algorithms for Problem solving

-
Image
  Below is the important Graph Algorithms for problem solving Algorithms Cycle Detection Algorithm  For Directed graph Cycle can be detected using : 1) DFS-Based Cycle Detection using  color marking (visited array)     void dfs(node):       mark visited       for neighbor:          if not visited:              dfs(neighbor)        stack.push(node) 2) Kahn’s Algorithm : Build the Graph → Create an adjacency list from the prerequisites array. Compute In-Degree → Count the number of prerequisites (incoming edges) for each course. Start BFS with Zero In-Degree Nodes → Add all courses with zero prerequisites to a queue. Process Courses in BFS Order → Remove edges and reduce in-degrees. Check if All Courses Were Taken → If all courses were processed, return true ; otherwise, there’s a cycle.     // Simple idea of Kahn's: while (queue is n...
Post a Comment
Read more

Meeting Room 1 and Meeting Room 2 of Leetcode

-
                                    Meeting Room 1 and Meeting Room 2 of Leetcode 252. Meeting Rooms Given an array of meeting time  intervals  where  intervals[i] = [start i , end i ] , determine if a person could attend all meetings. Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: false Example 2: Input: intervals = [[7,10],[2,4]] Output: true Solution: Sort according to Ending time. public boolean canAttendMeetings ( int [][] intervals ) { Arrays . sort (intervals, ( int [] a, int [] b) -> { return a[ 1 ] - b[ 1 ]; }); int n = intervals . length ; for ( int i = 1 ;i<n;i++){ int st = intervals[i][ 0 ]; int en = intervals[i][ 1 ]; if (st < intervals[i- 1 ][ 1 ]){ return false ; } } return true ; }
Post a Comment
Read more

LeetCode 271: Encode and Decode String

-
LeetCode 271: Encode and Decode String   Design an algorithm to encode   a list of strings   to   a string . The encoded string is then sent over the network and is decoded back to the original list of strings. Implement the  encode  and  decode  methods. You are not allowed to solve the problem using any serialize methods (such as  eval ). Example 1: Input: dummy_input = ["Hello","World"] Output: ["Hello","World"] Explanation: Machine 1: Codec encoder = new Codec(); String msg = encoder.encode(strs); Machine 1 ---msg---> Machine 2 Machine 2: Codec decoder = new Codec(); String[] strs = decoder.decode(msg); Example 2: Input: dummy_input = [""] Output: [""] Solution: Decided to use => len(str) + "#" + str as encoding public class Codec { public String encode ( List < String > strs ) { String ans = "" ; for ( int i = 0 ; i < strs . size (); i++) { ...
Post a Comment
Read more

Differences Between Combination Sum1, Combination Sum2 and Combination Sum 3

-
  Differences Between Combination Sum1, Combination Sum2 and Combination Sum 3 Leetcode has 4 types of Cobination Sum Problems. We should know the similarities and differences among all those problems:- https://leetcode.com/problems/combination-sum/ https://leetcode.com/problems/combination-sum-ii/description/ https://leetcode.com/problems/combination-sum-iii/
Post a Comment
Read more

Types of Question related to 2 Nodes of a Graph

-
  Existence of a Path Is there a path from node A A A to node B B B ?  1971. Find if Path Exists in Graph Does a path satisfying certain constraints (e.g., through specific nodes or avoiding certain nodes/edges) exist?  Distance Between Two Nodes Shortest distance : Using algorithms like Dijkstra, Bellman-Ford, or BFS (for unweighted graphs). 787. Cheapest Flights Within K Stops Exact distance or range : Finding if a specific distance exists. Number of Paths Between Two Nodes Simple paths : Count paths where no node is revisited. All paths : Count paths (with possible revisits). K-length paths : Paths of exactly or at most k k k edges Shortest Path Between Two Nodes Weight-based shortest path : Using weights on edges. Fewest edges : Finding paths with the smallest number of edges. Maximum Flow or Minimum Cut Between Two Nodes Maximum flow problems deal with finding the maximum "amount" of a resource that can flow between two nodes in a capacitated graph. Connectivity Qu...
Post a Comment
Read more

Observer Design Pattern

-
Observer Design is one of the most important Design Pattern. It has many practical usage like notification services. The main two entities are Publisher(class) and Observer (interface) . Publisher is a class with functions like addObserver and notifyyObservers. Here class WeatherStation is extending Publisher class so that all the functions of Publisher can come to it. Here two Observers Mobile and Monitor is implementing interface  Observer. Inside Mobile and Monitor class, they are subscribing to WeatherData inside the constructors. import java.util.*; interface  Observer {  void  notifyy(); } class Mobile implements Observer{     WeatherStation ws;     public Mobile(WeatherStation ws) {         this.ws = ws;         ws.addObserver(this);     }          @Override     public void notifyy() {         System.out.println("Mobile is noti...
Post a Comment
Location: Bengaluru, Karnataka, India
Read more

Divide Intervals Into Minimum Number of Groups

-
  Divide Intervals Into Minimum Number of Groups  Leetcode Problem  Divide Intervals Into Minimum Number of Groups   is very much similar to the number-of-the-smallest-unoccupied-chair  Here we have to divide the given intervals into minimum number of groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other. Solution: We will think each interval as combination of two events ,  startTime  and endTime. 1) We create a list of events and then sort that list.  2) After that, we Initialise a min heap. which can be thinked like different baskets or groups.  3) We iterate through the events one by one, and assign each events to groups (picked from minheap).      While iterating starting event we pick a group from min heap and keep track in an array.       While iterating ending event through our tracking array, we release the group again in min...
Post a Comment
Read more