Skip to content

Latest commit

 

History

History
85 lines (56 loc) · 3.92 KB

PROBLEMS.md

File metadata and controls

85 lines (56 loc) · 3.92 KB

Coding Problems

All problems are enumerated from zero and formatted as [algo-xx]. Difficulty of each problem is annotated in the title as [easy|medium|hard]

[algo-00] Most frequently occurring item in array [easy]

Given an array, find the most frequent element in it. If there are multiple elements that appear a maximum number of times, print any one of them. E.g. [1,2,1,3,1] -> 1

Input: arr int[], n int Output: int

Solution

  • Use a hash map to keep track of occurrences for each item
  • keep track of the item with most occurrences

Time Complexity: O(n) -> We need to check the whole array Auxiliary space: O(n) -> It's possible that the array has all unique numbers

[algo-01] Minesweeper Game [medium]

Problem description can be found at leetcode

Solution

  • First check if the cell at the click is a mine.
  • If click position is not a mine, perform DFS from the click position, searching for empty cells "E"
  • If there is a mine in the surroundings of the cell i.e. 1 cell in all 8 directions, stop DFS and set the sell with the number of mines found. If there are no mines, mark the cell with "B" and continue DFS

Time Complexity: O(m * n) -> Worst case we will visit every cell Auxiliary space: O(m + n) -> Since we are doing DFS, at some point our que could contain all the items from the a cell's row and all the items from a the column.

[algo-02] Validate Binary Search Tree [medium]

Problem description can be found at leetcode

Solution

  • For each node we need to check if expectations are met for the value and the left and right subtree
  • All values on the left should be compared to a max value.
  • All values on the right should be compared to a min value.

NOTE: it can also be solved by traversing the tree in-order.

Time Complexity: O(n) -> We visit all nodes in the tree Auxiliary space: O(1) -> The extra space is constant

[algo-03] Longest Substring Without Repeating Characters [medium]

Problem description can be found at leetcode

Solution

  • The problem says that the input string can contain letters, numbers and symbols. This tell us that we cannot simply use an array[26] for the letters in [a-z]
  • When we are iterating the string we are performing 3 operations
    • Counting the amount of chars a substring has
    • Checking if we have seen a repetition
    • Updating the max count

E.g. 1 - "abcblkj", max = 0, Array[a-z] indexes where indexes[i] = -1; i in [a-z] 2 - When i = 3 we have: index[str[i]] = 1; max = 3; start = 0 -> start = index[str[i]] + 1 = 2; index[str[i]] = i = 3 2 - When i = len(str) -1 we have: max = 4; start = 2; indexes['j'] = -1

Time Complexity: O(n) -> We iterate the whole string Auxiliary space: O(1) -> The extra space is the number of characters in [a-z]

[algo-04] Minimim Path Sum [medium]

Problem description can be found at leetcode

Solution

This is a weighted vertice graph problem. A solution doing DFS would be valid but the runtime would be O(2^(n+m)). When calculating a minPath on a node, we know that: minCost[i][j] = matrix[i][j] + min(minCost[i-1][j], minCost[i][j-1]). So, for each node, the minPath at that point is the minimum between the path until the node on the top and the path until the node to the left. With that in mind, we can pre-fill our matrix of costs on the first row and first column. Steps:

  • Pre-fill first column and row
  • Iterate over the matrix and fill the rest of cells knowing that minCost[i][j] = matrix[i][j] + min(minCost[i-1][j], minCost[i][j-1]).

Time Complexity: O(m * n) -> We visit all the cells in the matrix Auxiliary space: O(m * n) -> We store the cost of all the cells