Least Number of Unique Integers after K Removals

 Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

 

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

 

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

My answer:

Basic logic: get count of each number, sort them ascending by count, reduce k by each count from the num with smallest quantity until k is negative. Reducing k by one number's count with remaining k>=0 meaning such number can be removed given k elements will be removed

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> numCountMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < arr.length; i ++) {
            Integer count = numCountMap.getOrDefault(arr[i], 0);
            count ++;
            numCountMap.put(arr[i], count);
        }
        List<Integer> list = new ArrayList<>(numCountMap.values());
        Collections.sort(list);
        int uniqNumCount= list.size();
        for (Integer element : list) {
            k -= element;
            if (k < 0) {
                break;
            } else {
                uniqNumCount --;
            }
            
        }
        return uniqNumCount;
 
    }
}

Largest Time for Given Digits

 Given an array of 4 digits, return the largest 24 hour time that can be made.

The smallest 24 hour time is 00:00, and the largest is 23:59.  Starting from 00:00, a time is larger if more time has elapsed since midnight.

Return the answer as a string of length 5.  If no valid time can be made, return an empty string.

 

Example 1:

Input: [1,2,3,4]
Output: "23:41"

Example 2:

Input: [5,5,5,5]
Output: ""

 

Note:

1. A.length == 4
2. 0 <= A[i] <= 9

My Answer:

Basic Logic: since number of input array is fixed, 4, number of all 4 digits combination is fixed as well, 4*3*2. We can sort all the combinations first in descending order, and then find the 1st valid combination

class Solution {
    public String largestTimeFromDigits(int[] A) {
        
        if (A == null || A.length != 4) {
            return "";
        }
        Arrays.sort(A);
        if (A[0] < 0 || A[0] > 2 || (A[0] == 2 && A[1] > 3) || (A[0] == 2 && A[1] <= 3 && A[2] >=6)) {
            return "";
        }
        List<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
        List<String> allResults = getAllCombinations(A, 0).stream().map(s -> {
            StringBuilder sb = new StringBuilder(s);
            sb.insert(2, ":");
            return sb.toString();
        }).collect(Collectors.toList());
        Collections.sort(allResults, Collections.reverseOrder());
        for (String result : allResults) {
            if (isResultValid(result)) {
                return result;
            }
        }
        return "";
    }
    
    private boolean isResultValid(String result) {
        if (Integer.valueOf(result.substring(0,2)) >= 24 || Integer.valueOf(result.substring(3,5)) > 59) {
            return false;
        }
            return true;
    }
    
    private List<String> getAllCombinations(int A[], int index) {
        
        if (index >= A.length ) {
            return new ArrayList<String>(){
                {
                    add("");
                }
            };
        }
        List<String> currentResults = new ArrayList<String>();
        List<String> nextResults = getAllCombinations(A, index + 1);
        for (String nextResult : nextResults) {
            for (int i = 0; i <= nextResult.length(); i ++) {
                StringBuilder sb = new StringBuilder(nextResult);
                sb.insert(i, String.valueOf(A[index]));
                currentResults.add(sb.toString());
            }
        }
        return currentResults;
    }
}

[2018-Interview] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Answer from Jiuzhang:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    private int findPosition(int[] arr, int start, int end, int key) {
        int i;
        for (i = start; i <= end; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }

    private TreeNode myBuildTree(int[] inorder, int instart, int inend,
            int[] preorder, int prestart, int preend) {
        if (instart > inend) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[prestart]);
        int position = findPosition(inorder, instart, inend, preorder[prestart]);

        root.left = myBuildTree(inorder, instart, position - 1,
                preorder, prestart + 1, prestart + position - instart);
        root.right = myBuildTree(inorder, position + 1, inend,
                preorder, position - inend + preend + 1, preend);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length != preorder.length) {
            return null;
        }
        return myBuildTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
    }
}

[2018-Interview] Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

My answer: iterative solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        Set<TreeNode> visitedNodes = new HashSet<TreeNode>();
        stack.addLast(root);

        while(!stack.isEmpty()) {
            TreeNode current = stack.peekLast();
            if (current.left != null && !visitedNodes.contains(current.left)) {
                stack.addLast(current.left);
                continue;
            } 
            
                result.add(current.val);
                visitedNodes.add(current);
                stack.removeLast();
                if (current.right != null) {
                    stack.addLast(current.right);
                }
            
        }
        
        return result;
    }
}

Jiuzhang solution:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        TreeNode curt = root;
        while (curt != null || !stack.empty()) {
            while (curt != null) {
                stack.add(curt);
                curt = curt.left;
            }
            curt = stack.pop();
            result.add(curt.val);
            curt = curt.right;
        }
        return result;
    }
}

[2018-Interview] Intersection of Two Linked Lists

Original question:
https://leetcode.com/problems/intersection-of-two-linked-lists/description/


