Week 1: Basic Algorithms

Continuing last week, we are going to go over those basic algorithms that appear in coding interviews frequently. Note that the content below is just an overview, and we will discuss them later with full details. In this week, just learn what they are and how they work superficially, in BFS manner.

Recursion and Divide and Conquer:

LeetCode #50. Pow(x, n) (medium)

LeetCode #169. Majority Element (easy)

More problems can be found here:

LeetCode: Recursion I

LeetCode: Recursion II

Greedy Algorithm:

Greedy Algorithm usually doesn’t appear in a coding interview. In fact greedy algorithm is not a certain algorithm, maybe we should just call it “greedy approach”. If you design a perfect algorithm using greedy approach for a problem, most likely it won’t apply to another problem, even they look similar. That is, greedy approach is not universal, and it requires quite a bit cleverness. As a result, this category doesn’t appear in coding interviews that often. That means, you don’t have to study really hard on this topic. Your task in this week is just to read through and memorize the following solutions, and you are good to go.

LeetCode #169: Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

Algorithm:

The main idea is that if we eliminate every pair of majority element and non-majority element, the majority element will still be majority in the new list, since it appears more than ⌊ n/2 ⌋ times. The algorithm is the following: suppose the first element in nums is the majority element, and initialize count to 1. Loop the rest of nums. If the next element is still the same, increment count; otherwise, decrement count. If count is decreased to 0, suppose the next element is the majority element, and keep looping. The code is here:

Solution:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if majority == nums[i]:
                count += 1
            else:
                count -= 1
            if count == 0:
                if i == len(nums):
                    break
                else:
                    majority = nums[i + 1]
        return majority

Analysis:

This algorithm uses a for loop that runs n - 1 times, and all operations inside the for loop takes time O(1), so the overall running time is O(n). It is also an in-place algorithm, thus takes O(1) space.

LeetCode #321: Create Maximum Number

LeetCode #122. Best Time to Buy and Sell Stock II (easy)

BFS and Topological Sorting:

DFS:

Rabin-Karp Algorithm:

LeetCode #28. Implement strStr() (easy)

Manacher’s Algorithm:

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s