Πώς να εφαρμόσετε 8 βασικούς αλγόριθμους γραφήματος σε JavaScript

Σε αυτό το άρθρο, θα εφαρμόσω 8 αλγόριθμους γραφημάτων που διερευνούν τα προβλήματα αναζήτησης και συνδυασμού (διαβάσεις, συντομότερη διαδρομή και αντιστοίχιση) γραφημάτων σε JavaScript.

Τα προβλήματα δανείζονται από το βιβλίο, Elements of Programming Interviews in Java. Οι λύσεις στο βιβλίο κωδικοποιούνται σε Java, Python ή C ++ ανάλογα με την έκδοση του βιβλίου που διαθέτετε.

Παρόλο που η λογική πίσω από τη μοντελοποίηση των προβλημάτων είναι γλώσσα-αγνωστικική, τα αποσπάσματα κώδικα που παρέχω σε αυτό το άρθρο χρησιμοποιούν ορισμένες προειδοποιήσεις JavaScript.

Κάθε λύση σε κάθε πρόβλημα χωρίζεται σε 3 ενότητες: μια επισκόπηση της λύσης, τον ψευδοκώδικα και τέλος τον πραγματικό κώδικα σε JavaScript.

Για να δοκιμάσετε τον κώδικα και να δείτε ότι κάνει αυτό που πρέπει να κάνει, μπορείτε να χρησιμοποιήσετε τα Εργαλεία Dev του Chrome για να εκτελέσετε τα αποσπάσματα στο ίδιο το πρόγραμμα περιήγησης ή να χρησιμοποιήσετε το NodeJS για να τα εκτελέσετε από τη γραμμή εντολών.

Υλοποίηση γραφήματος

Οι 2 πιο συχνά χρησιμοποιούμενες αναπαραστάσεις γραφημάτων είναι ο πίνακας γειτνίασης και ο πίνακας γειτνίασης.

Τα προβλήματα που θα λύσω είναι για αραιά γραφήματα (λίγα άκρα) και οι λειτουργίες κορυφής στην προσέγγιση λίστας γειτνίασης είναι σταθερές (προσθέτοντας μια κορυφή, O (1)) και γραμμικό χρόνο (διαγραφή μιας κορυφής, O (V + E )). Επομένως, θα μείνω με αυτήν την εφαρμογή ως επί το πλείστον.

Ας το ξεπεράσουμε με μια απλή , μη κατευθυνόμενη, μη σταθμισμένη εφαρμογή γραφημάτων χρησιμοποιώντας μια λίστα γειτνίασης . Θα διατηρήσουμε ένα αντικείμενο (adjacencyList) που θα περιέχει όλες τις κορυφές στο γράφημα ως κλειδιά. Οι τιμές θα είναι ένας πίνακας όλων των γειτονικών κορυφών. Στο παρακάτω παράδειγμα, η κορυφή 1 συνδέεται με τις κορυφές 2 και 4, ως εκ τούτου adjacencyList: {1: [2, 4]} και ούτω καθεξής για τις άλλες κορυφές.

Για να δημιουργήσουμε το γράφημα, έχουμε δύο συναρτήσεις: addVertex και addEdge . Το addVertex χρησιμοποιείται για να προσθέσετε μια κορυφή στη λίστα. Το addEdge χρησιμοποιείται για τη σύνδεση των κορυφών προσθέτοντας τις γειτονικές κορυφές και στις συστοιχίες προέλευσης και προορισμού, καθώς αυτό είναι ένα μη κατευθυνόμενο γράφημα. Για να δημιουργήσουμε ένα κατευθυνόμενο γράφημα, μπορούμε απλά να αφαιρέσουμε τις γραμμές 14–16 και 18 στον παρακάτω κώδικα.

Πριν από την αφαίρεση μιας κορυφής, πρέπει να επαναλάβουμε τη σειρά των γειτονικών κορυφών και να αφαιρέσουμε όλες τις πιθανές συνδέσεις με αυτήν την κορυφή.

