Euclidean Algorithm

The Euclidean algorithm finds the greatest common divisor (GCD) of two non-negative integers and is often used to showcase the concept of recursion.

Java Implementations

The source code containing four different implementations can be found here, showcasing both recursive and iterative concepts.

JavaScript Demo

Graph Clone

Problem

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

A graph is defined as:

struct Node {
    vector neighbors;
}

Solution

A simple breadth-first traversal is being used.

typedef unordered_map<Node *, Node *> Map;

Node *clone(Node *graph) {
    if (!graph) return NULL;

    Map map;
    queue<Node *> q;
    q.push(graph);

    Node *graphCopy = new Node();
    map[graph] = graphCopy;

    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        int n = node->neighbors.size();
        for (int i = 0; i < n; i++) {
            Node *neighbor = node->neighbors[i];

            if (map.find(neighbor) == map.end()) {
                Node *p = new Node();
                map[node]->neighbors.push_back(p);
                map[neighbor] = p;
                q.push(neighbor);
            } else {
                map[node]->neighbors.push_back(map[neighbor]);
            }
        }
    }

    return graphCopy;
}

Babylonian Algorithm

\text{Computing the square root} \, \sqrt[k]{a} \, \text{for} \, a > 0

Gray Code

Encoding

public String[] encodeGrayCode(int n){
    String[] result = new String[n];
    for (int i = 0; i < n; i++) {
       int shift = i >>> 1;
       int gray = shift ^ i;
       result[i] = Integer.toBinaryString(gray);
    }
    return result;
}

Decoding

public int decodeGrayCode(int n){
    int output = n;
    while ((n >>>= 1) != 0) {
        output ^= n;
    }
    return output;
}