Ankur and Rishabh are two friends and want to buy some fruits from the market. They both have a list of their favourite fruit represented by strings. Your task is to help them find out their common favourite fruit with the minimum index sum. If there is a tie in …
Given the root of a binary search tree and two nodes n1 and n2, find the LCA(Lowest Common Ancestor) of the nodes in a given binary search tree. Example Naive Approach for Lowest Common Ancestor in Binary Search Tree Find the LCA(n1, n2) using the optimal approach to find LCA …
KMP(Knuth-Morris-Pratt) algorithm is used for pattern searching in a given string. We are given a string S and a pattern p, our goal is to determine whether or not the given pattern is present in the string. Example Input: S = “aaaab” p = “aab” Output: true Naive Approach The …
In the sudoku solver problem we have given a partially filled (9 x 9) sudoku, write a program to complete the puzzle. Sudoku must satisfy the following properties, Every number(1-9) must appear exactly once in a row and once in a column. Every number(1-9) must appear exactly once in a …
We write Arithmetic expressions in following three notations – Prefix Notation In this notation, the operands are written after the operator. It is also known as Polish Notation. For instance: +AB is a prefix expression. Infix Notation In this notation, the operators are written between the operands. It is similar …
Given a string s of length n. Check whether there is a closing parenthesis for every opening parentheses i.e. if all the parentheses are balanced. In other words, we can also say that, if we have a ‘}’, ‘)’ and ‘]’ for every ‘{‘, ‘(‘ and ‘[‘ respectively, the expression …
In the Evaluation of the postfix expression problem, we have given a string s containing a postfix expression. Evaluate the given expression. Example Input : s = “231*+9-” Output : -4 Input : s = “100 200 + 2 / 5 * 7 +” Output : 757 For Operands Having Single Digits Algorithm …
Given a string containing balanced parenthesis. Find if the expression/string contains duplicate parenthesis or not. Duplicate Parenthesis When an expression is in the middle of or surrounded by the same type of balanced parenthesis i.e. enclosed between the same type of opening and closing parenthesis more than once it is …
In expression evaluation problem, we have given a string s of length n representing an expression that may consist of integers, balanced parentheses, and binary operations ( +, -, *, / ). Evaluate the expression. An expression can be in any one of prefix, infix, or postfix notation. Example See …
In Balanced Expression with Replacement problem we have given a string s containing parenthesis i.e. ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’. The string also contains x at some places as a replacement of parenthesis. Check if the string can be converted into an expression with valid parenthesis after replacing all …