Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. Example: Consider the following matrix: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] Given target = 5, return true.
Design a max stack that supports push, pop, top, peekMax and popMax. push(x) – Push element x onto stack. pop() – Remove the element on top of the stack and return it. top() – Get the element on the top. peekMax() – Retrieve the maximum element in the stack. popMax() – Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.
Given a binary tree, find the subtree with maximum average. Return the root of the subtree. It’s guaranteed that there is only one subtree with maximum average. Example Given a binary tree: 1 / \ -5 11 / \ / \ 1 2 4 -2 return the node 11. Solution public class Solution { private class ResultType { public int sum, size; public ResultType(int sum, int size) { this.sum = sum; this.
Given two trees, T1 and T2, write an function to test whether T2 is a subtree of T1. Solution public class Subtree { public boolean isSubTree(TreeNode T1, TreeNode T2) { if (T2 == null) return true; if (T1 == null) return false; return (isSameTree(T1,T2) || isSubTree(T1.left, T2) || isSubTree(T1.right, T2)); } public boolean isSameTree(TreeNode T1, TreeNode T2) { if (T1 == null && T2 == null) return true; if (T1 == null || T2 == null) return false; if (T1.
Given a Binary Tree, find the minimum sum path from a leaf to root. For example, in the following tree, there are three leaf to root paths 8->-2->10, -4->-2->10 and 7->10. The sums of these three paths are 16, 4 and 17 respectively. The minimum of them is 17 and the path for minimum is -4->-2->10. 10 / \ -2 7 / \ 8 -4 Solution public class PathSum { public int Solution(TreeNode root) { if (root == null) return 0; if (root.
Solution public class CacheMiss { public int missCount(int[] array, int size) { if (array == null) return 0; List<Integer> cache = new LinkedList<>(); int count = 0; for (int i = 0; i < array.length; i++) { if (cache.contains(array[i])) { cache.remove(new Integer(array[i])); } else { count++; if (size == cache.size()) cache.remove(0); } cache.add(array[i]); } return count; } }
Given a node from a cyclic linked list which is sorted in ascending order, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the cyclic list. If there are multiple suitable places for insertion, you may choose any place to insert the new value.
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction. Given the ball’s start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction. Given the ball’s start position, the destination and the maze, determine whether the ball could stop at the destination. The maze is represented by a binary 2D array.
Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target. Return the difference between the sum of the two integers and the target. Example Given array nums = [-1, 2, 1, -4], and target = 4. The minimum difference is 1. (4 - (2 + 1) = 1). Challenge: Do it in O(nlogn) time complexity. Solution public class Solution { /* * @param nums: an integer array * @param target: An integer * @return: the difference between the sum and the target */ public int twoSumClosest(int[] nums, int target) { if (nums == null && nums.