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 seq...

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

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...

MIUI 12 will be rolled out in Q3, which was officially mentioned here. If you are looking for a resource that compiles all of the new MIUI 12 features in one place, then you’ve arrived at the right place. Here are all of the new features in MIUI 12: Also visit here to find list of devices getting MIUI 12 updates. New Features in MIUI 12 Key UI Changes Xiaomi has been working hard to refine the UI for the past few software releases. A close look at MIUI 12 should be enough to tell you that it’s the most minimal and clean UI that the software has offered to date.  The company has also improved app opening and closing animations in MIUI 12 to reduce stutter and tearing. The company has integrated its own technologies and algorithms into its Android skin to get real-time blur in the background while closing an app, for example. Several other new animations can be found across the board – even within system apps. Also visit here to find list of devices getting MIUI ...

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

In this article we are going to learn about how to convert int to string in java. It is necessary to know type conversion because, when a number is converted to string it is useful for many easy manipulation. In this you will find all the ways to convert int to string in java and at end of article you will find code containing all learned methods. Integer.toString(int num) It is one of best method to remember, because toString() has ability to convert any data type to string representation. It is also used to provide the string representation of entire class in default way and if you want to retrieve in your wish, then you can override that method and we will discuss about this later on another topic. public static String toString(int num) Parameters num, a integer   Returns string representation of any data type valueOf(int num) It is also another best method which has ability to covert to any data type. valueOf() returns string containing a number. ...

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 ...

In Java, a number stored in a string can be used to do longest operations in easiest way such as removing duplicates etc. Also String has the capacity to store big integers also. But in some cases it will be useful if you know about type conversion between all data types. Here in this topic we are going to learn about the conversion of number stored in a string to integer in java. Also, along with that method explanation, there is a final code at end which contains both method conversion. A string can be converted int in Java in following ways. parseInt(String s)   The characters in string must be decimal digits excepts character at 0. At 0, it can be ASCII '- or +' to indicate sign of numbers. public static int parseInt (String s) throws NumberFormatException Parameters s - which is of type string containing digits Returns Returns the number of Integer type Exception Throws NumberFormatException , if the string does not contain parsable Integers val...

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 indi...

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<Integ...

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...

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];            ...

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 ...

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){       ...

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 Solu...

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.lengt...

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'){          ...

In last Spring tutorial, we learned about the history and versions of Spring. This post will explain about the spring architecture and mostly used containers of spring. CORE CONTAINER The core container consists of Beans, Core, Context, SpEL. It consists of factory for creating beans and managing bean dependencies. 1) The Bean provides BeanFactory used for creating beans and also it is the implementation of factory pattern. 2) The Core container includes IoC(Inversion of Control) and DI(Dependency Injection). 3) The Context module builds on the solid base provided by the Core and Beans modules and it is a medium to access any objects defined and configured. The ApplicationContext interface is the focal point of the Context module. 4) The SpEL module provides a powerful expression language for querying and manipulating an object graph at runtime.   DATA ACCESS LAYER              ...