YuWebdesign



JavaScript Data Structures and Algorithms Interview Questions

By YuwebDesign


Analysis of Algorithms

Profiling

an approach, that decides which algorythm is better for a particular application,
by trying them both and see how long they take.

Problems with Profiling:

  1. Before you can compare the algorithms,
    you have to implement them both.
  2. The results might depend on what kind of computer you use.

    One algorithm might be better on one machine;
    the other might be better on a different machine.

  3. The results might depend on the size of the problem
    or the data provided as input.

Algorithm Analysis

Algorithm Analysis makes it possible to compare algorithms
without having to implement them.


But we have to make some assumptions:

  1. To avoid dealing with the details of computer hardware,
    we usually identify the basic operations that make up an algorithm —
    like addition, multiplication, and comparison of numbers —
    and count the number of operations each algorithm requires.
  2. To avoid dealing with the details of the input data,
    the best option is to analyze the average performance
    for the inputs we expect.

    If that’s not possible, a common alternative is to analyze the worst case scenario.

  3. Finally, we have to deal with the possibility
    that one algorithm works best for small problems
    and another for big ones.

    In that case, we usually focus on the big ones,
    because for small problems the difference probably doesn’t matter,
    but for big problems the difference can be huge.

This kind of analysis lends itself to simple classification of algorithms.

E.g., if we know that the run time of Algorithm A
tends to be proportional to the size of the input, n,
and Algorithm B tends to be proportional to n2,
we expect A to be faster than B, at least for large values of n.

Space Complexity
how much more memory is required
by doubling the problem set.

Runtime Complexity/ big O notation
describes the performance of an algorithm
according to how their run time or space requirements grow
as the input size grows.

Runtime Complexity answers the question
how much more time/processing power is required
to run the algorithm
if we double the inputs.

Worst case scenario
The Big O notation
defines an upper bound of an algorithm,
it bounds a function only from above.

For example, consider the case of Insertion Sort.
It takes linear time in best case and quadratic time in worst case.
We can safely say that the time complexity of Insertion sort is O(n^2).
Note that O(n^2) also covers linear time.

The general step wise procedure for Big-O runtime analysis is as follows:

  1. Figure out what the input is and what n represents.
  2. Express the maximum number of operations, the algorithm performs in terms of n.
  3. Eliminate all excluding the highest order terms.
  4. Remove all the constant factors.

Classification of Algorithms

Common Functions for Big-O

Most simple algorithms fall into just a few categories:

f(n) Name Description
O(1) Constant time Run time does not depend on the size of the input.

No matter how many elements we are working with
the algorithm will always take the same amount of time.

E.g, if you have an array of n elements
and you use the bracket operator ([]) to access one of the elements,
this operation takes the same number of operations
regardless of how big the array is.

O(log(n)) Logarithmic Doubling the number of elements you are iterating over
does not double the amount of work.
Always assume that searching operations are log(n).
O(n) Linear Run time is proportional to the size of the input.

E.g., when iterating through all elements in a collection of data.

If you see a for loop spanning from 0 to array.length,
you probably have n, or linear runtime.

Iterating through half a collection – still O(n).

If you add up the elements of an array,
you have to access n elements and perform n − 1 additions.
The total number of operations (element accesses and additions)
is 2n − 1, which is proportional to n.

O(n+m) When iterating through two different collections
with separate for loops.
O(n log(n)) Log Linear Doubling the number of elements you are iterating over
does not double the amount of work.

Always assume that any sorting operation is n log(n)

O(n^2) Quadratic run time is proportional to n2
if every element in a collection has to be compared
to every other element
(“the handshake problem”).

E.g., Two nested loops
iterating over the same collection.

suppose you want to check whether any element in a list appears more than once.
A simple algorithm is to compare each element to all of the others.
If there are n elements and each is compared to n − 1 others,
the total number of comparisons is n2 − n,
which is proportional to n2 as n grows.

O(n^3) Cubic
O(2^n) Exponential If you add a single element to a collection
the processing power required doubles.

