DSA Tuotiral

Got it! Here’s the updated 8-hour JavaScript DSA training plan with examples without using inbuilt functions like .push(), .pop(), .shift(), .split(), etc.

---

🚀 8-Hour JavaScript DSA Training Plan (Without Inbuilt Functions)

---

Hour 1: Introduction to DSA & Complexity Analysis

• Topics:
  • What is DSA?
  • Time and Space Complexity (Big O Notation)
• Examples:

1. Constant Time – O(1)O(1)

function getFirstElement(arr) {
    return arr[0];
}

2. Linear Time – O(n)O(n)

function findMax(arr) {
    var max = arr[0];
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

3. Find second highest

nums = [1, 2, 3, 4, 5, 6, 7]

max = -Infinity
second_highest = -Infinity

for(let i = 0; i < nums.length; i++){
    if(nums[i] > max) {
        second_highest = max
        max = nums[i]
    } else if(nums[i] > second_highest && nums[i] !== max)
        second_highest = nums[i]

}

console.log("Maximum: ", max);
console.log("Second Highest: ", second_highest);

4. Sort array using bubble sort

function bubbleSort(arr) {
    let n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        // Last i elements are already sorted, so no need to check them
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap the elements
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    return arr;
}

// Example usage
const nums = [5, 2, 9, 1, 5, 6];
console.log(bubbleSort(nums)); // Output: [1, 2, 5, 5, 6, 9]

5. Unique Array – O(n2)

uniq = []
for(let i = 0; i < nums.length; i++) {
    let in_array = true
    for(let j = 0; j < uniq.length; j++) {
        if(nums[i] === uniq[j]) {
            in_array = false
            break
        }
    }
    
    if(in_array)
        uniq[uniq.length] = nums[i]
}

console.log("Unique Array: ", uniq);

---

Hour 2: Arrays and Strings

• Topics:
  • Manually manipulating arrays and strings
• Examples:

1. Reverse an Array

function reverseArray(arr) {
    var reversed = [];
    for (var i = arr.length - 1; i >= 0; i--) {
        reversed[reversed.length] = arr[i];
    }
    return reversed;
}
console.log(reverseArray([1, 2, 3, 4])); // [4, 3, 2, 1]

2. Check if a String is a Palindrome

function isPalindrome(str) {
    var reversed = "";
    for (var i = str.length - 1; i >= 0; i--) {
        reversed += str[i];
    }
    return str === reversed;
}
console.log(isPalindrome("madam")); // true

3. String is panagram or not

function isPangram(sentence) {
    // Convert the sentence to lowercase
    sentence = sentence.toLowerCase();

    // Create a set to store unique letters
    const letters = new Set();

    for (let char of sentence) {
        // Check if the character is an alphabet letter
        if (char >= 'a' && char <= 'z') {
            letters.add(char);
        }
    }

    // If the set size is 26, it's a pangram
    return letters.size === 26;
}

// Example Usage
console.log(isPangram("The quick brown fox jumps over the lazy dog")); // true
console.log(isPangram("Hello World"));                                 // false

4. String is anagram or not

function isAnagram(str1, str2) {
    const formatStr = (str) => str.toLowerCase().replace(/[^a-z]/g, '');

    str1 = formatStr(str1);
    str2 = formatStr(str2);

    if (str1.length !== str2.length) return false;

    const charCount = {};

    // Count characters from str1
    for (let char of str1) {
        charCount[char] = (charCount[char] || 0) + 1;
    }

    // Reduce the count based on str2
    for (let char of str2) {
        if (!charCount[char]) return false;
        charCount[char]--;
    }

    return true;
}

// Test cases
console.log(isAnagram("listen", "silent"));         // true
console.log(isAnagram("hello", "world"));           // false
console.log(isAnagram("Triangle", "Integral"));     // true
console.log(isAnagram("Dormitory", "dirty room"));  // true

---

Hour 3: Linked Lists

• Topics:
  • Manually implement Linked List operations
• Examples:

function Node(data) {
    this.data = data;
    this.next = null;
}

function LinkedList() {
    this.head = null;
}

LinkedList.prototype.insert = function (data) {
    var newNode = new Node(data);
    if (!this.head) {
        this.head = newNode;
        return;
    }
    var current = this.head;
    while (current.next !== null) {
        current = current.next;
    }
    current.next = newNode;
};

LinkedList.prototype.display = function () {
    var current = this.head;
    while (current !== null) {
        console.log(current.data);
        current = current.next;
    }
};

var list = new LinkedList();
list.insert(10);
list.insert(20);
list.display();

3.1. Linked List complete example

// Node class to represent each element in the linked list
class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// LinkedList class
class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }

    // Add element at the end of the list
    append(value) {
        const newNode = new Node(value);

        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }

    // Add element at the beginning of the list
    prepend(value) {
        const newNode = new Node(value);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }

    // Insert element at a specific position
    insertAt(value, index) {
        if (index < 0 || index > this.size) {
            console.log("Invalid index");
            return;
        }

        if (index === 0) {
            this.prepend(value);
            return;
        }

        const newNode = new Node(value);
        let current = this.head;
        let previous;
        let count = 0;

        while (count < index) {
            previous = current;
            current = current.next;
            count++;
        }

        previous.next = newNode;
        newNode.next = current;
        this.size++;
    }

    // Remove element by value
    remove(value) {
        if (!this.head) return;

        if (this.head.value === value) {
            this.head = this.head.next;
            this.size--;
            return;
        }

        let current = this.head;
        let previous = null;

        while (current && current.value !== value) {
            previous = current;
            current = current.next;
        }

        if (current) {
            previous.next = current.next;
            this.size--;
        } else {
            console.log("Value not found in the list.");
        }
    }

    // Get index of a value
    indexOf(value) {
        let current = this.head;
        let index = 0;

        while (current) {
            if (current.value === value) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    // Check if the list is empty
    isEmpty() {
        return this.size === 0;
    }

    // Get the size of the list
    getSize() {
        return this.size;
    }

    // Print the list
    print() {
        if (this.isEmpty()) {
            console.log("List is empty");
            return;
        }

        let current = this.head;
        let result = "";
        while (current) {
            result += current.value + " -> ";
            current = current.next;
        }
        console.log(result + "null");
    }

    // Clear the list
    clear() {
        this.head = null;
        this.size = 0;
    }
}

// Example Usage
const list = new LinkedList();

list.append(10);
list.append(20);
list.append(30);
list.print(); // Output: 10 -> 20 -> 30 -> null

list.prepend(5);
list.print(); // Output: 5 -> 10 -> 20 -> 30 -> null

list.insertAt(15, 2);
list.print(); // Output: 5 -> 10 -> 15 -> 20 -> 30 -> null

list.remove(20);
list.print(); // Output: 5 -> 10 -> 15 -> 30 -> null

console.log("Index of 15:", list.indexOf(15)); // Output: 2

console.log("Size of list:", list.getSize()); // Output: 4

list.clear();
list.print(); // Output: List is empty

---

Hour 4: Stacks and Queues

• Topics:
  • Manual stack and queue implementation
• Examples:

1. Stack Implementation

function Stack() {
    this.items = [];
    this.top = -1;
}

Stack.prototype.push = function (element) {
    this.top++;
    this.items[this.top] = element;
};

Stack.prototype.pop = function () {
    if (this.top < 0) return null;
    var popped = this.items[this.top];
    this.top--;
    return popped;
};

var stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // 20

1.1. Complete Stack Example

class Stack {
    constructor() {
        this.items = {};
        this.top = 0; // To keep track of the index
    }

    // Add element to the stack
    push(element) {
        this.items[this.top] = element;
        this.top++;
    }

    // Remove element from the stack
    pop() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        this.top--;
        const removedItem = this.items[this.top];
        delete this.items[this.top];
        return removedItem;
    }

    // View the top element of the stack
    peek() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.items[this.top - 1];
    }

    // Check if the stack is empty
    isEmpty() {
        return this.top === 0;
    }

    // Get the size of the stack
    size() {
        return this.top;
    }

    // Print all elements in the stack
    print() {
        let result = '';
        for (let i = 0; i < this.top; i++) {
            result += this.items[i] + ' ';
        }
        console.log(result.trim());
    }

    // Clear the stack
    clear() {
        this.items = {};
        this.top = 0;
    }
}

