5

Cracking the Coding Interview (Subject) / algorithms (Lesson)

This lesson was created by Aglae.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• logarithms: - what is it? example with base 2, examlple with base 3 - what does log base two mean, why is it central in computer science? - what does the base mean? - example balanced binary tree (how many levels n = 9) - example split array in halves (how many times n = 8) - binary search (search how many times n = 8) what is it? Logarithm asks a question: log10100 = 10? example 1 - log24 = 2;     22 = 4- question asked: what power of 2 gives us the 4?   example 2 - log381 = 4;    34 = 81- question asked: what power of 3 gives us 81 log base 2: - log28 = 83- it means cutting in half: 8 -> 4 -> 2 -> 1  cut in half three times (power)- in computer science most of the time using log base 2- two is often left out what does the base mean?- it means in how many parts we are going to cut the number- e.g. log28 means cutting in half: 8 -> 4 -> 2 -> 1- e.g. log10100 means cutting in tenth: 100 -> 10 -> 1 (cutting 2 times: 102) binary tree (balanced)- tree with n = 9 nodes has at least 1 + floor(log9) levels- 1 + 3 (minus decimal) = 4 split array in halves- n = 8 split three times till reach 1 - log8 = 3- e.g. merge-sort binary-search- n = 8, sorted array- log8 = 3- max operations = 3 when number not in array
• greedy algorithms - definition - examples - pros (3) con (1) - when to use? (2) - knapsack and fractional knapsack problem definition:- make locally optimal solution at each stage with hope of finding global optimum examples:- take largest chunk first- give amount of money in minimum number of bills- fill knapsack pros:- simple- easy to implement- runs fast cons:- very few cases where it returns global optimum- eg traversing binary tree to get max sum of nodes making greedy choices when to use:- greedy choice property (optimal local choice leads to global optimum)- optimal substructure (optimal solution contains optimal solution of subproblems) use case examples:- fractional knapsack problem- Prim's minimum spanning tree fractional knapsack problem: a) knapsack problem: thief wants to take maxiumum value in knapsack- given is amount (m3/kg and value)- cannot be solved greedy, has to be done with dynamic programming- because greatest value per pond does not yield optimal solution b) fractional knapsack problem: objects can be devidedgreedy works here!
• Searching algorithms (How they work & runtime) - linear search - binary search linear search·      loop through list to find element ·      O(N) – worst case: element is not in list or at last position  binary search·      on sorted list ·      look at middle element ·      split array in half and look at middle element ·      O(log N)       worst case: element is not in list       takes log N because n is everytime split in half
• merge sort: - how it works - runtime - code how it works: -       split arrays recursively in half an merge them together -       array = [2, 5, 6, 1, 7, 3] -       recursive function which splits until [x] or [] (base case) and returns merged array runtime: -       worst case: O(n log n) -       log n: splitting in half -       n: merging code: def merge_sort(array):    if len(array) == 0 or len(array) == 1:        return array    else:        left_array, right_array = array[:len(array)//2], array[len(array)//2:]        sorted_left_array = merge_sort(left_array)        sorted_right_array = merge_sort(right_array)        return merge_sorted_arrays(sorted_left_array, sorted_right_array) def merge_sorted_arrays(left_array, right_array):    sorted_array = []    i_left, i_right = 0, 0    while i_left < len(left_array) and i_right < len(right_array):        current_left = left_array[i_left]        current_right = right_array[i_right]        if current_left < current_right:            sorted_array.append(current_left)            i_left += 1        elif current_right < current_left:            sorted_array.append(current_right)            i_right += 1        else:            sorted_array.append(current_left)            sorted_array.append(current_right)            i_left += 1            i_right += 1    if i_left < len(left_array):        sorted_array += left_array[i_left:]    elif i_right < len(right_array):        sorted_array += right_array[i_right:]    return sorted_array
• Quick Sort: - how it works - runtime (average, worst-case) - code how it works: -       select pivot element -       sort so that every element on left is smaller or equal to pivot, every element on right is bigger than pivot -       left and right pointer walk towards middle -       repeat on left and right side   runtime: -       average: O (n log n) o   pivot is roughly the median o   each element gets called n log n times (swaps) -       worstcase: n2 o   pivot is each time largest or smallest element   code: def quick_sort(array):     if not array or len(array) == 1:         return array     pivot = random.choice(array)     i_left = 0     i_right = len(array) - 1     while i_left < i_right:         left_element = array[i_left]         right_element = array[i_right]         if left_element > pivot:             if right_element <= pivot:                 array[i_left], array[i_right] = right_element, left_element                 i_left += 1                 i_right -= 1             else:                 i_right -= 1         elif right_element <= pivot:             i_left += 1         else:             i_left += 1             i_right -= 1     if array[i_left] <= pivot:         i_left += 1     return quick_sort(array[:i_left]) + quick_sort(array[i_left:]) 

back  |  next 1 / 1