Data Structures Flashcards
Variables are stored in _______________?
RAM (Random Access Memory)
_________ is connected to a memory controller and it does all the real work inside our computer.
Processor
The ____________ does the actual reading and writing to and from RAM. It has a direct connection to each shelf of RAM.
Memory controller
The processor has a ______ where it stores a copy of stuff it’s recently read from RAM.
Cache. This cache is much faster to read from than RAM, so the processor saves time whenever it can read something from cache instead of going out to RAM
What happens when the processor asks for the contents of a given memory address?
Memory controller also sends the contents of a handful of nearby memory addresses. And the processor puts all of it in the cache.
For a 64-bit integer, how much space is taken by 0 and 32,000.
It does not matter, both take up the same space in RAM i.e 64 bits.
Time complexity of addition, subtraction, multiplication, and division of fixed-width integers
O(1)
One +ve and -ve of using Arrays
+ve: Fast lookup of O(1)
-ve: Big block of uninterrupted free memory is require to store the array.
How to store different strings of different lengths to an array?
Using pointers to store the starting address of each string in the array.
What is one negative of using pointers to store addresses in an array?
It is not cache-friendly.
This slowdown isn’t reflected in the big O time cost. Lookups in this pointer-based array are still O(1) time.
Worst case of adding in dynamic arrays.
O(n). The amortized (avg) time is O(1)
For prepend, which one is better - Linked list or Dynamic arrays?
Linked List since it takes O(1) time, whereas Dynamic arrays has to shift each character, which leads to O(n)
Time to lookup in Linked List
O(i)
Which one is better for lookup and Why? Linked List or Dynamic Arrays
Dynamic Arrays because it is O(1) and it is cache-friendly
What is logarithmic asking?
What power must we raise this base to, in order to get this answer?