// Example Usage
const stack = new Stack();

stack.push(10);
stack.push(20);
stack.push(30);
stack.print();  // Output: 10 20 30

console.log(stack.peek()); // Output: 30

console.log(stack.pop());  // Output: 30
stack.print();             // Output: 10 20

console.log(stack.isEmpty()); // Output: false

stack.clear();
console.log(stack.isEmpty()); // Output: true

2. Queue Implementation

function Queue() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
}

Queue.prototype.enqueue = function (element) {
    this.items[this.rear] = element;
    this.rear++;
};

Queue.prototype.dequeue = function () {
    var item = this.items[this.front];
    delete this.items[this.front];
    this.front++;
    return item;
};

var queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.dequeue()); // 10

2.2. Complete Queue Example

class Queue {
    constructor() {
        this.items = {};
        this.front = 0;
        this.rear = 0;
    }

    // Enqueue (add) element to the queue
    enqueue(element) {
        this.items[this.rear] = element;
        this.rear++;
    }

    // Dequeue (remove) element from the queue
    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        const removedItem = this.items[this.front];
        delete this.items[this.front];
        this.front++;
        return removedItem;
    }

    // View the front element of the queue
    peek() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items[this.front];
    }

    // Check if the queue is empty
    isEmpty() {
        return this.rear === this.front;
    }

    // Get the size of the queue
    size() {
        return this.rear - this.front;
    }

    // Print all elements in the queue
    print() {
        let result = '';
        for (let i = this.front; i < this.rear; i++) {
            result += this.items[i] + ' ';
        }
        console.log(result.trim());
    }

    // Clear the queue
    clear() {
        this.items = {};
        this.front = 0;
        this.rear = 0;
    }
}

