Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity. Example 1: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 return [9, 8, 6, 5, 3] Example 2: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 return [6, 7, 6, 0, 4] Example 3: nums1 = [3, 9] nums2 = [8, 9] k = 3 return [9, 8, 9] Solution: public class Solution { public int[] maxNumber(int[] nums1, int[] nums2, int k) { int m = nums1.length; int n = nums2.length; int[] ans = new int[k]; for(int i=Math.max(0, k-n); i<=k && i<=m; i++){ int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k-i)); if(larger(candidate, 0, ans, 0)) ans = candidate; } return ans; } public boolean larger(int[] nums1, int i, int[] nums2, int j){ int m = nums1.length; int n = nums2.length; while(i<m && j<n && nums1[i]==nums2[j]){ i++; j++; } return (j==n && i<m) || (i<m && nums1[i]>nums2[j]); } public int[] maxArray(int[] nums, int k){ int[] ans = new int[k]; for(int i=0, j=0; i<nums.length; i++){ while(nums.length-i+j>k && j>0 && ans[j-1]<nums[i]) j--; if(j<k) ans[j++] = nums[i]; } return ans; } public int[] merge(int[] nums1, int[] nums2){ int[] ans = new int[nums1.length+nums2.length]; for(int i=0, j=0, r=0; r<ans.length; r++){ ans[r] = larger(nums1, i, nums2, j) ?

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome. Example 1: Given words = [“bat”, “tab”, “cat”] Return [[0, 1], [1, 0]] The palindromes are [“battab”, “tabbat”] Example 2: Given words = [“abcd”, “dcba”, “lls”, “s”, “sssll”] Return [[0, 1], [1, 0], [3, 2], [2, 4]]

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example, Given: s1 = “aabcc”, s2 = “dbbca”, When s3 = “aadbbcbcac”, return true. When s3 = “aadbbbaccc”, return false. Solution: public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int m = s1.length(); int n = s2.length(); if(m+n!=s3.length()) return false; boolean[][] dp = new boolean[m+1][n+1]; for(int i=0; i<=m;

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13. Hint: Beware of overflow. Solution public class Solution { public int countDigitOne(int n) { int ans = 0; for(long m=1; m<=n; m*=10){ int a = (int)(n /

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. Solution: /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public List<Interval> merge(List<Interval> intervals) { List<Interval> ans

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B). Buildings Skyline Contour The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height.

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results. Example: Given “bcabc” Return “abc” Given “cbacdcbc” Return “acdb” Solution: public class Solution { public String removeDuplicateLetters(String s) { Map<Character, Integer> map = new HashMap<>(); for(int i=0; i<s.length(); i++) map.put(s.charAt(i), i); StringBuilder sb =

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. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.) Note: You can assume that you can always reach the last index.

Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. Solution: public class Solution { public int maximumGap(int[] nums) { if(nums.length<2) return 0; int max = Integer.MIN_VALUE; int