data structures : lists, sets & maps

strings are…

• Ordered (you can look up an element using its index)

• immutable (you can’t add, remove, or update characters)

what is a string

A string is an immutable sequence of characters.

If the length of the string is n, what is the big-O time complexity of “adding” a single exclamation point to the end of a string?

O(n)

If the number of times you want to repeat a letter is n, what is the big-O time complexity of building a string of length n using concatenation?

O(n²)

time complexity of the operation index?

fruit[0]

O(1)

time complexity for operation length?

len(fruit)

O(1)

time complexity for operation slice?

fruit[4: ]

O(k)

time complexity for operation concatenate ?

fruit = ‘pine’ + ‘apple’

O(m+n)

lists are…

• Ordered (you can look up an element using its index)

• Mutable (you can add, remove, or update elements)

what is the worst case?

O(n)

what is the worst case?

O(n)

What is the worst time complexity case for these searches?

O(n)

What do you think the time complexity of TimSort is?

O(n)

What sorting algorithm do you think the built-in python sort functions use?

Timsort

What search algorithm do you think these functions use - linear search or binary search?

Linear search, since there’s no guarantee that the list is sorted.

What is a stack?

a data structure that uses the principle of “Last In First Out” - the last item to get added to the is the first item that will get removed.

What can you use in python if you ever need a stack?

append or pop

what is a queue?

is a data structure that uses the principle of “First In First Out” - the first item to get added to the is the first item that will get removed.

What can you use if you ever need a queue?

A python deque

append O(1)

popleft O(1)

Which one is more optimal?

the second one

What are sets

stores unique values in no particular order.

sets are……

• Unordered: Elements are unordered, so they are not indexable.

• Mutable: can be modified by adding or removing elements.

• is unique  - there are no duplicates.

What are set operations time complexity avg case

O(1)

union

A | B

intersection

A & B

difference

A - B

symmetric difference

A ^ B

dictionaries in python are…

a collection of key-value pairs.

key points are

• Unordered: The order of elements in a dictionary is not guaranteed.

• Mutable: You can add, remove, or modify elements in a dictionary.

• must be unique: can only appear once in a dictionary.

• can be of any immutable data type: 

what are common key types

strings, numbers, and tuples.

what can values be?

strings, numbers, lists, dictionaries, or any other Python object.

dictionary operations average time case are?

O(1)

what is a hash function

takes as input any piece of data and returns as output an integer value in a given range.

Why do sets and dictionaries have O(1) operations?

Since accessing and overwriting an item at a particular index of a list is O(1), set and dictionary operations are also O(1). 

What are the key properties of a good hash function

• The same input always produces the same output. This is crucial for lookups.  

• should distribute inputs evenly across the output range to minimize collisions

• Calculating the value should be fast.

what data types can be used as keys in a dictinoary?

immutable objects or user-defined objects such as strings, numbers, booleans, etc.

what data types can not be used as keys in a dictionary?

lists, dictionaries, sets

is this a good key?

yes

is this a good key?

no

is this a good key?

yes

is this a good key?

no