Categories
interview

Throttling (ES6)

Sometimes, we need to limit the number of method calls based on time. A throttling method is the way to go.

Code

/**
 * @param {(...args:any[]) => any} func
 * @param {number} wait
 * @returns {(...args:any[]) => any}
 */
function throttle(func, wait) {
  let blocked = false;
  let lastArgs;

  const caller = function() {
    if (lastArgs) {
      func.apply(this, lastArgs);
      setTimeout(caller, wait);
      lastArgs = undefined;
    } else {
      blocked = false;
    }
  };

  return function(...args) {
    if (!blocked) {
      blocked = true;
      func.apply(this, args); // leading vs trailing throttling.
      setTimeout(caller, wait);
    } else {
      lastArgs = args;
    }
  };
}

const logger = (inp) => console.log(inp);

const throttledMethod = throttle(logger, 1000);

const button = document.createElement('button');
button.innerText = 'Throttle';
document.body.appendChild(button);
button.addEventListener('click', () => throttledMethod('Hello World!'));

Demo

Categories
interview

Range Sum Query 2D Mutable – Java

We can use a 2D Binary Indexed Tree (Fenwick Tree) to efficiently calculate sum in a rectangular area in a mutable 2D matrix.

public class RangeSum {
    int[][] bit;
    int[][] inp;

    public RangeSum(int[][] inp) {
        this.inp = inp;
        this.bit = new int[inp.length + 1][inp[0].length + 1];
        for (int i = 0; i < inp.length; i++)
            for (int j = 0; j < inp[0].length; j++)
                add(i, j, inp[i][j]);
    }

    public void add(int i, int j, int delta) {
        // Increment the first set bit from the right. 
        // https://www.quora.com/In-programming-what-does-n-n-return
        // Faster increment i = i | (i + 1)
        for (int row = i + 1; row <= this.inp.length; row += row & (-row))
            for (int col = j + 1; col <= this.inp[0].length; col += col & (-col))
                this.bit[row][col] += delta;
    }

    public void update(int i, int j, int value) {
        int delta = value - this.inp[i][j];
        this.inp[i][j] = value;
        this.add(i, j, delta);
    }

    public int calcSum(int i, int j) {
        int sum = 0;
        // Remove the first set bit from the right.
        // Faster decrement i = (i & (i + 1)) - 1
        for (int row = i + 1; row > 0; row -= row & (-row))
            for (int col = j + 1; col > 0; col -= col & (-col))
                sum += this.bit[row][col];
        return sum;
    }

    public int getSum(int row1, int col1, int row2, int col2) {
        return calcSum(row2, col2) - calcSum(row1 - 1, col2) - calcSum(row2, col1 - 1) + calcSum(row1 - 1, col1 - 1);
    }

    public static void main(String[] args) {
        int[][] arr = {
                        {1, 2, 3},
                        {4, 5, 6},
                        {7, 8, 9}
                      };
        RangeSum rangeSum = new RangeSum(arr);
        System.out.println(rangeSum.getSum(1, 1, 2, 2)); // 28
        rangeSum.update(1, 1, 10);
        System.out.println(rangeSum.getSum(0, 0, 2, 2)); // 50
        System.out.println(rangeSum.getSum(1, 1, 2, 2)); // 33
    }
}

An alternative approach could be to convert the 2D array into a 1D array. For example:

...

public int getIndex(int x, int y) {
  // Size of the array is this.totalColumns * this.totalRows
  return this.totalColumns * x + y;
}

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');
    }
}
Categories
Uncategorized

Drag Drop ES6

The following code demonstrates drag drop functionality in ES6.

<script>
  const onDrop = (e) => {
    e.preventDefault();
 e.target.appendChild(document.getElementById(e.dataTransfer.getData('target')));
  };
  const onDragOver = (e) => e.preventDefault();
  const onDragStart = (e) => e.dataTransfer.setData('target', e.target.id);
  
</script>
<div id="dest" ondrop="onDrop(event)" ondragover="onDragOver(event)" style="height: 200px; width: 200px; border: 1px solid #000; padding: 10px; box-sizing: border-box;"></div>
<img id="source" draggable="true" ondragstart="onDragStart(event)" src="http://via.placeholder.com/180x180" />

Demo

Categories
Uncategorized

Loader ES6

The following is the implementation of a simple Javascript (ES6) loader.

<script>
  const load = () => {
    let width = 0;
    const id = setInterval(() => {
      if (width === 100)
        clearInterval(id);
      else
        document.getElementById('bar').style.width = `${++width}%`;
    }, 10);
  };
</script>
<div id="loader" style="height: 100px; width: 600px; border: 1px solid #000;">
  <div id="bar" style="background-color: green; width: 0; height: 100px;" class="">
  </div>
</div>
<button onclick="load()">Load</button>

Demo

Categories
Uncategorized

Add Events ES6

In the example below, we create a button and attach a click event to it.

const button = document.createElement('button');
 button.innerHTML = 'Click';
 document.body.appendChild(button);
 const test = (val) => {
   console.log('clicked ' + val);
 };
 button.addEventListener('click', test.bind(this, 'test'));

Demo

Categories
interview

Debounce (ES6)

Sometimes, we would like to wait a certain minimum time period before successive method calls. For example in events like onscroll(), onresize(), this can go a long way in terms of optimizing the page performance as a whole.

The wrapping of the methods using a Debounce method is a simple way to achieve the desired result.

const debounce = (fn, interval) => {
  let timeout;
  return (...rest) => {
    if (timeout)
      clearTimeout(timeout);
      timeout = setTimeout(() => {
        fn.apply(this, rest);
      }, interval);
  };
}

const test = (inp) => {
  console.log(inp);
};

const db = debounce(test, 1000);
const cb = () => {
  db('test');
};
const button = document.createElement('button');
button.innerHTML = 'fire';
document.body.appendChild(button);
button.addEventListener('click', cb);

Demo

Categories
interview

Minimum Window Substring – Java

The brute force method would be calculate all the substrings, which would be inefficient.

Runtime Complexity O(m + n)

Space Complexity O(m+n)

class Solution {
    public String minWindow(String s, String t) {
        int tLen = t.length();
        int sLen = s.length();
        if (tLen > sLen)
            return "";
        int[] pattern = new int[256];
        int[] given = new int[256];
        for (int i = 0; i < tLen; i++)
            pattern[t.charAt(i)]++;
        int mstart = 0, size = 0, start = 0, min = sLen + 1;
        for (int j = 0; j < s.length(); j++) {
            char curr = s.charAt(j);
            if (given[curr] < pattern[curr])
                size++;
            given[curr]++;
            if (size == tLen) {
                while (given[s.charAt(start)] > pattern[s.charAt(start)]) {
                    given[s.charAt(start)]--;
                    start++;
                }
                int len = j - start + 1;
                if (len < min) {
                    min = len;
                    mstart = start;
                }
            }
        }
        if (size < tLen)
            return "";
        return s.substring(mstart, mstart + min);
    }
}