Practice for FAANG coding interviews.
Description for recursive_staircase.ipynb:
Apparently, this is a common question in coding interviews of FAANG companies.
Problem description and more at https://www.youtube.com/watch?v=5o-kdjv7FD0.
Description for ben_award_1.ipynb:
Following along and solving the problems in this video https://www.youtube.com/watch?v=_Q6TTdIEAvQ&t=654s.
Description for count_rectangles.ipynb:
Finding a solution for the coding interview problem in https://www.youtube.com/watch?v=EuPSibuIKIg&list=WL&index=2&t=0s.
It runs at a terrible time complexity. But given the interview's time limit, it is acceptable.
Description for num_ways_to_decode_message.ipynb:
Coding a solution to the problem described in https://www.youtube.com/watch?v=qli-JCrSwuk&list=WL&index=2&t=0s.
Description for longest_non_repeating_substring_lenght.ipynb:
Coding two approaches (slow, fast) for finding the longest substring without repetition.
Description for longest_palindromic_substring.ipynb:
A sliding-window approach to finding th longest palindromic substring in a given string. A recursive approach is also possible.
Description for balanced_parentheses.ipynb:
Checking that the parentheses in a given string are balanced. Every opening bracket must have a corresponding closing bracket. Solution uses stack data structure.
Description for Sorting_list_with_unique_numbers.ipynb:
Given a list of numbers with only 3 unique numbers (1, 2, 3), sort the list in O(n) time. A genralization for m unique numbers, which m<n, is also implemented.
Description for two_sums.ipynb:
Given a list of numbers, and a target number k, return whether or not there are two numbers in the list that add up to k. Three approaches were implemented. The first checks every pair to find a match, which runs in O(n^2) time. The second method also runs in O(n^2) time. The third method uses to pointers to find a match and runs in a linear time.
Description for find_Pythagorean_triplets.ipynb:
Given a list of numbers, find if there exists a pythagorean triplet in that list. The implemented method uses a meet-in-the-middle technique on the sorted list which runs in O(n) + O(nlogn) + n*O(n) = O(n^2) time (for squre, sort, and find).
Description for minimum_size_subarray_sum.ipynb:
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum โฅ s. If there isn't one, return 0 instead. The implemented method uses a sliding-window approach.
Description for random_pick_range_list.ipynb:
Given a list of ranges (all integer), return a random number that is present in one of the ranges. Every number must have the same selection probability. It is assumed that the ranges don't overlap. The problem is described in https://www.youtube.com/watch?v=1R2Ju_zgPfE&ab_channel=KeepOnCoding.