| public int[] rangeAdd(int size, int[][] updates) { | |
| //Concept question since the idea of sorting/merging is more complicated. | |
| // The logic add all values from start index to "end of array" instead of end index. | |
| // But to avoid the additional add, update the end+1 index with negative value(-x). | |
| // This compensates the +x till the end of array. (+x -x = 0) | |
| //res[0,2,3,0,-5]: <- obtained from the first loop. | |
| //sum[0] = res[0] = 0; |
| public List<Integer> largestDivisibleSubset(int[] nums) { | |
| Arrays.sort(nums); | |
| int maxSubsetLength = 0; | |
| int maxSubsetLengthStartIndex = 0; | |
| int[] dp = new int[nums.length]; | |
| int[] parent = new int[nums.length]; // to keep track of the subset forming a chain | |
| // Useful concept for other problems as well. | |
| for(int i = nums.length - 1 ; i >= 0; i--) { | |
| parent[i] = i; | |
| for(int j = i; j < nums.length; j++) { |
| public boolean isPerfectSquare(int num) { | |
| long low = 0, high = num; | |
| while(low <= high) { | |
| long mid = low + (high - low)/2; | |
| //int product = mid * mid; | |
| // if(mid != 0 && product/mid != mid) { | |
| // high = mid - 1; // integer overflow; | |
| // continue; | |
| // } | |
| if(mid * mid == num) { |
| // Find Leaves of Binary Tree | |
| // LeafTraversal | |
| // Concept Problem | |
| //Given a binary tree, find all leaves and then remove those leaves. | |
| // Then repeat the previous steps until the tree is empty. | |
| public List<List<TreeNode>> leafTraversal(TreeNode root) { |
| /*Given a nested list of integers, return the sum of all integers in the list weighted by their depth. | |
| Each element is either an integer, or a list -- whose elements may also be integers or other lists. | |
| Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight. | |
| Example 1: | |
| Given the list [[1,1],2,[1,1]], return 8. (four 1's at depth 1, one 2 at depth 2) | |
| Example 2: |
| public long sum(List<NestedInteger> list) { | |
| long result = 0; | |
| Queue<NestedInteger> itemQueue = new LinkedList<NestedInteger>(); | |
| Queue<Integer> depth = new LinkedList<Integer>(); | |
| for(NestedInteger item : list) { | |
| itemQueue.add(item); | |
| depth.add(1); | |
| } | |
| while(!itemQueue.isEmpty()) { | |
| NestedInteger item = itemQueue.poll(); |
| public class Solution { | |
| public long sum(List<NestedInteger> list) { | |
| return sumRecurse(list, 0); // 0 being the depth | |
| } | |
| public long sumRecurse(List<NestedInteger> list, int level) { | |
| if(list == null || list.size() == 0) { | |
| return 0; | |
| } | |
| long sum = 0; |
| // Counts the number of hits in the past 5 minutes. | |
| //Each function accepts a timestamp parameter (in seconds granularity) and | |
| //you may assume that calls are being made to the system in chronological order | |
| //(ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1. | |
| //It is possible that several hits arrive roughly at the same time. | |
| public class HitCounter { | |
| int windowSize = 5 * 60; // since time interval is in seconds. | |
| Map<Long, Long> timeStampBucket = new HashMap<Long, Long>(); |
| public class Test { | |
| public static void main(String[] args) { | |
| System.out.println("Mjolnir!"); | |
| } | |
| } |
#System Design Cheatsheet
Picking the right architecture = Picking the right battles + Managing trade-offs
##Basic Steps
