Want to Crack Leetcode Problems Easily?

Top 10 Algorithms for Coding Interview

Till right now, I have only mastered four types of problems: DFS, BFS, string. Thanks to sourabreddy’s medium post about these types of problems, they have become so much easier. Please check his website for these types of questions. Like he said, geeksforgeeks have very good and easy understanding tutorials about basic algorithms.

The steps to crack these problems. (1) The first and foremost is to be patient, to understand the question well. (2) Then, analyze a toy example, figure out how would you solve this problem without programming, what type of knowledge or tactics you have used (math, the algorithms you have mastered before), what is the logic behind this. Make sure to put all the possible situations in the example (From simple to more complex).(3) After the main problem is resolved, think about special cases, twit your pseudo-code a little to solve the special cases. (4) To convert this thinking process to coding should be an easy step.

The tutorial list:

Leetcode Pattern 1 | BFS + DFS == 25% of the problems — part 1

Leetcode Pattern 1 | DFS + BFS == 25% of the problems — part 2

Note: DFS can be used to:

• Find all the solutions, and record the path to get the solution
• Detect cycles

BFS:

• Find the shortest path
• Check levels or steps
• Can be used to solve puzzles. 773. Sliding Puzzle

Leetcode Pattern 2 | Sliding Windows for Strings

Note: Understanding the application situation of each basic algorithm is the key step to figure out which algorithm to use in order to solve a problem you met.

Based on the above tutorials, for String categories, it missed the type of two strings:

Two Strings

Find common sub strings (longest) between two string. Using longest common substring DP. Note: it is the same if its two arrays

Suppose we have string A and B, each with m and n chars. If we use bruteforce, then in A, there could be M² substring, and to locate these substring in B, we spend O(n) for each substring, which makes the total complexity to be O(n*M²).

But now, if we use the LCS method, the time and space complexity will be O(n*m) . LCS is DP method that we can use bottom-up with memorization.

Pseudo-code of LCS
init a[M+1][N+1] two dimensional matrix with [0]
for i in [0,M):
    for j in [0,N+1):
        if A[i]==A[j]:
            a[i+1][j+1]=a[i][j]+1
            result = max(result,a[i+1][j+1])
        else:
            a[i+1][j+1] = 0

Array

For array problems, math will play an important role here. For simple questions, basic math and data structure can solve the problems.

Subcategories:

• sum of K numbers of elements in the list = Target, return either the index or the elements(might need to avoid repetition). (2/3/4 sums)
• Partition a list into K equal part. (DP)
• Maximum subarray 718,
• Duplicates 217, 26, 27, 219, 287, 442

Two pointers: If you see in the problem that you can do comparison and it is always one type of satisfactory element is in ahead of the other, this could be resolved by two pointers(t1). Or one starts from the beginning, one from the end and going to the middle(t2). e.g. 122. Best Time to Buy and Sell Stock II (multiple transaction, accumulate sectional profit), 26, 27, 283. Move Zeroes, 121. Best Time to Buy and Sell Stock (keep track of min_price and max_profit, single pass, one transaction), 88. Merge Sorted Array, 167. Two Sum II — Input array is sorted(t2), 11. Container With Most Water (t2, move with greedy programming)

Hashset: 268. Missing Number

DP:39. Combination Sum, 416. Partition Equal Subset Sum, 698. Partition to K Equal Sum Subsets

LCS:718. Maximum Length of Repeated Subarray

Duplicates:

Find duplicates: Floyd’s Tortoise and Hare algorithm, either linked list or an array : 287, for this type, typically can only find one duplicated element.

Remove duplicates: or it is the same to remove certain number 26,27 (in-place)

Sort array
#use two pointers
slow, faster = 0,0
for faster in xrange(1, len(nums)):
    if nums[slow]!=nums[faster]:
        nums[slow+1]=nums[faster]
        slow+=1
return slow+1

