This is a practice for heap. The problem is from this blog: link check my recent code on github by PriorityQueue: link package feb; public class FindMedian { /* * Return the median of arr[]. It uses a max heap, min heap. Keep the number * of elements in 2 heaps differ… Read More »
This one is from g4g. link Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1. This is actually… Read More »
This is a practice for binary search. The aim is to find the first element in an sorted array, which is smaller than a target value. For example: arr = {1, 3, 4, 6, 7}, value = 5. Returns 2. arr = {1, 2, 5, 5, 5, 5, 6}, value = 5. Returns 1. arr… Read More »
Problem: For any given input of numbers, find the maximum sum in a range (x, y| x<=y), the sum is defined as (A[i]+ A[i+1] + … + A[j]) where x<=i<=j<=y. This problem can be solved by greedy algotithm: public class LargestSequence { public static void main(String[] args) { int[] arr = { -3,… Read More »
This is the O(n) solution, without result permutation output. Thanks to the answer from careerup link. I wrote my understanding and analysis. The basic idea is that we start with arr[0] and then see how many more elements you can include before you violate the max-min<=k constraint. When it reaches some index ‘end’ you can… Read More »
This problem is given by Junmin Liu. I dicussed with him, and thought about this for 2 days, and finally came up with this the O(n) time, O(1) soluiton. Problem: Give a list of unsorted number, find the min window or min sublist of the list, such as if sublist is sorted, the whole list… Read More »
Problem: Return the pair of indices that forms the slice where the difference between the maximum and minimum in the slice <= k. Pair of indices shouldn’t be like (i,i). Consider k is 2. And the array is 3 5 7 6 3. Output: (0,1) (1,2) (1,3) (2,3) Analysis: A brute-force idea is to recursively find… Read More »
Problem: The input is a sequence x1,x2,…,xn of integers in an arbitrary order, and another sequence a1,a2,..,an of distinct integers from 1 to n (namely a1,a2,…,an is a permutation of 1, 2,…, n). Both sequences are given as arrays. Design an 0(n logn) algorithm to order the first sequence according to the order imposed by… Read More »
Toady, I read about bolts and nuts problem. The method is similar to quicksort. But one difference is that, we should partition the array by an uncertain pivot. It means we don’t know where the pivot is in the array. The normal way should be traverse the array for one time, and found the position… Read More »
Problem The idea of the solution is very easy: use binary search. But when I wrote it, it took me a long time to verify the code. For example, find the 4th number from a=[2, 4, 6, 8] and b=[5,9] The result should be 6. Solution Basic idea: a=[0,…,a_start, …, a_mid,…,a_end,…,a.length-1] b=[0,…,b_start, …, b_mid,…,b_end,…,b.length-1] Let… Read More »