Month: February 2025

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! 🚀