Nice Example … visit more
Shivam Kumar - Dec 5, 2015
Nice Example … visit more Java examples
Thanks Java Proficiency. But the problem that you have provided is not same as above problem. Regards.
Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
Problem Given an array arr[], find the maximum j – i such that arr[j] > arr[i].
Example Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Input: {1, 2, 3, 4, 5, 6} Output: 5 (j = 5, i = 0) Input: {6, 5, 4, 3, 2, 1} Output: -1 Solution Method 1 (Simple but Inefficient)
[Read More]
Deterministic Selection - Select the i th smallest element
We have already seen RSelect or Random Selection here. Now lets focus on DSelect.
Though RSelect is good, and works in linear time, but it deterministically runs in O(n) time, even in worst case. But the downside is that it doesn’t runs as fast as RSelect, but its worst case is still better. Like in quicksort, we had it better than merge sort, but worst case of quicksort was worse than mergesort.
[Read More]
Sorting 10 GB file of integer with limited ram.
Problem
I have only x GB RAM in computer. I have a text file of 10 GB data.This file contains numbers. x is less than 10. How will I sort them?
Solution
Generic algorithm
Here is the generic algorithm:
split the file into parts (buffers) that you can sort in-memory then when all buffers are sorted take 2 (or more) at the time and merge them (like merge sort) until there’s only 1 buffer remaining which will be the sorted file Example x = 4
[Read More]
Sorting a 2GB file with one string per line
Problem
If you have a 2GB file with one string per line, which sorting algorithm would you use to sort the file and why?
Solution
When an interviewer gives a size limit of 2GB, it should tell you something – in this case, it suggests that they don’t want you to bring all the data into memory.
So what do we do? We only bring part of the data into memory.
[Read More]
Sort an array of strings so that anagrams are next to each other
Problem
Write a method to sort an array of strings so that all the anagrams are next to each other.
Example
INPUT : "xyz", "ca", "ab", "ac", "ba", "zyx" OUTPUT: "ab", "ba", "ac", "ca", "xyz", "zyx" Lets see the solutions now.
Solution
Method 1 - Using bubble sort
Check if two pairs of strings are anagrams or not, if yes, swap.
Java code
private static boolean areAnagrams(String s1, String s2) { if (s1.
[Read More]
Merge two sorted arrays - One having big enough buffer to hold another
Problem You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
Another way to ask same question
Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n.
[Read More]
Merge Overlapping Intervals
Problem Given a collection of intervals, merge all overlapping intervals.
Input - Collection of intervals
Output - Collection of mutually exclusive intervals after merging
Example Given \[1,3\],\[2,6\],\[8,10\],\[15,18\], return \[1,6\],\[8,10\],\[15,18\]. Solution Method 1 - Brute force
A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from list and merge the other into the first interval.
[Read More]
Given an array of 100,000 pixel color values and each of which is an integer in the range (0,255). Give sorting algorithm.
We should use counting sort.
There are only 256 key value, so aux array will have only 256 values, and in O(n) time and 2 passes we will be able to sort in efficient way.
Insertion sort on linked list
If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n2) time in the worst case (though it also has O(n) best-case behavior), so it’s probably not a good choice unless you specifically want to avoid merge sort.
The idea behind the insertion sort algorithm is as follows:
[Read More]