Invert a binary tree. Example: Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1 Trivia: This problem was inspired by this original tweet by Max Howell: Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off. Solution: ...
Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours. Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour. ...
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible. Note: The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: ...
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC" Note: If there is no such window in S that covers all characters in T, return the empty string “”. If there is such window, you are guaranteed that there will always be only one unique minimum window in S. Solution: ...
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? Solution: /** * 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; * } * } */ class Solution { private List<Integer> list = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { if (root == null) { return Collections.emptyList(); } Stack<TreeNode> q = new Stack<>(); TreeNode curr = root; while (!q.isEmpty() || curr != null) { while (curr != null) { q.push(curr); curr = curr.left; } curr = q.pop(); list.add(curr.val); curr = curr.right; } return list; } public List<Integer> inorderTraversal2(TreeNode root) { if (root == null) { return Collections.emptyList(); } inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); return list; } }
Remove all elements from a linked list of integers that have value val. Example: Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5 Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeElements(ListNode head, int val) { if (head == null) { return head; } while (head != null && head.val == val) { head = head.next; } ListNode node = head; ListNode prev = null; while (node != null) { if (node.val == val) { prev.next = node.next; } else { prev = node; } node = node.next; } return head; } }
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2. You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b. ...
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once. Follow up: Your solution should run in O(log n) time and O(1) space. Example 1: Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2 Example 2: Input: nums = [3,3,7,7,10,11,11] Output: 10 Constraints: 1 <= nums.length <= 10^5 0 <= nums[i] <= 10^5 Solution: ...
Given a positive integer num, write a function which returns True if num is a perfect square else False. Follow up: Do not use any built-in library function such as sqrt Example 1: Input: num = 16 Output: true Example 2: Input: num = 14 Output: false Solution: class Solution { public boolean isPerfectSquare(int num) { return isPerfectSquareSearch(num); } public boolean isPerfectSquareNewTon(int num) { if (num < 2) return true; int root = num; while (root - num / root > 0) { root = (root + num/root) / 2; System.out.printf("%d\n", root); } return root * root == num; } public boolean isPerfectSquareSearch(int num) { if (num < 2) return true; long left = 2, right = num / 2, x; while (left <= right) { x = left + (right - left) / 2; if (x * x == num) return true; if (x * x > num) { right = x - 1; } else { left = x + 1; } System.out.printf("%d\n", x); } return false; } float abs(int num) { if (num < 0) return -num; else return num; } }
You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane. Example 1: Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true Example 2: Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false Solution: class Solution { public boolean checkStraightLine(int[][] coordinates) { // x2 - x1 int xdiff = coordinates[1][0] - coordinates[0][0]; // y2 - y1 int ydiff = coordinates[1][1] - coordinates[0][1]; for (int i = 2; i < coordinates.length; i++) { int curr_xdiff = coordinates[i][0] - coordinates[i-1][0]; int curr_ydiff = coordinates[i][1] - coordinates[i-1][1]; if (ydiff * curr_xdiff != xdiff * curr_ydiff) { return false; } } return true; } }