Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

Example

numbers=[2, 7, 11, 15], target=9

return [1, 2]

Note

You may assume that each input would have exactly one solution

Challenge

Either of the following solutions are acceptable:

• O(n) Space, O(nlogn) Time
• O(n) Space, O(n) Time

Subarray Sum

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Example

Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Note

There is at least one subarray that it’s sum equals to zero.

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Note

Do not allocate extra space for another array, you must do this in place with constant memory.

Example

Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

Example

Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Challenge

Your algorithm should run in O(n) time and uses constant space.

Remove Element

Given an array and a value, remove all occurrences of that value in place and return the new length.

The order of elements can be changed, and the elements after the new length don’t matter.

Example

Given an array [0,4,4,0,0,2,4,4], value=4

return 4 and front four elements of the array is [0,0,0,2]

Note

1. Return the length of new array A
2. Don’t create another container

Longest Common Prefix

Given k strings, find the longest common prefix (LCP).

Example

For strings “ABCD”, “ABEF” and “ACEF”, the LCP is “A”

For strings “ABCDEFG”, “ABCEFG” and “ABCEFA”, the LCP is “ABC”

strStr

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Example

If source = “source” and target = “target”, return -1.

If source = “abcdabcdefg” and target = “bcd”, return 1.

Challenge

O(n²) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Longest Common Substring

Given two strings, find the longest common substring

Return the length of it.

Example

Given A = “ABCD”, B = “CBCE”, return 2.

Note

The characters in substring should occur continuously in original string. This is different with subsequence.

• substring: 必须是一个string中连续的一部分
• subsequence: 把一个string, 任意去掉一些字符后，得到的结果，不需要是连续的。

Compare Strings

Example

For A = “ABCD”, B = “ACD”, return true.

For A = “ABCD”, B = “AABC”, return false.

Note

The characters of B in A are not necessary continuous or ordered.

Two Strings Are Anagrams

Write a method anagram(s,t) to decide if two strings are anagrams or not.

Example

Given s=“abcd”, t=“dcab”, return true.

Challenge

O(n) time, O(1) extra space