The Coding Shala

Home >> Data Structures >> Graph Representation using Adjacency Matrix Graph Representation using Adjacency Matrix In this post, we will see how to represent a graph using the Adjacency Matrix. Generally, the Adjacency matrix is used to check if there is any edge available between two vertices or not. In the Adjacency matrix, we take a 2D array of size v*V, where V is the number of vertices in a graph and array[i][j] = 1 indicates that there is an edge between vertex i and j. The following example explains the Adjacency matrix of a graph: Graph Representation using Adjacency Matrix Java Program We have given the number of vertices 'v' and edges 'E' of a bidirectional graph. Our task is to build a graph through the adjacency matrix and print it. Example 1: Input: 5 7 0 1 0 4 1 2 1 3 1 4 2 3 3 4 Output: 0 1 0 0 1  1 0 1 1 1  0 1 0 1 0  0 1 1 0 1  1 1 0 1 0  Java Code: import java.util....

Home >> Data Structures >> Graph Representation Using Adjacency List Graph Representation Using Adjacency List In this post, we will see how to represent a Graph using the Adjacency List. We used an array of lists. The Size of the array is the number of vertices and arr[i] represents the list of vertices adjacent to the ith vertex. The following example shows how to represent a graph using adjacency list: Graph Representation using Adjacency list Java Program We have given the number of edges 'E' and vertices 'V' of a bidirectional graph. Now our task is to build a graph through the adjacency list and print the adjacency list for each vertex. Example 1: Input: 5 7  //vertex and edges 0 1 0 4 1 2 1 3 1 4 2 3 3 4 Output: 0-> 1-> 4 1-> 0-> 2-> 3-> 4 2-> 1-> 3 3-> 1-> 2-> 4 4-> 0-> 1-> 3 Java Code:  import java.util.* ; class Graph...

Home >> Interview Questions >> Evaluate Reverse Polish Notation How to Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. The  Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note:  The division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation. Example 1: Input: ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2: Input: ["4", "13", "5", "/", "+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3: Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", ...

Home >> Interview Questions >> Valid Parentheses Valid Parentheses Problem Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.  An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1: Input: "()" Output: true Example 2: Input: "()[]{}" Output: true Example 3: Input: "(]" Output: false Example 4: Input: "([)]" Output: false Example 5: Input: "{[]}" Output: true Valid Parentheses Java Program Method 1: We can do this using a stack. Push into the stack if opening brackets come else check with the top element of the stack with a closing bracket. Java Code:  class Solution { public boolean i...

Home >> Programming Questions >> Check if String is Palindrome or not Check if given String is Palindrome or not Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note: For the purpose of this problem, we define empty string as valid palindrome. Example 1: Input: "A man, a plan, a canal: Panama" Output: true Example 2: Input: "race a car" Output: false Palindrome String Java Program Method 1: We will check char if they are alphanumeric then will compare them. Java Code: class Solution { public boolean isPalindrome ( String s ) { int i = 0 ; int len = s . length ()- 1 ; s = s . toUpperCase (); System . out . println ( s ); while ( i <= len ){ if (! Character . isLetterOrDigit ( s . charAt ( i ))) i ++; else if (! Character . isLetterOrDigit ( s . charAt (...

Home >> Data Structures >> Introduction to Graph Introduction to Graph Data Structure The graph is one of the most important data structures that solve many real-world problems. A graph is a non-linear data structure. A Graph organizes items in an interconnected network. The following is an example of the graph: A graph G is an ordered pair of a set V of Vertices and a set E of Edges.                              G = (V,E). Ordered pair means: (a,b) not equals to (b,a) if,  a not equals to b. Unordered pair is: {a,b} = {b,a} In the graph, edges can be two types: Directed and Undirected edges. So based on the edges type graph can be two types: A directed graph or Digraph An undirected graph In the directed graph there is a direction from one vertex to another. An example of a Directed graph is the Internet(Web). In Web one page contains a link to another p...

Home >> Interview Questions >> Minimum Depth of a Binary Tree Find Minimum Depth of Binary Tree Given a binary tree, find its minimum depth.  The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7],     3    / \   9  20       /  \    15   7 return its minimum depth = 2. Find Minimum Depth of Binary Tree Java Program Method 1: Using recursion. Java Code:  /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth ( TreeNode root ) { if ( root == null ) return 0 ; if ( root . left == null...