DSA
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
const fish = ['dory', 'bruce', 'marlin', 'nemo'];
const nemo = ['nemo'];
const everyone = ['dory', 'bruce', 'marlin', 'nemo', 'gill', 'bloat', 'nigel', 'squirt', 'darla', 'hank'];
const large = new Array(10).fill('nemo');
function findNemo2(fish) {
let t0 = performance.now();
for (let i = 0; i < fish.length; i++) {
if (fish[i] === 'nemo') {
console.log('Found NEMO!');
}
}
let t1 = performance.now();
console.log("Call to find Nemo took " + (t1 - t0) + " milliseconds.");
}
findNemo2(everyone)
// What is the Big O of the below function? (Hint, you may want to go line by line)
function funChallenge(input) {
let a = 10; // O(1)
a = 50 + 3; // O(1)
for (let i = 0; i < input.length; i++) { // O(n)
anotherFunction(); // O(n)
let stranger = true; // O(n)
a++; // O(n)
}
return a; // O(1)
}
// Big O calculation - 3 + n + n + n + n = 3 + 4n -> O(3 + 4n) -> O(n)
class MyArray {
constructor() {
this.length = 0;
this.data = {};
}
get(index) {
return this.data[index];
}
push(item) {
this.data[this.length] = item;
this.length++;
return this.length;
}
pop() {
const lastItem = this.data[this.length - 1];
delete this.data[this.length - 1];
this.length--;
return lastItem;
}
delete(index) {
const item = this.data[index];
this.shiftItems(index);
return item;
}
shiftItems(index) {
for (let i = index; i < this.length - 1; i++) {
this.data[i] = this.data[i + 1];
}
delete this.data[this.length - 1];
this.length--;
}
}
class HashTable {
constructor(size){
this.data = new Array(size);
}
_hash(key) {
let hash = 0;
for (let i =0; i < key.length; i++){
hash = (hash + key.charCodeAt(i) * i) % this.data.length
}
return hash;
}
set(key, value) {
let address = this._hash(key)
if (!this.data[address]) {
this.data[address] = []
}
this.data[address].push([key, value])
//console.log(this.data)
}
get(key) {
const address = this._hash(key)
const currentBucket = this.data[address]
console.log(currentBucket)
if (currentBucket) {
for (let i=0; i < currentBucket.length; i++) {
if (currentBucket[i][0] === key) {
console.log(currentBucket[i])
return currentBucket[i][1]
}
}
}
return undefined
}
keys() {
let result = []
console.log(this.data)
for (let i=0; i < this.data.length; i++) {
if (this.data[i]) {
if (this.data[i].length > 1) {
for (let j=0; j < this.data[i].length; j++) {
result.push(this.data[i][j][0])
}
} else {
result.push(this.data[i][0][0])
}
}
}
console.log(result)
return result
}
}
const myHashTable = new HashTable(5);
myHashTable.set('grapes', 10000)
myHashTable.set('apples', 9)
myHashTable.set('oranges', 4)
myHashTable.set('kiwis', 2)
//console.log(myHashTable.get('grapes'))
myHashTable.keys()
//myHashTable.get('apples')
JavaScript
INFO