Master the coding interview (udemy) Flashcards
- Hash Table Implementation
View hash table and try to recall how to enter set and get methods
View Problem
- A class that has a contructor that forms an array and its length by params provided.
- Inside Class we have a function that creates a hash out of params named ‘key’. This ‘key’ is a string that helps us create a hash(number).
-
Set() function
- set function takes key and value
- variable that runs _hash function using key
- condition if hash results exist in data array. if it doesnt create array at that location
push an array of key and value to that location
*return data
What are the pros and cons of Hash Tables
Pros: Fast lookups, Fast inserts, and Flexible Keys
Cons: Unordered and slow key iteration
What are the differences between using linked lists and arrays.
Arrays-
Cons: Harder to insert,or delete values in the middle
Pros: Faster to iterate
Linked Lists -
Cons: Slower than arrays to iterate
Pros: Easier to insert or delete items in the middle
What is a pointer?
Its a reference to another place in memory or another object or another node. Its like the Genie pointing from an island up to the object.
Objects don’t technically store values. They store pointers! These pointers might have a name (key, in objects) or a number (index, in arrays).
The pointers can be imagined as crew members in the flying ships. Look closer and you will see they are genies 🧞♂️! Each is responsible for finding a specific value, by shining a spotlight on the location of that value
Create a singly linked list and append , prepend,and insert function,traverse function and remove function(). Start off doing one at a time.
view
Are objects embedded in head of a linked list?
Why do we get [object] when we console a linked list more that 2?
No they are not embedded, even though they look like they are. They point to a different object.
We get [object] because the console tries to save memory/speed instead of listing all objects. To see all objects, then we have to use JSON.stringifty()
Add a reverse function to a singly linked list
Reversing a Linked List – Train Analogy 🚂
```javascript
class LinkedList {
constructor(value) {
this.head = {
value: value,
next: null
};
this.tail = this.head;
this.length = 1;
}
reverse() {
if (!this.head || !this.head.next) {
return this; // If there’s 0 or 1 train car, no need to reverse
}
let prev = null; // No train cars behind us yet (end of reversed train)
let current = this.head; // Start at the front of the train (Engine)
this.tail = this.head; // The Engine will become the new last car (tail)
while (current !== null) {
let next = current.next; // Store the next train car before detaching it
// Reverse the connection: Detach the current train car and attach it to the reversed train
current.next = prev;
// Move forward: Now this train car (current) is the last one in the reversed order
prev = current;
// Move to the next train car in the original direction
current = next;
}
// prev is now the new "front" of the reversed train (linked list)
this.head = prev;
return this; // Return the modified linked list }
printList() {
let current = this.head;
let output = “”;
while (current) {
output += current.value + “ → “;
current = current.next;
}
console.log(output + “null”);
}
}
~~~
🚂 Train Analogy Step-by-Step
Imagine you have a train with cars connected in a line, and you want to turn it around.
Initial Train Cars (Linked List)
🚂 Engine → Car A → Car B → Car C → null
Each train car is a node, connected by links.
Step 1: Start with the Engine (Head of List)
- prev = null (No reversed train yet)
- current = Engine (Start at the front)
- Action: Detach Engine from Car A and set its next to null.
🚂 Now the train looks like:
Engine (alone) Car A → Car B → Car C → null
(Reversed train: Engine)
Step 2: Move to Car A
- prev = Engine
- current = Car A
- next = Car B
- Action: Detach Car A and attach it behind Engine.
🚂 Now the train looks like:
Car A → Engine Car B → Car C → null
(Reversed train: Car A → Engine)
Step 3: Move to Car B
- prev = Car A
- current = Car B
- next = Car C
- Action: Detach Car B and attach it behind Car A.
🚂 Now the train looks like:
Car B → Car A → Engine Car C → null
(Reversed train: Car B → Car A → Engine)
Step 4: Move to Car C (Last Car)
- prev = Car B
- current = Car C
- next = null
- Action: Detach Car C and attach it behind Car B.
🚂 Final Reversed Train:
Car C → Car B → Car A → Engine → null
(Final reversed linked list)
Final Result
✅ New head is Car C (was the last car before)
✅ New tail is Engine (was the head before)
Printing the Train Before and After
Here’s how you can use the printList() function to visualize the reversal:
```javascript
const myTrain = new LinkedList(1);
myTrain.head.next = { value: 2, next: { value: 3, next: { value: 4, next: null } } };
myTrain.tail = myTrain.head.next.next.next;
myTrain.length = 4;
console.log(“Original train order:”);
myTrain.printList();
console.log(“\nReversed train order:”);
myTrain.reverse();
myTrain.printList();
~~~
Expected Output
Original train order: 1 → 2 → 3 → 4 → null Reversed train order: 4 → 3 → 2 → 1 → null
🚂 Your train has successfully reversed!
🔹 Summary
- We detach each train car one by one and attach it to the reversed train.
- The Engine (head) becomes the last car (tail).
- The last car (tail) becomes the Engine (head).
- The process is O(n) time complexity, since we process each node once.
Why use stacks and queues?
Explain stacks.
Explain queques. Why would we not want to use arrays for queues?
Why would we ever want to use something like this?
And this is an important topic in computer science.You will see that we can build things like Stacks and Queues, which are using arrays or linked lists. Unlike arrays and link lists, we have less methods or less actions that we can perform on stacks and Queues. And sometimes it’s good to have these higher level data structures that are built on top of lower level ones like link lists and arrays to limit the operations you can do on them. That’s actually a benefit in computer science. Having this limited ability on a data structure is an advantage because you can control that. Whoever uses this data structure performs only the right operations that are efficient. If you give somebody all the tools in the world. It’s a lot harder for them to operate than if you just give them two or three so that they know exactly what they need to do.
Stacks is like stacking plates. LIFO “last in first out”. You can’t access the bottom plate,only the top. We can use the stack to get the last item in memory.
Ques are like an entrance to a rollercoaster. FIFO “first in first out”. Ques can be used in an app like waiting for tickets for a concert. Ques can be used in a restaurant app for reservations for a table. Enqueue means add person to line. dequeue means remove person from line. Peek usually finds the first person in line. We usually don’t use lookup().
You don’t want to use arrays for queues because when we unshift the array, all indexes will have to shift which is bad.
whats the javascript engine that chrome uses?
what does it do?
there’s 2 parts to that javascript engine what are they and what do they do?
Is javascript single threaded?
what is stack over flow? *not the website
What is the javascript runtime enviroment?
The engine is v8 and it reads the javascript we create and changes it to machine executable instructions for the browser.
Memory Heap - Where memory allocation happens. For example ‘const a=1;’ uses up the memory heap. And with all memory, we have limited amount that we can actually have.
So by increasing the number of variables that we have, imagine if I had just this page full of variables and instead of just numbers, they’re like very, very big arrays. Well, memory leaks happen when you have unused memory, such as, let’s say we’re not using the variable A, but it’s still there. Well, by having unused memory, just laying around, it fills up this memory heap. And that’s why you might hear why global variables are bad. Global variables are bad because if we don’t forget to clean up after ourselves, we fill up this memory heap and eventually the browser will not be able to.
Call Stack - Where your code is executed. Tells you where you are in your program.
Yes javascript is single threaded. It is called one line at a time. What happens if one line is looped millions of times?
Stack over flow would keep piling a plate on top of the plate stack forever. Example:
function foo(){
foo() ;
}
foo();
What is the javascript runtime enviroment?
In what order will ‘1’,’2’,’3’ be called in the following:
console.log(‘1’)
setTimeout( ()=>
console.log(‘2’), 0 }
console.log(‘3’)
and why?
- Optional: How Javascript Work time: 14:41
image
As you can see setTimeout is part of the web api.
setTimeout will still get sent to the web api. Even though its 0 seconds it will still console.log(‘3’) before console.log(‘2’) because it took extra time going to the web api and event loop.
JavaScript is a single threaded language that can be non blocking.
It has one call stack and it does one thing at a time in order to not block the single thread.
It can be asynchronous with callback functions and these callback functions gets run in the background through the callback queue and then the event loop to bring it back into the call stack.
What is garbage collecting in Javascript?
Garbage collection (GC) is an automatic process in JavaScript that reclaims memory by removing objects that are no longer accessible or needed. This helps prevent memory leaks and ensures efficient use of system resources. Example : Problem Stack exercise line 54
**Problem: Implement a Queue using stacks
**
//Hint: its like we have 2 cups with a list inside. To remove from the front we
//move everything to the other cup backwards and remove the last item using pop(because)
//its actually the first item. when we want to add to the list we move everything
//to the other cup backwards then at at the end of the list.
//build a constructor with this.first and this.last that are both equal to empty arrays
//create enqueue
//var for this.first length
//for loop to push onto this.last . we will push this.first last item by using pop();
//push value ot this.first array
//create dequeue
//var for this.last length;
//create for loop to push onto this.first. we want to pust the last item in this.last
//create peek
//create conditional to see if this.first length is greater than 0.everything
//that is enqueued would be in this.last so this statement wouldnt run. Everything
//would have to be in this.first.
//if items are in this.last then return the first item of this.last array
Explain what a tree is.
What in web development is an example of a tree?
In what game, before machine learning, was the tree data structure used?
- Imagine an upside down tree with its branches growing downward. A tree starts off with a root(parent). It has children. Those can have children. The outer children can be called leafs.
- The document object model is an example of a tree data structure
- Chess
view
1.What is a binary tree?
2.Most actions in a binary tree would be O(log N). 3.What does that mean?
4.What are the 2 rules of binary search tree?
5.whats the difference between unbalanced and balanced trees?
1.Each node can only have either zero one or two nodes, and each child can only have one parent.
This is a binary tree. Each node represents a certain state.
2.Andrei compares log inside “O(log N)” as divide and conquour. For example if we search for ‘zipper’ definition in a dictionary , we will go to the section ‘Z’ instead of look through every word.
3.Whenever we move right the value increases. 4.Whenever we move left the value decreases.
5.Unbalanced is when a tree is not symmetrical and this can cause Big O to change for the worse. Balanced trees are symmetrical and has better big O.
Building a Binary Tree Search Tree
1.Create insert()
2. Create lookup()
3. Create remove()
Problem
//create a node class
//create a class for binary search tree
//create insert tree
// to insert we want to check if root is empty or not
//console.log(‘current.left:’,this);
//console.log(‘current.right:’,this);
//create lookup()
//create scenerio where there is no root
//create a situation which currentNode is always true. That currentNode should be changing
//node as we iterate. currentNode should should be larger,smaller,equal or not exist. If it
//doesnt exist then return false
//create remove();
//we want to use look up() logic. Inside condition of ==. Inside that create a situation
//of currentNode having no children, 2 children or none.
//No children //if currentnode left and right do not exist // if left child == currentNode the left child equal null ///else right child = null // Two children //we need to keep track of the parent and right child in a variable. //use iteration to check if left child is not null. if not null we make the child into the parent // the new child from previous left child // out of iteration or if child is null we make current.value be the child value //Use a conditional if left child equals to current child then we make left child equal //current child right else right child equal current child right. // One child //create a ternary that makes childnot currentNode left. if true return currentNode left //if false return currentNode right // create else statement that if left child = currentNode return child left=childnode //else right child equal childnode //return this // if no number exist to search for return false
Logic building.
3. I need to think about the scenerio of a node having no children, one child, and 2 children. use the parent node to see if target node is on its left or right. if so do something. With 2 children first step is going right if possible. After we must check left from there on because we want the smallest (of the biggest) to take over.
* using while loops as a tool to keep iterating until we hit a dead end (null)
This won’t be in an interview
Explain what AVL trees and red/black trees are?
They are used to balance Binary search trees. Most likely we will use these in production through a library.
Explain a binary heap
The difference from a binary tree and binary heap is that binary trees put greater values to the right and lesser values to the left. With binary heap it doesnt matter as long as the parent is always greater than the children. An example andrei gives of using this over a binary tree is getting numbers over 33, we would only grab the root(101) and its children (72 and 33).
A binary heap is a tree-based data structure that maintains a special order:
✅ It is a complete binary tree → every level is filled except possibly the last one.
✅ It follows the heap property:
Min-Heap: The parent node is smaller than its children. (Root = smallest)
Max-Heap: The parent node is greater than its children. (Root = largest)
⏬ Example of a Min-Heap ⏬
3
/ \
10 15
/ \ /
20 30 17
The smallest value (3) is at the root.
Every parent node is smaller than its children.
When Would You Use a Binary Heap in Web Development?
A binary heap is great for efficiently handling priority queues, where the highest-priority item needs to be processed first.
💡 Example: Task Scheduling in a Web App
Imagine a background job queue where different tasks have different priorities:
Rendering a webpage → High priority
Sending an email → Medium priority
Data backup → Low priority
A Min-Heap Priority Queue ensures that the highest-priority task is processed first, keeping the application smooth and responsive.
🔥 Real-World Example: Many job schedulers (like in Node.js event loops or AWS SQS) use a binary heap internally to manage task execution efficiently. 🚀
What is a priority que?
An analogy that andrei gives is like a line at a club. There is going to be a que but there are also going to be people who get priority because they paid more.
Another analogy is people boarding on a plane. The pilot is the root. We then add 3 people from left to right. Then we add a steward thats more priority than the regular people. The steward would become root.left. We alway add to the left then right.
