1rosehip / javascript-algorithm-questions

JavaScript Algorithm Questions

JavaScript Algorithm Questions

Strings

Implement an algorithm to determine if a string has all unique characters.

1. O(n) time complexity and O(n) space complexity using helper object / Codepen
2. O(n) time complexity and O(1) space complexity using bitwise operators / Codepen
3. O(n log n) time complexity and O(1) space complexity using sorting / Codepen

Remove the duplicate characters in a string without using any additional buffer.

1. O(n) time complexity and O(1) space complexity / Codepen

Check whether two strings are anagram of each other.

1. O(n) time complexity and O(1) space complexity using sorting / Codepen
2. O(n) time complexity and O(n) space complexity using helper object / Codepen

Search for a pattern in the text

1. O(mn) time complexity where n = length of the text and m = length of the pattern / Codepen
2. KMP algorithm: O(m + n) time complexity where n = length of the text and m = length of the pattern / Codepen

Anagram substring search

1. O(n) time complexity where n = length of the text / Codepen
2. O(n) time complexity where n = length of the text / Codepen

Find the smallest window in a string containing all characters of another string

1. O(n) time complexity / Codepen

Find longest common substring

1. Solution using suffix arrays, O(n) time complexity / Codepen
2. Solution using 2d array, O(mn) / Codepen

Find longest common subsequence

1. Solution using 2d array, O(mn) / Codepen

Arrays

Write code to reverse an array in place.

1. O(n) time complexity and O(1) space complexity / Codepen

Given an NxN matrix, write a method to rotate it by 90 degrees.

1. O(n^2) time complexity and O(1) space complexity using matrix transpose / Codepen
2. O(n^2) time complexity and O(1) space complexity / Codepen
3. O(n^2) time complexity and O(n^2) space complexity using additional arrays / Codepen

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

1. O(nm) time complexity and O(1) space complexity using bitwise operators / Codepen

Binary search for the sorted arrays

1. Time complexity O(log n), space complexity O(1) / Codepen

Linked Lists

JavaScript linked list implementations

1. Singly-linked list implementation - add, remove, get, toString / Codepen
2. Doubly-linked list implementation - add, remove, get, toString / Codepen

Sort linked list

1. Sort singly-linked list using merge sort - O(n log n) time complexity and O(n) space complexity / Codepen

Remove duplicates from unsorted linked list

1. Remove duplicates from unsorted singly-linked list using merge sort - O(n log n) time complexity and O(n) space complexity, the array order is not saved / Codepen

2. Remove duplicates from unsorted singly-linked list using beffer - O(n) time complexity and O(n) space complexity, the array order is saved / Codepen

Add 2 numbers represented as singly-linked list.

You have two numbers represented by a linked list, where each node contains a sin- gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE:

Input: (3 -> 1 -> 5), (5 -> 9 -> 2)

Output: 8 -> 0 -> 8

1. O(n) time complexity and O(1) space complexity / Codepen

Stack

JavaScript stack implementations

1. Stack implementation using array / Codepen
2. Stack implementation using singly-linked-list - push, pick and isEmpty O(1), pop O(n) / Codepen
3. Stack implementation using doubly-linked-list - push, pop, pick, isEmpty O(1) / Codepen

Queue

JavaScript queue implementations

1. Queue implementation using array / Codepen

Binary Tree

JavaScript binary tree implementations

1. Binary tree insert using queue; inorder, preorder and postorder traversals; find a node; remove a node; find deepest node; / Codepen

Binary Search Tree

JavaScript search binary tree implementations

1. Binary search tree insert; inorder, preorder and postorder traversals; find a node; remove a node; find min node; / Codepen

Trie

JavaScript trie implementations

1. Trie insert, check if contains a whole word, find words by prefix / Codepen

Suffix Array

Suffix array initialization

1. Suffix array initialization - time complexity O(n^2 Log n), space compexity O(n^2) / Codepen
2. LCP array (Longest Common Prefix array) / Codepen

Graphs

1. DFS and DFS - adjacency matrix representation
2. DFS and DFS - adjacency list representation