The Fellow Programmer

Given a binary tree where each path going from the root to any leaf form a valid sequence , check if a given string is a valid sequence in such binary tree. We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree. Example 1: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1] Output: true Explanation: The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). Other valid sequences are: 0 -> 1 -> 1 -> 0 0 -> 0 -> 0   Example 2: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1] Output: false Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence.   Example 3: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1] Output: false Explanation: The path 0 -> 1 -> 1 is a sequence, but it is not a

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6   Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9   20     /  \     15   7 Output: 42       /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int result = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { findMax(root); return result; } int findMax(TreeNode root) { if (root == null) return 0; int left = Math.max(findMax(root.left), 0); int right = Math.

You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the FirstUnique  class: FirstUnique(int[] nums) Initializes the object with the numbers in the queue. int showFirstUnique()  returns the value of the first unique integer of the queue, and returns -1 if there is no such integer. void add(int value)  insert value to the queue. Example 1: Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2);            // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 first

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4     public class Solution { public int maximalSquare(char[][] matrix) { int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0; int maxlen = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == '1') { int len = 1; boolean flag = true; while (len + i < rows && len + j < cols && flag) { for (int k = j; k <= len + j; k++) { if (matrix[i + len][k] == '0') { flag = false; break; } }

Given two strings text1 and text2 , return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence  of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0. Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3. Example 2: Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3. Example 3: Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.   Example 2: Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.   class Solution { public boolean canJump(int[] nums) { int i, max = 0, length = nums.length; for(i=0;i<length && i<=max;i++){ if(i+nums[i]>max){ max = i+nums[i]; } } return i == length; } }   Try it on Leetcode  Here, we are going to solve exactly what the question explains. 1) As problem statement indicates, we are stori

Design and implement a data structure for Least Recently Used (LRU) cache . It should support the following operations: get and put . get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. The cache is initialized with a positive capacity. Follow up: Could you do both operations in O(1) time complexity? Example: LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4   METHOD 1:   class LRUCache { HashMap<Integer,Intege

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. Example 1: Input: [5,7] Output: 4   Example 2: Input: [0,1] Output: 0   METHOD 1:   class Solution { public int rangeBitwiseAnd(int m, int n) { if(m == 0){ return 0; } while(n > m){ n = n & n-1; System.out.println(n); } return n; } }   Try it on Leetcode Here while we are doing BITWISE AND from n, at some point it would be less than m. And at that point whatever m we do BITWISE AND it will be n, Consider the rxample [5,7] Take 7 -> 0000 0111 (7) & 0000 0110 (6) -> 0000 0110 (6) Take 6 -> 0000 0110 (6) & 0000 0101 (5) -> 0000 0100 (4) At this point it is less than m(i.e.,5), and it exits from loop. Then return n. Consider if n at that point is doing BITWISE AND it will be again 4.  0000 01

Given an array of integers and an integer k , you need to find the total number of continuous subarrays whose sum equals to k . Example 1: Input: nums = [1,1,1], k = 2 Output: 2   Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]. class Solution {     public int subarraySum(int[] nums, int k) {                  int count = 0;         for (int i = 0; i < nums.length; ++i) {             int sum = 0;             for (int j = i; j < nums.length; ++j) {                 sum += nums[j];                 if (sum == k)                 {                     count++;                 }             }         }         return count;             } } Here, take i element and j starts from i continues till end of array and add each element to sum. If it equals to k, then increment count . Time Complexity: O(n^2) METHOD 2: class Solution {     public i

A binary matrix means that all elements are  0  or  1 . For each  individual row of the matrix, this row is sorted in non-decreasing order. Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a  1  in it. If such index doesn't exist, return -1 . You can't access the Binary Matrix directly.   You may only access the matrix using a  BinaryMatrix  interface: BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y)  (0-indexed). BinaryMatrix.dimensions()  returns a list of 2 elements  [n, m] , which means the matrix is n * m . Submissions making more than 1000  calls to  BinaryMatrix.get  will be judged Wrong Answer .  Also, any solutions that attempt to circumvent the judge will result in disqualification. For custom testing purposes you're given the binary matrix mat  as input in the following four examples. You will not have access the binary matrix directly. It is one of FACEBOOK INTERVIEW ques

Return the root node of a binary search tree that matches the given preorder traversal. [Form Binary Search Tree from Preorder Traversal] (Recall that a binary search tree is a binary tree where for every node , any descendant of node.left has a value <   node.val , and any descendant of node.right has a value >   node.val .  Also recall that a preorder traversal displays the value of the  node first, then traverses node.left , then traverses node.right .) /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ class Solution {     public TreeNode bstFromPreorder(int[] preorder) {         if(preorder.length == 0){             return null;         }         TreeNode root = new TreeNode(preorder[0]);         for(int i = 1; i < preorder.length; i++){             constructBinarySearchTree(root, preorder[i]);             System.out.println(root.val

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] ). You are given a target value to search. If found in the array return its index, otherwise return -1 . You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of  O (log  n ). Example 1: Input: nums = [ 4,5,6,7,0,1,2] , target = 0 Output: 4   Example 2: Input: nums = [ 4,5,6,7,0,1,2] , target = 3 Output: -1   OPTION 1:   class Solution { public int search(int[] nums, int target) { for(int i=0;i<nums.length;i++){ if(nums[i] == target){ return i; } } return -1; } }  Here, it is easiest solution. Traverse the entire array, if num[i] is equal to target, return index position. Else return -1. Time Complexity: O(n) OPTION 2: class Solution {     public int sea

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [   [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.    class Solution { public int minPathSum(int[][] grid) { int i, j; for(i=0;i<grid.length;i++){ for(j=0;j<grid[i].length;j++){ if(i==0 && j>0){ grid[i][j] = grid[i][j] + grid[i][j-1]; } else if(j==0 && i>0){ grid[i][j] = grid[i][j] + grid[i-1][j]; } else if(i!=0 && j!=0){ grid[i][j] = grid[i][j] + Math.min(grid[i][j-1], grid[i-1][j]); } } } return grid[grid.length-1][grid[0].l

Given a 2d grid map of '1' s (land) and '0' s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: 11110 11010 11000 00000 Output:  1 Example 2: Input: 11000 11000 00100 00011 Output: 3    This is one of common Google Coding question according to Leetcode. class Solution {     public int numIslands(char[][] grid) {                 int count = 0, i, j;         for(i=0;i<grid.length;i++){             for(j=0;j<grid[i].length;j++){                 if(grid[i][j] == '1'){                     count += 1;                     findSurroundings(grid, i, j);                 }             }         }         return count;     }         private void findSurroundings(char[][]grid, int i, int j){         if(i<0 || i>=grid.length || j<0 || j>=grid[i].length ||

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules: Any left parenthesis '(' must have a corresponding right parenthesis ')' . Any right parenthesis ')' must have a corresponding left parenthesis '(' . Left parenthesis '(' must go before the corresponding right parenthesis ')' . '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string. An empty string is also valid. Example 1: Input: "()" Output: True   Example 2: Input: "(*)" Output: True   Example 3: Input: "(*))" Output: True   Note: The string size will be in the range [1, 100].  class Solution {     public boolean checkValidString(String s) {        int left = 0, rem = 0;        for (

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i] . Example: Input: [1,2,3,4] Output: [24,12,8,6]     Constraint:  It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer. Note: Please solve it without division . class Solution {     public int[] productExceptSelf(int[] nums) {                 int prod = 1, k=0;         int []res = new int[nums.length];         for(int i=0;i<nums.length;i++){             prod = 1;             for(int j=0;j<nums.length;j++){                 if(i!=j){                     prod *= nums[j];                 }             }             res[i] = prod;         }         return res;     } } Try it on Leetcode Here, avoid division method because array may contains zero. Take each element in array and multiply with other elements in ar

You are given a string s  containing lowercase English letters, and a matrix  shift , where  shift[i] = [direction, amount] : direction  can be 0  (for left shift) or 1  (for right shift).  amount  is the amount by which string  s  is to be shifted. A left shift by 1 means remove the first character of s and append it to the end. Similarly, a right shift by 1 means remove the last character of s and add it to the beginning. Return the final string after all operations. Example 1: Input: s = "abc", shift = [[0,1],[1,2]] Output: "cab" Explanation:   [0,1] means shift to left by 1. "abc" -> "bca" [1,2] means shift to right by 2. "bca" -> "cab" Example 2: Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]] Output: "efgabcd" Explanation:   [1,1] means shift to right by 1. "abcdefg" -> "gabcdef" [1,1] means shift to right by 1. "gabcdef" -> &qu

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0  and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number  of 0 and 1.   Note: The length of the given binary array will not exceed 50,000.     class Solution { public int findMaxLength ( int [] nums) { Map<Integer, Integer> map = new HashMap<>(); map.put( 0 , - 1 ); int ans = 0 ; int balance = 0 ; for ( int i = 0 ; i < nums.length; i++) { balance += nums[i] == 1 ? 1 : - 1 ; if (map.containsKey(balance)) { ans = Math.max(ans, i - map.get(balance)); } else { map.put(balance, i); } } return ans; } } METHO

We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest  stones and smash them together.  Suppose the stones have weights x and y with x <= y .  The result of this smash is: If x == y , both stones are totally destroyed; If x != y , the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x . At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.) Example 1: Input: [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value  of last stone. Note: 1 <= stones.length <= 30 1 <= stones[i] <= 1000 class Solution {     public int lastStoneWeight(

Given an integer array nums , find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation:  [4,-1,2,1] has the largest sum = 6.   class Solution { public int maxSubArray(int[] nums) { int i, j, max1 = 0, max2 = Integer.MIN_VALUE, sum=0; for(i=0;i<nums.length;i++){ sum = nums[i]; max1 = nums[i]; for(j=i+1;j<nums.length;j++){ sum += nums[j]; if(sum>max2){ max2 = sum; } } if(max1>=max2){ max2 = max1; } } return max2; } }   Here we are taking each element and calculating sum till the end. Storing that max value and again repeating previous steps until end of array. If anyone had different solution leave it as a comment. Try this on Leetcode