Categories
interview

Use DFS to flatten Javascript Objects

This is straight forward implementation of the DFS (Depth First Search) traversal algorithm using recursion.

 var obj = {
  baz: {
    foo: {
      bar: "5"
    },
    hell: {
      sin: "0"
    }
  },
  a: {
    b: "1"
  }
};

var hash = {};
var str = '';

var dfs = function(obj, str) {
  for (var key in obj) {
    if (obj.hasOwnProperty(key)) {
      if (typeof obj[key] === 'string')
        hash[str + key] = obj[key];
      else {
        dfs(obj[key], str + key + '.');
      }
    }
  }
};
dfs(obj, str);
console.log(hash);
var obj = {
  baz: {
    foo: {
      bar: "5"
    },
    hell: {
      sin: "0"
    }
  },
  a: {
    b: "1"
  }
};
var tracker = [];
var hashMap = {};
var hashKey = '';

function dfs(obj, tracker) {
  for (var key in obj) {
    if (obj.hasOwnProperty(key)) {

      if (typeof obj[key] == "string") {
        tracker.push(key);
        hashKey = appendArray(tracker);
        hashMap[hashKey] = obj[key];
        tracker.pop();
      } else {
        tracker.push(key);
        dfs(obj[key], tracker);
        tracker.pop();
      }
    }
  }
}
dfs(obj, tracker);
console.log(hashMap);

function appendArray(arr) {
  var ret = '';
  for (var i = 0; i < arr.length; i++) {
    ret = ret + '.' + arr[i];
  }
  return ret.substring(1, ret.length);
}

const test = {
  baz: {
    foo: {
      bar: "5"
    },
    hell: {
      sin: "0"
    }
  },
  a: {
    b: "1"
  }
};

const flatten = (obj, str = '', temp = {}) => {
  for (const [key, val] of Object.entries(obj)) {
    if (typeof val === 'object') {
      flatten(val, `${str}${key}.`, temp);
    } else {
      temp[`${str}${key}`] = val;
    }
  }
};

const output = {};
flatten(test, '', output);
console.log(output);

Output

Object {baz.foo.bar: "5", baz.another.bar: "0", a.b: "1"}

Demo

Categories
interview

Get maximum sum rectangle sub matrix in a 2D matrix

This problem can be solved using Kadane’s Algorithm.
We start by taking an empty array of zeros of size of the number of rows of input matrix.
We move from left to right columns and calculate max for every column and update up, down, left, right accordingly.
Input matrix mxn
Time = O(m*n*n)
Space = O(m)

package algos;

import java.util.HashMap;

class solution {

	public solution() {
	}

	public HashMap getMaxSum(int[] arr) {
		int max = arr[0], start = 0, end = 0, mstart = 0, mend = 0, currmax = arr[0];
		for (int i = 1; i < arr.length; i++) {

			if (arr[i] > arr[i] + currmax) {
				currmax = arr[i];
				start = i;
				end = i;
			} else {
				currmax = currmax + arr[i];
				end = i;
			}

			if (currmax > max) {
				max = currmax;
				mstart = start;
				mend = end;
			}
		}
		HashMap result = new HashMap();
		result.put("up", mstart);
		result.put("down", mend);
		result.put("max", max);
		return result;
	}

	public HashMap getMaxSubArray(int[][] matrix) {
		int max = matrix[0][0], left = 0, right = 0, up = 0, down = 0;
		int[] rowArray = new int[matrix.length];
		for (int cl = 0; cl < matrix[0].length; cl++) {
			for (int i = 0; i < matrix.length; i++) {
				rowArray[i] = 0;
			}
			for (int cr = cl; cr < matrix[0].length; cr++) {
				for (int row = 0; row < matrix.length; row++) {
					rowArray[row] += matrix[row][cr];
				}
				HashMap currentSet = getMaxSum(rowArray);
				if (currentSet.get("max") > max) {
					max = currentSet.get("max");
					up = currentSet.get("up");
					down = currentSet.get("down");
					left = cl;
					right = cr;
				}
			}
		}

		HashMap result = new HashMap();
		result.put("up", up);
		result.put("down", down);
		result.put("left", left);
		result.put("right", right);
		result.put("max", max);
		return result;
	}

}