Maximum Subarray: 53 (sum), 152 (product)

Kadane’s Algorithm: O(n) vs brute force O(N²)

Initialize:
    max_so_far = -maxint
    max_ending_here = 0
for i in xrange(len(a)):
  (a) max_ending_here = max_ending_here + a[i]

  (b) if( max_ending_here > max_so_far) #update the max
            max_so_far = max_ending_here
  (c) if(max_ending_here < 0) # discard the values before
            max_ending_here = 0
return max_so_far

Python code:

from   sys import maxint
class Solution(object):    
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_so_far = -maxint - 1
        max_ending_here = 0
        for i in range(0, len(nums)):
            max_ending_here = max_ending_here + nums[i]
            if (max_so_far < max_ending_here):
                max_so_far = max_ending_here
 
            if max_ending_here < 0:
                max_ending_here = 0  
        return max_so_far
# brute force
import  sys
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        rst = -sys.maxint
        for i in xrange(len(nums)):
            add = nums[i]
            if add>rst:
                rst = add
            for j in xrange(i+1,len(nums)):
                add+=nums[j]
                if add>rst:
                    rst = add
        return rst

For the product: we need to record the min_ending_here, for the max_ending_here, can only be [1, +infinity), min_ending_here (-infinity, 1]

Initialize:
    max_so_far = -maxint
    max_ending_here = 1
    min_ending_here = 1
for i in xrange(len(a)):
  (a) if a[i]>=0 # keep the same
            max_ending_here = max_ending_here *a[i]
            min_ending_here = min(min_ending_here *a[i], 1)
            max_so_far = max(max_ending_here,max_so_far)
            if nums[i]==0:
                   max_ending_here = 1
                   min_ending_here = 1  
  (b) else: #negative, then max and the min is going to be changed
            max_so_far = max(min_ending_here * nums[i], max_so_far)
            #exchange the max_ending here and the min_ending_here
            temp = max_ending_here
            max_ending_here = max (min_ending_here * nums[i], 1)
            min_ending_here = temp * nums[i] # mini change to be negative again 
return max_so_far

Find a certain sum in the list: or a set (Use the elements repeatly), use Dynamic Programming:

e.g. 39. Combination Sum

[2, 3, 6, 7] and target 7, A solution set is:

[
  [7],
  [2, 2, 3]
]

The python code:

from bisect import *
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        r=[]
        candidates.sort()
        #print candidates
        idx = bisect_left(candidates,target)
        #print 'idx',idx
        if idx<0 :
            return []
        #idx = min(idx, len(nums))
        if idx<len(candidates) and candidates[idx]== target:
            r.append([target])
            
        def DFS(remain,index, r_lst):
            #print r_lst, remain
            #end condition
            if remain == 0:
                r.append(r_lst)
                return
            if remain<0 or index>=idx:
                return
            for i in xrange(remain//candidates[index]+1):
                #print 'append', candidates[index], r_lst
                new_lst = r_lst+ [candidates[index]]*(i)
                rslt = DFS(remain-candidates[index]*(i), index+1,new_lst)
                    #return False
            return 
        DFS(target,0,[])
        return r

e.g. 416. Partition Equal Subset Sum

[1,1,2,5,5,5] T= sum/2 = 12

def DFS(remain, start,end,memo):
#End condtion
if remain == 0: return True
if remain<0: return False
#check memo
if remain not in memo:
    for i in xrange(start, end):
        memo[remain] =any(DFS(r-nums[i],i+1,end, memo)
return memo[remain]

Extend to k subset: 698. Partition to K Equal Sum Subsets

Methods:

• Sort the list or not at the begin. (O(nlogn)
• Brute force searching (recursively O(2^n))
• Hash-map (dictionary in Python), can lower the complexity by one power of n
• Recursive with memorization (DP, top-down )
• Bottom-up with memorization (DP, bottom-up)

What do I think about coding interviews?