class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) { this.adjacencyList[vertex] = []; } } addEdge(source, destination) { if (!this.adjacencyList[source]) { this.addVertex(source); } if (!this.adjacencyList[destination]) { this.addVertex(destination); } this.adjacencyList[source].push(destination); this.adjacencyList[destination].push(source); } removeEdge(source, destination) { this.adjacencyList[source] = this.adjacencyList[source].filter(vertex => vertex !== destination); this.adjacencyList[destination] = this.adjacencyList[destination].filter(vertex => vertex !== source); } removeVertex(vertex) { while (this.adjacencyList[vertex]) { const adjacentVertex = this.adjacencyList[vertex].pop(); this.removeEdge(vertex, adjacentVertex); } delete this.adjacencyList[vertex]; } }

Διαδρομές γραφήματος

Με βάση την εφαρμογή των γραφημάτων στην προηγούμενη ενότητα, θα εφαρμόσουμε τις διαβάσεις γραφημάτων: πρώτη αναζήτηση εύρους και πρώτη αναζήτηση βάθους.

Πρώτη αναζήτηση

Το BFS επισκέπτεται τους κόμβους ένα επίπεδο κάθε φορά . Για να αποφευχθεί η επίσκεψη στον ίδιο κόμβο περισσότερες από μία φορές, θα διατηρήσουμε ένα αντικείμενο επισκέψεων .

Δεδομένου ότι πρέπει να επεξεργαστούμε τους κόμβους με τρόπο First In First Out, η ουρά είναι ένας καλός υποψήφιος για τη χρήση της δομής δεδομένων. Η πολυπλοκότητα του χρόνου είναι O (V + E).

function BFS Initialize an empty queue, empty 'result' array & a 'visited' map Add the starting vertex to the queue & visited map While Queue is not empty: - Dequeue and store current vertex - Push current vertex to result array - Iterate through current vertex's adjacency list: - For each adjacent vertex, if vertex is unvisited: - Add vertex to visited map - Enqueue vertex Return result array

Πρώτη αναζήτηση βάθους

Το DFS επισκέπτεται τους κόμβους βάθος. Δεδομένου ότι πρέπει να επεξεργαστούμε τους κόμβους με τρόπο Last In First Out, θα χρησιμοποιήσουμε μια στοίβα .

Ξεκινώντας από μια κορυφή, θα ωθήσουμε τις γειτονικές κορυφές στη στοίβα μας. Κάθε φορά που εμφανίζεται μια κορυφή, επισημαίνεται ως επίσκεψη στο αντικείμενο που επισκεφτήκαμε. Οι γειτονικές κορυφές του ωθούνται στη στοίβα. Δεδομένου ότι αναδύουμε πάντα μια νέα γειτονική κορυφή, ο αλγόριθμός μας θα εξερευνά πάντα ένα νέο επίπεδο .

Μπορούμε επίσης να χρησιμοποιήσουμε τις εγγενείς κλήσεις στοίβας για να εφαρμόσουμε αναδρομικά το DFS. Η λογική είναι η ίδια.

Η πολυπλοκότητα του χρόνου είναι η ίδια με BFS, O (V + E).

function DFS Initialize an empty stack, empty 'result' array & a 'visited' map Add the starting vertex to the stack & visited map While Stack is not empty: - Pop and store current vertex - Push current vertex to result array - Iterate through current vertex's adjacency list: - For each adjacent vertex, if vertex is unvisited: - Add vertex to visited map - Push vertex to stack Return result array
Graph.prototype.bfs = function(start) { const queue = [start]; const result = []; const visited = {}; visited[start] = true; let currentVertex; while (queue.length) { currentVertex = queue.shift(); result.push(currentVertex); this.adjacencyList[currentVertex].forEach(neighbor => { if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } }); } return result; } Graph.prototype.dfsRecursive = function(start) { const result = []; const visited = {}; const adjacencyList = this.adjacencyList; (function dfs(vertex){ if (!vertex) return null; visited[vertex] = true; result.push(vertex); adjacencyList[vertex].forEach(neighbor => { if (!visited[neighbor]) { return dfs(neighbor); } }) })(start); return result; } Graph.prototype.dfsIterative = function(start) { const result = []; const stack = [start]; const visited = {}; visited[start] = true; let currentVertex; while (stack.length) { currentVertex = stack.pop(); result.push(currentVertex); this.adjacencyList[currentVertex].forEach(neighbor => { if (!visited[neighbor]) { visited[neighbor] = true; stack.push(neighbor); } }); } return result; }

