Optimizing Performance with HashSets in Python

Introduction

Greetings, programming enthusiast! In this unit, we're embarking on a thrilling numerical quest, where unidentified bridges connect the islands of data. On these bridges, we'll see hashes and bins, all converging into sets! Throughout our journey, we'll utilize the fundamental concepts of Python's built-in data type, the set, to formulate an optimal solution. So, fasten your seatbelt and get ready to solve problems!

Task Statement

The task for this unit is to devise a Python function that accepts two lists containing unique integers and returns another list containing the elements common to both input lists. This task provides an intriguing perspective on deriving similarities between two data sequences, a scenario commonly encountered in data comparisons and analytics. For illustration, suppose we're given two lists: Python list1 = [1, 2, 3, 5, 8, 13, 21, 34] list2 = [2, 3, 5, 7, 13, 21, 31] The common_elements(list1, list2) function should comb through these arrays of integers and extract the common elements between them. The expected outcome in this case should be: Python [2, 3, 5, 13, 21]

Brute Force Solution and Complexity Analysis

O(n*m)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Additional Set Methods

The set data type in Python is not only efficient but also provides a plethora of useful methods for performing various operations. Let's explore some of these operations (the average time complexity is also provided):

Union (|): The union is a method or operation that combines all unique elements from two sets. Essentially, the resultant set will contain all elements present in both the sets. The | operator or the union() function can be used to perform this operation. Time complexity - O(len(set1)+len(set2)).

Python

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
union_set = set1 | set2
print(union_set)  # prints: {1, 2, 3, 4, 5, 6}

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
union_set = set1 | set2
print(union_set)  # prints: {1, 2, 3, 4, 5, 6}

Difference (-): The difference operation removes the elements present in the second set from the first set. The - operator or the difference() function performs this operation. Time complexity - O(len(set1)).

Python

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
diff_set = set1 - set2
print(diff_set)  # prints: {1, 2}

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
diff_set = set1 - set2
print(diff_set)  # prints: {1, 2}

Symmetric Difference (^): It returns a set containing elements which are in either of the sets but not in both. In other words, it outputs elements that only reside in one of the sets. The ^ operator or the symmetric_difference() function executes this operation. Time complexity - O(len(set1) + len(set2)).

Python

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
sym_diff_set = set1 ^ set2
print(sym_diff_set)  # prints: {1, 2, 5, 6}

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
sym_diff_set = set1 ^ set2
print(sym_diff_set)  # prints: {1, 2, 5, 6}

Subset (<=): This operation checks if the first set is a subset of the second set. It returns True if all elements of the first set are present in the second set, otherwise False. The <= operator or the issubset() function achieves this. Time complexity - O(len(set1)).

Python

set1 = {1, 2, 3}
set2 = {1, 2, 3, 4, 5}
print(set1 <= set2)  # prints: True

set1 = {1, 2, 3}
set2 = {1, 2, 3, 4, 5}
print(set1 <= set2)  # prints: True

Knowing these operations will allow you to use Python sets to their full potential and help you devise efficient solutions for a variety of problems.

Introduction

Task Statement

Brute Force Solution and Complexity Analysis

Join the 1M+ learners on CodeSignal

Introduction to Set Solution

Solution Building: Step 1

Solution Building: Step 2

Solution Building: Step 3

Additional Set Methods

The Power of `in` with Sets

Lesson Summary