INDEX

• Choose Language for coding interview :link:
• Consider Time Complexity :link:
• Implement Data Structures :link:
• Implement Sorting algorithms :link:
  • Quick Sort
  • Merge Sort
  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Counting Sort
• Problem solving
  • LeetCode :link:
  • Codility :link:
  • Google KickStart :link:
  • BOJ :link:
  • Programmers :link:

Language

Questions for choosing the right language for your coding interview

1. Are you interviewing for a language-specific job?
2. What is your best language?
3. How easy is it to solve algorithmic problems in the language?
4. Is the language easy to understand for people who don’t know it?
5. Do they use that language at the company?

TimeComplexity

Expected time complexity to perform the operation on the data limit N within the time limit of 1 to 10 seconds is as follows.

Time complexity of Python built-in Functions

list

append vs insert vs extend more

• If we want to add an element at the end of a list, we should use append. It is faster and direct.

• If we want to add an element somewhere within a list, we should use insert. It is the only option for this.

• If we want to combine the elements of another iterable to our list, then we should use extend.

• Dictionary.pop(i) takes O(1)

collections.deque

set

Dictionary

more: python wiki-Time complexity , UCI- Complexity of Python Operations

Sorting

Quick Sort

# space complexity in worst case: O(N)
def quickSort(self, nums: List[int]) -> List[int]:
    if len(nums) < 2: return nums
    pivot = nums[-1]
    lower = [ x for x in nums if x < pivot ]
    same = [ x for x in nums if x == pivot ]
    higher = [ x for x in nums if x > pivot ]
    return self.quickSort(lower)+ same + self.quickSort(higher)

const quickSort = (nums) => {
    if (nums.length < 2) {
        return nums
    }
    const pivot = nums[0]
    const less = nums.filter(x => x < pivot)
    const greater = nums.filter(x => x > pivot)
    const same = nums.filter(x => x === pivot)
    return [...quickSort(less), ...same, ...quickSort(greater)]
}

Merge Sort

def mergeSort(self, nums: List[int]) -> List[int]:
    if len(nums) < 2: return nums
    mid = len(nums) // 2
    a, b = self.mergeSort(nums[:mid]), self.mergeSort(nums[mid:])
    i, j, res = 0, 0, []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            res.append(a[i])
            i += 1
        else:
            res.append(b[j])
            j += 1
    res = res + a[i:] if i < len(a) else res
    res = res + b[j:] if j < len(b) else res
    return res

const mergeSort = (nums) => {
    if (nums.length < 2) {
        return nums
    }
    const mid = Math.floor(nums.length/2)
    const [a, b] = [mergeSort(nums.slice(0, mid)), mergeSort(nums.slice(mid))]
    const sortedNums = []
    let i = 0, j = 0
    while (i < a.length && j < b.length) {
        sortedNums.push(a[i] < b[j] ? a[i++] : b[j++])
    }
    while (i < a.length) {
        sortedNums.push(a[i++])
    }
    while (j < b.length) {
        sortedNums.push(b[j++])
    }
    return sortedNums
}

Bubble Sort

def bubbleSort(self, nums: List[int]) -> List[int]:
        N = len(nums) - 1
        for i in range(N):
            for j in range(N - i):
                if nums[j] > nums[j + 1]:
                    nums[j + 1], nums[j] = nums[j], nums[j + 1]
        return nums

Insertion Sort

def insertionSort(self, nums: List[int]) -> List[int]:
    for i in range(1, len(nums)):
        curr = i
        for j in reversed(range(i)):
            if nums[j] <= nums[curr]:
                break
            nums[j], nums[curr] = nums[curr], nums[j]
            curr -= 1
    return nums

Selection Sort

def selectionSort(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            m = i
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[m]:
                    m = j
            nums[m], nums[i] = nums[i], nums[m]
        return nums

Counting Sort

• condition: we have to know the range of the sorted values.
  1. Count the number of each unique elements in the array.
  2. Iterate through the array of counters in increasing order.

def countingSort(A: List[int],k: int) -> : List[int]:
    # A is consisted with integers range 0 to k
    n = len(A)
    # We need additional memory O(k)
    count = [0] * (k+1)
    for i in range(n):
        count[A[i]] += 1
    inx = 0
    for i in range(k+1):
        for j in range(count[i]): # smaller than O(A)
            A[inx] = i
            inx += 1
    return A