Αναζήτηση λαβυρίνθου

Δήλωση προβλήματος:

Λαμβάνοντας υπόψη μια 2D σειρά ασπρόμαυρων καταχωρήσεων που αντιπροσωπεύουν λαβύρινθο με καθορισμένα σημεία εισόδου και εξόδου, βρείτε ένα μονοπάτι από την είσοδο προς την έξοδο, εάν υπάρχει. - Aziz, Adnan, et al. Στοιχεία συνεντεύξεων προγραμματισμού

Θα αντιπροσωπεύσουμε τις λευκές καταχωρήσεις με 0 και τις μαύρες καταχωρήσεις με 1. Οι λευκές καταχωρήσεις αντιπροσωπεύουν ανοιχτές περιοχές και οι μαύροι τοίχοι εισόδων. Τα σημεία εισόδου και εξόδου αντιπροσωπεύονται από έναν πίνακα, τον 0ο δείκτη και τον 1ο δείκτη γεμάτο με τους δείκτες γραμμής και στήλης, αντίστοιχα.

Λύση:

  • Για να μετακινηθείτε σε διαφορετική θέση, θα κωδικοποιήσουμε τις τέσσερις πιθανές κινήσεις στη σειρά κατευθύνσεων (δεξιά, κάτω, αριστερά και πάνω · χωρίς διαγώνιες κινήσεις):
