Dmitrii Volyx

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

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. ...

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1: Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2: Input: [-7,-3,2,3,11] Output: [4,9,9,49,121] Note: 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order. Solution: /** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * int guess(int num); */ public class Solution extends GuessGame { public int guessNumber(int n) { int l = 0; int r = n + 1; while (l < r) { int mid = l + (r - l) / 2; int guess = guess(mid); if (guess == 0) { return mid; } if (guess == 1) { l = mid; } else { r = mid + 1; } } return r; } }

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example: Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 Solution: ...

We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I’ll tell you whether the number is higher or lower. You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0): -1 : My number is lower 1 : My number is higher 0 : Congrats! You got it! Example : ...