Algorithms and solutions for coding interview questions

After earning my MSc in Mathematics, I started working on practical things. So I never had time to look at these algorithms questions that you are expected to know on coding interviews in software companies. I finally wanted to set aside some time to recall how to think about simple algorithms. I choose python as my language of choice.

Methodology

Every solution is another function in Solution class. When starting to solve problems, the goal is to solve them fast and dirty at the first iteration, and these will be functions that start with simple_ keyword. After validating the solution, I should iterate more to find a better or different implementation. This will force me to think more about problem and to obtain a better understanding.

Automatic stats generation in README

At first, I started manually inserting each solved problem in README, but it was cumbersome and impractical. Then I figured that I could write some script that would do, and this script would be run with Github actions every time I make a commit with new solution. To solve this, I needed to put some metadata for every solution and best approach is to add it in file so that file represents a problem and possible solution. I used python doc strings and put all the relevant metadata at the beginning of each file. This needed to be in a format that script would know how to parse. I choose YAML and after a string is extracted, parsing is done with the help of grey-matter. The script is done in Typescript and Solution interface is defined like this.

---
title: Roman to integer
number: 13
difficulty: easy
tags: ['Hash table','Math','String']
url: https://leetcode.com/problems/roman-to-integer/
solved: true
---

When you run the script, it scans for files in folders and subfolders, parses and collects the solution's metadata. It then processes this solution list for all relevant statistics, tags, and other info. We then take content from intro.md, and strings we created from this solution statistics and write this in the official README.md file. This script is located at ./src/run.ts, and this is the corresponding Github action configuration. It also makes new commit because README file is changed. .

name: write-stats
run-name: Writing stats in README
on: ['push']
jobs:
  run-script:
    runs-on: ubuntu-latest
    steps:
      - uses: actions/checkout@v3
        with:
          ref: ${{github.head_ref}}
      - uses: actions/setup-node@v3
        with:
          node-version: '14'
      - run: yarn
      - run: yarn start
      - uses: stefanzweifel/git-auto-commit-action@v4
        with:
          commit_message: Automatic commit - write stats to README

Problems solved

⚪ Easy: 13

🔵 Medium: 13

🔴 Hard: 2

Total: 28

Solutions

1. 🔵 Container With Most Master
2. ⚪ Best Time To Buy And Sell Stock
3. 🔵 Integer To Roman
4. ⚪ Single Number
5. ⚪ Roman To Integer
6. ⚪ Longest Common Prefix
7. 🔵 Two Sum II - Input Array Is Sorted
8. ⚪ Majority Element
9. ⚪ Two Sum
10. ⚪ Valid Parentheses
11. ⚪ Merge Two Sorted Lists
12. 🔵 Generate Parentheses
13. ⚪ Remove Duplicates From Sorted Array
14. 🔵 Add Two Numbers
15. 🔴 Longest Valid Parentheses
16. ⚪ Search Insert Position
17. 🔵 Longest Substring Without Repeating Characters
18. 🔵 Rotate Image
19. 🔵 Maximum Subarray
20. 🔵 Spiral Matrix
21. 🔵 Longest Palindromic Substring
22. 🔵 Search A 2D Matrix
23. 🔵 Subsets
24. ⚪ Palindrome Number
25. 🔵 Sort List
26. ⚪ Palindrome Linked List
27. 🔴 Merge K Sorted Lists
28. ⚪ Middle Of The Linked List

Tags by count

1. Array: 13
2. String: 8
3. Two Pointers: 6
4. Linked List: 6
5. Dynamic Programming: 5
6. Hash Table: 5
7. Math: 5
8. Binary Search: 3
9. Divide And Conquer: 3
10. Stack: 3
11. Recursion: 3
12. Matrix: 3
13. Bit Manipulation: 2
14. Sorting: 2
15. Backtracking: 2
16. Merge Sort: 2
17. Greedy: 1
18. Counting: 1
19. Sliding Window: 1
20. Simulation: 1
21. Divider And Conquer: 1
22. Heap (Priority Queue): 1