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:
 Before you can compare the algorithms,
you have to implement them both.  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.  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:
 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.  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.
 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 n^{2},
we expect A to be faster than B, at least for large values of n.
how much more memory is required
by doubling the problem set.
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.
 Figure out what the input is and what n represents.
 Express the maximum number of operations, the algorithm performs in terms of n.
 Eliminate all excluding the highest order terms.
 Remove all the constant factors.
Classification of Algorithms
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 E.g, if you have an array of n elements 
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, Iterating through half a collection – still O(n). If you add up the elements of an array, 
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 n^{2} if every element in a collection has to be compared to every other element (“the handshake problem”). E.g., Two nested loops suppose you want to check whether any element in a list appears more than once. 
O(n^3)  Cubic  
O(2^n)  Exponential 
If you add a single element to a collection the processing power required doubles. 
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 datatype
using the array data structure.
Javascript natively implements several datastructures.
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
 Queues are used whenever we need to manage objects in order
starting with the first one in.  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:
 unshift
adds a element to the beginning of the array  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:
 hackernoon
 https://www.geeksforgeeks.org/implementationqueuejavascript/
 https://medium.com/javascriptinplainenglish/javascriptwhatarestackandqueue79df7af5a566
Sources:
 geeksforgeeks.org,
 free course by William Fiset  Software Engineer at Google,
 Data Structure course by Log(n) Academy,
 data structures course by University of California San Diego & National Research University Higher School of Economics,
 Data Structures and Performance by University of California San Diego,
 Algorithms, Part I by Princeton University
Leave a Reply or Comment