My answer:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // the core logic is to find length diff between headA and headB
        // assuming headA has N more elements than headB does
        // then move node currentB from beginning of headB and the currentA node from Nth element of headA
        if (headA == null || headB == null) {
            return null;
        }
        if (headA == headB) {
            return headA;
        }
        ListNode currentA = headA;
        ListNode currentB = headB;
        ListNode endA = null;
        ListNode endB = null;
        
        while (true) {
            if (currentB == null) {
                currentB = headA;
            }
            if (currentA == null) {
                currentA = headB;
            }
            
            if (currentA.next == null) {
                endA = currentA;
            }

            if (currentB.next == null) {
                endB = currentB;
            }

            if (endA != null && endB != null && endA != endB) {
                return null;
            }

            if (currentA == currentB) {
                return currentA;
            }
            
            currentA = currentA.next;
            currentB = currentB.next;
        }
    }
}

[2018-Interview] Odd Even Linked List

Original question: https://leetcode.com/problems/odd-even-linked-list/description/

My answer:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null ) {
            return head;
        }
        ListNode evenHead = head.next;

        ListNode currentOdd = head;
        ListNode currentEven = head.next;
        while (currentOdd != null && currentEven != null && currentEven.next != null) {
            currentOdd.next = currentEven.next;
            currentEven.next = currentEven.next.next;
            currentOdd = currentOdd.next;
            currentEven = currentEven.next;
        }
        currentOdd.next = evenHead;
        return head;
    }
}

[2018-Interview] Add Two Numbers

Original question: https://leetcode.com/problems/add-two-numbers/description/

My answer:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        int addOne = (l1.val + l2.val) / 10;
        int newVal = (l1.val + l2.val) % 10;
        ListNode root = new ListNode(newVal);
        l1 = l1.next;
        l2 = l2.next;
        ListNode currentNode = root;
        while (l1 != null && l2 != null) {
            newVal = (l1.val + l2.val + addOne) % 10;
            addOne = (l1.val + l2.val + addOne) / 10;
            ListNode newNode = new ListNode(newVal);
            currentNode.next = newNode;
            currentNode = currentNode.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode remainNode = l1 == null? l2 : l1;
        while (addOne != 0) {
            int currentVal = 0;
            if (remainNode != null) {
                currentVal = remainNode.val;
            }
            newVal = (currentVal + addOne) % 10;
            addOne = (currentVal + addOne) / 10;
            ListNode newNode = new ListNode(newVal);
            currentNode.next = newNode;
            currentNode = currentNode.next;
            remainNode = remainNode != null? remainNode.next : null;
        }
        if (remainNode != null) {
            currentNode.next = remainNode;
        }
        return root;
    }
}

[2018-Interview] Increasing Triplet Subsequence

Original question: https://leetcode.com/problems/increasing-triplet-subsequence/description/

Got answers from Jiuzhang:

Answer 1: O(n) time, O(1) space

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int[] preNums = new int[2];
        preNums[0] = nums[0];
        preNums[1] = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] <= preNums[0]) {
                preNums[0] = nums[i];
            } else if (nums[i] <= preNums[1]) {
                preNums[1] = nums[i];
            } else {
                return true;
            }
        }
        return false;
    }
}

Answer 2: O(n) time, O(n) space

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

// O(n) memory, if you want O(1)memory take a look at the c++ version
public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 2)
            return false;
        int n = nums.length;
        boolean []has_first_small = new boolean[n];
        int smallest = nums[0];
        has_first_small[0] = false;
        for (int i = 0; i < n; i ++) {
            if (smallest < nums[i]) {
                has_first_small[i] = true;
            }
            smallest = Math.min(smallest, nums[i]);
        }
        
        int biggest = nums[n-1];
        for (int i = n-2; i >=0; i--) {
            if(has_first_small[i] == true) {
                if (nums[i] < biggest) {
                    return true;
                }
                biggest = Math.max(biggest, nums[i]);
            }
        }
        return false;
    }
}

[2018-Interview] Longest Palindromic Substring

Original question: https://leetcode.com/problems/longest-palindromic-substring/description/

My answer:

Used answer from Jiuzhang as reference:

https://www.jiuzhang.com/solutions/longest-palindromic-substring/

Answer 1: DP solution

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i ++) {
            isPalindrome[i][i] = true;
        }

        int maxLength = 1;
        int start = 0;
        
        for (int i = n - 2; i >= 0; i --) {
            isPalindrome[i][i + 1] = s.charAt(i) == s.charAt( i + 1);
            if (isPalindrome[i][i + 1] ) {
                start = i;
                maxLength = 2;
            }
        }

        for (int i = n - 1; i >= 0; i --) {// start from end; 
            // otherwise, if start from beginning, there won't be [i+1][j-1] for reference
            for (int j = i + 2; j < n; j ++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
                if (isPalindrome[i][j]) {
                    if (j - i + 1 > maxLength) {
                        maxLength = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);
    }
}

Answer 2: try to find the longest palindrome with each point as center point

/**
* 本参考程序来自九章算法，由 @令狐冲 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0, len = 0, longest = 0;
        for (int i = 0; i < s.length(); i++) {
            len = findLongestPalindromeFrom(s, i, i);
            if (len > longest) {
                longest = len;
                start = i - len / 2;
            }
            
            len = findLongestPalindromeFrom(s, i, i + 1);
            if (len > longest) {
                longest = len;
                start = i - len / 2 + 1;
            }
        }
        
        return s.substring(start, start + longest);
    }
    
    private int findLongestPalindromeFrom(String s, int left, int right) {
        int len = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            len += left == right ? 1 : 2;
            left--;
            right++;
        }
        
        return len;
    }
}