July 22, 2025 - Daily Drill¶
🎯 Daily Goals¶
- Review Anki Deck
- Lumosity training
- Leetcode
- Developing laplace
📝 What I learned:¶
Leetcode problem¶
1249. Minimum Remove to Make Valid Parentheses
Thinking Process¶
First, we need to think of how a string is considered valid. If you have solved valid parenthesis problem before. You would remember we use a left counter to keep track of how many left parenthese there are in the current string prefix. If any string prefix has the invariant where left count is always greater or equal to zero, then we are half way to a valid string. We only need to check if the left coutner is zero when we reach the end of the string. In other word, to make a string valid, we need to get rid of any ")" that makes the left counter smaller than zero. This process would get rid of any ")" that is extra. What about the "("? We can do another pass in the reverse direction and keep a right counter for the ")" paranthesis. After two passes we can finally get a valid string with minimal removal.
Implementation¶
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
ret = list(s)
left_cnt = 0
for idx, c in enumerate(s):
if c == "(":
left_cnt += 1
elif c == ")":
if left_cnt == 0:
ret[idx] = ""
continue
left_cnt -= 1
right_cnt = 0
for idx in range(len(ret) - 1, -1 ,-1):
c = ret[idx]
if c == ")":
right_cnt += 1
elif c == "(":
if right_cnt == 0:
ret[idx] = ""
continue
right_cnt -= 1
return "".join(ret)
Key Takeaways¶
- how to check if a string is valid
- use inplace modification for O(1) space
- understand what does the left and right counter really represent
Complexity Analysis¶
Denote the length of the string as n
Time Complexity: O(n) Space Complexity: O(1)
314. Binary Tree Vertical Order Traversal
Thinking Process¶
My intuition is to create a perform a BFS on all the node and associate each node to a column list. There should be a container wrapper on this column list object where it knows what is its previous column list at and the next column list at. Since we need to further travese the node.left and node.right. Naturally, I think of a doubly linked list. By putting a list as a value in a doubly linked node, it can easily traverse forward and backward. One last problem is that how to keep track of the head of the doubly linked list. The candidate of the head of the linked list is always created when certain link node does not have a prev node and yet we need to traverse left. Whenever that happens we mark the node as the head. Here is my initial implementation.
Implementation¶
from collections import deque
class LinkNode:
def __init__(self, lst=None, prev=None, next=None):
self.lst = lst if lst else []
self.prev = prev
self.next = next
class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
dummy_head = LinkNode()
cur_node = LinkNode()
dummy_head.next = cur_node
queue = deque([(root, cur_node)])
while queue:
node, link_node = queue.popleft()
link_node.lst.append(node.val)
if node.left:
if not link_node.prev:
link_node.prev = LinkNode(next=link_node)
dummy_head.next = link_node.prev
queue.append((node.left, link_node.prev))
if node.right:
if not link_node.next:
link_node.next = LinkNode(prev=link_node)
queue.append((node.right, link_node.next))
ret = []
cur = dummy_head.next
while cur:
ret.append(cur.lst)
cur = cur.next
return ret
In hindsight, we can also use a defaultdict(list) to achieve the same effect. We can simply let the root node's column list to be list 0 and decrease the index when we traverse left and increase when traversing right. Also, keep track of the smallest index, since we need it when returning.
Complexity Analysis¶
Denote the number of all nodes as n
Time Complexity: O(n) Space Complexity: O(n)
Since we traverse through all node once using BFS and create a replication of all node values in the column lists.
Lanchain¶
What are langchain's main functionality:
- API encapsulation
- Structuring LLM output
- Tool incorporation
- Memory Management
- RAG, Agent Development
- Server and API release
Chain¶
Definition
A chain is an abstraction that defines a sequence of steps to process input and generate output using one or more language models
Basic Example
from langchain_core.output_parsers import StrOutputParser
from langchain.chat_models import init_chat_model
model = init_chat_model("gpt-4o-mini", model_provider="openai")
basic_qa_chain = model | StrOutputParser()
question = "introduce yourself"
result = basic_qa_chain.invoke(question)
Use the | pipeline symbol for chaining steps
The classic one would also involve predefined prompt
from langchain_core.output_parsers import StrOutputParser
from langchain.chat_models import init_chat_model
from langchain.prompts import ChatPromptTemplate
model = init_chat_model("gpt-4o-mini", model_provider="openai")
prompt_template = ChatPromptTemplate([
("system", "you are a helpful asssitant, please answer based on users' questions),
("user", "This is user's question: {topic}, please answer with 'yes' or 'no')
])
bool_qa_chain = prompt_template | model | StrOutputParser()
question = "introduce yourself"
result = bool_qa_chain.invoke(question)
There are quite a lot of different output parser available for langchain. However, as more and more models supports function calling these parsing steps are done automatically by the function calling tools.
Prompt Templates¶
Prompt templates takes in a dictionary where each key represents a variable in the prompt template to fill in and then returns a PromptValue object which is passed down into the LLM or ChatModel downstream. PromptValue can be useful to switch between Message type and the str.
To create a PromptTemplate