Space Complexity

Question 1

What is space complexity?

Answer 1

Space complexity of an algorithm refers to the total space consumed by the algorithm with respect to input size.

Space complexity includes both auxiliary space and space consumed by input

Question 2

What takes space?

Answer 2

variables
data structures
function call
allocations

Question 3

Rule Book

Answer 3

rule 1: always worst case
rule 2: remove constants
rule 3: different inputs should have different variables. O(a + b)
rule 4: drop non-dominant terms

Question 4

Interviews: What is the tradeoff between saving time and saving space?

Answer 4

you have to first decide which one you’re optimizing for

Question 5

Knowledge test: If you’re working at Twitter and your boss asks you to build a feature that allows a user to click a button next to their name to retrieve their oldest tweet and newest tweet.

based on Big O notation, what can we assume about this problem?

how would you solve this?

Answer 5

1st assumption: we must find 1st tweet
2nd assumption: we must find nth tweet

we don’t know how the tweets are stored, but based on how they’re stored we may be able to just grab the first entry from the database and the last entry from the database.

if the ds is an array, the Big O would be constant time

Question 6

Twitter problem extended: boss asks you to compare the dates of tweets

Answer 6

tweets = [{ tweet: ‘whatup’, date: 2012 } , { tweet: ‘a bucket’, date: 2014 }, { tweet: ‘buckets’, date: 2018 }]

compare each tweet with the other tweets and compare their dates

this will be nested loops, which means it will be a Big O of O(n^2)