QuincyLarson
commented
8 years ago @alayek imho this is the sort of concept that would be best taught through a @brianamarie CS concept video 📹 👩 💻
Closed QuincyLarson closed 7 years ago
QuincyLarson
commented
8 years ago @alayek imho this is the sort of concept that would be best taught through a @brianamarie CS concept video 📹 👩 💻
CarlJKashnier
commented
8 years ago Working on getting the Set() for ES5 explained I think 8 or so challenges should be about right to build the whole Set() function. Let me know what needs to be reworked. (First go at creating challenges, so I want to ensure this is right before I create the next few.) I don't have chai installed local but my console test show it working.
var set = new Object();
set.foo = true;
// See if foo exists in our set:
console.log(set.foo) // trueIn the next few exercises, we will build a full featured Set from scratch.
In this exercise you will add a function to add a value to our set collection:
this.add = function(){
//some code to add value to the set
}assert((function(){var test = new Set(); return (typeof test.add === 'function')}()), 'message: Your <code>Set</code> class should have a <code>add</code> method.');
assert(function(){var test = new Set; test.add("a");test.add("b";test.add("a");return test.values() === [ 'a', 'b' ])}(), 'message: Your code needs to prevent duplicates.');function Set() {
// the var collection will hold our set
var collection = [];
// this method will check for the presence of an element and return true or false
this.has = function(element) {
return (collection.indexOf(element) !== -1);
};
// this method will return all the values in the set
this.values = function() {
return collection;
};
// change code below this line
// change code above this line
};
var setA = new Set();
setA.add("a");
setA.add("b");
setA.add("b");
console.log(setA.values() // should be [ 'a', 'b'];this.add = function(element) {
if(!this.has(element)){
collection.push(element);
return true;
}
return false;
};Set - Exercise 2 - remove from Set
In this exercises we are going to create a delete function for our Set. The function should be named this.remove
assert((function(){var test = new Set(); return (typeof test.remove === 'function')}, 'message: Your <code>Set</code> class should have a <code>remove</code> method.');
assert(function(){var test = new Set; test.add("a");test.add("b");test.remove("a");return (test.values() === [ 'b' ])}), 'message: Your code should remove the item from');function Set() {
// the var collection will hold the set
var collection = [];
// this method will check for the presence of an element and return true or false
this.has = function(element) {
return (collection.indexOf(element) !== -1);
};
// this method will return all the values in the set
this.values = function() {
return collection;
};
// this method will add an element to the set
this.add = function(element) {
if(!this.has(element)){
collection.push(element);
return true;
}
return false;
};
// change code below this line
// change code above this line
};
var setA = new Set();
setA.add("a");
setA.add("b");
setA.remove("b");
console.log(setA.values())//should be [ 'a' ];this.remove = function(element) {
if(this.has(element)){
index = collection.indexOf(element);
collection.splice(index,1);
return true;
}
return false;
};Set - Exercise 3 - Size of the set
In this exercise we are going to create a size function for our Set. This function should be named this.size and it should return the size of the collection.
assert((function(){var test = new Set(); return (typeof test.size === 'function')}, 'message: Your <code>Set</code> class should have a <code>size</code> method.');
assert(function(){var test = new Set; test.add("a");test.add("b");test.remove("a");return (test.size() === 2)}), 'message: return the number of elements in the collection.');function Set() {
// the var collection will hold the set
var collection = [];
// this method will check for the presence of an element and return true or false
this.has = function(element) {
return (collection.indexOf(element) !== -1);
};
// this method will return all the values in the set
this.values = function() {
return collection;
};
// this method will add an element to the set
this.add = function(element) {
if(!this.has(element)){
collection.push(element);
return true;
}
return false;
};
// this method will remove an element from a set
this.remove = function(element) {
if(this.has(element)){
index = collection.indexOf(element);
collection.splice(index,1);
return true;
}
return false;
};
// change code below this line
// change code above this line
}
var setA = new Set();
setA.add("a");
setA.add("b");
console.log(setA.size()) // should be 2;this.size = function() {
return collection.length;
};Set - Exercise 4 - Perform a union on 2 Sets of data.
In this exercise we are going to perform a union on 2 sets of data. We will create a method on our Set data structure called union. This method should take another set as an argument and update the set you called the method on to be the union of the two sets, excluding any duplicate values.
assert((function(){var test = new Set(); return (typeof test.union === 'function')}, 'message: Your <code>Set</code> class should have a <code>union</code> method.');
assert(function(){ var setA = new Set(); var setB = new Set(); setA.add("a"); setA.add("b"); setA.add("c"); setB.add("c"); setB.add("d"); var unionSetAB = setA.union(setB);return (unionSetAB.values() === [ 'a', 'b', 'c', 'd' ])}), 'message: The proper collection was returned');function Set() {
// the var collection will hold the set
var collection = [];
// this method will check for the presence of an element and return true or false
this.has = function(element) {
return (collection.indexOf(element) !== -1);
};
// this method will return all the values in the set
this.values = function() {
return collection;
};
// this method will add an element to the set
this.add = function(element) {
if(!this.has(element)){
collection.push(element);
return true;
}
return false;
};
// this method will remove an element from a set
this.remove = function(element) {
if(this.has(element)){
index = collection.indexOf(element);
collection.splice(index,1);
return true;
}
return false;
};
// this method will return the size of the set
this.size = function() {
return collection.length;
};
// change code below this line
// change code above this line
};
var setA = new Set();
var setB = new Set();
setA.add("a");
setA.add("b");
setA.add("c");
setB.add("c");
setB.add("d");
var unionSetAB = setA.union(setB);
console.log(unionSetAB.values())//should be [ 'a', 'b', 'c', 'd' ];this.union = function(otherSet) {
var unionSet = new Set();
var firstSet = this.values();
var secondSet = otherSet.values();
firstSet.forEach(function(e){
unionSet.add(e);
});
secondSet.forEach(function(e){
unionSet.add(e);
});
return unionSet;
};Set - Exercise 5 - Perform a intersection on 2 Sets of data.
In this exercise we are going to perform an intersection on 2 sets of data. An intersection of sets represents all values that are common to two or more sets. This method should be called this.intersection. This method should return a new set containing the intersection of the sets the method was called against.
assert((function(){var test = new Set(); return (typeof test.intersection === 'function')}, 'message: Your <code>Set</code> class should have a <code>intersection</code> method.');
assert(function(){ var setA = new Set(); var setB = new Set(); setA.add("a"); setA.add("b"); setA.add("c"); setB.add("c"); setB.add("d"); var intersectionSetAB = setA.intersection(setB);return (intersectionSetAB.values() === [ 'c' ])}), 'message: The proper collection was returned');function Set() {
// the var collection will hold the set
var collection = [];
// this method will check for the presence of an element and return true or false
this.has = function(element) {
return (collection.indexOf(element) !== -1);
};
// this method will return all the values in the set
this.values = function() {
return collection;
};
// this method will add an element to the set
this.add = function(element) {
if(!this.has(element)){
collection.push(element);
return true;
}
return false;
};
// this method will remove an element from a set
this.remove = function(element) {
if(this.has(element)){
index = collection.indexOf(element);
collection.splice(index,1);
return true;
}
return false;
};
// this method will return the size of the collection
this.size = function() {
return collection.length;
};
// this method will return the union of two sets
this.union = function(otherSet) {
var unionSet = new Set();
var firstSet = this.values();
var secondSet = otherSet.values();
firstSet.forEach(function(e){
unionSet.add(e);
});
secondSet.forEach(function(e){
unionSet.add(e);
});
return unionSet;
};
// change code below this line
// change code above this line
};
var setA = new Set();
var setB = new Set();
setA.add("a");
setA.add("b");
setA.add("c");
setB.add("c");
setB.add("d");
var intersectionSetAB = setA.intersection(setB);
console.log(intersectionSetAB.values())//should be [ 'c' ];this.intersection = function(otherSet) {
var intersectionSet = new Set();
var firstSet = this.values();
firstSet.forEach(function(e){
if(otherSet.has(e)){
intersectionSet.add(e);
}
});
return intersectionSet;
};Set - Exercise 6 - Perform a difference on 2 Sets of data.
In this exercise we are going to perform a difference on 2 sets of data. A difference of sets should compare two sets and return the items present in the first set that are absent in the second. This method should be called this.difference and should return a new set containing only the items that result from taking the difference of two sets.
assert((function(){var test = new Set(); return (typeof test.difference === 'function')}, 'message: Your <code>Set</code> class should have a <code>difference</code> method.');
assert(function(){ var setA = new Set(); var setB = new Set(); setA.add("a"); setA.add("b"); setA.add("c"); setB.add("c"); setB.add("d"); var differenceSetAB = setA.difference(setB);return (differenceSetAB.values() === [ 'a', 'b' ])}), 'message: The proper collection was returned');function Set() {
// the var collection will hold the set
var collection = [];
// this method will check for the presence of an element and return true or false
this.has = function(element) {
return (collection.indexOf(element) !== -1);
};
// this method will return all the values in the set
this.values = function() {
return collection;
};
// this method will add an element to the set
this.add = function(element) {
if(!this.has(element)){
collection.push(element);
return true;
}
return false;
};
// this method will remove an element from a set
this.remove = function(element) {
if(this.has(element)){
index = collection.indexOf(element);
collection.splice(index,1);
return true;
}
return false;
};
// this method will return the size of the collection
this.size = function() {
return collection.length;
};
// this method will return the union of two sets
this.union = function(otherSet) {
var unionSet = new Set();
var firstSet = this.values();
var secondSet = otherSet.values();
firstSet.forEach(function(e){
unionSet.add(e);
});
secondSet.forEach(function(e){
unionSet.add(e);
});
return unionSet;
};
// this method will return the intersection of two sets as a new set
this.intersection = function(otherSet) {
var intersectionSet = new Set();
var firstSet = this.values();
firstSet.forEach(function(e){
if(otherSet.has(e)){
intersectionSet.add(e);
}
});
return intersectionSet;
};
// change code below this line
// change code above this line
};
var setA = new Set();
var setB = new Set();
setA.add("a");
setA.add("b");
setA.add("c");
setB.add("c");
setB.add("d");
var differenceSetAB = setA.difference(setB);
console.log(differenceSetAB.values()) // should be [ 'a', 'b' ];this.difference = function(otherSet) {
var differenceSet = new Set();
var firstSet = this.values();
firstSet.forEach(function(e){
if(!otherSet.has(e)){
differenceSet.add(e);
}
});
return differenceSet;
};Set - Exercise 7 - Perform a subset check on 2 Sets of data.
In this exercise we are going to perform a subset test on 2 sets of data. This will compare the first set, against the second and if the first set is fully contained within the Second then it will return true. This method should be called this.subset. At this point, we have added a lot of useful functionality to our Set data structure. This will complete the challenges for the set data structure.
assert((function(){var test = new Set(); return (typeof test.subset === 'function')}, 'message: Your <code>Set</code> class should have a <code>union</code> method.');
assert(function(){ var setA = new Set(); var setB = new Set(); setA.add("a"); setB.add("b"); setB.add("c"); setB.add("a"); setB.add("d"); var subSetSetAB = setA.subset(setB);return (subSetSetAB === true)}), 'message: The first Set() was contained in the second Set');function Set() {
// the var collection will hold the set
var collection = [];
// this method will check for the presence of an element and return true or false
this.has = function(element) {
return (collection.indexOf(element) !== -1);
};
// this method will return all the values in the set
this.values = function() {
return collection;
};
// this method will add an element to the set
this.add = function(element) {
if(!this.has(element)){
collection.push(element);
return true;
}
return false;
};
// this method will remove an element from a set
this.remove = function(element) {
if(this.has(element)){
index = collection.indexOf(element);
collection.splice(index,1);
return true;
}
return false;
};
// this method will return the size of the collection
this.size = function() {
return collection.length;
};
// this method will return the union of two sets
this.union = function(otherSet) {
var unionSet = new Set();
var firstSet = this.values();
var secondSet = otherSet.values();
firstSet.forEach(function(e){
unionSet.add(e);
});
secondSet.forEach(function(e){
unionSet.add(e);
});
return unionSet;
};
// this method will return the intersection of two sets as a new set
this.intersection = function(otherSet) {
var intersectionSet = new Set();
var firstSet = this.values();
firstSet.forEach(function(e){
if(otherSet.has(e)){
intersectionSet.add(e);
}
});
return intersectionSet;
};
// this method will return the difference of two sets as a new set
this.difference = function(otherSet) {
var differenceSet = new Set();
var firstSet = this.values();
firstSet.forEach(function(e){
if(!otherSet.has(e)){
differenceSet.add(e);
}
});
return differenceSet;
};
// change code below this line
// change code above this line
};
var setA = new Set();
var setB = new Set();
setA.add("a");
setB.add("b");
setB.add("c");
setB.add("a");
setB.add("d");
var subSetSetAB = setA.subset(setB);
console.log(subSetSetAB) // should be true;this.subset = function(otherSet) {
var firstSet = this.values();
var isSubset = true;
firstSet.forEach(function(e){
if(!otherSet.has(e)){
isSubset = false;
return;
}
});
return isSubset;
};@CarlJKashnier these look solid. Rather than showing the finished set as a challenge, is there a final thing campers could do to it? Otherwise, we should probably give them a heads up on exercise 7 that it's the final set challenge.
CarlJKashnier
commented
8 years ago I will delete 8 and add the note to 7.
CarlJKashnier
commented
8 years ago I'm working ES6 Sets next
CarlJKashnier
commented
8 years ago ES6 Set - Exercise 1 - Creating and adding to sets
Now we have worked through ES5, we are going to perform similar actions in ES6. This will be considerably easier. Set is now now a provided data structure like Object, Array, etc. so many of the operations we wrote by hand are now included for us. Let's take a look:
To create a new empty set:
let set = new Set();You can create a set with a value:
let set = new Set(1);You can create a set with an array:
let set = new Set([1,2,3]);Once you have created a set, you can add the values you wish using set.add:
let set = new Set([1,2,3]);
set.add([4,5,6]);For this exercise, we will return a set with the following values: 1, 2, 3, 'Taco', 'Cat', 'Awesome'
assert((function(){let test = checkSet(); let testArr = [...test]; testArr === [ 1, 2, 3, 'Taco', 'Cat', 'Awesome'])}, 'message: Your Set was returned correctly!');function checkSet(){
let set = new Set([1,2,3,3,2,1,2,3,1]);
// change code below this line
// change code above this line
console.log(set)
};
checkSet();set.add('Taco');
set.add('Cat');
set.add('Awesome');ES6 Set - Exercise 2 - Removing items from a set
Now we will see how we can remove items from an ES6 Set.
Let's create a Set:
let set = new Set([1,2,3]);Once you have created a set object, you can remove values you no longer want with delete. For example:
let set = new Set([1,2,3]);
set.delete(1);
console.log([...set]) // should return [ 2, 3 ]In this exercise we will return a Set with the passed parameter.
assert((function(){let test = checkSet(); let testArr = [...test]; testArr === [ 2, 3 ])}, 'message: Your Set was returned correctly!');function checkSet(itemToRemove){
let set = new Set([1,2,3,3,2,1,2,3,1]);
// change code below this line
// change code above this line
console.log(set)
}
checkSet(1);set.delete(itemToRemove);ES6 Set - Exercise 3 - .has and .size
Now we will look at the .has and .size methods available on the Set object.
let set = new Set([1,2,3]);
let hasTwo = set.has(2); // will return true or false
let howBig = set.size; // will return an integer representing the size of the Array
console.log("Has a 2: " + hasTwo); // should be true
console.log("Length of Set: " + howBig); // should show 3In this exercise we will pass in an array of a values and a value to check for. We will return a new array with (true or false) for the presence of the value and the size of the Set.
assert((function(){let test = checkSet([1,2,3], 2); test === [ true, 3 ])}, 'message: Your Set was returned correctly!');function checkSet(arrToBeSet, checkValue){
// change code below this line
// change code above this line
console.log(set)
}
let checkSetOutput = checkSet([1,3,5],5);
console.log(checkSetOutput)let set = Set(arrToBeSet);
let hasValue = set.has(checkValue);
let sizeOfSet = set.size;
return ([hasValue, sizeOfSet]);ES6 Set - Exercise 4 - Spread and Notes for ES5 Set() Integration.
Next up is one of the coolest things in ES6!
The noble spread operator! '...' can take iterable objects in ES6 and turn them into arrays
Let's create a Set, and check out the spread function.
let set = new Set([1,2,3]);
let setToArr = [...set]
console.log(setToArr) // returns [ 1, 2, 3 ]Awesome, right!?
In this exercise we will pass in a set object. We will return an array with the values of the Set.
The ES5 Set() function we created, can be used to perform union, intersection, difference and subset functions using the new ES6 Sets with very little modification.
assert((function(){let test = checkSet(new Set([1,2,3,4,5,6,7])); test === [ 1, 2, 3, 4, 5, 6, 7 ])}, 'message: Your Set was returned correctly!');function checkSet(set){
// change code below this line
// change code above this line
};
let checkSetOutput = checkSet(new Set([1, 2, 3, 4, 5, 6, 27]));
console.log(checkSetOutput);return [...set];Priority Queue - Methods for queuing with priority
In this challenge you will be creating a Priority Queue. A Priority Queue is a special type of Queue with one primary difference, that you can set the priority in the queue as either high represented by 0 or low represented by an integer greater than 0 during the enqueue process. Item priority will override the placement order: that is, an item enqueue with a higher priority than any preceding items will be moved to the front of the queue. If items have equal priority, then placement order will decide their dequeue order. For instance:
collection = [['taco',1]]
PriorityQueue.enqueue(['kitten', 1]);
console.log([...PriorityQueue])
// would be [['taco', 1], ['kitten', 1]]
// not [['kitten', 1], ['taco', 1]]For this challenge, you will create an object called PriorityQueue. You will need to add an enqueue method for adding items with a priority, a dequeue method for popping off the front item, a size method to return the number of items in the queue, and finally an isEmpty method that will return true or false if the queue is empty.
assert((function(){var test = new PriorityQueue(); return (typeof test.enqueue === 'function')}()), 'message: Your <code>Queue</code> class should have a <code>enqueue</code> method.');
assert((function(){var test = new PriorityQueue(); return (typeof test.denqueue === 'function')}()), 'message: Your <code>Queue</code> class should have a <code>denqueue</code> method.');
assert((function(){var test = new PriorityQueue(); return (typeof test.front === 'function')}()), 'message: Your <code>Queue</code> class should have a <code>front</code> method.');
assert((function(){var test = new PriorityQueue(); return (typeof test.size === 'function')}()), 'message: Your <code>Queue</code> class should have a <code>size</code> method.');
assert((function(){var test = new PriorityQueue(); return (typeof test.isEmpty === 'function')}()), 'message: Your <code>Queue</code> class should have a <code>isEmpty</code> method.');
assert((function(){var test = new PriorityQueue(); DMV.enqueue(['David Brown', 2]);DMV.enqueue(['Jon Snow', 1]); return ([...test]===[['Jon Snow', 1],['David Brown', 2]])}()),'message: Your code did not correctly prioritize the incoming items.')
assert((function(){var test = new PriorityQueue(); DMV.enqueue(['David Brown', 2]);DMV.enqueue(['Jon Snow', 1]); return (test.size()===2)}()),'message: Your code did not correctly add the incoming items.')
assert((function(){var test = new PriorityQueue(); DMV.enqueue(['David Brown', 2]);DMV.enqueue(['Jon Snow', 1]);DMV.dequeue(); return (test.size()===1)}()),'message: Your code did not correctly dequeue 1 item.')
assert((function(){var test = new PriorityQueue(); DMV.enqueue(['David Brown', 2]);DMV.enqueue(['Jon Snow', 1]);DMV.dequeue();DMV.dequeue(); return (DMV.isEmpty()===true)}()),'message: Your code is not correctly reporting that the queue is empty.')
assert((function(){var test = new PriorityQueue(); DMV.enqueue(['David Brown', 1]);DMV.enqueue(['Jon Snow', 1]); return ([...test]===[['David Brown', 2], ['Jon Snow', 1]])}()),'message: Your code did not correctly prioritize the incoming items. If 2 items have the same priority the older item remains infront of new items')function PriorityQueue () {
let collection = [];
this.printCollection = function(){
(console.log(collection));
};
// Only change code below this line
// Only change code above this line
}
// Test your queue class
var DMV = new PriorityQueue();
DMV.enqueue(['David Brown', 2]);
DMV.enqueue(['Jon Snow', 1]);
DMV.dequeue();
DMV.front();
DMV.isEmpty();
DMV.size();
DMV.dequeue();
DMV.isEmpty();function PriorityQueue () {
collection = [];
this.printCollection = function(){
(console.log(collection));
};
this.enqueue = function(newItem) {
if (collection.length === 0) {
collection.push(newItem);
} else {
var inserted = false;
collection = collection.reduce(function(newCollection, item) {
if (newItem[1] < item[1] && !inserted) {
newCollection.push(newItem);
inserted = true;
}
newCollection.push(item);
if (newItem[1] == item[1] && !inserted) {
newCollection.push(newItem);
inserted = true;
}
return newCollection;
}, []);
if (!inserted) {
collection.push(newItem);
}
}
return collection;
};
this.dequeue = function() {
if (collection.length > 0) {
var item = collection.shift();
return item[0];
} else {
return 'The queue is empty.';
}
};
this.front = function() {
return collection[0];
};
this.size = function() {
return collection.length;
};
this.isEmpty = function() {
return collection.length > 0 ? false : true;
};
}In this challenge you will be creating a Circular Queue. A circular queue is basically a queue that writes to the end of a collection then begins over writing itself at the beginning of the collection. This is type of data structure has some useful applications in certain situations. For example, a circular buffer can be used in streaming media. Once the queue is full, new media data simply begins to overwrite old data.
A good way to illustrate this concept is with an array:
[1, 2, 3, 4, 5]
^Read @ 0
^Write @ 0Here the read and write are both at position 0. Now the queue gets 3 new records a, b, and c. Our queue now looks like:
[a, b, c, 4, 5]
^Read @ 0
^write @ 3As the read head reads, it can remove values or keep them:
[, , , 4, 5]
^Read @ 3
^write @ 3Once the write reaches the end of the array it loops back to the beginning:
[f, , , d, e]
^Read @ 3
^write @ 1So as you can see the buffer consumes less memory, this can be useful for processing large data file conversions and prevent a memory leak from slowing down a conversion process.
Instructions:
In this challenge you will implement a 5 element circular buffer. Your component will maintain a read pointer and a write pointer. New items can be added singly or as an array of items (Hint, use Array.isArray()). New items will be added to the collection starting at position 0, advancing the write pointer. As the queue is dequeued it will delete the data and advance the read pointer. We will also create methods to return the entire queue and the front of the queue.
assert((function(){var test = new CircularQueuee(); test.enqueue('a'); test.enqueue('b'); test.enqueue('c'); test.enqueue('d'); test.enqueue('e'); test.enqueue('f'); return (test.printCollection === ['f', 'b', 'c', 'd', 'e'])}()), 'message: Your <code>Queue</code> class should have a <code>enqueue</code> method.');
assert((function(){var test = new CircularQueuee(); test.enqueue('a'); test.enqueue('b'); test.enqueue('c'); test.enqueue('d'); test.enqueue('e'); test.enqueue('f'); test.dequeue; return (test.printCollection === ['', 'b', 'c', 'd', 'e'])}()), 'message: Your <code>dequeue</code> method did not remove the first item.');function CircularQueue () {
let collection = [,,,,];//remember length of 5
this.printCollection = function(){
(console.log(collection));
return collection;
};
// Only change code below this line
// Only change code above this line
}
// Test your queue class
var CircQue = new CircularQueue();
CircQue.enqueue([1,2,3,4,5,6]);
CircQue.printCollection();//collection should look like [6,2,3,4,5]
CircQue.dequeue()
CircQue.printCollection();//collection should look like [,2,3,4,5]
CircQue.dequeue()
CircQue.printCollection();//collection should look like [,,3,4,5]
CircQue.dequeue()
CircQue.dequeue()
CircQue.front()//should return 5
CircQue.dequeue()
CircQue.front()//should return Null
CircQue.dequeue()//should not advance past WriteHeadvar readPosition = 0;
var writePosition = 0;
this.enqueue = function(item){
if (Array.isArray(item)) {
//add each
for (var i = 0; i < item.length; i++){
//write each item
collection.splice(writePosition, 1, item[i]);
//inc the pointer
writePosition++;
//back to the front if at the end
if (writePosition +1 > collection.length) {
writePosition = 0;
}
}
} else {
//add one
collection.splice(writePosition, 1, item);
//inc the pointer
writePosition++;
//back to the front if at the end
if (writePosition + 1 > collection.length) {
writePosition = 0;
}
}
}
this.dequeue = function(){
collection.splice(readPosition,1,'');
readPosition++;
if (readPosition + 1 > collection.length) {
readPosition = 0;
}
}
this.front = function(){
console.log(collection[readPosition]);
return collection[readPosition];
}
koustuvsinha
commented
8 years ago amazing work @CarlJKashnier! sorry all i am quite busy these days to contribute, but we need more contributors like him to finish this off quickly. so thanks a ton to all who have helped :smile:
alayek
commented
8 years ago @CarlJKashnier even if you don't have images, you can provide examples of what a usecase would be in real life. Or draw analogies.
Like carousel images in webpages. Or take someone's Facebook Photo album. When you reach the last image, you hit next, and you get back to the first image.
This is not to say they are implemented using circular queues. But the concept of circular queues are easier to view or imagine with known daily life examples such as these.
You are doing a great job! Just have faith in your write up. 👍
m-oliv
commented
8 years ago I'm researching the Doubly Linked Lists in order to create some challenges.
I'm thinking of including a similar set of challenges as you have for the Linked Lists. Aside from the usual add / remove / search is there anything else I should work on?
QuincyLarson
commented
8 years ago @m-oliv that sounds great. I can't think of anything else that would need to be regarding doubly linked lists covered off the top of my head.
HKuz
commented
8 years ago Hi folks, just want to give you all a head's up that for these challenges, where relevant, you can use the latest ES2016 syntax (discussed in this thread). It looks like a number already are, which is great 😄
QuincyLarson
commented
8 years ago @HKuz I don't know whether you saw this yet, but based on the results of this survey I think moving forward with our "ES6 is just JavaScript now" approach is the right thing to do http://stateofjs.com/2016/introduction/
HKuz
commented
8 years ago @QuincyLarson - I hadn't seen that survey, some interesting points in there! Also good to know about the current standard. For the challenges just in terms of long-term maintainability, if JS is on an annual update schedule, makes sense to group JS all together and layer in the latest syntax changes as they come. Otherwise that section would need to be renamed/revised each new update (or risk looking stale).
QuincyLarson
commented
8 years ago @HKuz yes - I agree. I think the Basic JavaScript section will continue to be the biggest single section of Free Code Camp. We can just cover new features as they are released. My understanding is that it will only be a few new features a year. ES6 was special in that it had years worth of planned features all piled up waiting to be released.
CarlJKashnier
commented
8 years ago The check boxes up top are out of date, can a maintainer update this, I think it is safe to start on pathing problems now. I want to write those up to help improve the quality of the dungeon crawlers.
erictleung
commented
8 years ago Challenge Description
This challenge starts a series of challenges that will teach graph data structures and some algorithms involving graphs. You may be familiar with graphs with an x- and y-axis found in your math classes. However, here graphs mean a different thing.
The data structure of
graphsare collections of things and the relationships or connections among them. Graphs are also known as networks.When talking about graphs, the precise term for "objects" are
nodesorvertices. Similarly, the precise term for "connections" isedges.One example of graphs is a social network where the
nodesare you and other people, and theedgesare whether two people are friends with each other.There are two major types of graphs:
directedandundirected. Undirected graphs are graphs without any direction on the edges between nodes. Directed graphs, in contrast, are graphs with a direction in its edges.An example of an undirected graph could be a social network. The nodes are people and the edges are friendship. An example of a directed network could be the internet and web page links. Here, the nodes are web pages and the directed edges are links to other pages, which might not necessarily point the other way.
Instructions
Click "Run tests" to go to the next challenge to find out how different ways to represent graphs in JavaScript like the one in the editor.
Challenge Seed
var undirected = {
1: [2],
2: [1]
};Challenge Tests
assert(Object.keys(undirected).length === 2, 'message: <code>undirected</code> should only contain two nodes.');Challenge Solution
var undirected = {
1: [2],
2: [1]
};Challenge Description
Graphs can be represented in different ways. Here we describe one way, which is called an
adjacency list.An adjacency list is essentially a bulleted list where the left side is the node and the right side lists all the other nodes it's connected to. Below is a representation of an adjacency list.
Node1: Node2, Node3 Node2: Node1 Node3: Node1Above is an undirected graph because
Node1is connected toNode2andNode3, and that information is consistent with the connectionsNode2andNode3show. An adjacency list for a directed graph would mean each row of the list shows direction. If the above was directed, thenNode2: Node1would mean there the directed edge is pointing fromNode2towardsNode1.We can represent the undirected graph above as an adjacency list by putting it within a JavaScript object.
var undirectedG = { Node1: ["Node2", "Node3"], Node2: ["Node1"], Node3: ["Node3"] };This can also be more simply represented as an array where the nodes just have numbers rather than string labels.
var undirectedGArr = [ [1, 2], # Node1 [0], # Node2 [2] # Node3 ];Instructions
Create a social network as an undirected graph with 4 nodes/people named
James,Jill,Jenny, andJeff. There are edges/relationships between James and Jeff, Jill and Jenny, and Jeff and Jenny.
Challenge Seed
var undirectedAdjList = {
};Challenge Tests
assert(Object.keys(undirectedAdjList).length === 4, 'message: <code>undirectedAdjList</code> should only contain four nodes.');
assert(undirectedAdjList.James.includes("Jeff") && undirectedAdjList.Jeff.includes("James"), 'message: There should be an edge between <code>Jeff</code> and <code>James</code>.');
assert(undirectedAdjList.Jill.includes("Jenny") && undirectedAdjList.Jill.includes("Jenny"), 'message: There should be an edge between <code>Jill</code> and <code>Jenny</code>.');
assert(undirectedAdjList.Jeff.includes("Jenny") && undirectedAdjList.Jenny.includes("Jeff"), 'message: There should be an edge between <code>Jeff</code> and <code>Jenny</code>.');Challenge Solution
var undirectedAdjList = {
"James": ["Jeff"],
"Jill": ["Jenny"],
"Jenny": ["Jill", "Jeff"],
"Jeff": ["James", "Jenny"]
};@erictleung awesome work! These look solid!
erictleung
commented
8 years ago Challenge Description
Another way to represent a graph is to put it in an
adjacency matrix.An
adjacency matrixis a two-dimensional (2D) array where each nested array has the same number of elements as the outer array. In other words, it is a matrix or grid of numbers, where the numbers represent the edges. Zeros mean there is no edge or relationship.1 2 3 ------ 1 | 0 1 1 2 | 1 0 0 3 | 1 0 0Above is a very simple, undirected graph where you have three nodes, where the first node is connected to the second and third node. Note: The numbers to the top and left of the matrix are just labels for the nodes.
Below is a JavaScript implementation of the same thing.
var adjMat = [ [0, 1, 1], [1, 0, 0], [1, 0, 0] ];Unlike an adjacency list, each "row" of the matrix has to have the same number of elements as nodes in the graph. Here we have a three by three matrix, which means we have three nodes in our graph.
A directed graph would look similar. Below is a graph where the first node has an edge pointing toward the second node, and then the second node has an edge pointing to the third node.
var adjMatDirected = [ [0, 1, 0], [0, 0, 1], [0, 0, 0] ];Graphs can also have
weightson their edges. So far, we haveunweightededges where just the presence and lack of edge is binary (0or1). You can have different weights depending on your application.Instructions
Create an adjacency matrix of an undirected graph with five nodes. This matrix should be in a multi-dimensional array. These five nodes have relationships between the first and fourth node, the first and third node, the third and fifth node, and the fourth and fifth node. All edge weights are one.
Challenge Seed
var adjMatUndirected = [
];Challenge Tests
assert((adjMatUndirected.length === 5) && adjMatUndirected.map(function(x) { return x.length === 5 }).reduce(function(a, b) { return a && b }) , 'message: <code>undirectedAdjList</code> should only contain five nodes.');
assert((adjMatUndirected[0][3] === 1) && (adjMatUndirected[3][0] === 1), 'message: There should be an edge between the first and fourth node.');
assert((adjMatUndirected[0][2] === 1) && (adjMatUndirected[2][0] === 1), 'message: There should be an edge between the first and third node.');
assert((adjMatUndirected[2][4] === 1) && (adjMatUndirected[4][2] === 1), 'message: There should be an edge between the third and fifth node.');
assert((adjMatUndirected[3][4] === 1) && (adjMatUndirected[4][3] === 1), 'message: There should be an edge between the fourth and fifth node.');Challenge Solution
var adjMatUndirected = [
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 1],
[0, 0, 1, 1, 0]
];Challenge Description
Yet another way to represent a graph is to put it in an
incidence matrix.An
incidence matrixis a two-dimensional (2D) array. Generally speaking, an incidence matrix relates two different classes of objects between its two dimensions. This kind of matrix is similar to an adjacency matrix. However, the rows and columns mean something else here.In graphs, we have edges and nodes. These will be our "two different classes of objects". This matrix will have the rows be the nodes and columns be the edges. This means that we can have an uneven number of rows and columns.
Each column will represent a unique edge. Also, each edge connects two nodes. To show that there is an edge between two nodes, you will put a
1in the two rows of a particular column. Below is a 3 node graph with one edge between node1and node3.1 --- 1 | 1 2 | 0 3 | 1Here is an example of an
incidence matrixwith 4 edges and 4 nodes. Remember, the columns are the edges and rows are the nodes themselves.1 2 3 4 -------- 1 | 0 1 1 1 2 | 1 1 0 0 3 | 1 0 0 1 4 | 0 0 1 0Below is a JavaScript implementation of the same thing.
var incMat = [ [0, 1, 1, 1], [1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 0] ];To make a directed graph, use
-1for an edge leaving a particular node and1for an edge entering a node.var incMatDirected = [ [ 0, -1, 1, -1], [-1, 1, 0, 0], [ 1, 0, 0, 1], [ 0, 0, -1, 0] ];Graphs can also have
weightson their edges. So far, we haveunweightededges where just the presence and lack of edge is binary (0or1). You can have different weights depending on your application. A different weight is represented as numbers greater than 1.Instructions
Create an incidence matrix of an undirected graph with five nodes and four edges. This matrix should be in a multi-dimensional array.
These five nodes have relationships following relationships. The first edge is between the first and second node. The second edge is between the second and third node. The third edge is between the third and fifth node. And four edge is between the fourth and second node. All edge weights are one and the edge order matters.
Challenge Seed
var incMatUndirected = [
];Challenge Tests
assert((incMatUndirected.length === 5) && incMatUndirected.map(function(x) { return x.length === 4 }).reduce(function(a, b) { return a && b }) , 'message: <code>undirectedAdjList</code> should only contain five nodes.');
assert((incMatUndirected[0][0] === 1) && (incMatUndirected[1][0] === 1), 'message: There should be a first edge between the first and second node.');
assert((incMatUndirected[1][1] === 1) && (incMatUndirected[2][1] === 1), 'message: There should be a second edge between the second and third node.');
assert((incMatUndirected[2][2] === 1) && (incMatUndirected[4][2] === 1), 'message: There should be a third edge between the third and fifth node.');
assert((incMatUndirected[1][3] === 1) && (incMatUndirected[3][3] === 1), 'message: There should be a fourth edge between the second and fourth node.');Challenge Solution
var incMatUndirected = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 0, 1, 0]
];Sorry for the lag time, got busy with school work :sweat_smile: Hopefully, I'll be able to finish up most of these the next few weeks.
QuincyLarson
commented
7 years ago @erictleung solid work! Thrilled that you've found time to work on these again. Our curriculum expansion process is almost finished and these data structure challenges are highly anticipated, to say the least 😄
Also, good luck finishing up your semester.
bonham000
commented
7 years ago @QuincyLarson and anyone else still watching this Issue: So I am working on several of the tree challenges at the moment and will be able to post some of them soon, however, first should we discuss different options in JavaScript for creating data structures like this? I can think of at least these five options (below) with seemingly equivalent functionality and so far some different methods are used in the current challenges written here.
1) Is there a best practice for this or does it not really matter? Someone I asked tonight said defining methods on the prototype is a good way. 2) Should we try to have all the challenges written the same way for consistently? Or should we write them differently to showcase a variety of methods?
// helper node
let Node = function(value) {
this.data = value;
this.next = null;
};
// MANY METHODS:
// 1) with ES6 class syntax
// could also optionally define the methods on the prototype here
class LinkedList {
constructor() {
this.start = null;
this.getStart = function() {
return this.start;
}
this.add = function(value) {
this.start = new Node(value);
};
};
};
// 2) just make an object
// this won't be created with the new keyword like the rest but still works
let LinkedList = {
start: null,
getStart: function() {
return this.start;
},
add: function(value) {
this.start = new Node(value);
}
};
// 3) with a function and this
let LinkedList = function() {
this.start = null;
this.getStart = function() {
return this.start;
}
this.add = function(value) {
this.start = new Node(value);
};
};
// 4) using closure to reference data
let LinkedList = function() {
let start = null;
this.getStart = function() {
return start;
};
this.add = function(value) {
start = new Node(value);
};
};
// 5) using prototype and shorthand for method declarations
let LinkedList = function() {
this.start = null;
};
LinkedList.prototype = {
getStart() {
return this.start;
},
add(value) {
this.start = new Node(value);
}
};
let List = new LinkedList();Personally I liked writing the methods on the prototype because it moves these from the actual object to behind the scenes but I really don't know what's best here.
bonham000
commented
7 years ago I took a look at the tree challenges posted above here and went to work trying to fill in the remaining ones. I've taken the existing challenges and tried to break them up into smaller pieces where I thought it was possible and also write them with an overall consistent narrative.
bonham000
commented
7 years ago Title: Find the Minimum and Maximum Value in a Binary Search Tree
Description: This series of challenges will introduce the tree data structure. Trees are an important and versatile data structure in computer science. Of course, their name comes from the fact that when visualized they look much like the trees we are familiar with in the natural world. A tree data structure begins with one node, typically referred to as the root, and from here branches out to additional nodes, each of which may have more child nodes, and so on and so forth. The data structure is usually visualized with the root node at the top; you can think of it as a natural tree flipped upside down.
First, let's describe some common terminology we will encounter with trees. The root node is the top of the tree. Data points in the tree are called nodes. Nodes with branches leading to other nodes are referred to as the parent of the node the branch leads to (the child). Other more complicated familial terms apply as you might expect. A subtree refers to all the descendants of a particular node, branches may be referred to as edges, and leaf nodes are nodes at the end of the tree that have no children. Finally, note that trees are inherently recursive data structures. That is, any children of a node are parents of their own subtree, and so on. The recursive nature of trees is important to understand when designing algorithms for common tree operations.
To begin, we will discuss a particular type of a tree, the binary tree. In fact, we will actually discuss a particular binary tree, a binary search tree. Let's describe what this means. While the tree data structure can have any number of branches at a single node, a binary tree can only have two branches for every node. Furthermore, a binary search tree is ordered with respective to the child subtrees, such that each left subtree is less than or equal to the parent node, and each right subtree is greater than or equal to the parent node. Binary search trees are very common and useful data structures because they provide logarithmic time in the average case for several common operations such as lookup, insertion, and deletion.
Instructions: We'll start simple. We've defined the skeleton of a binary search tree structure here in addition to a function to create nodes for our tree. Observe that each node may have a left and right value. These will be assigned child subtrees if they exist. In our binary search tree, define two methods,
findMin and findMax. These methods should return the minimum and maximum value held in the binary search tree. If you get stuck, reflect on the invariant that must be true for binary search trees: each left subtree is less than or equal to its parent and each right subtree is greater than or equal to
its parent. Let's also say that our tree can only store integer values. If the tree is empty, either method should return null.
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// find minimum value in tree
this.findMin = function(node = this.root) {
if (node == null) {
return null;
} else {
if (node.left == null) {
return node.value;
} else {
return this.findMin(node.left);
};
};
};
// find maximum value in tree
this.findMax = function(node = this.root) {
if (node == null) {
return null;
} else {
if (node.right == null) {
return node.value;
} else {
return this.findMax(node.right);
};
};
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
}
};// TESTS --------------------------------
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.findMin == 'function')})(), 'The binary search tree has a method called findMin.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.findMax == 'function')})(), 'The binary search tree has a method called findMax.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.findMin !== 'function') { return false; }; test.add(4); test.add(1); test.add(7); test.add(87); test.add(34); test.add(45); test.add(73); test.add(8); return test.findMin() == 1; })(), 'The findMin method returns the minimum value in the binary search tree.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.findMax !== 'function') { return false; }; test.add(4); test.add(1); test.add(7); test.add(87); test.add(34); test.add(45); test.add(73); test.add(8); return test.findMax() == 87; })(), 'The findMax method returns the maximum value in the binary search tree.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.findMin !== 'function') { return false; }; if (typeof test.findMax !== 'function') { return false; }; return (test.findMin() == null && test.findMax() == null) })(), 'The findMin and findMax methods return null for an empty tree.');Title: Add a New Element to a Binary Search Tree
Instructions: Now that we have an idea of the basics lets write a more complex method.
In this challenge, we will create a method to add new values to our binary search tree. The method should be called add and it should accept an integer value to add to the tree. Take care to maintain the invariant of a binary search tree: the value in each left child should be less than or equal to the parent value, and the value in each right child should be greater than or equal to the parent value. Here, let's make it so our tree cannot hold duplicate values. If we try to add a value that already exists, the method should return null. Otherwise, if the addition is successful, undefined should be returned.
Hint: trees are naturally recursive data structures!
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.add = function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
isBinarySearchTree() {
if (this.root == null) {
return null;
} else {
let check = true;
function checkTree(node) {
if (node.left != null) {
let left = node.left;
if (left.value > node.value) {
check = false;
} else {
checkTree(left);
}
}
if (node.right != null) {
let right = node.right;
if (right.value < node.value) {
check = false;
} else {
checkTree(right);
};
};
};
checkTree(this.root);
return check;
};
}
};// TESTS --------------------------------
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.add == 'function')})(), 'The binary search tree has a method called add.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.add !== 'function') { return false; }; test.add(4); test.add(1); test.add(7); test.add(87); test.add(34); test.add(45); test.add(73); test.add(8); return (test.isBinarySearchTree()); })(), 'The add method adds elements according to the binary search tree rules.')
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.add !== 'function') { return false; }; test.add(4); return test.add(4) == null; })(), 'Adding an element that already exists returns null');Title: Check if an Element is Present in a Binary Search Tree
Description: Now that we have a general sense of what a binary search tree is let's talk about it in a little more detail. Binary search trees provide logarithmic time for the common operations of lookup, insertion, and deletion in the average case, and linear time in the worst case. Why is this? Each of those basic operations requires us to find an item in the tree (or in the case of insertion to find where it should go) and because of the tree structure at each parent node we are branching left or right and effectively excluding half the size of the remaining tree. This makes the search proportional to the logarithm of the number of nodes in the tree, which creates logarithmic time for these operations in the average case.
Ok, but what about the worst case? Well, consider constructing a tree from the following values, adding them left to right: 10, 12, 17, 25. Following our rules for a binary search tree, we will add 12 to the right of 10, 17 to the right of this, and 25 to the right of this. Now our tree resembles a linked list and traversing it to find 25 would require us to traverse all the items in linear fashion. Hence, linear time in the worst case. The problem here is that the tree is unbalanced. We'll look a little more into what this means in the following challenges.
Instructions: In this challenge, we will create a utility for our tree. Write a method isPresent which takes an integer value as input and returns a boolean value for the presence or absence of that value in the binary search tree.
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.isPresent = function(element) {
if (this.root != null) {
function searchTree(node) {
if (element == node.value) {
return true;
} else if (element < node.value) {
if (node.left != null) {
return searchTree(node.left);
} else {
return false;
};
} else {
if (node.right != null) {
return searchTree(node.right);
} else {
return false;
};
};
};
return searchTree(this.root);
} else {
return false;
};
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
}
};
// TESTS --------------------------------
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.isPresent == 'function')})(), 'The binary search tree has a method called isPresent.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.isPresent !== 'function') { return false; }; test.add(4); test.add(7); test.add(411); test.add(452); return ( test.isPresent(452) && test.isPresent(411) && test.isPresent(7) && !test.isPresent(100) ); })(), 'The isPresent method correctly checks for the presence of absence of elements added to the tree.')
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.isPresent !== 'function') { return false; }; return test.isPresent(5) == false; })(), 'isPresent handles cases where the tree is empty.');Title: Find the Minimum and Maximum Height of a Binary Search Tree
Description: In the last challenge we described a scenario in which a tree could become unbalanced. To understand the concept of balance, let's take a look at another tree property: height. Height in a tree represents the distance from the root node to any given leaf node. Different paths in a highly branched tree structure may have different heights, but for a given tree there will be a minimum and maximum height. If the tree is balanced, these values will differ at most by one. This means that in a balanced tree, all the leaf nodes exist within the same level, or if they are not within the same level they are at most one level apart.
The property of balance is important for trees because it is what determines the efficiency of tree operations. As we explained in the last challenge, we face worst case time complexity for heavily unbalanced trees. Self-balancing trees are commonly used to account for this issue in trees with dynamic data sets. Common examples of these include AVL trees, red-black trees, and B-trees. These trees all contain additional internal logic which re-balance the tree when insertions or deletions create a state of imbalance.
Note: A similar property to height is depth, which refers to how far a given node is from the root node.
Instructions: Write two methods for our binary tree: findMinHeight and findMaxHeight. These methods should return an integer value for the minimum and maximum height within a given binary tree, respectively. If the node is empty let's assign it a height of -1 (that's the base case). Finally, add a third method isBalanced which returns a true or false depending on whether the tree is balanced or not. You can use the first two methods you just wrote to determine this.
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.isBalanced = () => (this.findMinHeight() > this.findMaxHeight() - 1) ? false : true;
this.findMinHeight = function(node = this.root) {
if (node == null) {
return -1;
};
let left = this.findMinHeight(node.left);
let right = this.findMinHeight(node.right);
if (left < right) {
return left + 1;
} else {
return right + 1;
};
};
this.findMaxHeight = function(node = this.root) {
if (node == null) {
return -1;
};
let left = this.findMaxHeight(node.left);
let right = this.findMaxHeight(node.right);
if (left > right) {
return left + 1;
} else {
return right + 1;
};
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
}
};// TESTS --------------------------------
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.findMinHeight == 'function')})(), 'The binary search tree has a method called findMinHeight.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.findMaxHeight == 'function')})(), 'The binary search tree has a method called findMaxHeight.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.isBalanced == 'function')})(), 'The binary search tree has a method called isBalanced.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.findMinHeight !== 'function') { return false; }; test.add(4); test.add(1); test.add(7); test.add(87); test.add(34); test.add(45); test.add(73); test.add(8); return (test.findMinHeight() == 1); })(), 'The findMinHeight method returns the minimum height of the tree.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.findMaxHeight !== 'function') { return false; }; test.add(4); test.add(1); test.add(7); test.add(87); test.add(34); test.add(45); test.add(73); test.add(8); return (test.findMaxHeight() == 5); })(), 'The findMaxHeight method returns the maximum height of the tree.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.findMaxHeight !== 'function') { return false; }; return (test.findMaxHeight() == -1); })(), 'An empty tree returns a height of -1.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.isBalanced !== 'function') { return false; }; test.add(4); test.add(1); test.add(7); test.add(87); test.add(34); test.add(45); test.add(73); test.add(8); return test.isBalanced(); })(), 'The isBalanced method returns true if the tree is a balanced binary search tree.');Title: Use Depth First Search in a Binary Search Tree
Description: We know how to search a binary search tree for a specific value. But what if we just want to explore the entire tree? Or what if we don't have an ordered tree and we need to just search for a value? Here we will introduce some tree traversal methods which can be used to explore tree data structures. First up is depth-first search. In depth-first search, a given subtree is explored as deeply as possible before the search continues on to another subtree. There are three ways this can be done:
As you may guess, you may choose different search methods depending on what type of data your tree is storing and what you are looking for. For a binary search tree, an inorder traversal returns the nodes in sorted order.
Instructions: Here we will create these three search methods on our binary search tree. Depth-first search is an inherently recursive operation which continues to explore further subtrees so long as child nodes are present. Once you understand this basic concept, you can simply rearrange the order in which you explore the nodes and subtrees to produce any of the three searches above. For example, in post-order search we would want to recurse all the way to a leaf node before we begin to return any of the nodes themselves, whereas in pre-order search we would want to return the nodes first, and then continue recursing down the tree.
Define inorder, preorder, and postorder methods on our tree. Each of these methods should return an array of items which represent the tree traversal. Be sure to return the integer values at each node in the array, not the nodes themselves. Finally, return null if the tree is empty.
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.inorder = function() {
if (this.root == null) {
return null;
} else {
var result = new Array();
function traverseInOrder(node) {
if (node.left != null) {
traverseInOrder(node.left);
};
result.push(node.value);
if (node.right != null) {
traverseInOrder(node.right);
};
}
traverseInOrder(this.root);
return result;
};
};
this.preorder = function() {
if (this.root == null) {
return null;
} else {
var result = new Array();
function traversePreOrder(node) {
result.push(node.value);
if (node.left != null) {
traversePreOrder(node.left);
};
if (node.right != null) {
traversePreOrder(node.right);
};
};
traversePreOrder(this.root);
return result;
};
};
this.postorder = function(node, arr) {
if (this.root == null) {
return null;
} else {
var result = new Array();
function traversePostOrder(node) {
if (node.left != null) {
traversePostOrder(node.left);
}
if (node.right != null) {
traversePostOrder(node.right);
}
result.push(node.value);
};
traversePostOrder(this.root);
return result;
}
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
}
};// TESTS
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.inorder == 'function')})(), 'The binary search tree has a method called inorder.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.preorder == 'function')})(), 'The binary search tree has a method called preorder.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.postorder == 'function')})(), 'The binary search tree has a method called postorder.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.inorder !== 'function') { return false; }; test.add(7); test.add(1); test.add(9); test.add(0); test.add(3); test.add(8); test.add(10); test.add(2); test.add(5); test.add(4); test.add(6); return (test.inorder().join('') == '012345678910'); })(), 'The inorder method returns an array of the node values that result from an inorder traversal.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.preorder !== 'function') { return false; }; test.add(7); test.add(1); test.add(9); test.add(0); test.add(3); test.add(8); test.add(10); test.add(2); test.add(5); test.add(4); test.add(6); return (test.preorder().join('') == '710325469810'); })(), 'The preorder method returns an array of the node values that result from a preorder traversal.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.postorder !== 'function') { return false; }; test.add(7); test.add(1); test.add(9); test.add(0); test.add(3); test.add(8); test.add(10); test.add(2); test.add(5); test.add(4); test.add(6); return (test.postorder().join('') == '024653181097'); })(), 'The postorder method returns an array of the node values that result from a postorder traversal.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.inorder !== 'function') { return false; }; return (test.inorder() == null); })(), 'The inorder method returns null for an empty tree.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.preorder !== 'function') { return false; }; return (test.preorder() == null); })(), 'The preorder method returns null for an empty tree.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.postorder !== 'function') { return false; }; return (test.postorder() == null); })(), 'The postorder method returns null for an empty tree.');Title: Use Breadth First Search in a Binary Search Tree
Description: Here we will introduce another tree traversal method: breadth-first search. In contrast to the depth-first search methods from the last challenge, breadth-first search explores all the nodes in a given level within a tree before continuing on to the next level. Typically, queues are utilized as helper data structures in the design of breadth-first search algorithms.
In this method, we start by adding the root node to a queue. Then we begin a loop where we dequeue the first item in the queue, add it to a new array, and then inspect both its child subtrees. If it's children are not null, they are each enqueued. This process continues until the queue is empty.
Instructions: Let's create a breadth-first search method in our tree called levelOrder. This method should return an array containing the values of all the tree nodes, explored in a breadth-first manner. Be sure to return the values in the array, not the nodes themselves. A level should be
traversed from left to right. Next, let's write a similar method called reverseLevelOrder which performs the same search but in the reverse direction (right to left) at each level.
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.levelOrder = function() {
let result = [];
let Q = [];
if (this.root != null) {
Q.push(this.root);
while(Q.length > 0) {
let node = Q.shift();
result.push(node.value);
if (node.left != null) {
Q.push(node.left);
};
if (node.right != null) {
Q.push(node.right);
};
};
return result;
} else {
return null;
};
};
this.reverseLevelOrder = function() {
let result = [];
let Q = [];
if (this.root != null) {
Q.push(this.root);
while (Q.length > 0) {
let node = Q.shift();
result.push(node.value);
if (node.right != null) {
Q.push(node.right);
};
if (node.left != null) {
Q.push(node.left);
};
};
return result;
} else {
return null
};
}
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
}
};// TESTS --------------------------------
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.levelOrder == 'function')})(), 'The binary search tree has a method called levelOrder.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.reverseLevelOrder == 'function')})(), 'The binary search tree has a method called reverseLevelOrder.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.levelOrder !== 'function') { return false; }; test.add(7); test.add(1); test.add(9); test.add(0); test.add(3); test.add(8); test.add(10); test.add(2); test.add(5); test.add(4); test.add(6); return (test.levelOrder().join('') == '719038102546'); })(), 'The levelOrder method returns an array of the tree node values explored in level order.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.reverseLevelOrder !== 'function') { return false; }; test.add(7); test.add(1); test.add(9); test.add(0); test.add(3); test.add(8); test.add(10); test.add(2); test.add(5); test.add(4); test.add(6); return (test.reverseLevelOrder().join('') == '791108305264'); })(), 'The reverseLevelOrder method returns an array of the tree node values explored in reverse level order.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.levelOrder !== 'function') { return false; }; return (test.levelOrder() == null); })(), 'The levelOrder method returns null for an empty tree.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.reverseLevelOrder !== 'function') { return false; }; return (test.reverseLevelOrder() == null); })(), 'The reverseLevelOrder method returns null for an empty tree.');Title: Delete a Leaf Node in a Binary Search Tree
Description: This is the first of three challenges where we will implement a more difficult operation in binary search trees: deletion. Deletion is difficult because removing nodes breaks links in the tree. These links must be carefully reestablished to ensure the binary tree structure is maintained. For some deletions, this means the tree must be rearranged. In general, you will encounter one of three cases when trying to delete a node:
1) Leaf Node: The target to delete has zero children. 2) One Child: The target to delete only has one child. 3) Two Children: The target to delete has two child nodes.
Removing a leaf node is easy, we simply remove it. Deleting a node with one child is also relatively easy, we simply remove it and link its parent to child of the node we deleted. Removing a node with two children is more difficult, however, because this creates two child nodes that need to be reconnected to the parent tree. We'll see how to deal with this case in the third challenge. Additionally, you need to be mindful of some edge cases when handling deletion. What if the tree is empty? What if the node to delete is the root node? What if there are only two elements in the tree? For now, let's handle the first case where we delete a leaf node.
Instructions: Create a method on our binary tree called remove. We'll build the logic for our deletion operation in here. First, you'll want to create a function within remove that finds the node we are trying to delete in the current tree. If the node is not present in the tree, remove should return null. Now, if the target node is a leaf node with no children, then the parent reference to it should be set to null. This effectively deletes the node from the tree. To do this, you will have to keep track of
the parent of the node we are trying to delete as well. It will also be useful to create a way to track the number of children the target node has, as this will determine which case our deletion falls under.
We will handle the second and third cases in the next challenges. Good luck!
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// case 1: target has no children, change code below this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.remove = function(value) {
if (this.root == null) {
return null;
};
let target;
let parent = null;
// find the target value and its parent
(function findValue(node = this.root) {
if (value == node.value) {
target = node;
} else if (value < node.value && node.left != null) {
parent = node;
return findValue(node.left);
} else if (value < node.value && node.left == null) {
return null;
} else if (value > node.value && node.right != null) {
parent = node;
return findValue(node.right);
} else {
return null;
};
}).bind(this)();
if (target == null) {
return null;
}
// count the children of the target to delete
let children = (target.left != null ? 1 : 0) + (target.right != null ? 1 : 0);
// case 1: target has no children
if (children == 0) {
if (target == this.root) {
this.root = null;
}
else {
if (parent.left == target) {
parent.left = null;
} else {
parent.right = null;
};
};
}
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
},
inorder: function() {
if (this.root == null) {
return null;
} else {
var result = new Array();
function traverseInOrder(node) {
if (node.left != null) {
traverseInOrder(node.left);
};
result.push(node.value);
if (node.right != null) {
traverseInOrder(node.right);
};
}
traverseInOrder(this.root);
return result;
};
},
isBinarySearchTree() {
if (this.root == null) {
return null;
} else {
let check = true;
function checkTree(node) {
if (node.left != null) {
let left = node.left;
if (left.value > node.value) {
check = false;
} else {
checkTree(left);
}
}
if (node.right != null) {
let right = node.right;
if (right.value < node.value) {
check = false;
} else {
checkTree(right);
};
};
};
checkTree(this.root);
return check;
}
}
};// TESTS --------------------------------
// general tests:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.remove == 'function')})(), 'The binary search tree has a method called remove.');
// tests for case 1:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; return (test.remove(100) == null); })(), 'Trying to remove an element that doesn\'t exist returns null.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(500); test.remove(500); return (test.inorder() == null); })(), 'If the root node has no children, deleting it sets the root to null.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(5); test.add(3); test.add(7); test.add(6); test.add(10); test.add(12); test.remove(3); test.remove(12); test.remove(10); return (test.inorder().join('') == '567'); })(), 'The remove method removes leaf nodes from the tree');Title: Delete a Node with One Child in a Binary Search Tree
Description: Now that we can delete leaf nodes let's move on to the second case: deleting a node with one child. For this case, say we have a tree with the following nodes 1 — 2 — 3 where 1 is the root. To delete 2, we simply need to make the right reference in 1 point to 3. More generally,
to delete a node with only one child, we make that node's parent reference the next node in the tree.
Instructions: We've provided some code in our remove method that accomplishes the tasks from the last challenge. We find the target to delete and its parent and define the number of children
the target node has. Let's add the next case here for target nodes with only one child. Here, we'll have to determine if the single child is a left or right branch in the tree and then set the correct reference in the parent to point to this node. In addition, let's account for the case where the target is the root node (this means the parent node will be null). Feel free to replace all the starter code with your own as long as it passes the tests.
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.remove = function(value) {
if (this.root == null) {
return null;
};
let target;
let parent = null;
// find the target value and its parent
(function findValue(node = this.root) {
if (value == node.value) {
target = node;
} else if (value < node.value && node.left != null) {
parent = node;
return findValue(node.left);
} else if (value < node.value && node.left == null) {
return null;
} else if (value > node.value && node.right != null) {
parent = node;
return findValue(node.right);
} else {
return null;
};
}).bind(this)();
if (target == null) {
return null;
}
// count the children of the target to delete
let children = (target.left != null ? 1 : 0) + (target.right != null ? 1 : 0);
// case 1: target has no children
if (children == 0) {
if (target == this.root) {
this.root = null;
}
else {
if (parent.left == target) {
parent.left = null;
} else {
parent.right = null;
};
};
}
// case 2: target has one child, change code below this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.remove = function(value) {
if (this.root == null) {
return null;
};
let target;
let parent = null;
// find the target value and its parent
(function findValue(node = this.root) {
if (value == node.value) {
target = node;
} else if (value < node.value && node.left != null) {
parent = node;
return findValue(node.left);
} else if (value < node.value && node.left == null) {
return null;
} else if (value > node.value && node.right != null) {
parent = node;
return findValue(node.right);
} else {
return null;
};
}).bind(this)();
if (target == null) {
return null;
}
// count the children of the target to delete
let children = (target.left != null ? 1 : 0) + (target.right != null ? 1 : 0);
// case 1: target has no children
if (children == 0) {
if (target == this.root) {
this.root = null;
}
else {
if (parent.left == target) {
parent.left = null;
} else {
parent.right = null;
};
};
}
// case 2: target has one child
else if (children == 1) {
let newChild = (target.left != null) ? target.left : target.right;
if (parent == null) {
target.value = newChild.value;
target.left = null;
target.right = null;
} else if (newChild.value < parent.value) {
parent.left = newChild;
} else {
parent.right = newChild;
}
target = null;
}
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
},
inorder: function() {
if (this.root == null) {
return null;
} else {
var result = new Array();
function traverseInOrder(node) {
if (node.left != null) {
traverseInOrder(node.left);
};
result.push(node.value);
if (node.right != null) {
traverseInOrder(node.right);
};
}
traverseInOrder(this.root);
return result;
};
},
isBinarySearchTree() {
if (this.root == null) {
return null;
} else {
let check = true;
function checkTree(node) {
if (node.left != null) {
let left = node.left;
if (left.value > node.value) {
check = false;
} else {
checkTree(left);
}
}
if (node.right != null) {
let right = node.right;
if (right.value < node.value) {
check = false;
} else {
checkTree(right);
};
};
};
checkTree(this.root);
return check;
}
}
};// TESTS --------------------------------
// general tests:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.remove == 'function')})(), 'The binary search tree has a method called remove.');
// tests for case 1:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; return (test.remove(100) == null); })(), 'Trying to remove an element that doesn\'t exist returns null.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(500); test.remove(500); return (test.inorder() == null); })(), 'If the root node has no children, deleting it sets the root to null.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(5); test.add(3); test.add(7); test.add(6); test.add(10); test.add(12); test.remove(3); test.remove(12); test.remove(10); return (test.inorder().join('') == '567'); })(), 'The remove method removes leaf nodes from the tree');
// tests for case 2:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(-1); test.add(3); test.add(7); test.add(16); test.remove(16); test.remove(7); test.remove(3); return (test.inorder().join('') == '-1'); })(), 'The remove method removes nodes with one child.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(15); test.add(27); test.remove(15); return (test.inorder().join('') == '27'); })(), 'Removing the root in a tree with two nodes sets the second to be the root.');Title: Delete a Node with Two Children in a Binary Search Tree
Description: Removing nodes that have two children is the hardest case to implement. Removing a node like this produces two subtrees that are no longer connected to the original tree structure. How can we reconnect them? One method is to find the smallest value in the right subtree of the target node and replace the target node with this value. Selecting the replacement in this way ensures that it is greater than every node in the left subtree it becomes the new parent of but also less than every node in the right subtree it becomes the new parent of.
Once this replacement is made the replacement node must be removed from the right subtree. Even this operation is tricky because the replacement may be a leaf or it may itself be the parent of a right subtree. If it is a leaf we must remove its parent's reference to it. Otherwise, it must be the right child of the target. In this case, we must replace the target value with the replacement value and make the target reference the replacement's right child.
Instructions: Let's finish our remove method by handling the third case. We've provided some code again for the first two cases. Add some code now to handle target nodes with two children. Any edge cases to be aware of? What if the tree has only three nodes? Once you are finished this will complete our deletion operation for binary search trees. Nice job, this is a pretty hard problem!
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.remove = function(value) {
if (this.root == null) {
return null;
};
let target;
let parent = null;
// find the target value and its parent
(function findValue(node = this.root) {
if (value == node.value) {
target = node;
} else if (value < node.value && node.left != null) {
parent = node;
return findValue(node.left);
} else if (value < node.value && node.left == null) {
return null;
} else if (value > node.value && node.right != null) {
parent = node;
return findValue(node.right);
} else {
return null;
};
}).bind(this)();
if (target == null) {
return null;
}
// count the children of the target to delete
let children = (target.left != null ? 1 : 0) + (target.right != null ? 1 : 0);
// case 1: target has no children
if (children == 0) {
if (target == this.root) {
this.root = null;
}
else {
if (parent.left == target) {
parent.left = null;
} else {
parent.right = null;
};
};
}
// case 2: target has one child
else if (children == 1) {
let newChild = (target.left != null) ? target.left : target.right;
if (parent == null) {
target.value = newChild.value;
target.left = null;
target.right = null;
} else if (newChild.value < parent.value) {
parent.left = newChild;
} else {
parent.right = newChild;
}
target = null;
}
// case 3: target has two children, change code below this line
};
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.remove = function(value) {
if (this.root == null) {
return null;
};
let target;
let parent = null;
// find the target value and its parent
(function findValue(node = this.root) {
if (value == node.value) {
target = node;
} else if (value < node.value && node.left != null) {
parent = node;
return findValue(node.left);
} else if (value < node.value && node.left == null) {
return null;
} else if (value > node.value && node.right != null) {
parent = node;
return findValue(node.right);
} else {
return null;
};
}).bind(this)();
if (target == null) {
return null;
}
// count the children of the target to delete
let children = (target.left != null ? 1 : 0) + (target.right != null ? 1 : 0);
// case 1: target has no children
if (children == 0) {
if (target == this.root) {
this.root = null;
}
else {
if (parent.left == target) {
parent.left = null;
} else {
parent.right = null;
};
};
}
// case 2: target has one child
else if (children == 1) {
let newChild = (target.left != null) ? target.left : target.right;
if (parent == null) {
target.value = newChild.value;
target.left = null;
target.right = null;
} else if (newChild.value < parent.value) {
parent.left = newChild;
} else {
parent.right = newChild;
}
target = null;
}
// case 3: target has two children
else if (children == 2) {
let replacementParent = null;
// replace target with minimum value in right subtree
function findMin(node) {
if (node.left == null) {
return node;
} else {
replacementParent = node;
return findMin(node.left);
};
};
let replacement = findMin(target.right);
if (replacement.left == null && replacement.right == null) {
target.value = replacement.value;
if (replacementParent != null) {
replacementParent.left = null;
} else {
target.right = null;
}
} else {
target.value = replacement.value;
target.right = replacement.right;
replacement = null;
};
}
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
},
inorder: function() {
if (this.root == null) {
return null;
} else {
var result = new Array();
function traverseInOrder(node) {
if (node.left != null) {
traverseInOrder(node.left);
};
result.push(node.value);
if (node.right != null) {
traverseInOrder(node.right);
};
}
traverseInOrder(this.root);
return result;
};
},
isBinarySearchTree() {
if (this.root == null) {
return null;
} else {
let check = true;
function checkTree(node) {
if (node.left != null) {
let left = node.left;
if (left.value > node.value) {
check = false;
} else {
checkTree(left);
}
}
if (node.right != null) {
let right = node.right;
if (right.value < node.value) {
check = false;
} else {
checkTree(right);
};
};
};
checkTree(this.root);
return check;
}
}
};// TESTS --------------------------------
// general tests:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.remove == 'function')})(), 'The binary search tree has a method called remove.');
// tests for case 1:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.remove == 'function') ? (test.remove(100) == null) : false})(), 'Trying to remove an element that doesn\'t exist returns null.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; test.add(500); test.remove(500); return (typeof test.remove == 'function') ? (test.inorder() == null) : false})(), 'If the root node has no children, deleting it sets the root to null.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; test.add(5); test.add(3); test.add(7); test.add(6); test.add(10); test.add(12); test.remove(3); test.remove(12); test.remove(10); return (typeof test.remove == 'function') ? (test.inorder().join('') == '567') : false})(), 'The remove method removes leaf nodes from the tree');
// tests for case 2:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(-1); test.add(3); test.add(7); test.add(16); test.remove(16); test.remove(7); test.remove(3); return (test.inorder().join('') == '-1'); })(), 'The remove method removes nodes with one child.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(15); test.add(27); test.remove(15); return (test.inorder().join('') == '27'); })(), 'Removing the root in a tree with two nodes sets the second to be the root.');
// tests for case 3:
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(1); test.add(4); test.add(3); test.add(7); test.add(9); test.add(11); test.add(14); test.add(15); test.add(19); test.add(50); test.remove(9); if (!test.isBinarySearchTree()) { return false; }; test.remove(11); if (!test.isBinarySearchTree()) { return false; }; test.remove(14); if (!test.isBinarySearchTree()) { return false; }; test.remove(19); if (!test.isBinarySearchTree()) { return false; }; test.remove(3); if (!test.isBinarySearchTree()) { return false; }; test.remove(50); if (!test.isBinarySearchTree()) { return false; }; test.remove(15); if (!test.isBinarySearchTree()) { return false; }; return (test.inorder().join('') == '147'); })(), 'The remove method removes nodes with two children while maintaining the binary search tree structure.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.remove !== 'function') { return false; }; test.add(100); test.add(50); test.add(300); test.remove(100); return (test.inorder().join('') == 50300); })(), 'The root can be removed on a tree of three nodes.');Title: Invert a Binary Tree
Instructions: Here will we create a function to invert a binary tree. Given a binary tree, we want to produce a new tree that is equivalently the mirror image of this tree. Running an inorder traversal on an inverted tree will explore the nodes in reverse order when compared to the inorder traversal of the original tree. Write a method to do this called invert on our binary tree. Calling this method should invert the current tree structure. Ideally, we would like to do this in-place in linear time. That is, we only visit each node once and we modify the existing tree structure as we go, without using any additional memory. Good luck!
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
};// SEED CODE --------------------------------
function BinarySearchTree() {
this.root = null;
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
function BinarySearchTree() {
this.root = null;
this.invert = function(node = this.root) {
if (node == null) {
return null;
} else {
[node.left, node.right] = [node.right, node.left];
this.invert(node.left);
this.invert(node.right);
};
};
};// TAIL CODE --------------------------------
BinarySearchTree.prototype = {
add: function(value) {
let node = this.root;
if (node == null) {
this.root = new Node(value);
return;
} else {
function searchTree(node) {
if (value < node.value) {
if (node.left == null) {
node.left = new Node(value);
return;
} else if (node.left != null) {
return searchTree(node.left)
};
} else if (value > node.value) {
if (node.right == null) {
node.right = new Node(value);
return;
} else if (node.right != null) {
return searchTree(node.right);
};
} else {
return null;
};
};
return searchTree(node);
};
},
inorder: function() {
if (this.root == null) {
return null;
} else {
var result = new Array();
function traverseInOrder(node) {
if (node.left != null) {
traverseInOrder(node.left);
};
result.push(node.value);
if (node.right != null) {
traverseInOrder(node.right);
};
}
traverseInOrder(this.root);
return result;
};
}
};// TESTS --------------------------------
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() }; return (typeof test == 'object')})(), 'The BinarySearchTree data structure exists.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; return (typeof test.invert == 'function')})(), 'The binary search tree has a method called invert.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.invert !== 'function') { return false; }; test.add(4); test.add(1); test.add(7); test.add(87); test.add(34); test.add(45); test.add(73); test.add(8); test.invert(); return test.inorder().join('') == '877345348741'; })(), 'The invert method correctly inverts the tree structure.');
assert((function() { let test = false; if (typeof BinarySearchTree !== 'undefined') { test = new BinarySearchTree() } else { return false; }; if (typeof test.invert !== 'function') { return false; }; return (test.invert() == null); })(), 'Inverting an empty tree returns null.');Title: Create a Trie Search Tree
Description: Here we will move on from binary search trees and take a look at another type of tree structure called a trie. A trie is an ordered search tree commonly used to hold strings, or more generically associative arrays or dynamic datasets in which the keys are strings. They are very good at storing sets of data when many keys will have overlapping prefixes, for example, all the words in a dictionary.
Unlike a binary tree, nodes are not associated with actual values. Instead, the path to a node represents a specific key. For instance, if we wanted to store the string code in a trie, we would have four nodes, one for each letter: c — o — d — e. Following that path through all these nodes will then create code as a string — that path is the key we stored. Then, if we wanted to add the string coding, it would share the first three nodes of code before branching away after the d. In this way, large datasets can be stored very compactly. In addition, search can be very quick because it is effectively limited to the length of the string you are storing. Furthermore, unlike binary trees a node can store any number of child nodes.
As you might have guessed from the above example, some metadata is commonly stored at nodes that hold the end of a key so that on later traversals that key can still be retrieved. For instance, if we added codes in our example above we would need some way to know that the e in code represents the end of a key that was previously entered. Otherwise, this information would effectively be lost when we add codes.
Instructions: Let's create a trie to store words. It will accept words through an add method and store these in a trie data structure. It will also allow us to query if a given string is a word with an isWord method, and retrieve all the words entered into the trie with a print method. isWord should return a
boolean value and print should return an array of all these words as string values.
In order for us to verify that this data structure is implemented correctly, we've provided a Node structure for each node in the tree. Each node will be an object with a keys property which is a JavaScript Map object. This will hold the individual letters that are valid keys of each node. We've also
created an end property on the nodes that can be set to true if the node represents the termination of a word.
// HELPER CODE --------------------------------
const displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));// SEED CODE --------------------------------
let Node = function() {
this.keys = new Map();
this.end = false;
this.setEnd = function() {
this.end = true;
};
this.isEnd = function() {
return this.end;
};
};
let Trie = function() {
// change code below this line
// change code above this line
};// SOLUTION CODE --------------------------------
let Node = function() {
this.keys = new Map();
this.end = false;
this.setEnd = function() {
this.end = true;
};
this.isEnd = function() {
return this.end;
};
};
let Trie = function() {
this.root = new Node();
this.add = function(input, node = this.root) {
if (input.length == 0) {
node.setEnd();
return;
} else if (!node.keys.has(input[0])) {
node.keys.set(input[0], new Node(input[0]));
return this.add(input.substr(1), node.keys.get(input[0]));
} else {
return this.add(input.substr(1), node.keys.get(input[0]));
};
};
this.isWord = function(word) {
let node = this.root;
while (word.length > 1) {
if (!node.keys.has(word[0])) {
return false;
} else {
node = node.keys.get(word[0]);
word = word.substr(1);
};
};
return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
};
this.print = function() {
let words = new Array();
let search = function(node = this.root, string) {
if (node.keys.size != 0) {
for (let letter of node.keys.keys()) {
search(node.keys.get(letter), string.concat(letter));
};
if (node.isEnd()) {
words.push(string);
};
} else {
string.length > 0 ? words.push(string) : undefined;
return;
};
};
search(this.root, new String());
return words.length > 0 ? words : null;
};
};// TESTS:
assert((function testTrie() { let test = false; if (typeof Trie !== 'undefined') { test = new Trie() } else { return false; }; return (typeof test.add == 'function') }()), 'The Trie has an add method.');
assert((function testTrie() { let test = false; if (typeof Trie !== 'undefined') { test = new Trie() } else { return false; }; return (typeof test.print == 'function') }()), 'The Trie has a print method.');
assert((function testTrie() { let test = false; if (typeof Trie !== 'undefined') { test = new Trie() } else { return false; }; return (typeof test.isWord == 'function') }()), 'The Trie has an isWord method.');
assert((function testTrie() { let test = false; if (typeof Trie !== 'undefined') { test = new Trie() } else { return false; }; test.add('jump'); test.add('jumps'); test.add('jumped'); test.add('house'); test.add('mouse'); let added = test.print(); return (added.indexOf('jump') != -1 && added.indexOf('jumps') != -1 && added.indexOf('jumped') != -1 && added.indexOf('house') != -1 && added.indexOf('mouse') != -1 && added.length == 5); }()), 'The print method returns all items added to the trie as strings in an array.');
assert((function testTrie() { let test = false; if (typeof Trie !== 'undefined') { test = new Trie() } else { return false; }; test.add('hop'); test.add('hops'); test.add('hopped'); test.add('hoppy'); test.add('hope'); return (test.isWord('hop') && !test.isWord('ho') && test.isWord('hopped') && !test.isWord('hopp') && test.isWord('hoppy') && !test.isWord('hoping')); }()), 'The isWord method returns true only for words added to the trie and false for all other words.');@bonham000 wow - excellent work! You did a great job of describing terminology in a fairly lay-accessible way, too.
You've covered a number of common data structure interview questions here, and are making fast progress.
Regarding your question yesterday:
1) Is there a best practice for this or does it not really matter? Someone I asked tonight said defining methods on the prototype is a good way. 2) Should we try to have all the challenges written the same way for consistently? Or should we write them differently to showcase a variety of methods?
There are good arguments for both of these approaches. I personally think that keeping things consistent will make it easier for campers to focus on the task at hand. This is better for moral, as it's easier for them to get into the groove.
bonham000
commented
7 years ago Title: Implement Bubble Sort
Description: This is the first of several challenges on sorting algorithms. Given an array of unsorted items, we want to be able to return a sorted array. We will see several different methods to do this and learn some tradeoffs between these different approaches. While most modern languages have built-in sorting methods for operations like this, it is still important to understand some of the common basic approaches and learn how they can be implemented.
Here we will see bubble sort. The bubble sort method starts at the beginning of an unsorted array and 'bubbles up' unsorted values towards the end, iterating through the array until it is completely sorted. It does this by comparing adjacent items and swapping them if they are out of order. The method continues looping through the array until no swaps occur at which point the array is sorted. This method requires multiple iterations through the array and for average and worst cases has quadratic time complexity. While simple, it is usually impractical in most situations.
Instructions: Write a function bubbleSort which takes an array of integers as input and returns an array of these integers in sorted order. We've provided a helper method to generate a random array of integer values.
// SEED CODE
// generate a randomly filled array
let array = new Array();
(function createArray(size = 5) {
array.push(+(Math.random() * 100).toFixed(0));
return (size > 1) ? createArray(size - 1) : undefined;
})(12);
function bubbleSort(array) {
// change code below this line
// change code above this line
return array;
};// SOLUTION CODE
function bubbleSort(array) {
let current = 0;
let passed = false;
while (!passed) {
current = 0;
passed = true;
while (current < array.length - 1) {
if (array[current] > array[current + 1]) {
passed = false;
[array[current], array[current + 1]] = [array[current + 1], array[current]];
};
current++;
};
current = 0;
};
return array;
};// TAIL CODE
function isSorted(arr) {
let check = (i) => (i == arr.length - 1) ? true : (arr[i] > arr[i + 1]) ? false : check(i + 1);
return check(0);
};// tests
console.assert(typeof bubbleSort == 'function', 'bubbleSort is a function');
console.assert(isSorted(bubbleSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92])), 'bubbleSort returns a sorted array');Title: Implement Selection Sort
Description: Here we will implement selection sort. Selection sort works by selecting the minimum value in a list and swapping it with the first value in the list. It then starts at the second position, selects the smallest value in the remaining list, and swaps it with the second element. It continues iterating through the list and swapping elements until it reaches the end of the list. Now the list is sorted. Selection sort has quadratic time complexity in all cases.
Instructions: Write a function selectionSort which takes an array of integers as input and returns an array of these integers in sorted order.
// SEED CODE
// generate a randomly filled array
let array = new Array();
(function createArray(size = 5) {
array.push(+(Math.random() * 100).toFixed(0));
return (size > 1) ? createArray(size - 1) : undefined;
})(12);
function selectionSort(array) {
// change code below this line
// change code above this line
return array;
};// SOLUTION CODE
function selectionSort(array, idx = 0) {
if (idx == array.length) return array;
function findLeast(i, min) {
if (i == array.length) return min;
if (array[i] < array[min]) min = i;
return findLeast(i + 1, min);
};
let swap = findLeast(idx + 1, idx);
[array[idx], array[swap]] = [array[swap], array[idx]];
return selectionSort(array, idx + 1);
};// TAIL CODE
function isSorted(arr) {
let check = (i) => (i == arr.length - 1) ? true : (arr[i] > arr[i + 1]) ? false : check(i + 1);
return check(0);
};// tests
console.assert(typeof selectionSort == 'function', 'selectionSort is a function');
console.assert(isSorted(selectionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92])), 'selectionSort returns a sorted array');Title: Implement Insertion Sort
Description: The next sorting method we'll look at is insertion sort. This method works by building up a sorted array at the beginning of the list. It begins the sorted array with the first element. Then it inspects the next element and swaps it backwards into the sorted array until it is in sorted position. It continues iterating through the list and swapping new items backwards into the sorted portion until it reaches the end. This algorithm has quadratic time complexity in the average and worst cases.
Instructions: Write a function insertionSort which takes an array of integers as input and returns an array of these integers in sorted order.
// SEED CODE
// generate a randomly filled array
let array = new Array();
(function createArray(size = 5) {
array.push(+(Math.random() * 100).toFixed(0));
return (size > 1) ? createArray(size - 1) : undefined;
})(12);
function insertionSort(array) {
// change code below this line
// change code above this line
return array;
};// SOLUTION CODE
function insertionSort(array) {
let idx = 1;
while (idx < array.length) {
let pos = idx;
while (array[pos - 1] > array[pos]) {
[array[pos - 1], array[pos]] = [array[pos], array[pos - 1]];
pos--;
}
idx++;
}
return array;
}// TAIL CODE
function isSorted(arr) {
let check = (i) => (i == arr.length - 1) ? true : (arr[i] > arr[i + 1]) ? false : check(i + 1);
return check(0);
};// tests
console.assert(typeof insertionSort == 'function', 'insertionSort is a function');
console.assert(isSorted(insertionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92])), 'insertionSort returns a sorted array');Title: Create a Doubly Linked List
Description: All of the linked lists we've created so far are singly linked lists. Here, we'll create a doubly linked list. As the name implies, nodes in a doubly linked list have references to the next and previous node in the list. This allows us to traverse the list in both directions but it also requires more memory to be used because every node must contain an additional reference to the previous node in the list.
Instructions: We've provided a Node object and started our DoublyLinkedList. Let's
add two methods to our doubly linked list called add and remove. The add method should accept integers or strings and add them to the list and remove should accept an integer or string and remove all copies of this integer or string that exist in the list. Be careful to handle any possible edge cases when writing these methods, such as deletions for the first or last element. Also, removing any item on an empty list should return null.
Note that since we can traverse the list backwards, we can now track the tail of the list. The tail should
refer to the element most recently added.
// SEED CODE
let Node = function(data, prev) {
this.data = data;
this.prev = prev;
this.next = null;
};
let DoublyLinkedList = function() {
this.head = null;
this.tail = null;
// change code below this line
// change code above this line
};// SOLUTION CODE
let Node = function(data, prev) {
this.data = data;
this.prev = prev;
this.next = null;
};
let DoublyLinkedList = function() {
this.head = null;
this.tail = null;
this.add = function(data) {
if (this.head == null) {
this.head = new Node(data, null);
this.tail = this.head;
} else {
let node = this.head;
let prev = null;
while (node.next != null) {
prev = node;
node = node.next;
};
let newNode = new Node(data, node);
node.next = newNode;
this.tail = newNode;
};
};
this.remove = function(data) {
if (this.head == null) {
return null;
} else {
let node = this.head;
let prev = null;
while (node.next != null) {
if (node.data == data) {
let nextNode = node.next;
if (prev == null) {
nextNode.prev = null;
this.head = nextNode;
node = nextNode;
} else {
prev.next = nextNode;
nextNode.prev = prev;
node = nextNode;
}
} else {
prev = node;
node = node.next;
};
};
if (node.data == data) {
prev.next = null;
this.tail = prev;
};
};
};
};// TAIL CODE
DoublyLinkedList.prototype = {
print() {
if (this.head == null) {
return null;
} else {
let result = new Array();
let node = this.head;
while (node.next != null) {
result.push(node.data);
node = node.next;
};
result.push(node.data);
return result;
};
},
printReverse() {
if (this.tail == null) {
return null;
} else {
let result = new Array();
let node = this.tail;
while (node.prev != null) {
result.push(node.data);
node = node.prev;
};
result.push(node.data);
return result;
};
}
};// TESTS
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; return (typeof test == 'object')})(), 'The DoublyLinkedList data structure exists.');
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; if (test.add == undefined) { return false; }; return (typeof test.add == 'function')})(), 'The DoublyLinkedList has a method called add.');
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; if (test.remove == undefined) { return false; }; return (typeof test.remove == 'function')})(), 'The DoublyLinkedList has a method called remove.');
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; return (test.remove(100) == null); })(), 'Removing an item from an empty list returns null.');
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; test.add(5); test.add(6); test.add(723); return (test.print().join('') == '56723'); })(), 'The add method adds items to the list.');
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; test.add(50); test.add(68); test.add(73); return (test.printReverse().join('') == '736850'); })(), 'Each node keeps track of the previous node.');
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; test.add(25); test.add(35); test.add(60); test.remove(25); return ( test.print().join('') == '3560' ) })(), 'The first item can be removed from the list.');
assert((function() { let test = false; if (typeof DoublyLinkedList !== 'undefined') { test = new DoublyLinkedList() }; test.add(25); test.add(35); test.add(60); test.remove(60); return ( test.print().join('') == '2535' ) })(), 'The last item can be removed from the list.');
@koustuvsinha is in charge of coordinating the expansion of these challenges, but he needs your help.
For each challenge, please reply to this GitHub issue with:
Current status of challenge development: