Data Structures

Question 1

Explain the difference between Stacks and Queues

Answer 1

Stacks VS Queues:

Stacks:

• Can be built with Arrays and Linked Lists
• Arrays allow cache locality, which makes it technically faster since their items are right next to each other in memory
• Linked lists items are scattered all over memory and have extra memory onto them

Queues:

• Never build with an array ONLY LINKED LISTS
• Because we would have to shift the indexes everytime

Question 2

What are Queues and what they can be used for?

Answer 2

Queues (FIFO):

• lookup O(n)
• enqueue O(n) – aka push aka add to the queue
• dequeue O(1) – aka pop aka remove the first person in line
• peek O(1) – whats the first item that’ll come up?
• First one in, first out (ROLLERCOASTER LINE)
• Used for:

—- if you had any waitlist to buy tix for a concert, reservations, uber, lyft

—- a printer

Question 3

Should you use an array to build a Queue?

Answer 3

Never use an ARRAY to build a QUEUE

• its inefficient
• removing the first item, so if you use an array you will have to shift the indexes

Question 4

What is a Stack and what can it be used for?

Answer 4

STACK (LIFO):

• lookup O(n)
• pop O(1)
• push O(1)
• peek O(1) – view the top plate
• Last one in, first one out
• Useful for:
  
  • — Need to know the very last value that was added

Question 5

What are the pros and cons for Linked Lists?

Answer 5

LINKED LISTS

GOOD:

• Fast Insertion
• Fast Deletion
• Ordered
• Flexible Size

BAD:

• Slow lookup
• More memory

Question 6

Difference between a Singly vs Doubly Linked list?

Answer 6

Singly vs Doubly (When to use)

• Singly

— simple implementation

— less memory

– Cannot traverse from back to front

Good option when:

• Less memory or memory is expensive
• Want to do fast insertion and deletion

Doubly

• Can traverse the list
• If you need to delete a previous node, you don’t need to traverse from the head node and find what the previous node is
• Requires more memory in storage

Question 7

What is good about a doubly linked list?

Answer 7

Doubly Linked list

• Allows us to traverse our list forwards/backwards

Question 8

What is a pointer?

Answer 8

Pointer is just a reference to another variable.

const obj1 = { a: true }

const obj2 = obj1;

both point to the same thing in memory

Question 9

What is a linked list and some of its qualities?

Answer 9

Definition of Linked List:

Linked lists are data structures that represent a series of nodes where each node contains two pieces of information: the value of the node and a pointer/reference to the next node in the list. The beginning of the list is called the head and the node at the end of the list is referred to as the tail, which points to the empty value; null.

notes

• nodes are scattered
• iterating through it is slower
• INSERTing into it is a lot better (no shifting of the arrays)
• you can sort data
• prepend O(1)
• append O(1)
• lookup O(n) aka Traversal - we have to start from Head
• insert O(n) - Have to go one by one to find the index and insert there
• delete O(n) - Have to find the items

Question 10

What is a tradeoff for Hash tables?

Answer 10

Tradeoffs of Hash tables

• Fast (better time complexity) but adds more memory aka Space complexity

Question 11

What are some differences between Hash tables and Arrays?

Answer 11

Hash tables vs Arrays

Hash tables

• when u want quick access to a certain item [search O(1)]
• no concept of order
• flexible keys
• fast inserts
• good collision resolution needed***

Bad: unordered and slow key iteration

Arrays

• not so quick for search O(n)
• each item is placed on a shelf next to each other in memory

Question 12

Difference between a Map vs. Object?

Answer 12

Map vs. Object

• Map allows you to store any type of data as a key
• Object only allows strings as keys

Question 13

What is the Big O of

‘asdfasfasfasfdasdfa’.length?

Answer 13

Depends on the language you are using. JavaScript has .length built in to each string.. so its a property of an object. so in JS it’ll be O(1) constant time

Question 14

What adds to Space Complexity?

Answer 14

For space complexity, we don’t care about the input size.

What takes up space?

• Variables
• Data Structures ( like creating a new array and adding items to it)
• function calls
• allocations

Question 15

What to consider when thinking of Space Complexity?

Answer 15

Space Complexity:

• Heap - store variables
• Stack - keep track of functions calls

Question 16

What to consider when thinking of Scalability?

Answer 16

Scalability:

• Speed
• Memory

Question 17

What is the Big O of nested loops?

Answer 17

If you see nested loops, use multiplication to determine Big O

O(n^2) -> Quadratic Time

Question 18

What are the rules of Big O?

Answer 18

Big O Rules:

1) Worst Case
2) Remove Constants
3) Different terms for inputs
4) Drop Non Dominants

Question 19

What is Constant Time?

Answer 19

O(1) -> Constant Time (Grabbing the first item in the array)

the length of data doesn’t matter.

const compressFirstBox = boxes => {

console.log(boxes[0]);

}

Question 20

What is Linear Time?

Answer 20

O(n) -> Linear Time

Question 21

What makes good code?

Answer 21

1) Readable

2) Scalable (Big O)

Question 22

Whats the difference between Single threaded and Multi threaded?

Answer 22

• Single threaded = Has only ONE call stack (FIFO) one thing at a time
• Multi threaded = Has MORE than one call stack

Question 23

Whats the difference between Asynchronous and Synchronous programming?

Answer 23

Synchronous programming is when lines of code get executed one at a time

Asynchronous programming (image processing, api calls) - multiple things can happen at different times

• setTimeout()
• callback functions

Question 24

What is Stack overflow and what can cause it?

Answer 24

Stack Overflow:

• When the call stack runs out of space
• Caused by infinite loop or Recursion - a function that calls itself

Question 25

What will the console print out?

console.log(‘1’);

setTimeout(()=> {

console.log(‘2’);

}, 0);

console.log(‘3’);

Answer 25

Because we are still using the setTimeout api, it still goes through the process of the web api, then the callback queue, then the event loop.. only after console.log(‘3’) will it print ‘2’.