Categories
interview

Product of Array Except Self – Java

Time – O(n)
Space – 0(1)  – Neglecting the output array that is expected to be returned.

class Solution {
 public int[] productExceptSelf(int[] nums) {
  int n = nums.length;
  int[] output = new int[n];
  int temp = 1;
  // product from left to right excluding nums[i]
  for (int i = 0; i < n; i++) {
   output[i] = temp;
   temp *= nums[i];
  }
  temp = 1;
  // product from right to left excluding nums[i]
  for (int i = n - 1; i >= 0; i--) {
   output[i] *= temp;
   temp *= nums[i];
  }
  return output;
 }
}
Categories
interview

Copy List with Random Pointer (Reference) – Java

This method doesn’t use a HashMap.

Copy List with Random Pointer

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
 public RandomListNode copyRandomList(RandomListNode head) {
  if (head == null)
   return null;
  // Step 1 - Store copy in next
  RandomListNode n = head;
  while (n != null) {
   RandomListNode c = new RandomListNode(n.label);
   c.next = n.next;
   n.next = c;
   n = c.next;
  }
  // Step 2 - Copy Random reference
  n = head;
  while (n != null) {
   if (n.random != null) {
    n.next.random = n.random.next;
   }
   n = n.next.next;
  }
  // Step 3 - Break references
  n = head;
  RandomListNode ret = head.next;
  while (n != null) {
   RandomListNode copy = n.next;
   n.next = copy.next;
   if (n.next != null) {
    copy.next = n.next.next;
   }
   n = n.next;
  }
  return ret;
 }
}

 

 

Categories
interview

Flatten Binary Tree to Linked List – Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public void flatten(TreeNode root) {
  moveLeftToRight(root);
 }

 public TreeNode moveLeftToRight(TreeNode root) {
  if (root == null)
   return null;
  TreeNode last = null;
  TreeNode right = root.right;
  if (root.left != null) {
   root.right = root.left;
   root.left = null;
   last = moveLeftToRight(root.right);
   last.right = right;
  }
  if (right != null) {
   last = moveLeftToRight(right);
  }
  return (last != null ? last : root);
 }
}
Categories
interview

3Sum

Time O(n2) & Memory O(1)

class Solution {
 public List < List < Integer >> threeSum(int[] nums) {
  int n = nums.length;
  List < List < Integer >> list = new ArrayList < List < Integer >> ();
     if(nums == null || nums.length<3)
        return list;
  Arrays.sort(nums);
  int left, right;
  for (int i = 0; i < n - 2; i++) {
   if(i > 0 && nums[i] == nums[i-1])
       continue;
   left = i + 1;
   right = n - 1;
   while (left < right) {
    if (nums[left] + nums[right] + nums[i] == 0) {
     List < Integer > temp = new ArrayList < Integer > ();
     temp.add(nums[i]);
     temp.add(nums[left]);
     temp.add(nums[right]);
     list.add(temp);
     left++;
     right--;
     while (nums[left] == nums[left - 1]) {
      left++;
     }
     while (left< right && nums[right] == nums[right + 1]) {
      right--;
     }
    } else if (nums[left] + nums[right] + nums[i]  > 0) {
     right--;
    } else
     left++;
   }
  }
  return list;
 }
}

Javascript ES6

const get3Sum = (arr) => {
  const results = [];
  arr.sort((a, b) => a - b);
  for (let i = 0; (i < arr.length - 2) && (arr[i] <= 0); i++) {
    if (i === 0 || arr[i] !== arr[i - 1]) {
      getPair(arr, i, results);
    }
  }
  return results;
};

const getPair = (arr, i, results) => {
  let left = i + 1;
  let right = arr.length - 1;
  while (left < right) {
    const sum = arr[i] + arr[left] + arr[right];
    if (sum === 0) {
      results.push([arr[i], arr[left++], arr[right--]]);
      while (arr[left - 1] == arr[left]) {
        left++;
      }
    } else if (sum < 0) {
      left++;
    } else if (sum > 0) {
      right--;
    }
  }
};

console.log(get3Sum([-1, 0, 1, 2, -1, -4]));
// [[-1 , 0, 1], [-1, -1, 2]]

Demo

Categories
interview

Trapping Rain Water

Javascript (ES6)

/**
 * @param {number[]} height
 * @return {number}
 */
const trap = function(height) {
  const left = [];
  const right = [];
  let lmax = height[0];
  let rmax = height[height.length - 1];
  for (let i = 0; i < height.length; i++) {
    if (height[i] > lmax) {
      lmax = height[i];
    }
    left[i] = lmax;
    let j = height.length - i - 1;
    if (height[j] > rmax) {
      rmax = height[j];
    }
    right[j] = rmax;
  }
  let total = 0;
  for (let i = 0; i < height.length; i++) {
    total += Math.abs(height[i] - Math.min(left[i], right[i]));
  }
  return total;
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6

Demo

Java

Time: O(n)
Memory: O(n)


class Solution {
 public int trap(int[] height) {
  int n = height.length;
  if (n == 0)
   return 0;
  int[] left = new int[n];
  int[] right = new int[n];
  left[0] = height[0];
  right[n - 1] = height[n - 1];
  int j;
  for (int i = 1; i < n; i++) {
   left[i] = Math.max(left[i - 1], height[i]);
   right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
  }
  int area = 0;
  for (int i = 1; i < n - 1; i++) {
   area += Math.min(left[i], right[i]) - height[i];
  }
  return area;
 }
}
Categories
interview

CSS Margins Collapsing

CSS Vertical Margins  of adjoining elements collapse vertically by default unless contained in a flexbox.

CSS Horizontal Margins never collapse.

Continue reading “CSS Margins Collapsing”
Categories
interview

Frog Jump – Java

This solution uses a HashMap

Continue reading “Frog Jump – Java”
Categories
Uncategorized

Flexbox – Div at end of row

The following lines of code demonstrate how to align a div at the end of the flexbox row when you want to display the rest of the them at the start.
flexbox

Continue reading “Flexbox – Div at end of row”
Categories
Uncategorized

Unit testing method called with parameters

The following two unit tests demonstrate the scenario where you would want to write a unit test to verify whether a method was called with the required parameters. It also tests how many times a method was invoked by passing a mock method.

Continue reading “Unit testing method called with parameters”
Categories
Uncategorized

Allow arrow functions as properties in React Components using eslint

If you don’t configure your .eslintrc file, then you might see this “Parsing error: Unexpected token =” when you do the following in your react components.

class HomeComponent extends Component {
  
  state = {
    term: '',
  };

  setTerm = (term) => {
    this.setState({ term });
  };

  ...
}

To use arrow functions as properties in React components you can do the following.

Continue reading “Allow arrow functions as properties in React Components using eslint”