SI100B Midterm Revision Notes

1. Fast-Slow pointer

Definition(quoted fromhttps://www.educative.io/interview-prep/coding/introduction-to-fast-and-slow-pointers)

‘Similar to the two pointers pattern, the fast and slow pointers pattern uses two pointers to traverse an iterable data structure, but at different speeds, often to identify cycles or find a specific target. The speeds of the pointers can be adjusted according to the problem statement. The two pointers pattern focuses on comparing data values, whereas the fast and slow pointers method is typically used to analyze the structure or properties of the data.’

For example, if we have a list called nums ,and we want to implement a function that moves all 0 to the end of the list, we can think of two pointers.

• right:(the ‘Fast’ one) This pointer’s job is to scan the entire list.
• left:(the ‘Slow’ one) You can see this pointer as a mark, which keeps track of the position where the next non-zero element should be inserted.

So the entire code should be:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left,right=0,0
        while right < len(nums):
            if nums[right]!=0:
                nums[right],nums[left]=nums[left],nums[right]
                left+=1
            right+=1

2.Reminders when using join() and split() method

Note that the .split() and .join() are BOTH methods of STRING, when using .join(), the iterable object should be passed as a parameter!

DO NOT write a command likeres=list.join('')

CORRECT usage example:

Input:

ls = ('One','Two','Three')
x = ''.join(ls)
print(x)
y = 'One Two Three'.split()
print(y)

Output:

OneTwoThree
['One', 'Two', 'Three']

3. The sorted() function and .sort() method

BIG IDEA: sorted() is a built-in function in python, while sort() is a method of list.

Syntax

.sort()

list.sort(reverse=False, key=None) # Note that the parameter 'key' takes a function

Reminder: DO NOT pass this expression to any variable! If you want a new ordered list, use sorted() instead

sorted()

numbers = [5, 2, 9, 1]
print(sorted(numbers, reverse=True)) # Output: [9, 5, 2, 1]