Category: DSA

DSA Tuotiral

by

March 11, 2025

1:42 pm

Leave a comment on DSA Tuotiral

DSA

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];
}
  1. 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]
  1. 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
  1. 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
  1. 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
  1. 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));

DSA Assesment

by

February 27, 2025

3:02 am

Leave a comment on DSA Assesment

DSA

Sure! Here are three easy-level DSA problems using Array, Linked List, and Map, along with their solutions in JavaScript.

1. Array Problem (Easy)

Problem: Find the Second Largest Element

Given an array of integers, find the second largest element in the array.
If there is no second largest element, return -1.

Example:

Input: arr = [10, 5, 20, 8]
Output: 10

Input: arr = [7, 7, 7]
Output: -1

Solution (JavaScript)

function secondLargest(arr) {
    if (arr.length < 2) return -1;

    let largest = -Infinity, secondLargest = -Infinity;

    for (let num of arr) {
        if (num > largest) {
            secondLargest = largest;
            largest = num;
        } else if (num > secondLargest && num < largest) {
            secondLargest = num;
        }
    }

    return secondLargest === -Infinity ? -1 : secondLargest;
}

// Test Cases
console.log(secondLargest([10, 5, 20, 8])); // Output: 10
console.log(secondLargest([7, 7, 7])); // Output: -1
console.log(secondLargest([3])); // Output: -1

Time Complexity: O(n)O(n)

2. Linked List Problem (Easy)

Problem: Find the Middle Node of a Linked List

Given a singly linked list, return the middle node.
If there are two middle nodes, return the second one.

Example:

Input: 1 → 2 → 3 → 4 → 5
Output: 3

Input: 1 → 2 → 3 → 4 → 5 → 6
Output: 4

Solution (JavaScript)

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function findMiddle(head) {
    let slow = head, fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;  // Move slow one step
        fast = fast.next.next;  // Move fast two steps
    }

    return slow.val;
}

// Helper function to create a linked list
function createLinkedList(arr) {
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

// Test Cases
let head1 = createLinkedList([1, 2, 3, 4, 5]);
console.log(findMiddle(head1)); // Output: 3

let head2 = createLinkedList([1, 2, 3, 4, 5, 6]);
console.log(findMiddle(head2)); // Output: 4

Time Complexity: O(n)O(n)

3. Map Problem (Easy)

Problem: Find First Non-Repeating Character

Given a string s, find the first non-repeating character and return its index.
If all characters repeat, return -1.

Example:

Input: "leetcode"
Output: 0  // ('l' is the first unique character)

Input: "aabb"
Output: -1  // (No unique character)

Solution (JavaScript)

function firstUniqueChar(s) {
    let charCount = new Map();

    // Count frequency of characters
    for (let char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }

    // Find the first unique character
    for (let i = 0; i < s.length; i++) {
        if (charCount.get(s[i]) === 1) return i;
    }

    return -1;
}

// Test Cases
console.log(firstUniqueChar("leetcode")); // Output: 0
console.log(firstUniqueChar("loveleetcode")); // Output: 2
console.log(firstUniqueChar("aabb")); // Output: -1

Time Complexity: O(n)O(n)

These problems are great for understanding Array, Linked List, and Map usage in JavaScript. Let me know if you need more! 🚀