// Example Usage
const queue = new Queue();

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.print();  // Output: 10 20 30

console.log(queue.peek()); // Output: 10

console.log(queue.dequeue()); // Output: 10
queue.print();               // Output: 20 30

console.log(queue.isEmpty()); // Output: false

queue.clear();
console.log(queue.isEmpty()); // Output: true

---

Hour 5: Recursion

• Examples:

1. Factorial Using Recursion

function factorial(n) {
    if (n === 0) return 1;
    return n * factorial(n - 1);
}
console.log(factorial(5)); // 120

2. Fibonacci Series

function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(6)); // 8

---

Hour 6: Searching and Sorting

• Examples:

1. Binary Search

function binarySearch(arr, target) {
    var left = 0, right = arr.length - 1;
    while (left <= right) {
        var mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // 2

2. Bubble Sort

function bubbleSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        for (var j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
console.log(bubbleSort([5, 2, 9, 1])); // [1, 2, 5, 9]

---

Hour 7: Trees and Graphs

• Examples:

1. Binary Search Tree (Insert & Traverse)

function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

function insert(root, val) {
    if (!root) return new TreeNode(val);
    if (val < root.val) root.left = insert(root.left, val);
    else root.right = insert(root.right, val);
    return root;
}

function inOrderTraversal(root) {
    if (root) {
        inOrderTraversal(root.left);
        console.log(root.val);
        inOrderTraversal(root.right);
    }
}

var root = null;
root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 15);
inOrderTraversal(root); // 5 10 15

---

Hour 8: Hashing and Final Assignment

• Examples:

function HashTable(size) {
    this.table = new Array(size);
}

HashTable.prototype.hash = function (key) {
    var hash = 0;
    for (var i = 0; i < key.length; i++) {
        hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
};

HashTable.prototype.set = function (key, value) {
    var index = this.hash(key);
    this.table[index] = [key, value];
};

HashTable.prototype.get = function (key) {
    var index = this.hash(key);
    if (this.table[index] && this.table[index][0] === key) {
        return this.table[index][1];
    }
    return undefined;
};

var ht = new HashTable(10);
ht.set("name", "John");
console.log(ht.get("name")); // John

Complete Program

// Tuple Example using Class (Simulated Tuple)
class Tuple {
    constructor(...elements) {
        this.elements = elements;
    }
    get(index) {
        return this.elements[index];
    }
    set(index, value) {
        this.elements[index] = value;
    }
}

const tuple = new Tuple(1, 'hello', true);
console.log(tuple.get(0)); // Accessing element

tuple.set(1, 'world'); // Modifying element
console.log(tuple.get(1));

// Map Example using Class
class CustomMap {
    constructor() {
        this.map = new Map();
    }
    add(key, value) {
        this.map.set(key, value);
    }
    get(key) {
        return this.map.get(key);
    }
    delete(key) {
        this.map.delete(key);
    }
    iterate() {
        for (const [key, value] of this.map.entries()) {
            console.log(key, value);
        }
    }
}

const customMap = new CustomMap();
customMap.add('name', 'John');
customMap.add('age', 30);
console.log(customMap.get('name'));
customMap.delete('name');
customMap.iterate();

// Linear Search using Function
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

// Binary Search using Function
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// KMP String Search using Function
function KMPSearch(pattern, text) {
    const lps = computeLPSArray(pattern);
    let i = 0, j = 0;
    while (i < text.length) {
        if (pattern[j] === text[i]) {
            i++; j++;
        }
        if (j === pattern.length) {
            console.log('Pattern found at index', i - j);
            j = lps[j - 1];
        } else if (i < text.length && pattern[j] !== text[i]) {
            j !== 0 ? j = lps[j - 1] : i++;
        }
    }
}

function computeLPSArray(pattern) {
    const lps = [0];
    let len = 0, i = 1;
    while (i < pattern.length) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else if (len !== 0) {
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return lps;
}

// Tree Node and Traversal using Class
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class TreeTraversal {
    static dfs(node) {
        if (!node) return;
        console.log(node.value);
        this.dfs(node.left);
        this.dfs(node.right);
    }

    static bfs(root) {
        const queue = [root];
        while (queue.length > 0) {
            const node = queue.shift();
            console.log(node.value);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
}

// Bubble Sort using Function
function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

const sampleArray = [5, 3, 8, 4, 2];
console.log(bubbleSort(sampleArray));