## SumoLogic Interview Question for SDE-3s

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

/*
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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

In the first solution, the time complexity should be T(n) = 2*(n-1) + n^2 = O(n^2)
because we are traversing the seg tree for all possible combinations of i and j?

Comment hidden because of low score. Click to expand.
0
of 0 vote

djcsjdcsdjc

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

Comment hidden because of low score. Click to expand.
0

What are 'a' and 'b' according to your code?

Comment hidden because of low score. Click to expand.
0

I am not sure if I understood the question well

but I don't think this about finding second maximum,
for e.g if we have 8 4 3 1
the answer is 3, 4 ( and'ing 3 and 1 has value of 1 right ) and not 1, 2 ( and'ing 8 and 4 would be 0 right?)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.