CS

Question 1

What does the acronym LIFO mean?

Answer 1

Last-in-first-out

Question 2

What methods are available on a Stack data structure?

Answer 2

• .push() - put something on top
  
  • .pop() - take something off the top
  • (Convenience but not required for a Stack) .peek() - look at what’s on top without taking it off

Question 3

What must you do to access the value at an arbitrary point in a stack (not just the “top”)?

Answer 3

• Store the items you pop off somewhere
  
  • If you can destroy the stack, just keep popping off
  • Searching the stack is O(n)

Question 4

What does the acronym FIFO mean?

Answer 4

First-in-first-out

Question 5

What methods are available on a Queue data structure?

Answer 5

• .enqueue() - Add something to the queue (by the nature of queues, to the end)
  
  • .dequeue() - Remove something from the queue (by the nature of queues, from the start)
  • There may or may not be a convenience method .peek() among others

Question 6

What must you do to access the value at an arbitrary point in a queue (not just the “front”)?

Answer 6

.dequeue() values until you reach the desired point

Question 7

What are some examples of simple operations?

Answer 7

• Declaring/assigning a variable
  
  • Accessing/assigning array by index
  • Accessing/assigning object by property
  • Single-step expressions (i + 200, i < 200)
  • A truth test

Question 8

What is the order of best-to-worst time complexities?

Answer 8

• O(1) - constant time (increasing n has no effect)
  
  • O(log n) - logarithmic time (increasing n increases simple operations by log n)
  • O(n) - linear time (increasing n increases simple operations by n)
  • O(n log n) - log-linear time
  • O(n^2) - quadratic time (increasing n increases simple operations by n^2)
  • O(2^n) - exponential time
  • O(n!) - factorial time

Question 9

What time-complexities are generally considered bad? Good?

Answer 9

• O(1), and O(log n) are good
  
  • O(n) is acceptable
  • O(n log n) is ok
  • Everything above that is bad and should be used very carefully

Question 10

How are linked lists different from an array?

Answer 10

• Items in a linked list can only be accessed by sequentially traversing the list. Arrays can directly access desired values.
  
  • Arrays store memory continuously (in the same place) which allows index access to be done via a simple jump, giving O(1) complexity. Linked lists do not have to allocate memory ahead of time and items can be stored all around the memory.
  • Because linked lists are just pointing to each other, prepending something takes O(1) time. If there is a tail pointer, appending something is also O(1) time. Otherwise, appending something in the middle or at the end takes O(n) time.

Question 11

How would you access an arbitrary node in a linked list (not just the “head”)?

Answer 11

Repeatedly access the next node in the list until you reach the desired one

Question 12

How can you construct a stack with a linked list?

Answer 12

Stacks can add to the end and remove from the end

- Iterate through linked list until you get to the last
- Add: Set the next to the new value
- Remove: Keep track of the previous node, then once at  the last node go back to the previous and remove that node's next

Question 13

How can you construct a queue with a linked list?

Answer 13

Queues can add to the end and remove from the front

- Remove: Simply grab the head's next value, that is the head of the linked list where the first node has been dequeued
- Add: Iterate to the end and set the last node's next to the new value

Question 14

What must the return value ofmyFunctionbe if the following expression is possible?

```js
myFunction()();
```

Answer 14

It must return a function

Question 15

What does this code do?

js
    const wrap = value => () => value;
   

Answer 15

Creates a function factory wrap that takes one parameter value as its argument. The returned function takes no arguments but will return the argument for wrap’s value.

Question 16

In JavaScript, when is a function’s scope determined; when it is called or when it is defined?

Answer 16

• When it’s defined
• When a function within a function is defined, a reference to the lexical environment is created.
• When a parent function is called, the returned child function maintains the reference to the lexical environment of the parent function instance.

Question 17

What allows JavaScript functions to “remember” values from their surroundings?

Answer 17

• A closure, which is the function as well as the lexical environment for the function
• (Know this definition for interviews, simple and straightforward)

Question 18

What is debouncing, and how do you debounce an function?

Answer 18

• Debouncing is a programming technique to prevent a trigger from repeatedly calling a function but instead to only call the function a single time after the triggering event has concluded.
  
  • A function should take a function and a setTimeout delay as arguments. A variable is declared within the function to store a Timeout ID, followed by a returned function that clears the timeout for the stored Timeout ID and then sets a new Timeout and assigns the ID to the variable again

Question 19

How does debouncing utilize closures?

Answer 19

The function returned from the debouncing function “remembers” a timeout variable in its lexical environment and uses it to store a value to be used on its next iteration