Author: Shiva Charan Devabhaktuni

Categories
interview

Filter objects (ES6)

// There could potentially be more than 3 keys in the object below.
const items = [{
    color: 'red',
    type: 'tv',
    age: 18
  },
  {
    color: 'silver',
    type: 'phone',
    age: 20
  },
  {
    color: 'yellow',
    type: 'truck',
    age: 10
  },
  {
    color: 'blue',
    type: 'shirt',
    age: 5
  },
];

const excludes = [{
    k: 'color',
    v: 'silver'
  },
  {
    k: 'type',
    v: 'tv'
  },
  {
    k: 'color',
    v: 'red'
  }
];

// SOLUTION

const excludesMap = excludes.reduce((acc, curr) => {
  (acc[curr.k] || (acc[curr.k] = {}))[curr.v] = true;
  return acc;
}, {});

/*
color: red: true,
       green: true ... 
type: tv: true
       truck: true, ...

*/

const exclude = (items, excludes) => items.filter(item => {
  for (const [key, value] of Object.entries(item)) {
   if(excludesMap[key]?.[value])
      return false;
  }
  return true;
});

console.log(exclude(items, excludes));
/*
  [{
    age: 10,
    color: "yellow",
    type: "truck"
  }, {
    age: 5,
    color: "blue",
    type: "shirt"
  }]
*/

Demo

Categories
Uncategorized

Flatten an Array (ES6)

To flatten an array with depth of level 1:

const inputArray = [1, 2, 3, [4, 5]];
console.log([].concat(...inputArray));
// Output: [1, 2, 3, 4, 5]

Demo

To flatten an array of a specified depth:

const input = [1, 2, 3, [4, 5, 6, [8, 9, 10]], 11, [12, 13, 14]];

const flatten = (arr, depth) =>
  depth === 0 || !Array.isArray(arr) ? arr :
  arr.reduce((acc, curr) =>
    Array.isArray(curr) ? acc.concat(flatten(curr, depth - 1)) :
    acc.concat(curr), [])

console.log(flatten(input, 3));
// Ouput: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14]

Demo

To flatten an array infinitely:

const input = [1, 2, 3, [4, 5, 6, [8, 9, 10]], 11, [12, 13, 14]];

const flatten = (arr) =>
   !Array.isArray(arr) ? arr : arr.reduce((acc, curr) =>
    Array.isArray(curr) ? acc.concat(flatten(curr)) :
    acc.concat(curr), []);

console.log(flatten(input));
// Ouput: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14]

Demo

Categories
Uncategorized

Priority Queue Comparator using a HashMap

This is similar to a MinHeap.

import java.util.*; 
import java.lang.*;
 
public class GFG { 

    public static void main(String[] args) 
    { 
        HashMap<Integer, Integer> map 
            = new HashMap<>(); 
            map.put(10, 3);
            map.put(20, 2);
            map.put(30, 1);
      PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a,b) -> map.get(a) - map.get(b));
      pq.add(10);
      pq.add(30);
      pq.add(20);
      System.out.println(pq.poll());
      System.out.println(pq.poll());
      System.out.println(pq.poll());
    }   
}

Output

30
20
10
Categories
interview

Rotate Matrix

To perform in place rotation of a matrix, the matrix needs to be a square matrix (n x n i.e., n-rows and n-columns). This case is similar to a square image rotation. The Javascript (ES6) code to rotate a square matrix 90° in clockwise direction is as follows:

const rotateMatrix = inp => {
  let n = inp.length;
  for (let layer = 0; layer < Math.floor(n / 2); layer++) {
    for (let start = layer; start < n - layer - 1; start++) {
      let temp = inp[layer][start];
      inp[layer][start] = inp[n - start - 1][layer];
      inp[n - start - 1][layer] = inp[n - layer - 1][n - start - 1];
      inp[n - layer - 1][n - start - 1] = inp[start][n - layer - 1];
      inp[start][n - layer - 1] = temp;
    }
  }
};

const matrix = [
  [3, 4, 5],
  [2, 0, 6],
  [1, 8, 7]
];
rotateMatrix(matrix);
console.log(matrix);
/*
  [
    [1, 2, 3],
    [8, 0, 4],
    [7, 6, 5]
  ]
*/

Demo

Categories
Uncategorized

CSS animation – Card Slide-In

Using CSS @keyframes you can animate cards from left to right in the following way. This works on almost all major modern browsers.

Demo

Card 1

Card 2

<style>
.card {
  height: 100px;
  width: 250px;
  background: white;
  border-radius: 8px;
  border: 1px solid #999;
  box-shadow: 5px 5px 5px #999;
  animation: slidein 5s;
  animation-fill-mode: forwards;
  margin-right: 16px;
  transition-timing-function: cubic-bezier(0.1, 0.7, 1, 0.1);
}

@keyframes slidein {
  from {
    transform: translateX(-100%);
  }

  to {
    transform: translateX(100%);
  }
}
</style>
<div style="display:flex;">
  <div class="card">
  </div>
  <div class="card">
  </div>
  <div class="card">
  </div>
</div>
Categories
interview

Currying

Breaking down a function into a series of function calls with an argument. The following is an Javascript ES6 example of a sum function that returns the sum of the calls until no argument is passed.

Code

const sum = (val) => {
  let total = 0;
  if (val === undefined) {
    return total;
  }
  total = val;
  const ret = (x) => {
    if (x === undefined) {
      return total;
    }
    total += x;
    return ret;
  };
  return ret;
};

console.log(sum(5)(6)(0)(-1)()); // 10

Demo

Categories
Uncategorized

Copy to clipboard ES6 + Deselect

Code

<script>
const copy = () => {
  const elem = document.getElementById('demo');
  elem.select();
  document.execCommand('copy');
  elem.blur();
}
</script>
<input type="text" id="demo" value="Hello World!" />
<button onclick="copy()">
  Copy
</button>

Demo

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--;
    }
}