Skip to content

Latest commit

 

History

History
111 lines (77 loc) · 4.83 KB

extra-01-algorithm-and-data-structure.en.md

File metadata and controls

111 lines (77 loc) · 4.83 KB
Raw

Extra1: Algorithms and Data Structures

In Extra1, after learning about basic algorithms and data structures, you will practice using problems from LeetCode. It is recommended to solve the problems before looking at the explanations.

Textbooks

📖 Reference

🔰 Point

  • First, look up the following terms and be able to explain what they are.
    • Time complexity and space complexity
    • Big O notation
    • Associative arrays
  • Study the following basic algorithms on Udemy or other platforms and be able to explain them.
    • What is binary search? Explain why the time complexity of binary search is $O(\log n)$.
    • Explain the difference between LinkedList and Array.
    • Explain the hash table and estimate the time complexity.
    • Explain graph search algorithms and explain the difference between BFS (Breadth First Search) and DFS (Depth First Search).

Exercises

Word Pattern

Given a pattern p consisting of lowercase English letters and a string s separated by spaces, determine if s follows the pattern p. For example, if p = "abba" and s = "dog cat cat dog", then s follows the pattern p, but if p="abba" and s="dog cat cat fish", then s does not follow p.

🔰 Checkpoint

Step1: Think about how to split the string s by spaces.

Hint
  • In each language, there should be standard libraries or functions provided for string manipulation.
  • Use web search or ChatGPT, searching for "split string by spaces" or similar queries.

Step2: Consider how to manage which part of s corresponds to each character of the pattern p.

Hint
  • For example, in Example 1, the words in s corresponding to each character of p are a => dog, b => cat.
  • To manage such correspondences, using a dictionary or hash table would be beneficial.
  • For instance, in Python, you can manage the words in s that correspond to each character of p using a dict.
  • Also use web search or ChatGPT, looking up "Python dictionary" or similar queries.

Find All Numbers Disappeared in an Array

Given an array of n integers where each value is in the range [1, n], return all integers in the range [1, n] that do not appear in the array.

🔰 Checkpoint

Step1: Solve with O(n^2)-time and O(1)-space

Hint
  • You can solve it using a simple double loop, achieving O(n^2)-time and O(1)-space.

Step2: Solve with O(n)-time and O(n)-space

Hint
  • By preparing an array to record whether an element has appeared in the array nums, you can solve it in O(n)-time and O(n)-space.

Advanced: Solve with O(n)-time and O(1)-space (bonus)

Is it possible to solve it in O(1)-space, excluding the input and return?

Hint
  • Upon deeper consideration, it is possible to solve it in O(n)-time and O(1)-space.
  • This will be covered in the explanation, so give it a try.

Intersection of Two Linked Lists

Given two singly linked lists, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

🔰 Checkpoint

Step1: Solve with O(n)-time and O(n)-space

Hint
  • By using a Hash Table to record nodes, you can solve it in O(n)-time and O(n)-space.

Step2: Solve with O(n)-time and O(1)-space

Is it possible to solve it in O(1)-space, excluding the input and return?

Hint
  • By comparing the lengths of the two lists and adjusting the longer list to match the length of the shorter one, you can solve it in O(n)-time and O(1)-space.
  • This will be covered in the explanation.

Advanced: Solve using two pointers (bonus)

Hint
  • Start a pointer at the tail of one list and proceed to the head, reducing the problem to Floyd's Linked List Cycle Finding Algorithm.

Koko Eating Bananas (optional)

Non-overlapping Intervals (optional)

Longest Substring Without Repeating Characters (optional)