Set data structure

/
fundamentals

This tutorial is a part of the Data Structures and Algorithms class:

Set data structure:

  • inspired by Set from Math.
  • non-ordered elements.
  • distinct, no duplicate elements.
  • usually used to check if an element is within the Set (O(1)).

set

How data looks like (print it out!)

lecture-5/set-data-structure.js
// initialize
const setA = new Set([1, 2, 'a', 'b'])
const setB = new Set([2, 3, 'b', 'c'])

// print out, see how data looks like
console.log(setA) // Set { 1, 2, 'a', 'b' }
console.log(setB) // Set { 2, 3, 'b', 'c' }
$ node set-data-structure.js
Set { 1, 2, 'a', 'b' }
Set { 2, 3, 'b', 'c' }

Implement functions to find union and intersection set

lecture-5/set-data-structure.js
// function takes in 2 sets and return their union set
function union(setA, setB) {
  let _union = new Set(setA)
  for (let elem of setB) {
      _union.add(elem)
  }
  return _union
}

// function takes in 2 sets and return their intersection set
function intersection(setA, setB) {
  let _intersection = new Set()
  for (let elem of setB) {
      if (setA.has(elem)) {
          _intersection.add(elem)
      }
  }
  return _intersection
}

// union
console.log(union(setA, setB)) // Set { 1, 2, 'a', 'b', 3, 'c' }

// intersection
console.log(intersection(setA, setB)) // Set { 2, 'b' }
$ node set-data-structure.js
Set { 1, 2, 'a', 'b', 3, 'c' }
Set { 2, 'b' }

How to insert/delete/access/search data

lecture-5/set-data-structure.js
// insert
setA.add(4)
console.log(setA) // Set { 1, 2, 'a', 'b', 4 }

// delete
setA.delete(1)
console.log(setA) // Set { 2, 'a', 'b', 4 }

// search
console.log(setA.has('a')) // true
console.log(setA.has('c')) // false
$ node set-data-structure.js
Set { 1, 2, 'a', 'b', 4 }
Set { 2, 'a', 'b', 4 }
true
false

How fast to insert/delete/access/search data

Data Structure Insert Delete Access Search
Set O(1): add O(1): delete N/A O(1): has

⬆️ Time complexity (worst case) per operation

Real life interview questions

  1. Do you know how your data looks like?
  2. What is Set usually used for?
  3. How do you insert/delete/access/search with Set data structure?
  4. What is the Time Complexity of Set data structure on insert/delete/access/search operation?
  5. Write a simple program to demonstrate the substantial difference of search speed of Array and Set data structure.