SumoLogic Interview Question SDE-3s
Country: India
Interview Type: In-Person
/*
Given an array of integers you to find the range l,r such that
and operation of largest two element in that range is maximum.
For example:
Input
6 1 6
Output
1 3
You have to print lexicographically smallest range.
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct item
{
ll f;
ll s;
};
ll st,en,mx;
vector<ll> A;
vector<item> tree;
void build(long long node,long long start,long long end)
{
if(start == end)
{
// Leaf node will have a single element
tree[node].f=A[start];
// ll temp=A[start];
// ll k=0;
// while(temp)
// {
// temp/=2;
// k++;
// }
// tree[node].s=(1<<(k))-1;
tree[node].s=1;
}
else
{
long long int mid = (start + end) / 2;
// Recurse on the left child
build(2*node+1, start, mid);
// Recurse on the right child
build(2*node+2, mid+1, end);
//store two max elements
if(tree[2*node+1].f<tree[2*node+2].f)
{
tree[node].f=tree[2*node+2].f;
tree[node].s=max(tree[2*node+1].f,max(tree[2*node+1].s,tree[2*node+2].s));
}
else
{
tree[node].f=tree[2*node+1].f;
tree[node].s=max(tree[2*node+2].f,max(tree[2*node+1].s,tree[2*node+2].s));
}
}
}
item query(long long int node,long long int start,long long int end,long long int l,long long int r)
{
if(r < start or end < l)
{
item temp;
temp.f=-1;
temp.s=-1;
return temp;
}
if(l <= start and end <= r)
{
return tree[node];
}
item temp;
long long int mid = (start + end) / 2;
item p1 = query(2*node+1, start, mid, l, r);
item p2 = query(2*node+2, mid+1, end, l, r);
if(p1.f<p2.f)
{
temp.f=p2.f;
temp.s=max(p1.f,max(p1.s,p2.s));
}
else
{
temp.f=p1.f;
temp.s=max(p2.f,max(p1.s,p2.s));
}
return temp;
}
long long int nextPowerOf2(long long int n)
{
long long count = 0;
//First n in the below condition is for the case where n is 0
if (n && !(n&(n-1)))
return n;
while( n != 0)
{
n >>= 1;
count += 1;
}
return 1<<count;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int main()
{
ll n,i,j,x,tree_size;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
A.push_back(x);
}
tree_size=2*nextPowerOf2(n)-1;
tree.resize(tree_size+1);
mx=-1;
st=-1;
en=-1;
build(0,0,n-1);
//traverse seg tree n get answer by anding two max elements of the array......done in the build function
item temp;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
temp=query(0,0,n-1,i,j);
ll x=temp.f;
ll y=temp.s;
if(i==j)
{
y=x;
}
if((x&y)>mx)
{
mx=(x&y);
st=i;
en=j;
}
else if((x&y)==mx)
{
if(i<st)
{
st=i;
en=j;
}
else if(i==st)
{
if(j<en)
{
st=i;
en=j;
}
}
}
}
}
cout<<"Required range is : "<<st+1<<" to "<<en+1;
return 0;
}
How about this divide and conquer approach.
public class RangeLandR {
public static void main(String[] args) {
int[] arr = {6,1,6};
Value maxEnd = findMaxAnd(arr,0,arr.length-1);
System.out.println(maxEnd.data + " "+ maxEnd.left +" " + maxEnd.right);
}
private static Value findMaxAnd(int[] arr, int start, int end){
if(start == end)
return new Value(Integer.MIN_VALUE,-1,-1);
int mid = (start+end)/2;
Value left = findMaxAnd(arr,start,mid);
Value right = findMaxAnd(arr,mid+1,end);
Value crossOver = crossOver(arr,start,mid,end);
return (left.data >= right.data && left.data >= crossOver.data ) ? left :
(right.data>=left.data&& right.data>=crossOver.data ? right : crossOver);
}
private static Value crossOver(int[] arr, int start, int mid, int end){
int left = Integer.MIN_VALUE;
int right = Integer.MIN_VALUE;
int leftIndex = 0;
int rightIndex = 0;
for(int i = mid; i >=start; i--){
if(arr[i] > left){
left = arr[i];
leftIndex = i;
}
}
for(int i = mid+1; i <=end; i++){
if(arr[i] > right){
right = arr[i];
rightIndex = i;
}
}
//System.out.println(start + " " + end +" " + left +" " + right);
int value = left & right;
Value v = new Value(value,leftIndex,rightIndex);
return v;
}
}
class Value{
int data;
int left;
int right;
Value(int data, int left, int right){
this.data = data;
this.left = left;
this.right = right;
}
}
adcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdacadcdac
I think the logic should be same as finding the second maximum.
int findRange(int a[],int n) {
int maximum = INT_MIN;
int f = 0, s = 0;
for(int i=1;i<n;i++) {
if(a[i] > a[f] ) {
s = f;
f = i;
} else
s = (a[i] > a[s])?i:s;
if(b > maximum ) {
range = abs(a-b)+1;
maximum = b;
}
}
return range;
}
My Approach :
-Make a segment tree for two most maximum elements for each range
-Find the ans while traversing the seg tree.
Time Complexity :
T(n) = 2*(n-1) + n = O(n)
- coffeewithkaran007 May 28, 2016/* Given an array of integers you to find the range l,r such that and operation of largest two element in that range is maximum. For example: Input 6 1 6 Output 1 3 You have to print lexicographically smallest range. */ #include<bits/stdc++.h> using namespace std; #define ll long long int struct item { ll f; ll s; }; ll st,en,mx; vector<ll> A; vector<item> tree; void build(long long node,long long start,long long end) { if(start == end) { // Leaf node will have a single element tree[node].f=A[start]; // ll temp=A[start]; // ll k=0; // while(temp) // { // temp/=2; // k++; // } // tree[node].s=(1<<(k))-1; tree[node].s=1; } else { long long int mid = (start + end) / 2; // Recurse on the left child build(2*node+1, start, mid); // Recurse on the right child build(2*node+2, mid+1, end); //store two max elements if(tree[2*node+1].f<tree[2*node+2].f) { tree[node].f=tree[2*node+2].f; tree[node].s=max(tree[2*node+1].f,max(tree[2*node+1].s,tree[2*node+2].s)); } else { tree[node].f=tree[2*node+1].f; tree[node].s=max(tree[2*node+2].f,max(tree[2*node+1].s,tree[2*node+2].s)); } } } item query(long long int node,long long int start,long long int end,long long int l,long long int r) { if(r < start or end < l) { item temp; temp.f=-1; temp.s=-1; return temp; } if(l <= start and end <= r) { return tree[node]; } item temp; long long int mid = (start + end) / 2; item p1 = query(2*node+1, start, mid, l, r); item p2 = query(2*node+2, mid+1, end, l, r); if(p1.f<p2.f) { temp.f=p2.f; temp.s=max(p1.f,max(p1.s,p2.s)); } else { temp.f=p1.f; temp.s=max(p2.f,max(p1.s,p2.s)); } return temp; } long long int nextPowerOf2(long long int n) { long long count = 0; //First n in the below condition is for the case where n is 0 if (n && !(n&(n-1))) return n; while( n != 0) { n >>= 1; count += 1; } return 1<<count; } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int main() { ll n,i,j,x,tree_size; cin>>n; for(i=0;i<n;i++) { cin>>x; A.push_back(x); } tree_size=2*nextPowerOf2(n)-1; tree.resize(tree_size+1); mx=-1; st=-1; en=-1; build(0,0,n-1); //traverse seg tree n get answer by anding two max elements of the array......done in the build function item temp; for(i=0;i<n;i++) { for(j=i;j<n;j++) { temp=query(0,0,n-1,i,j); ll x=temp.f; ll y=temp.s; if(i==j) { y=x; } if((x&y)>mx) { mx=(x&y); st=i; en=j; } else if((x&y)==mx) { if(i<st) { st=i; en=j; } else if(i==st) { if(j<en) { st=i; en=j; } } } } } cout<<"Required range is : "<<st+1<<" to "<<en+1; return 0; }