Personalized Cheat Sheet

• Big-O
• Interview checklist
• Python
  • Time and space complexity
    • Time
    • Space
      • Making an actual copy as opposed to a reference
      • Sorting in Python
      • Bits required to represent an integer k
• System design interview template (for AI chatbot)
• Templates

Big-O

Interview checklist

Python

Time and space complexity

Time

Space

Making an actual copy as opposed to a reference

What is the space complexity of the following code?

def repeated_str(s):
    strs = []
    for i in range(len(s)):
        strs.append(s)

On the surface, it may seem like the space complexity would be $O(n^2)$, where $n$ is the length of the string s. But this is not correct because there is a difference between copying a variable and just referencing it. In Python, strs.append(s) just appends a reference of s, which takes just $O(1)$ space. Hence, $n$ references are made to the same object, which takes $O(n)$ space, not $O(n^2)$.

Of course, it's not the same across all programming languages. For the "primary" interviewing programming languages, we have the following:

Language	COPY of a string s	Making a REFERENCE of a string s
Python	s2 = s[:]	s2 = s
C/C++	s2 = s;	s2 = &s;
Go	s2 = s	s2 = s[:]
JavaScript	s2 = s.splice()	s2 = s

Sorting in Python

Python uses Timsort under the hood in its default sort method, meaning it has a worst-case space complexity of $O(n)$ even though it does the sorting in-place.

Bits required to represent an integer k

With 1 bit we can represent two values. With 2 bits we can represent four values. And so on. There's a repeated doubling pattern in terms of the number of values that can be represented. The range doubles for each additional bit, which means a number $k$ has $\log_{10}(k) = O(\log_{10} k)$ digits, which equates to $O(\lg k)$.

System design interview template (for AI chatbot)

AI chatbot prompt for practicing a system design round

As a senior/staff engineer, you are conducting a system design interview.

Your task is to guide the candidate through a popular system design question in a step-by-step manner.

Follow the structure below for the interview:

1. Question Selection: Choose a popular system design question to ask.
2. Requirements: Discuss both functional and non-functional requirements.
3. High-Level Design: Guide the candidate to create a high-level design.
4. Detailed Design: Go into more detailed components such as data flows, APls, storage, etc.
5. Scaling Considerations: Address scalability and performance optimization.
6. Conclusion: Summarize the design and provide feedback or suggestions for improvement.

Please start by selecting a popular system design question to ask.

Templates