Algorithm | Learn for Master - Part 5
  • Convert infix notation to reverse polish notation (Java)

    How to implement a calculator is a popular interview question. To answer this question well, you need to maser Stack data structures, convert an infix notation to RPN and evaluate reverse polish notation. 

    Since the input is usually in infix notation, e.g. “3 + 6 * 2”, it is difficult develop a program to evaluate it directly.

    In practice, we can implement a calculator algorithm into two steps:

    1. the first step is to convert your mathematical expressions, which is called infix notation, into Reverse Polish Notation (RPN),
    [Read More...]
  • LeetCode- Evaluate Reverse Polish Notation (Java)

    [LeetCode] Evaluate Reverse Polish Notation (RPN)
     Evaluate the value of an arithmetic expression in Reverse Polish Notation.
    Valid operators are +, -, *, /. Each operand may be an integer or another expression.
    Some examples:

    Analysis

    Evaluate RPN is the second step to build a calculator. Once we have converted the infix expression into the RPN,  we need to evaluate RPN to get the result. 

    The basic idea to evaluate reverse polish notation is to use a stack to process the strings.

    We scan the array of the RPN expression.

    [Read More...]
  • Leetcode – Reverse Words in a String II (Java)

    Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
    
    The input string does not contain leading or trailing spaces and the words are always separated by a single space.
    
    For example,
    Given s = "the sky is blue",
    return "blue is sky the".
    
    Could you do it in-place without allocating extra space?

    Analysis

    This problem is similar to the rotate array to right by k steps problem. 

    There are two steps:

    1. use the space ‘ ‘ to determine the boundary of words.
    [Read More...]
  • Leetcode- Rotate Array to right by K steps (java)

    Rotate an array of n elements to the right by k steps.

    For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

    How many different ways do you know to solve this problem?

    Analysis

    It is easy to use an intermediate array to solve this problem. Suppose the original array is A, the new array is B, we will copy 

    A[0:n-k -1] to B[k:n-1], and A[n – k:n-1] to B[0:k – 1], then we copy all the elements in B back to Array A using System.arrayCopy.

    [Read More...]
  • Leetcode – Best Time to Buy and Sell Stock (Java)

    Say you have an array for which the ith element is the price of a given stock on day i.

    If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

    Example 1:

    Example 2:

     
    Analysis:
     
    We scan the table, and record the minimum price in the range [0, i – 1], so the potential max profit is prices[i] – min(prices[0, i-1])
    The following is the implementation in Java:
     

     

    [Read More...]
  • Leetcode – Excel Sheet Column Number (Java)

    Given a column title as appear in an Excel sheet, return its corresponding column number.

    For example:

    Related to this question Excel Sheet Column Title

    This is a normal number system conversion problem.  Think about how we convert a binary number to a decimal number?

    1101001 = 1* 2 ^6 + 1 * 2^5 ..

    We can easily have the following implementation:

     

    [Read More...]
  • An efficient Prime number generation algorithm (Java)

    Given a number n, print all primes smaller than or equal to n. 

    For example, if n is 10, the output should be “2, 3, 5, 7″. If n is 20, the output should be “2, 3, 5, 7, 11, 13, 17, 19″.

    The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is not too large.

    Leetcode. Count Primes: https://leetcode.com/problems/count-primes/

    Here is the basic idea of this algorithm:

    1. Build a table or an array with n numbers from 1 to n. 
    [Read More...]
  • Leetcode – Largest Rectangle in Histogram Java

    Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

    Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

    The largest rectangle is shown in the shaded area, which has area = 10 unit.

    For example,
    Given heights = [2,1,5,6,2,3],
    return 10.

    Analysis

    A simple solution is to expand for each bar to its both left and right side until the bar is lower. 

    [Read More...]
  • Leetcode – Maximal Rectangle solution 1 (Java)

    Maximum Rectangle area for a 0 1 matrix.

    Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

    Source: https://leetcode.com/problems/maximal-rectangle/
     
    This is a hard one from Facebook.
     
    The key to solve this problem is to first build a matrix ones[][], where ones[i][j] means the number of continuous 1s to the cell matrix[i][j] in jth column. See the following figure. 
     
     
     leetcode maximal rectangle
     
     
    We have:

    We can fill up the matrix ones[][] using dynamic programming. The formula is :

    How to use the ones[][] matrix to calculate the maximum area?

    [Read More...]
  • Leetcode – Word Ladder solution In Java

    leetcode word   ladder

    Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word must exist in the dictionary. For example, given:

    One shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, the program should return its length 5.

    Analysis

    From each word, we can change its letter one by one, thus a bread first search tree is constructed. The problem becomes to find the shortest path from the start word to the end word.

    [Read More...]
Page 5 of 7« First...34567