Big O Notation
Big O Notation

Data Structures

Data Structures
are a particular way
of organizing information (data)
so that it can be used effectively
(e.g., with optimal runtime complexity
for adding or removing records).

E.g., we can store a list of items
having the same data-type
using the array data structure.

Javascript natively implements several datastructures.

A queue
is a simple linear data structure
that allows elements to be inserted from one end,
called the rear (also called tail),
and deleted from the other end,
called the front (also called head).

This behavior is called FIFO (First in First Out).

A very important concept is that a queue
deletes only the oldest element.

Applications
  1. Queues are used whenever we need to manage objects in order
    starting with the first one in.
  2. Scenarios include
    printing documents on a printer,
    call center systems answering people on hold people,
    and so on.
Creation

A queue can be implemented using an array or a linked list.

With implementing from an array can take arrays methods:

  1. unshift
    adds a element to the beginning of the array
  2. pop
    deletes the last element of the array
Implementation 1 (Array)
// create a Queue constructor function with a empty array inside
function Queue() {
  this.data = [];
}

// methods
Queue.prototype.add = function(record) {
  this.data.unshift(record);
}

Queue.prototype.remove = function() {
  this.data.pop();
}

Queue.prototype.first = function() {
  return this.data[0];
}

Queue.prototype.last = function() {
  return this.data[this.data.length - 1];
}

Queue.prototype.size = function() {
  return this.data.length;
}
const q = new Queue():
q.add(1);
q.add(2);
q.add(3);
console.log(q); // [3, 2, 1]
console.log(q.first()); // 3
console.log(q.last()); // 1
q.remove();
console.log(q); // [3, 2]
console.log(q.size()) // 2
Implementation 2 (Array)
class Queue 
{ 
    // Array is used to implement a Queue 
    constructor() { 
        this.items = []; 
    } 
                  
    enqueue(element) {     
        this.items.push(element); 
    }  
	
    dequeue() { 
        // returns underflow when called  
        // on empty queue 
        if(this.isEmpty()) 
            return "Underflow"; 
        return this.items.shift(); 
    } 
	
    front() { 
        // returns the front element of  
        // the queue without removing it. 
        if(this.isEmpty()) 
            return "No elements in Queue"; 
        return this.items[0]; 
    } 
	
    isEmpty() { 
        // return true if the queue is empty. 
        return this.items.length == 0; 
    } 
	
	peek() {
        if (this.isEmpty()) return 'Queue is empty'
        return this.queue[0]
    }
    
	printQueue() {
	    // returns a string of concatenated elements
        var str = ""; 
        for(var i = 0; i < this.items.length; i++) 
            str += this.items[i] +" "; 
        return str; 
    }
} 
var queue = new Queue(); 

console.log(queue.dequeue()); // Underflow
console.log(queue.isEmpty()); // true
queue.enqueue(10); 
queue.enqueue(20); 
queue.enqueue(30); 
queue.enqueue(40); 
queue.enqueue(50); 
queue.enqueue(60);
console.log(queue.front()); // 10
console.log(queue.front()); // 20
Implementation 3 (Linked List))
class Node {
  constructor(next, value) {
    this.next = next
    this.value = value
  }
}

class Queue {
  constructor() {
    this.queue = null
  }
  
  enqueue(element) {
    let head = this.queue
    let newNode = new Node(null, element)
    
    if (!head) {
      this.queue = newNode
    } else {
      let traverseNode = head
      while (traverseNode.next) {
        traverseNode = traverseNode.next
      }
      traverseNode.next = newNode
    }
  }
  
  dequeue() {
    let head = this.queue
    
    if (!head) return 'Queue is empty!'
    
    this.queue = head.next
    return head.value
  }
  
  peek() {
    if(!this.queue) return 'Queue is empty!'
    return this.queue.value
  }
}

Read more:

  1. hackernoon
  2. https://www.geeksforgeeks.org/implementation-queue-javascript/
  3. https://medium.com/javascript-in-plain-english/javascript-what-are-stack-and-queue-79df7af5a566