Data Structures

Question 1

Binary Search

Answer 1

function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);

        if (sortedArray[middle] === key) {
            // found the key
            return middle;
        } else if (sortedArray[middle] < key) {
            // continue searching to the right
            start = middle + 1;
        } else {
            // search searching to the left
            end = middle - 1;
        }
    }
    // key wasn't found
    return -1;
}
let targetList = [12, 1, 3, 9, 2].sort((a,b)=>a-b);//?
let index = binarySearch(targetList, 9); //?

Question 2

Binary Search Recursive

Answer 2

let arr = ['a','b','c','d','e','f','g','h','i','j'];
let num = 'c';
let count=0;

function binarySearchRec(arrN, numN) {
      \++count;
	let mid = Math.floor(arrN.length/2);
	let left = arrN.slice(0, mid);
	let right = arrN.slice(mid, arrN.length);
	
	if (num==arrN[mid]) {
		return `found, took ${count} attempts`;
	} else if (num<arrN[mid]) { 
		return binarySearchRec(left, num);
	} else {
		return binarySearchRec(right, num);
	}
}

binarySearchRec(arr, num);

Question 3

Bubble Sort

Answer 3

let arr = ["z", "d", "c", "a", "r", "g", "f"];
let sorted = false; 

function bubbleSort(arr) { 
	while (!sorted) {
		sorted = true;
		for (let i = 0; i < arr.length; i++) {
			if (arr[i] > arr[i+1]) {
                [arr[i], arr[i+1]] = [arr[i+1], arr[i]];
				sorted = false;
			}
		}
	}
	return arr;
}

console.log(bubbleSort(arr)); //? 

Question 4

Depth First Traversal

Answer 4

function Node (val, left, right) {
	this.val = val;
	this.left = left;
	this.right = right;
}

let nodeF = new Node ('F', null, null);
let nodeE = new Node ('E', null, null);
let nodeD = new Node ('D', null, null);
let nodeC = new Node ('C', nodeF, null);
let nodeB = new Node ('B', nodeD, nodeE);
let root = new Node ('A', nodeB, nodeC);

function DFS(node, dir){
	if (node === null) {
		return;
	} else {
		console.log(`Visiting node ${node.val}`);
		DFS(node.left, 'left');
		DFS(node.right, 'right');
	}
}

DFS(root, 'root');