[ [0,1], [1,0], [0,-1], [-1,0] ]
  • Για να παρακολουθείτε τα κελιά που έχουμε ήδη επισκεφτεί, θα αντικαταστήσουμε τις λευκές καταχωρίσεις ( 0 ) με μαύρες καταχωρήσεις ( 1's ) Βασικά χρησιμοποιούμε το DFS αναδρομικά για να διασχίσουμε το λαβύρινθο. Η βασική περίπτωση, που θα τερματίσει την επανάληψη, είναι είτε έχουμε φτάσει στο σημείο εξόδου μας και επιστρέψουμε αληθινές είτε έχουμε επισκεφθεί κάθε λευκή είσοδο και επιστρέφουμε ψευδείς .
  • Ένα άλλο σημαντικό πράγμα που πρέπει να παρακολουθείτε είναι να διασφαλίσουμε ότι είμαστε μέσα στα όρια του λαβύρινθου όλη την ώρα και ότι μόνο προχωρήσουμε αν είμαστε σε ένα λευκό εισόδου . Η λειτουργία isFeasible θα το φροντίσει.
  • Πολυπλοκότητα χρόνου: O (V + E)

Ψευδοκώδικας:

function hasPath Start at the entry point While exit point has not been reached 1. Move to the top cell 2. Check if position is feasible (white cell & within boundary) 3. Mark cell as visited (turn it into a black cell) 4. Repeat steps 1-3 for the other 3 directions
var hasPath = function(maze, start, destination) { maze[start[0]][start[1]] = 1; return searchMazeHelper(maze, start, destination); }; function searchMazeHelper(maze, current, end) { // dfs if (current[0] == end[0] && current[1] == end[1]) { return true; } let neighborIndices, neighbor; // Indices: 0->top,1->right, 2->bottom, 3->left let directions = [ [0,1] , [1,0] , [0,-1] , [-1,0] ]; for (const direction of directions) { neighborIndices = [current[0]+direction[0], current[1]+direction[1]]; if (isFeasible(maze, neighborIndices)) { maze[neighborIndices[0]][neighborIndices[1]] = 1; if (searchMazeHelper(maze, neighborIndices, end)) { return true; } } } return false; } function isFeasible(maze, indices) { let x = indices[0], y = indices[1]; return x >= 0 && x = 0 && y < maze[x].length && maze[x][y] === 0; } var maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]] hasPath(maze, [0,4], [3,2]);

Χρωματίστε ένα Boolean Matrix

Δήλωση προβλήματος:

Εφαρμόστε μια ρουτίνα που παίρνει ένα n X m Boolean array A μαζί με μια καταχώριση (x, y) και αναστρέφει το χρώμα της περιοχής που σχετίζεται με (x, y). - Aziz, Adnan, et al. Στοιχεία συνεντεύξεων προγραμματισμού

Τα 2 χρώματα θα αντιπροσωπεύονται από 0 και 1.

Στο παρακάτω παράδειγμα, ξεκινάμε στο κέντρο του πίνακα ([1,1]). Σημειώστε ότι από αυτήν τη θέση, μπορούμε να φτάσουμε μόνο στην άνω, αριστερή τριγωνική μήτρα. Δεν είναι δυνατή η επίτευξη της δεξιάς, της χαμηλότερης θέσης ([2,2]). Ως εκ τούτου, στο τέλος της διαδικασίας, είναι το μόνο χρώμα που δεν αναστρέφεται.

Λύση:

  • Όπως και στην προηγούμενη ερώτηση, θα κωδικοποιήσουμε έναν πίνακα για να καθορίσουμε τις 4 πιθανές κινήσεις.
  • Θα χρησιμοποιήσουμε το BFS για να διασχίσουμε το γράφημα.
  • Θα τροποποιήσουμε ελαφρώς τη λειτουργία isFeasible. Θα συνεχίσει να ελέγχει αν η νέα θέση βρίσκεται εντός των ορίων της μήτρας. Η άλλη απαίτηση είναι ότι η νέα θέση έχει το ίδιο χρώμα με την προηγούμενη θέση. Εάν η νέα θέση ταιριάζει με τις απαιτήσεις, το χρώμα της αναστρέφεται
  • Χρόνος πολυπλοκότητας: O (mn)

Ψευδοκώδικας:

function flipColor Start at the passed coordinates and store the color Initialize queue Add starting position to queue While Queue is not empty: - Dequeue and store current position - Move to the top cell 1. Check if cell is feasible 2. If feasible, - Flip color - Enqueue cell 3. Repeat steps 1-2 for the other 3 directions
function flipColor(image, x, y) { let directions = [ [0,1] , [1,0] , [0,-1] , [-1,0] ]; let color = image[x][y]; let queue = []; image[x][y] = Number(!color); queue.push([x,y]); let currentPosition, neighbor; while (queue.length) { currentPosition = queue.shift(); for (const direction of directions) { neighbor = [currentPosition[0]+direction[0], currentPosition[1]+direction[1]]; if (isFeasible(image, neighbor, color)) { image[neighbor[0]][neighbor[1]] = Number(!color); queue.push([neighbor[0], neighbor[1]]); } } } return image; } function isFeasible(image, indices, color) { let x = indices[0], y = indices[1]; return x >= 0 && x = 0 && y < image[x].length && image[x][y] == color; } var image = [[1,1,1],[1,1,0],[1,0,1]]; flipColor(image,1,1);

Υπολογισμός κλειστών περιοχών

Δήλωση προβλήματος:

Αφήστε το A να είναι ένας 2D πίνακας του οποίου οι καταχωρήσεις είναι είτε W είτε B. Γράψτε ένα πρόγραμμα που παίρνει το A και αντικαθιστά όλα τα W που δεν μπορούν να φτάσουν στα όρια με ένα B. - Aziz, Adnan, et al. Στοιχεία συνεντεύξεων προγραμματισμού

Λύση:

  • Instead of iterating through all the entries to find the enclosed W entries, it is more optimal to start with the boundary W entries, traverse the graph and mark the connected W entries. These marked entries are guaranteed to be not enclosed since they are connected to a W entry on the border of the board. This preprocessing is basically the complement of what the program has to achieve.
  • Then, A is iterated through again and the unmarked W entries (which will be the enclosed ones) are changed into the B entries.
  • We’ll keep track of the marked and unmarked W entries using a Boolean array of the same dimensions as A. A marked entry will be set to true.
  • Time complexity: O(mn)

Pseudocode:

function fillSurroundedRegions 1. Initialize a 'visited' array of same length as the input array pre-filled with 'false' values 2. Start at the boundary entries 3. If the boundary entry is a W entry and unmarked: Call markBoundaryRegion function 4. Iterate through A and change the unvisited W entry to B function markBoundaryRegion Start with a boundary W entry Traverse the grid using BFS Mark the feasible entries as true
function fillSurroundedRegions(board) { if (!board.length) { return; } const numRows = board.length, numCols = board[0].length; let visited = []; for (let i=0; i
    

Deadlock Detection (Cycle In Directed Graph)

Problem Statement:

One deadlock detection algorithm makes use of a “wait-for” graph to track which other processes a process is currently blocking on. In a wait-for graph, processes are represented as nodes, and an edge from process P to 0 implies 0 is holding a resource that P needs and thus P is waiting for 0 to release its lock on that resource. A cycle in this graph implies the possibility of a deadlock. This motivates the following problem.

Write a program that takes as input a directed graph and checks if the graph contains a cycle. – Aziz, Adnan, et al. Elements of Programming Interviews

In the wait-for graph above, our deadlock detection program will detect at least one cycle and return true.

For this algorithm, we’ll use a slightly different implementation of the directed graph to explore other data structures. We are still implementing it using the adjacency list but instead of an object (map), we’ll store the vertices in an array.

The processes will be modeled as vertices starting with the 0th process. The dependency between the processes will be modeled as edges between the vertices. The edges (adjacent vertices) will be stored in a Linked List, in turn stored at the index that corresponds to the process number.

class Node { constructor(data) { this.data = data; this.next = null; } } class LinkedList { constructor() { this.head = null; } insertAtHead(data) { let temp = new Node(data); temp.next = this.head; this.head = temp; return this; } getHead() { return this.head; } } class Graph { constructor(vertices) { this.vertices = vertices; this.list = []; for (let i=0; i
     

Solution:

  • Every vertex will be assigned 3 different colors: white, gray and black. Initially all vertices will be colored white. When a vertex is being processed, it will be colored gray and after processing black.
  • Use Depth First Search to traverse the graph.
  • If there is an edge from a gray vertex to another gray vertex, we’ve discovered a back edge (a self-loop or an edge that connects to one of its ancestors), hence a cycle is detected.
  • Time Complexity: O(V+E)

Pseudocode:

function isDeadlocked Color all vertices white Run DFS on the vertices 1. Mark current node Gray 2. If adjacent vertex is Gray, return true 3. Mark current node Black Return false
const Colors = { WHITE: 'white', GRAY: 'gray', BLACK: 'black' } Object.freeze(Colors); function isDeadlocked(g) { let color = []; for (let i=0; i
      

Clone Graph

Problem Statement:

Consider a vertex type for a directed graph in which there are two fields: an integer label and a list of references to other vertices. Design an algorithm that takes a reference to a vertex u, and creates a copy of the graph on the vertices reachable from u. Return the copy of u. – Aziz, Adnan, et al. Elements of Programming Interviews

Solution:

  • Maintain a map that maps the original vertex to its counterpart. Copy over the edges.
  • Use BFS to visit the adjacent vertices (edges).
  • Time Complexity: O(n), where n is the total number of nodes.

Pseudocode:

function cloneGraph Initialize an empty map Run BFS Add original vertex as key and clone as value to map Copy over edges if vertices exist in map Return clone
class GraphVertex { constructor(value) { this.value = value; this.edges = []; } } function cloneGraph(g) { if (g == null) { return null; } let vertexMap = {}; let queue = [g]; vertexMap[g] = new GraphVertex(g.value); while (queue.length) { let currentVertex = queue.shift(); currentVertex.edges.forEach(v => { if (!vertexMap[v]) { vertexMap[v] = new GraphVertex(v.value); queue.push(v); } vertexMap[currentVertex].edges.push(vertexMap[v]); }); } return vertexMap[g]; } let n1 = new GraphVertex(1); let n2 = new GraphVertex(2); let n3 = new GraphVertex(3); let n4 = new GraphVertex(4); n1.edges.push(n2, n4); n2.edges.push(n1, n3); n3.edges.push(n2, n4); n4.edges.push(n1, n3); cloneGraph(n1);

Making Wired Connections

Problem Statement:

Design an algorithm that takes a set of pins and a set of wires connecting pairs of pins, and determines if it is possible to place some pins on the left half of a PCB, and the remainder on the right half, such that each wire is between left and right halves. Return such a division, if one exists. – Aziz, Adnan, et al. Elements of Programming Interviews

Solution:

  • Model the set as a graph. The pins are represented by the vertices and the wires connecting them are the edges. We’ll implement the graph using an edge list.

The pairing described in the problem statement is possible only if the vertices (pins) can be divided into “2 independent sets, U and V such that every edge (u,v) either connects a vertex from U to V or a vertex from V to U.” (Source) Such a graph is known as a Bipartite graph.

To check whether the graph is bipartite, we’ll use the graph coloring technique. Since we need two sets of pins, we have to check if the graph is 2-colorable (which we’ll represent as 0 and 1).

Initially, all vertices are uncolored (-1). If adjacent vertices are assigned the same colors, then the graph is not bipartite. It is not possible to assign two colors alternately to a graph with an odd length cycle using 2 colors only, so we can greedily color the graph.

Extra step: We will handle the case of a graph that is not connected. The outer for loop takes care of that by iterating over all the vertices.

  • Time Complexity: O(V+E)

Pseudocode:

function isBipartite 1. Initialize an array to store uncolored vertices 2. Iterate through all vertices one by one 3. Assign one color (0) to the source vertex 4. Use DFS to reach the adjacent vertices 5. Assign the neighbors a different color (1 - current color) 6. Repeat steps 3 to 5 as long as it satisfies the two-colored constraint 7. If a neighbor has the same color as the current vertex, break the loop and return false
function isBipartite(graph) { let color = []; for (let i=0; i
       

Transform one string to another

Problem Statement:

Given a dictionary D and two strings s and f, write a program to determine if s produces t. Assume that all characters are lowercase alphabets. If s does produce f, output the length of a shortest production sequence; otherwise, output -1. – Aziz, Adnan, et al. Elements of Programming Interviews

For example, if the dictionary D is ["hot", "dot", "dog", "lot", "log", "cog"], s is "hit" and t is "cog", the length of the shortest production sequence is 5.

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

Solution:

  • Represent the strings as vertices in an undirected, unweighted graph, with an edge between 2 vertices if the corresponding strings differ in one character at most. We'll implement a function (compareStrings) that calculates the difference in characters between two strings.
  • Piggybacking off the previous example, the vertices in our graph will be
{hit, hot, dot, dog, lot, log, cog}
  • The edges represented by the adjacency list approach we discussed in section 0. Graph Implementation, will be:
{ "hit": ["hot"], "hot": ["dot", "lot"], "dot": ["hot", "dog", "lot"], "dog": ["dot", "lot", "cog"], "lot": ["hot", "dot", "log"], "log": ["dog", "lot", "cog"], "cog": ["dog", "log"] }
  • Once we finish building the graph, the problem boils down to finding the shortest path from a start node to a finish node. This can be naturally computed using Breadth First Search.
  • Time Complexity: O(M x M x N), where M is the length of each word and N is the total number of words in the dictionary.

Pseudocode:

function compareStrings Compare two strings char by char Return how many chars differ function transformString 1. Build graph using compareStrings function. Add edges if and only if the two strings differ by 1 character 2. Run BFS and increment length 3. Return length of production sequence
function transformString(beginWord, endWord, wordList) { let graph = buildGraph(wordList, beginWord); if (!graph.has(endWord)) return 0; let queue = [beginWord]; let visited = {}; visited[beginWord] = true; let count = 1; while (queue.length) { let size = queue.length; for (let i=0; i { if (!visited[neighbor]) { queue.push(neighbor); visited[neighbor] = true; } }) } count++; } return 0; }; function compareStrings (str1, str2) { let diff = 0; for (let i=0; i { graph.set(word, []); wordList.forEach( (nextWord) => { if (compareStrings(word, nextWord) == 1) { graph.get(word).push(nextWord); } }) }) if (!graph.has(beginWord)) { graph.set(beginWord, []); wordList.forEach( (nextWord) => { if (compareStrings(beginWord, nextWord) == 1) { graph.get(beginWord).push(nextWord); } }) } return graph; }

Where to go from here?

Hopefully, by the end of this article, you have realized that the most challenging part in graph problems is identifying how to model the problems as graphs. From there, you can use/modify the two graph traversals to get the expected output.

Other graph algorithms that are nice to have in your toolkit are:

  • Topological Ordering
  • Shortest Path Algorithms (Dijkstra and Floyd Warshall)
  • Minimum Spanning Trees Algorithms (Prim and Kruskal)

If you found this article helpful, consider buying me a coffee. It will keep me awake when I work on a video tutorial of this article :)                                        

References:

Aziz, Adnan, et al. Elements of Programming Interviews. 2nd ed., CreateSpace Independent Publishing Platform, 2012.