Month: January 2019

Categories
interview

Union find with path compression (Js, Java)

Javascript (ES6)

class UnionFind {
  constructor() {
    this.nodes = 0;
    this.sizeOf = [];
    this.parent = [];
    for (let i = 0; i < 10; i++) {
      this.nodes++;
      this.size[i] = 1;
      this.parent[i] = i;
    }
  }

  rootOf = (a) => {
    let current = a;
    while (this.parent[current] !== current) {
      current = this.parent[current];
    }
    this.compress(a, current);
    return current;
  };

  compress = (a, root) => {
    let curr = a;
    while (this.parent[current] !== current) {
      const next = this.parent[current];
      this.parent[current] = root;
      curr = next;
    }
    return current;
  };

  union = (a, b) => {
    const ap = rootOf(a);
    const bp = rootOf(b);
    if (this.sizeOf[ap] < this.sizeOf[bp]) {
      this.parent[ap] = bp;
      this.sizeOf[bp] += this.sizeOf[ap];
      this.compress(a, bp);
    } else {
      this.parent[bp] = ap;
      this.sizeOf[ap] += this.sizeOf[bp];
      this.compress(b, ap);
    }
    this.nodes--;
  };
}

Demo

Java

class UnionFind {
    int count;
    int[] parent;
    int[] size;

    public UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public find(int a) {
        int root = a;
        while (parent[root] != root)
            root = parent[root];
        compress(a, root);
        return root;
    }

    public void compress(int a, int root) {
        while (a != root) {
            int next = parent[a];
            parent[a] = root;
            a = next;
        }
    }

    public void union(int a, int b) {

        if (find(a) == find(b))
            return;

        int ap = parent[a];
        int bp = parent[b];

        if (size[ap] <= size[bp]) {
            parent[ap] = bp;
            size[bp] += size[ap];
            compress(a, bp);
        } else {
            parent[bp] = ap;
            size[ap] += size[bp];
            compress(b, ap);
        }
        count--;
    }
}
Categories
interview

Dropdown ES6

<html>

  <head>
    <style>
      .dropdown {
        position: relative;
        display: inline-block;
      }

      .dropdown-container {
        display: none;
        position: absolute;
        width: 150px;
        border: 1px solid #000;
      }

      .show {
        display: block;
      }

    </style>
    <script>
      const toggle = (e) => {
        document.getElementById('req')
        .classList.toggle('show');
        e.stopPropagation();
      };

      const bodyHandle = (e) => {
        if (document.getElementById('req')
          .classList.contains('show')) {
          document.getElementById('req')
            .classList.toggle('show');
        }
      };

    </script>
  </head>

  <div onclick="bodyHandle(event)"
       style="width: 100vw;
              height: 100vh;
              background-color: lightgreen;">
    <div class="dropdown" onclick="toggle(event)"
         style="background-color: skyblue;">
      <button id="button">Click</button>
      <div id="req" class="dropdown-container"
           style="background-color: lightyellow;">
        <div>item 1</div>
        <div>item 2</div>
        <div>item 3</div>
      </div>
    </div>
  </div>
  </body>

</html>

Demo

Categories
Uncategorized

Shifting Letters – Java O(n)

class Solution {
    public String shiftingLetters(String S, int[] shifts) {
        int n = shifts.length;
        int prev = 0;
        char[] arr = S.toCharArray();
        for (int i = n - 1; i >= 0; i--) {
            prev += shifts[i] % 26;
            arr[i] = getNextChar(arr[i], prev);
        }
        return new String(arr);
    }

    public char getNextChar(char a, int diff) {
        return (char)((((a - 'a') + diff) % 26) + 'a');
    }
}