Algorithms | Learn for Master - Part 6
• Leetcode Isomorphic Strings solution Java

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

Analysis

We can use a HashTable to map the letter from String1 to String2.

• Document Summarization using TextRank Example

TextRank is an algorithm based upon PageRank for text summarization. In TextRank, the vertices of the graph are sentences, and the edge weights between sentences denotes the similarity between sentences.

Use the following  steps, we can extracte important sentences from a set of documents.

1. Sentence identification: transfer the documents into sentences
2. Tokenization: Split each sentence into a set of words
3. Similarity calculation: Calculate the similarity between sentences
4. Build sentence graph: build a graph of  the sentences
5. TextRank: score the sentences via pagerank

Sentence identification

We can use nltk’s included Punkt module to get sentences from a document.

• 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),
• 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.

• 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.
• 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.

• Learn Spark by Examples

In this post, I briefly introduce Spark, and uses examples to show how to use the popular RDD method to analyze your data. You can refer to this post to setup the pySpark environment using Ipython Notebook.

SparkContext

SparkContext, or Spark context is the entry point to develop a spark application using the spark infrastructure.

Once a SparkContext object is created, it sets up the internal services and build a connection to the cluster managers, which manage the actual executors that conduct the specific computations.

The following diagram from the Spark documentation visualize the spark architecture:

The SparkContext object is usually referenced as the variable sc,

• Interview Questions: Edit distance

Edit distance related questions are frequently asked by many large companies such as Google, Facebook, Apple, Microsoft, Uber, Airbnb, Amazon, et al. In this post, we describe three kinds of problems related to edit distance.

What is edit distance?

Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. Edit distances can be applied in natural language processing for automatic spell correction by selecting words from a dictionary that have a low distance to the word in question.

• LeetCode – Binary Search Tree Iterator (Java)

Binary Search Tree Iterator

• Difficulty: Medium

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Source: https://leetcode.com/problems/binary-search-tree-iterator/

In this post, we describe a stack based method to solve the Binary Search Tree Iterator problem in Java. This solution similar to the stack based in oder traversal of a binary search tree.

• 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: