Amazon Interview Question
Java DevelopersCountry: United States
Interview Type: Phone Interview
You could be right by saying BST approach to start with. She actually asked me a couple of binary search tree theoretical questions before jumping to code part :)
Sort the ranges and remove one of the ranges that are overlapping. Time complexity O(nlogn), written in C++.
Output:
(1, 2) (3, 6) (8, 10)
Code:
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
struct range {
range(int a, int b) : a_(a), b_(b) { }
bool operator<(const range& other) const {
return a_ < other.a_ || b_ < other.b_;
}
int a_;
int b_;
};
std::ostream& operator<<(std::ostream& os, const range& r) {
os << "(" << r.a_ << ", " << r.b_ << ")";
return os;
}
bool overlaps(const range& r1, const range& r2) {
return (r2.a_ <= r1.b_) || (r2.a_ == r1.b_ && r2.b_ >= r1.b_);
}
std::vector<range> find_non_overlap(std::vector<range>& ranges) {
// Sort the ranges. Uses operator< from range struct. O(nlogn)
std::sort(ranges.begin(), ranges.end());
// Remove ranges that are overlapping. O(n)
for (auto it = std::next(ranges.begin()); it != ranges.end(); it++) {
auto prev_it = std::prev(it);
if (overlaps(*prev_it, *it)) {
it = ranges.erase(prev_it);
}
}
return ranges;
}
/**
* Given a list of ranges as input ((1,2),(3,4),(3,6),(8,10)), the output would
* be those ranges that don't overlap. For example, the output could be merging
* the ranges 1) (1,2) (3,4) 2) (1,2) (3,6) etc.
*
* The output cannot contain (3,4),(3,6) as 3 is common to both.
*/
int main() {
std::vector<range> ranges{{1,2}, {3,4}, {3,6}, {8,10}};
std::vector<range> result = find_non_overlap(ranges);
std::copy(result.begin(), result.end(), std::ostream_iterator<range>(std::cout, " "));
}
Looks like overlaps method is not correct. Your only checking for equality and not the overlap.
@Anonymous, @Gerald and @Raj, my first code just removed overlapping ranges. But I modified the code since I was confused about the question. Anyway, I've restored the old code and it's now removing the overlapping ranges. Please check again. It was a 2 line change.
@Diego, you code fails for the following input:
std::vector<range> ranges{{1,2}, {3,5}, {4,6}, {8,10}};
@Gerald thanks for the heads up. I fixed the overlaps() method and it appears to be working now. The output for your example is (1, 2) (4, 6) (8, 10).
Complexity can never be less than O(n^2) for this case as there can be possible n^2 cases if all of the ranges are NOT overlapping e.g. (1,2) (3,4) (5,6) (7,8) in this case total number of ranges that are not overlapping is C(n,2) which in O(n^2)
@loveCoding you are wrong. The array of ranges is sorted and the comparison is made only with adjacent ranges, not with all of them.
@Diego so what is your answer for {(1,2) (3,4) (5,6) (7,8)}
SO in this case when you compare only 2,6 and 7,8, you need to output (1,2)(7,8) , (3,4)(7,8) and (5,6)(7,8).. so outputing your result will any way take n^2 time
@loveCoding First the array will be sorted. I'm using std::sort. Some implementations use quicksort (n^2 worst case), others use mergesort (nlogn worst case). Then the array will be traversed and every range will be checked against next range only - O(n). If the next range overlaps, it's removed. Total complexity: O(nlogn) + O(n) = O(nlogn).
@loveCoding it seems like you didn't understand the problem. The answer for (1,2) (3,4) (5,6) (7,8) is (1,2) (3,4) (5,6) (7,8).
void check()
{
List<Integer[]> outputSets = new ArrayList<Integer[]>();
inputSets.add(new Integer[]{1,2});
inputSets.add(new Integer[]{3,4});
inputSets.add(new Integer[]{3,6});
inputSets.add(new Integer[]{8,10});
//sort all elements
outputSets.add(inputSets.get(0));
for(int i=1;i<inputSets.size();i++)
{
if(inputSets.get(i)[0]>inputSets.get(i-1)[1])
{
outputSets.add(inputSets.get(i));
}
}
for(int j=0;j<outputSets.size();j++)
{
System.out.print("{"+outputSets.get(j)[0]+" , "+outputSets.get(j)[1]+"}");
}
}
here my version:
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<pair<int,int>> get_pairs_non_overlapping(vector<pair<int,int>> &vec) {
unordered_map<int,vector<int>> ht;
set<int, std::greater<int>> to_del_pairs;
for(int i = 0; i < vec.size(); i++) {
int start = vec[i].first;
int end = vec[i].first + (vec[i].second - vec[i].first);
for(int j = start; j <= end; j++) {
auto it = ht.find(j);
if(it == ht.end()) {
vector<int> vec;
vec.push_back(i);
ht.insert(make_pair(j, vec));
}
else {
it->second.push_back(i);
}
}
}
for(auto it = ht.begin(); it != ht.end(); it++) {
if(it->second.size() > 1) {
for(auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
to_del_pairs.insert(*it2);
}
}
}
for(auto it = to_del_pairs.begin(); it != to_del_pairs.end(); it++) {
vec.erase(vec.begin() + *it);
}
return vec;
}
int main() {
// your code goes here
vector<pair<int,int>> in = {{1,2}, {3,4}, {3,6}, {8,10}};
vector<pair<int,int>> out = get_pairs_non_overlapping(in);
for_each(out.begin(), out.end(), [](pair<int,int> p) { cout << p.first << ", " << p.second << endl; });
return 0;
}
Brut force:
the function:
public List findNonOverLapingPair(List<int[]> set) {
List<int[]> temp = new ArrayList<int[]>(set);
List temp2 = new ArrayList();
for (int i = 0; i < set.size(); i++) {
temp.remove(0);
int check[] = set.get(i);
for (int[] is : temp) {
if (((check[0] < is[0] && check[0] < is[1]) && (check[1] < is[0] && check[1] < is[1]))
|| ((check[0] > is[0] && check[0] > is[1]) && (check[1] > is[0] && check[1] > is[1]))) {
Object o[]= {check,is};
temp2.add(o);
}
}
}
return temp2;
}
test code:
public static void main(String[] args) {
List<int[]> set = new ArrayList<int[]>();
int[] a = { 1, 2 };
int[] a2 = { 3, 4 };
int[] a3 = { 3, 6 };
int[] a4 = { 8, 10 };
set.add(a);
set.add(a2);
set.add(a3);
set.add(a4);
List l=new Main().findNonOverLapingPair(set);
for(Object o:l){
Object[] b=(Object[])o;
int[] i=(int[]) b[0];
int[] j=(int[]) b[1];
System.out.println(i[0]+","+i[1]+"::"+j[0]+","+j[1]);
}
}
output:
1,2::3,4
1,2::3,6
1,2::8,10
3,4::8,10
3,6::8,10
DO we have to ouput always in pairs? For example can answer in example be {(1,2) (3,6) 8,10)}
here an improved algorithm which is based on a BST.
time complexity should be O(n log n)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef struct node {
int lo;
int hi;
bool is_overlap;
node *left;
node *right;
node(int low, int high): lo(low), hi(high), is_overlap(false), left(NULL), right(NULL) {}
}node;
class Merge_Overlapping_Ranges {
private:
node *root;
public:
Merge_Overlapping_Ranges(): root(NULL) {}
// O(log n)
void insert(pair<int,int> &p) {
if(!root) {
root = new node(p.first, p.second);
}
else {
node *parent = NULL;
if(!query_interval(p, &parent)) {
int low = p.first;
int high = p.second;
node *tmp = new node(low, high);
if(low < parent->lo) {
parent->left = tmp;
}
else if(low > parent->lo) {
parent->right = tmp;
}
}
}
}
bool is_interval_overlap(int low, int high, node **parent) {
node *tmp = root;
node *prev = NULL;
while(tmp) {
prev = tmp;
if((low >= tmp->lo && low <= tmp->hi) || (high >= tmp->lo && high <= tmp->hi)) {
tmp->is_overlap = true;
return true;
}
else if(low < tmp->lo) {
tmp = tmp->left;
}
else if(low > tmp->lo) {
tmp = tmp->right;
}
}
*parent = prev;
return false;
}
bool query_interval(pair<int,int> &p, node **parent) {
if(is_interval_overlap(p.first, p.second, parent)) {
return true;
}
return false;
}
vector<pair<int,int>> get_non_overlapping_ranges() {
vector<pair<int,int>> vec;
stack<node*> s;
s.push(root);
while(!s.empty()) {
node *tmp = s.top();
s.pop();
if(!tmp->is_overlap) {
vec.push_back(make_pair(tmp->lo, tmp->hi));
}
if(tmp->right) {
s.push(tmp->right);
}
if(tmp->left) {
s.push(tmp->left);
}
}
return vec;
}
};
int main() {
// your code goes here
Merge_Overlapping_Ranges m;
vector<pair<int,int>> vec = {{1,2}, {3,4}, {3,6}, {8,10}};
// O(n log n)
for(int i = 0; i < vec.size(); i++) {
m.insert(vec[i]);
}
// O (n)
vec = m.get_non_overlapping_ranges();
for_each(vec.begin(), vec.end(), [](pair<int,int> p) { cout << p.first << ", " << p.second << endl; });
return 0;
}
input:
{{1,2}, {3,5}, {3,6}, {8,10}}
output:
{{1,2}, {8,10}}
@Sunny:
yes, check if a number within the range overlaps with any other range.
examples:
input: {{1,2}, {3,4}, {3,6}, {8,10}}
output: {{1,2}, {8,10}}
explanation: {3,4}, {3,6} ...overlap and will be removed
input: {{1,2}, {3,5}, {4,6}, {8,10}}
output: {{1,2}, {8,10}}
explanation: {3,5}, {4,6} ...overlap and will be removed
input: {{1,6}, {3,4}, {5,7}, {8,10}}
output: {{8,10}}
explanation: {1,6}, {3,4}, {5,7} ...overlap and will be removed
public void doItNew(int[][] x) {
int[] checker = new int[x.length];
for (int i = 0; i < x.length - 1; i++) {
for (int j = i + 1; j < x.length; j++) {
if (checkOverLap(x[i], x[j])) {
checker[i] = -1;
checker[j] = -1;
}
}
}
for (int i = 0; i < x.length ; i++) {
if (checker[i] != -1) {
for (int a1 : x[i]) {
System.out.print(a1 + "\t");
}
}
}
}
public boolean checkOverLap(int[] a, int[] b) {
return a[0] - b[1] <= 0 && a[1] - b[0] >= 0;
}
public void doItNew(int[][] x)
{
Arrays.sort(x,new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int[] checker = new int[x.length];
for (int i = 0; i < x.length - 1; i++) {
for (int j = i + 1; j < x.length; j++) {
if (checkOverLap(x[i], x[j])) {
checker[i] = -1;
checker[j] = -1;
}
else {
break;
}
}
}
for (int i = 0; i < x.length ; i++) {
if (checker[i] != -1) {
for (int a1 : x[i]) {
System.out.print(a1 + "\t");
}
}
}
}
public boolean checkOverLap(int[] a, int[] b) {
return a[0] - b[1] <= 0 && a[1] - b[0] >= 0;
}
Create 2 separate sets of tuples, in one set sort the intervals by the first number, in the second set sort the intervals by the second number. For each tuple in the first set, use binary search to find all tuples in the second set for which the second number in the tuple from the second set is less than equal to the first number in the tuple from the first set.
Sorting takes O(nlogn) time. Forming the set of intervals for each of n tuple takes O(logn) time (binary search). Thus O(nlogn) time complexity and O(n) space complexity.
This problem is like interval scheduling problem in which we have to schedule jobs which are compatible. We are given here (start,finish) time pair of each job.
Two approach:
Greedy:
1) Sort them based on the range end of each (start,end) pair.
2) Now take first pair which end first and add it to solution.
3) Iterate on sorted job to find jobs which are compatible with the result. This will be one scan to the input.
Note: We are adding job greedily to the solution set.
DP:
Sort the based on the end range.
Create Array which account for last job compatible with jth jon. Let it be p(j).
Now Use this recurrence solution.
M[i] = max(1+p(i),M[i-1]).
M[n] will give you number of max set compatible.
For printing solution you can iterate over M array one scan.
public class MergingRang {
public static void main(String[] args) {
List<Point> pointList = new ArrayList<Point>();
Point point;
point = new Point(3,4);
pointList.add(point);
point = new Point(1,2);
pointList.add(point);
point = new Point(3,6);
pointList.add(point);
point = new Point(8,10);
pointList.add(point);
Collections.sort(pointList);
for(int i=0;i<pointList.size()-1;i++){
for(int j=pointList.size()-1;j>i;j--){
if((pointList.get(i).y>=pointList.get(j).x) || (pointList.get(i).y>=pointList.get(j).y))
break;
else
System.out.println("("+pointList.get(i).x+","+pointList.get(i).y+")"+
"("+pointList.get(j).x+","+pointList.get(j).y+")");
}
}
}
}
class Point implements Comparable<Point>{
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o) {
// TODO Auto-generated method stub
return x-o.x;
}
}
package org.ram.java.exercises.careercup;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.LinkedList;
public class RangeProblem {
public static void main(String args[]) {
String pair1 = "1,2";
String pair2 = "3,6";
String pair3 = "2,3";
ArrayList<String> al = new ArrayList<String>();
LinkedHashSet<Integer> ls = new LinkedHashSet<>();
al.add(pair1);
al.add(pair2);
al.add(pair3);
for (String st : al) {
LinkedList<Integer> li = new LinkedList<Integer>();
Boolean canadd = true;
String ar[] = st.split(",");
Integer val = Integer.parseInt(ar[0]);
for (int i = 0; i <= Integer.parseInt(ar[1])
- Integer.parseInt(ar[0]); i++) {
System.out.println(val);
li.add(val);
val++;
if (ls.contains(val)) {
canadd = false;
} else {
ls.add(val);
}
}
if (canadd) {
System.out.println(li);
}
}
}
}
/*
* Given a list of ranges as input ((1,2),(3,4),(3,6),(8,10))
* the output would be those ranges that don't overlap.
* For example, the output could be merging the ranges
* 1) (1,2),(3,4)
* 2) (1,2) (3,6) etc
*
* The output cannot contain (3,4),(3,6) as 3 is common to both.
*/
package sort;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
public class MergeOverLappingIntervals
{
public static class Interval implements Comparable<Interval>
{
int start = 0;
int end = 0;
public Interval(int start, int end)
{
this.start = start;
this.end = end;
}
public Interval mergeWith(Interval other)
{
if((this.end >= other.start && this.start <= other.start)
|| (this.start <= other.end && this.end >= other.end)
|| (this.start >= other.start && this.end <= other.end)
|| (this.start <= other.start && this.end >= other.end))
{
return new Interval(Math.min(this.start, other.start), Math.max(this.end, other.end));
}
else
{
return null;
}
}
public int length()
{
return this.end - this.start;
}
public String toString()
{
return "(" + this.start + ", " + this.end + ")";
}
@Override
public int compareTo(Interval other) {
if(other == null)
{
throw new java.lang.IllegalArgumentException("Comparison can not be done with a NULL object!");
}
return this.start - other.start;
}
}
public static List<Interval> mergeNow(List<Interval> input)
{
if(input == null || input.size() < 1)
{
return input;
}
Collections.sort(input);
List<Interval> output = new ArrayList<Interval>();
Iterator<Interval> iterator = input.iterator();
Interval left = iterator.next();
Interval right = null;
while(iterator.hasNext())
{
right = iterator.next();
Interval merged = left.mergeWith(right);
if(merged != null)
{
left = merged;
}
else
{
output.add(left);
left = right;
// add the last one
if(!iterator.hasNext())
{
output.add(right);
}
}
}
return output;
}
public static void main(String[] args) {
List<Interval> input = new ArrayList<Interval>();
input.add(new Interval(8,10));
input.add(new Interval(3,4));
input.add(new Interval(1,2));
input.add(new Interval(3,6));
input.add(new Interval(4,5));
System.out.println(input);
System.out.println(mergeNow(input));
}
}
It is 1d interval search problem.
- warmingUp December 03, 2013Algorithm:
Create BST where each node stores an interval (lo,hi).
Use left endpoint as BST key. (here lo is BST key)
Store max endpoint in subtree rooted at node. (consider hi of all nodes)
Now:
To search for any one interval that intersects query interval (lo,hi):
If interval in node intersects query interval, return it.
Else if left subtree is null, go right.
Else if max endpoint in left subtree is less than lo, go right.
Else go left.