public class kadanes {
	public static void main(String[] args) {
		solution sol = new solution();
		int[][] matrix = { { -2, -2, -2 }, { 2, 2, 2 }, { -2, -2, -2 } };
		HashMap result = sol.getMaxSubArray(matrix);
		System.out.println("max:" + result.get("max") + " up:" + result.get("up") + " down:" + result.get("down")
				+ " left:" + result.get("left") + " right:" + result.get("right"));
	}
}

Output

max:6 up:1 down:1 left:0 right:2
Categories
interview

Kadane’s Algorithm for maximum sum subarray with Indices [Handles Negatives] O(n)

This algorithm can be used to calculate the maximum sum subarray with indices in any given array (length n) of integers in O(n) Time and O(1) space.

package algos;

class solution {

    public solution() {}

    public int getMaxSum(int[] arr) {
        int max = arr[0], start = 0, end = 0, mstart = 0, mend = 0, currmax = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i] + currmax) {
                currmax = arr[i];
                start = i;
            } else {
                currmax = currmax + arr[i];
            }
            end = i;
            if (currmax > max) {
                max = currmax;
                mstart = start;
                mend = end;
            }
        }
        System.out.println("start:" + mstart + " end:" + mend);
        return max;
    }
}

public class kadanes {
    public static void main(String[] args) {
        int[] arr = {-1, -4, -2};
        solution sol = new solution();
        System.out.println(sol.getMaxSum(arr));
    }
}

Output

start:0 end:0
 -1

This algorithm can be used to find out the maximum sum rectangular sub-matrix in an mxn matrix in O(n*n*m) time and O(m) space.

Javasript (ES6) Solution

const getMaxSum = (arr) => {
  if (!arr)
    return;
  let currMax = arr[0];
  let max = currMax;
  let currStart = 0;
  let currEnd = arr.length;
  let maxStart = currStart;
  let maxEnd = currEnd;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > arr[i] + currMax) {
      currStart = i;
      currMax = arr[i];
    } else {
      currMax += arr[i];
    }
    currEnd = i;
    if (currMax > max) {
      max = currMax;
      maxStart = currStart;
      maxEnd = currEnd;
    }
  }
  console.log(`start: ${maxStart}`);
  console.log(`end: ${maxEnd}`);
  console.log(`max: ${max}`);
};

getMaxSum([1, 2, -9, 9, 67, -1]);

// output
/*
"start: 3"
"end: 4"
"max: 76"
*/

Demo

Categories
interview

Sorting Objects in a Priority Queue

This is an implementation that shows you how to override the comparator to sort objects by a property in a Priority Queue. You can use Priority Queues in algorithms like Dijkstra’s and A* to remove the element with the least f(n) value in each iteration. Overriding the compare method can be used to sort ArrayLists (Dynamic Arrays in Java) with sort() method.

Comparator

package algos;
import java.util.Comparator;
import java.util.PriorityQueue;

class StringLengthComparator implements Comparator {
	@Override
	public int compare(Node x, Node y) {
		// Real code should
		// probably be more robust
		// You could also just return x.val- y.val,
		// which would be more efficient.
		if (x.val < y.val) { return -1; } if (x.val > y.val) {
			return 1;
		}
		return 0;
	}
}

class Node {
	String name;
	int val;

	public Node(String name, int val) {
		this.name = name;
		this.val = val;
	}
}

public class pqcls {
	public static void main(String[] args) {
		Comparator comparator = new StringLengthComparator();
		PriorityQueue queue = new PriorityQueue(10, comparator);
		Node n1 = new Node("Shiva", 2);
		Node n2 = new Node("John", 1);
		queue.add(n1);
		queue.add(n2);
		while (queue.size() != 0) {
			System.out.println(queue.remove().name);
		}
	}
}

Output:
John
Shiva

Lambda Functions

If you want to use a more shorter format you can use lambda functions

package algos;

import java.util.PriorityQueue;

public class pqcls {
 public static void main(String[] args)
 {
 PriorityQueue<Node> queue = 
 new PriorityQueue<Node>(10, (a,b)->a.val-b.val);
 Node n1 = new Node("Shiva", 2);
 Node n2 = new Node("John", 1);
 
 queue.add(n1);
 queue.add(n2);
 
 while (queue.size() != 0)
 {
 System.out.println(queue.remove().name);
 }
 }
 }

Output:
John
Shiva