Sharpening my programming skills

This is a collection of small (< 1h) Python challenges to keep your Python skills sharp.

Challenges

The challenges are explained in detail in the comments of the corresponding Python files.

Arrays

• zero_matrix.py: Zero entire column and row in 2D matrix if element is 0.
• merge_overlapping_intervals.py: Merge overlapping intervals in array together.
• rotate_matrix.py: Rotate 2D matrix 90 degrees.
• spiral_order.py: Return a 2D matrix in spiral order.
• temp_tracker.py: Temperature tracker to calculate mean, mode, min, max of temperature events.
• max_consecutive_gap.py: Find max consecutive gap of sorted form of unsorted numbers.
• find_permutation.py: Find first permutation based on two conditions.
• pascal_triangle.py: Generate the first n rows of the Pascal's triangle.
• wave_array.py: Sort array in a wave-like pattern.
• sorted_array_intersection.py: Find elements that occur in both of the two sorted arrays.
• rearrange_array.py: Rearrange array so that the values become the indizes.
• min_steps_infinite_grid.py: Cover given points in 2D grid in minimum steps.
• max_subarray.py: Calculate the max sum of a subarray.
• array_duplicate.py: Find the first duplicate in an array of integers.

Math

• palindrome_integer.py: Check if integer is palindrome without converting it to text.
• excel_column_number.py: Return column number based on Excel encoded column title.
• factorial_trailing_zeros.py: Count trailing zeros in factorial (n!).
• greatest_common_divisor.py: Greatest common divisor of two numbers.
• two_egg_problem.py: Solve the Two Egg Problem

Strings

• palindrome_string.py: Check if sentence is a palindrome.
• needle_haystack.py: Find substring in a string (without fancy KMP or Boyer-Moore).
• zigzag_string.py: Print text in a zigzag pattern to the screen.
• compare_version_numbers.py: Compare version strings like v1.1 and v1.2.
• longest_palindromic_substring.py: Find longest palindrome substring.
• roman_to_integer.py: Calculate integer from roman literals.
• integer_to_roman.py: Create roman literal from integer.
• length_last_word.py: Calculate length of last word in sentence.
• longest_common_prefix.py: Find longest common prefix in all strings.
• reverse_string_inplace.py: Reverse string or array in place.
• string_multiplication.py: Multiply two numbers represented as strings without big integer libraries.

Bit Manipulation

• bit_single_number.py: Find single number in array of pairs.
• power_of_2.py: Check if number is power of 2.

Two Pointers

• diffk.py: Find two values in sorted array with a difference of k.
• container_most_water.py: Based on vertical lines on a x-axis find the lines having the largest area.
• rectangle_intersection.py: Find intersection of two rectangles.

Binary Search

• binary_matrix_search.py: Test for existence of element in matrix using binary search.
• rotated_sorted_array_search.py: A sorted array is rotated at one place ⁉️.
• sqrt.py: Calculate square root using binary search.
• sorted_insert_position.py: Return found index of element or index where to insert it.
• search_range.py: Find range (start and end index) of a value in a sorted list.
• binary_occurrence_search.py: Count number of occurences of target value in sorted list.
• power.py: Implement pow(x, n) % d.

Stack

• generate_parentheses.py: Validate parentheses
• min_stack.py: Create a min stack preserving order of elements
• nearest_smallest_element.py: Find nearest element in array
• simplify_directory_path.py: Simplify UNIX path
• evaluate_expression.py: Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Linked Lists

• interesection_linked_list.py: Find intersection of two linked lists
• swap_list_nodes_in_pairs.py: Swap nodes in linked list in pairs
• merge_sorted_lists.py: Merge sorted linked lists
• partition_list.py: Partition linked list at pivot
• add_two_numbers_list.py: Add to numbers as linked lists
• list_cycle.py: Detect cycle in linked list
• reverse_linked_list.py: Reverse linked list
• reverse_linked_list_partial.py: Reverse linked list but only up to a certain node count.

Backtracking / Recursion

• modular_exponentiation.py: Modular exponentiation is a type of exponentiation performed over a modulus.
• permutations.py: Generate all permutations in a list
• unique_permutations.py: Calculate unique permutations
• letter_phone.py: Generate all possible digits on letter phone
• gen_parens.py: Given n pairs of parentheses generate all combinations of well formed parentheses.
• combinations.py: Given n numbers generate all possible k combinations

Hashing

• two_sum.py: Given an array of integers, find two numbers such that they add up to a specific target number
• points_on_straight_line.py: Given n points on 2D pane calculate max number of points on one straight line
• longest_substring_no_repeat.py: Calculate longest substring with unique characters

Maps

• anagrams.py: Given list of words return all words that are anagram of a given string.
• distinct_numbers_in_window.py: Given list of integers return the distinct numbers in window of size k.
• majority_element.py: Given an array find the majority element

Trees

• identical_binary_tree.py: Compare two binary trees
• inorder_traversal.py: Binary tree inorder traversal
• postorder_traversal.py: Binary tree postorder traversal
• preorder_traversal.py: Binary tree preorder traversal
• sorted_array_balanced_bst.py: Turn sorted array into balanced BST
• invert_binary_tree.py: Invert binary tree
• path_sum.py: Compare path sum of leaf nodes
• flatten_binary_tree_linked_list.py: Flatten a binary tree into a right sided linked list
• balanced_binary_tree.py: Check if a tree is balanced
• kth_smallest_tree_elem.py: Find the kth smallest element in a binary search tree
• valid_bst.py: Check if binary tree is valid BST
• zigzag_level_bst_traversal.py: Traverse BST in zig ziag level order
• max_tree_depth.py: Longest path to leaf
• min_tree_depth.py: Shortest path to leaf
• sum_root_leaf_numbers.py: Sum all root-to-leaf paths (node values are digits)
• merge_k_sorted_lists.py: Merge k sorted lists into one
• count_inversions.py: Count the number of inversions in an array.
• symmetric_binary_tree.py: Check if two binary trees are symmetric.
• least_common_ancestor.py: Find the least common ancestor of two values in an unordered binary tree.
• shortest_unique_prefix.py: Find the shortest unique prefix for each word in a set of words.
• order_people_heights.py: Order people with unique heights by the constraint how many taller people are standing in front of them.

Graphs

• level_order.py: Traverse tree in level order (BFS)
• black_shapes.py: Given a board of black and white fields find the number of black connected shapes

Greedy

• trading_stock.py: Figure out max profit given the stock prices of yesterday.
• bulbs.py: Given wrong wired light bulbs find the min number of switches to press to turn on all the bulbs.
• mice_holes.py: Given M mice and N holes on a straight line find min number of moves to assign all mice to the holes.