Arrays and Hashing

What is an array?

A data structure that is a collection of items of the same variable type that are stored at contiguous memory locations.

What is hashing?

A technique where data is mapped to a specific hash table index using a hash function for ease of access. Inserting, deleting and searching all have a time complexity of O(1).

What data structure is contains duplicate associated

to?

Arrays and Hashing

How should you answer contains duplicate?

class Solution:

def containsDuplicate(self, nums) -> bool:

seen = set()

for num in nums:

if num in seen:

return True

seen.add(num)

return False

Why are sets beneficial?

Checking a set has O(1) time complexity

What are the 2 main data structures in python context?

Linear and hash-based structures

What is the linear data structure?

Arrays

What are some features of an array?

Searching is O(n) we have to go one by one, but accessing by an index is O(1)

What are some hash-based structures?

Hash tables which use arrays + hash functions

What are sets?

Store unique values, with no order O(1) complexity

What are dictionary features?

Has a O(1) time complexity and based on key value pairs