Skip to content

Programming

2024-02-27

Problems

  • Interleaving strings

Topics

  • 3 dimensional DP

2024-02-26

Problems

  • Interleaving strings

Topics

  • Dynamic Programming (TopCoder tutorial)
  • Backtracking

Notes

  • For the interleaving strings problem, I tried a backtracking approach that is correct but it is not optimal. I am getting time limit exceed.

2024-02-25

Problems

  • Coin Change
  • Longest Palindromic sub sequence

Topics

  • Dynamic Programming
    • One dimensional (coin change)
    • Two dimensional (longest subsequence)

Notes

Coin Change

  • The greedy algorithm does not work in this case. For example:

coins=[2,10,11] amount=34

If I use 3 coins of value 11, I am not able to recover the amount.

Idea A

A(v,k) := Minimum amount of coins using the first k coins that sums up to v

A(0,k) = 0

A(v,k) = min_(i,a) A(v-ac,k-i) + a , where a >0, 0 < i < k, and ac <= v

Abandoned because 0 < v < 10^4. It is too memory expensive.

Idea B

A(k) := Minimum amount of coins that amounts to V using the first k coins.

Palindromic subsequence

  • First point is to realize that an optimal subsequence contains optimal subsequences.
  • Second point is to realize that palindromes are symetric from its center.
  • Therefore, we should construct the palindromes from its center. If the extreme characters are equal, they are going to enlarge the optimal palindrome.
  • Palindromes of even length are handled gracefully by initializing P(i,j) = 0 for j < i.
  • Therefore, the update rule is: 
    P(i,j) = 0 if j < i
P(i,i) = 1
P(i,j) = P(i+1,j-1) + 2             if s[i]==s[j]
         max(P(i+1,j),P(i,j-1))     otherwise

2024-02-24

Problems

  • Word Ladder
  • House Robber

Topics

  • Dijkstra and BFS for shortest path.
  • Min Heap
  • Dynamic Programming

2024-02-21

Problems

  • Kth largest element in array (I didn't get why it is in medium. It is a super easy problem)
  • Serialize and Deserialize a binary tree

Topics

  • Pre-Order; In-Order; Pos-Order traversals.
  • Visit and Explore.
  • Easy recursive solution.
  • Visit and Explore stacks if not using recursion.

Notes

  • I should probably redo these problems later.

Notes

For the BT serialization problem I used an event approach: - Start - End - Left - Right

2024-02-20

Notes

  • In Topological Sort, start visiting the graphs by its source (0 in degree). At each new node, a new source must appear if the graph has no cycle.

Problems

  • Clone Graph
  • Course schedule

Topics

  • DFS (using stack and not recursion)
  • Graphs (adjacency lists)
  • Topological Sort.
  • Heaps in python.

Resources

2024-02-18

Notes

  • Start by creating test cases if those do not exist already. Perhaps add more test cases.
  • In my 3Sum solution I used a Hash. Still was exceeding the running time, but the complexity was the best possible for the problem (O(n^2))
  • There is a solution involving array sorting and sliding windows (managing a left and right pointer). This solution uses less space.

Topics

  • Mutable types in Python: Types that allow modification of its items (in-place): list, sets, dictionaries.
  • Immutable types: tuple, strings.
  • Pass by assignment: Think every python object is a pointer. Argument e passed to a function is a pointer. If we access a member of the object, we are editing the object the pointer points to. If we reassign the object, then we are making the pointer to point to a different object (address).

References

  • Neet code playlist on strings. Neetcode
  • Grooking the code interview (patterns). Educative

Problem

  • Longest substring non-repeated characters (sliding window)
  • ThreeSum. (Hash, sliding window)

2024-02-17

Topics

Important

Use builtin id to get the address of a Python object.

Problems

  • Two Sum.
  • Merge two sorted linked lists.
  • Valid anagram.