Evaluation of Infix expressions

Infix notation is commonly used in arithmetic formula or statements, the operators are written in-between their operands. Let’s assume the below Operands are real numbers. Permitted operators: +,-, *, /, ^(exponentiation) Blanks are permitted in expression. Parenthesis are permitted Example: A * ( B + C ) / D 2 * (5 + 3) / … Read more

Valid Brackets – Part 2 | Stack Method

Objective: Given a string containing just the characters ( , ) determine if the input string is valid. Example: ()()(()(()))() valid: true )()()( valid: false ()()) valid: false Approach: Earlier we discussed the solution which keeps the count of open and closed parentheses. In this solution we will solve this problem using stack. Using Stack: Initialize a … Read more

Find median of two sorted arrays of same size

Objective:  Given two sorted arrays of size n. Write an algorithm to find the median of combined array (merger of both the given arrays, size = 2n). What is Median? The median is the value separating the higher half of a data sample, a population, or a probability distribution, from the lower half. For a data set, it may be thought … Read more

Single Threaded Binary Tree Complete Implementation

In earlier article “Introduction to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advantages it has over normal binary tree. In this article we will see the complete implementation of single threaded binary tree.( Click here to read about “double threaded binary tree”) Image Source : http://web.eecs.umich.edu/~akamil/teaching/su02/080802.ppt Single Threaded: … Read more

The Word Break Problem

Objective : Given an string and a dictionary of words, find out if the input string can be broken into a space-separated sequence of one or more dictionary words. Example: dictionary = [“I” , “have”, “Jain”, “Sumit”, “am”, “this”, “dog”] String = “IamSumit” Output: “I am Sumit” String =”thisisadog” Output : String can’t be broken … Read more

Dynamic Programming – Longest Increasing Subsequence

Objective: The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array such that all elements of the subsequence are sorted in increasing order. OR Given a array A[1,2,……,n] , calculate B[1,2….m] with B[i]

Backtracking – Search a Word In a Matrix

Objective : Given a 2D matrix of characters. Check whether the word exist in the matrix or not. If it exists then print its path. All movements are allowed (right, left, up, down and diagonally). Example: Approach: We will show the path as increment counter   Create a solution matrix of the same structure as … Read more

Backtracking – N Queens Problem

Objective : In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen’s problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one … Read more

Find the subarray with sum to a Given Value.

Objective: Given an array (non-negative) and an integer, Find the Subarray whose sum is equal to the given integer.

Examples:

int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 };
Integer = 55
Output : 55 is found between indexes 2 and 4
And Elements are : 14 22 19

Approach :

Naive Approach: Use 2 loops . Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

Read more