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')
function reverse(str){
if(!str || typeof str != 'string' || str.length < 2 ) return str;
const backwards = [];
const totalItems = str.length - 1;
for(let i = totalItems; i >= 0; i--){
backwards.push(str[i]);
}
return backwards.join('');
}
function reverse2(str){
//check for valid input
return str.split('').reverse().join('');
}
const reverse3 = str => [...str].reverse().join('');
reverse('Timbits Hi')
reverse('Timbits Hi')
reverse3('Timbits Hi')
function mergeSortedArrays(array1, array2){
const mergedArray = [];
let array1Item = array1[0];
let array2Item = array2[0];
let i = 1;
let j = 1;
//We should actually move these 2 if statements to line 2 so that we do the checks before we do assignments in line 3 and 4!
if(array1.length === 0) {
return array2;
}
if(array2.length === 0) {
return array1;
}
while (array1Item || array2Item){
if(array2Item === undefined || array1Item < array2Item){
mergedArray.push(array1Item);
array1Item = array1[i];
i++;
}
else {
mergedArray.push(array2Item);
array2Item = array2[j];
j++;
}
}
return mergedArray;
}
mergeSortedArrays([0,3,4,31], [3,4,6,30]);
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
}
}
//Google Question
//Given an array = [2,5,1,2,3,5,1,2,4]:
//It should return 2
//Given an array = [2,1,1,2,3,5,1,2,4]:
//It should return 1
//Given an array = [2,3,4,5]:
//It should return undefined
function firstRecurringCharacter(input) {
for (let i = 0; i < input.length; i++) {
for (let j = i + 1; j < input.length; j++) {
if(input[i] === input[j]) {
return input[i];
}
}
}
return undefined
}
function firstRecurringCharacter2(input) {
let map = {};
for (let i = 0; i < input.length; i++) {
if (map[input[i]] !== undefined) {
return input[i]
} else {
map[input[i]] = i;
}
}
return undefined
}
firstRecurringCharacter2([1,5,5,1,3,4,6])
//Bonus... What if we had this:
// [2,5,5,2,3,5,1,2,4]
// return 5 because the pairs are before 2,2
