The Fellow Programmer

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.   Example 1: Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation: The multilevel linked list in the input is as follows: After flattening the multilevel linked list it becomes: Example 2: Input: head = [1,2,null,3] Output: [1,3,2] Explanation: The input multilevel linked list is as follows: 1---2---NULL | 3---NULL Example 3: Input: head = [] Output: []   How multilevel linked list is represented in test case...

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree , but some nodes are null. The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation. Example 1: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: 4 Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9). Example 2: Input: 1 / 3 / \ 5 3 Output: 2 Explanation: The maximum width existing in the third level with the length 2 (5,3). Example 3: Input: 1 / \ 3 2 / 5 Output: 2 Explanation: The maximum width ...

Given an array nums of n integers, are there elements a , b , c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]   class Solution {     public List<List<Integer>> threeSum(int[] nums) {         if (nums.length < 3) return new ArrayList<>();         Arrays.sort(nums);         Set<List<Integer>> triplet= new HashSet<>();         for (int i = 0; i < nums.length - 2; i++) {             int j = i + 1;             int k = nums.length - 1;  ...

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island. Example: Input: [[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image below:   class Solution {     public int islandPerimeter(int[][] grid) {         int lands = 0, neighbours = 0;         for (int i = 0; i < grid.length; i++) {      ...

Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123. Example 2: Input: [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321. FAILED APPROACH:   class Solution {     public int[] plusOne(int[] digits) {         digits[digits.length-1]+=1;         return digits;     } } Try it on Leetcode Above code seems to be correct, the mistake occurs when at end contains 9      Input        Output   Output ...

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y , calculate the Hamming distance. Note: 0 ≤ x , y < 2 31 . Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different.   class Solution {     public int hammingDistance(int x, int y) {         String str = Integer.toBinaryString(x^y);         return str.replaceAll("0","").length();     } } Try it on Leetcode Here, we are going to solve in more easiest way. The hint hidden in this problem is, we need to convert integer to binary and compare both for any differences in 1's position. 1) Do XOR for both numbers.(XOR of same digits (0, 1) will be same). From this, we get difference in 1's position, but i...

Write a program to find the n -th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5 .  Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note:   1 is typically treated as an ugly number. n does not exceed 1690 .   class Solution {         public int nthUglyNumber(int n) {             int[] ugly = new int[n];             ugly[0] = 1;             int indexOf2 = 0, indexOf3 = 0, indexOf5 = 0;             int factorOf2 = 2, factorOf3 = 3, factorOf5 = 5;             for(int i=1;i<n;i++){       ...

There are 8 prison cells in a row, and each cell is either occupied or vacant. Each day, whether the cell is occupied or vacant changes according to the following rules: If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied. Otherwise, it becomes vacant. (Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.) We describe the current state of the prison in the following way:  cells[i] == 1 if the i -th cell is occupied, else cells[i] == 0 . Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.) Example 1: Input: cells = [0,1,0,1,1,0,0,1] , N = 7 Output: [0,0,1,1,0,0,0,0] Explanation: The following table summarizes the state of the prison on each day: Day 0: [0, 1, 0, 1, 1, 0, 0, 1] Day 1: [0, 1, 1, 0, 0, 0, 0, 0] Day 2: [0, 0, 0, 0, 1, 1, 1, 0] Day 3: [0, 1, 1, 0, 0, 1, ...

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span  of that stock's price for the current day. The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price. For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85] , then the stock spans would be [1, 1, 1, 2, 1, 4, 6] . Example 1: Input: ["StockSpanner","next","next","next","next","next","next","next"] , [[],[100],[80],[60],[70],[60],[75],[85]] Output: [null,1,1,1,2,1,4,6] Explanation: First, S = StockSpanner() is initialized. Then: S.next(100) is called and returns 1, S.next(80) is called and returns 1, S.next(60) is called and returns 1, S.next(70) is call...

Given two strings s1 and s2 , write a function to return true if s2 contains the permutation of s1 . In other words, one of the first string's permutations is the substring of the second string. Example 1: Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: s2 contains one permutation of s1 ("ba"). Example 2: Input: s1= "ab" s2 = "eidboaoo" Output: False Constraints: The input strings only contain lower case letters. The length of both given strings is in range [1, 10,000].   public class Solution {     public boolean checkInclusion(String s1, String s2) {         if (s1.length() > s2.length())             return false;         int[] s1Arr = new int[26];         int s1Length = s1.length(), s2Length = s2.length();         for (int ...

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree [3,9,20,null,null,15,7] , 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  * ...

There are 2N people a company is planning to interview. The cost of flying the i -th person to city A is costs[i][0] , and the cost of flying the i -th person to city B is costs[i][1] . Return the minimum cost to fly every person to a city such that exactly N people arrive in each city. Example 1: Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people  interviewing in each city. Note: 1 <= costs.length <= 100 It is guaranteed that costs.length is even. 1 <= costs[i][0], costs[i][1] <= 1000   class Solution {     public int twoCitySchedCost(int[][] costs) {         Arrays.sort(costs, (a, b...

You have a total of n coins that you want to form in a staircase shape, where every k -th row must have exactly k coins. Given n , find the total number of full staircase rows that can be formed. n is a non-negative integer and fits within the range of a 32-bit signed integer. Example 1: n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2. Example 2: n = 8 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3.   class Solution {     public int arrangeCoins(int n) {         int i = 1;         while(n >= 0){             n = n-i;             i++;         }         return i-2;   ...