Algorithm | Learn for Master - Part 4
• ### Leetcode – Remove Nth Node From End of List (Java)

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

```   Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
```

Note:
Given n will always be valid.
Try to do this in one pass.

Analysis:

The key to solve this problem is to use two pointers: pre and cur. The pre pointer moves N steps in the first place,

• ### Leetcode – Longest common prefix

Longest common prefix

Write a function to find the longest common prefix string amongst an array of strings.

Pay attention to the corner case: strs can be empty.

Analysis

We define cur to record the char at current round that is recorded by si.

If si equals to the current string’s length, we return the substring from 0 to si.

At the beginning of each round, cur is set as null.

So when cur is null, we know this is the first string to check in current round. We set cur as the letter of the current string at index si

For the following string,

• ### Leetcode – Roman to Integer (Java)

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis

The rules to transfer a roman to an integer can be understood using the following examples:

So for any two Roman letters in the form: Left Right

if the left is smaller than the right, the result will be right – left.

if the left is larger or equal to the right, the result will right + left.

See this link for more examples of the roman numbers.

• ### binary search – first bad version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version.

• ### Quicksort algorithm

Quicksort is one of the most famous sort algorithms because of its average good performance. Because of its importance and popularity, it is usually asked in technique interviews. It is also important to master QuickSort as its partitioning technique can also be used to find the Kth largest or smallest element of an array in O(n) time with O(1) space complexity.

How quickSort algorithm works

Given an array A[s … e], a pivot is chosen to rearrange the array into two parts: ALeft and Aright. All the elements in ALeft are less than or equal to the pivot,

• ### LeetCode – Merge Sorted Array without extra space

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Analysis

We have described how to merge two sorted arrays into a third sorted array. For this problem, as A is assumed to have enough space, we are not allowed to create a third array.

We cannot start the merge from the beginning of the two arrays,

• ### Merge two sorted arrays algorithm (Java)

Given two sorted arrays or lists, how to merge them into a sorted array?

This is a fundamental problem as it is a common requirement to merge two sorted arrays into one sorted array. The algorithm of merging two sorted arrays is also the basics of the one of the most famous sort algorithms: merge sort.

Suppose there are two sorted arrays A and B, and we want to merge them into a third Array C.

We define three indexes a, b, c, which points to the beginning of the three arrays A, B,

• ### LeetCode – Find the kth largest element in an unsorted array (Java)

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Analysis

It’s easy to first sort the array, then pick up the Kth largest element. The time complexity is O(nlogn) if we use quick sort.

Min Heap Based Method

A better method is use a min heap or PriorityQueue with size K.

• ### LeetCode – Median of Two Sorted Arrays Java Solution

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

Example 2:

Analysis

It is easy to come up with a O(n) solution. Then it is high likely that the interviewer will ask you to give the algorithm with time complexity O(logn).

For any problem with sorted array, to come up with a O(logN) solution, we should consider the binary search related algorithm.

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