Javascript DSA QnA solutions for product based company interview

-

Here are some JavaScript solutions to common Data Structures and Algorithms (DSA) questions frequently asked in product-based company interviews. These problems focus on fundamental topics like arrays, linked lists, sorting, and searching.

1. Find the Missing Number

Problem: Given an array of n distinct numbers from the range 1 to n+1, find the missing number.

Example:
Input: [1, 2, 4, 5, 6]
Output: 3

Solution: We can calculate the expected sum of the array (from 1 to n+1) and subtract the sum of the array elements to find the missing number.

javascript
function findMissingNumber(arr) {
  const n = arr.length;
  const expectedSum = (n + 1) * (n + 2) / 2;
  const actualSum = arr.reduce((acc, num) => acc + num, 0);
  return expectedSum - actualSum;
}

2. Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list and return its head.

Example:
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

Solution: We can reverse the linked list by updating the next pointers of the nodes iteratively.

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

function reverseLinkedList(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    let nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }
  return prev;
}

3. Find the Longest Substring Without Repeating Characters

Problem: Given a string, find the length of the longest substring without repeating characters.

Example:
Input: "abcabcbb"
Output: 3 (Longest substring is "abc")

Solution: Use a sliding window technique with a hash map to track characters in the current window.

javascript
function longestSubstring(s) {
  let charSet = new Set();
  let left = 0;
  let maxLength = 0;
  
  for (let right = 0; right < s.length; right++) {
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    charSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

4. Merge Two Sorted Arrays

Problem: Given two sorted arrays, merge them into one sorted array.

Example:
Input: [1, 3, 5] and [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6]

Solution: We can use two pointers, one for each array, and merge them into a result array.

javascript
function mergeSortedArrays(arr1, arr2) {
  let result = [];
  let i = 0, j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }

  result = result.concat(arr1.slice(i), arr2.slice(j));
  return result;
}

5. Find the Kth Largest Element in an Array

Problem: Given an array, find the kth largest element.

Example:
Input: [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Solution: Use a min-heap or Quickselect algorithm to efficiently find the kth largest element.

javascript
function findKthLargest(nums, k) {
  nums.sort((a, b) => b - a); // Sorting in descending order
  return nums[k - 1];
}

Alternatively, using a min-heap for optimized performance:

javascript
function findKthLargest(nums, k) {
  const minHeap = new MinPriorityQueue();
  nums.forEach(num => minHeap.add(num));

  let result;
  for (let i = 0; i < k; i++) {
    result = minHeap.poll();
  }

  return result;
}

6. Balanced Parentheses

Problem: Given a string containing just the characters '(', ')', {, }, [, and ], determine if the input string is valid. An input string is valid if:

  • Open brackets are closed by the correct type of brackets.
  • Open brackets are closed in the correct order.

Example:
Input: "()"
Output: true

Solution: Use a stack to keep track of open brackets.

javascript
function isValidParentheses(s) {
  let stack = [];
  const map = { ')': '(', '}': '{', ']': '[' };
  
  for (let char of s) {
    if (map[char]) {
      if (stack.pop() !== map[char]) {
        return false;
      }
    } else {
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

7. Top K Frequent Elements

Problem: Given a non-empty array of integers, return the k most frequent elements.

Example:
Input: [1,1,1,2,2,3], k = 2
Output: [1, 2]

Solution: Use a hash map to count the frequencies and then use a min-heap to find the top k elements.

javascript
function topKFrequent(nums, k) {
  const frequencyMap = new Map();
  nums.forEach(num => frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1));

  const sorted = [...frequencyMap.entries()].sort((a, b) => b[1] - a[1]);
  
  return sorted.slice(0, k).map(entry => entry[0]);
}

8. Detect a Cycle in a Linked List

Problem: Given a linked list, determine if it has a cycle.

Solution: We can use Floyd’s Cycle-Finding Algorithm (Tortoise and Hare), which uses two pointers moving at different speeds.

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

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }
  
  return false;
}

9. Binary Search

Problem: Given a sorted array of integers, find the index of a target value.

Example:
Input: [1, 2, 3, 4, 5], target = 3
Output: 2

Solution: Implement binary search using two pointers.

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;
    }
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1; // Target not found
}

Key Takeaways:

  • These solutions help demonstrate your understanding of common data structures (arrays, linked lists, hash maps, heaps) and how to apply algorithms (like binary search, sliding window, and sorting) efficiently.
  • Always pay attention to the time and space complexities for optimal solutions. For example, binary search has a time complexity of O(log n), while sorting has O(n log n).
  • Practice these problems regularly to improve your speed and confidence in tackling technical interviews.

Good luck with your interview preparation!

Comments

Post a Comment

Popular posts from this blog

PrimeNG tutorial with examples using frequently used classes

-
  PrimeNG Tutorial: Frequently Used Classes and Components PrimeNG is a comprehensive and flexible UI component library for Angular applications. It provides a wide range of ready-to-use components like forms, data tables, dialogs, buttons, and many others, all styled using Material Design principles. In this tutorial, we will explore some of the frequently used components and classes in PrimeNG , along with examples for creating interactive, modern, and responsive UIs. 1. Setting Up PrimeNG Before using PrimeNG components, you need to install PrimeNG in your Angular project. If you haven’t done so, follow these steps: Step 1: Install PrimeNG and PrimeIcons Run the following commands to install PrimeNG and PrimeIcons: bash Copy code npm install primeng npm install primeicons Step 2: Import Required Modules After installation, you need to import the relevant PrimeNG modules in your app.module.ts . Example of importing commonly used modules: typescript Copy code import { NgModule ...
Read more

Docker and Kubernetes Tutorials and QnA

-
 Docker and Kubernetes Tutorials: Detailed Guide Let's dive into detailed tutorials for Docker and Kubernetes, starting with their core concepts and progressing to hands-on examples. These tutorials are designed for both beginners and intermediate learners. Part 1: Docker Tutorial 1. Introduction to Docker Docker is a platform used to develop, ship, and run applications inside containers. Containers are lightweight, portable, and ensure consistent environments across different stages of the application lifecycle. They help solve the "works on my machine" problem. Key Concepts of Docker: Images : A blueprint for containers, containing everything needed to run an application (code, runtime, libraries, etc.). Containers : A runtime instance of an image, running isolated from the host system. Dockerfile : A script with a set of instructions to build Docker images. Docker Hub : A public repository of Docker images. Docker Compose : A tool to define and manage multi-container a...
Read more

Building strong foundational knowledge in frontend development topics

-
 These topics are essential for building strong foundational knowledge, and each comes with a simple solution or code snippet to illustrate the concept. 1. What is the difference between HTML, CSS, and JavaScript? Answer : HTML (Hypertext Markup Language) is used for structuring web content (headings, paragraphs, images, links, etc.). CSS (Cascading Style Sheets) is used for styling the layout, design, and appearance of the web content. JavaScript is used for adding interactivity and dynamic behavior to the website (e.g., form validation, animations, events). html <!-- HTML --> < div class = "box" > </ div > css /* CSS */ .box { width : 100px ; height : 100px ; background-color : blue; } javascript // JavaScript document . querySelector ( '.box' ). addEventListener ( 'click' , function ( ) { alert ( 'Box clicked!' ); }); 2. What are semantic HTML elements and why are they important? Answer : Semantic HTML elements cl...
Read more