SumoLogic Interview Question for SDE-3s


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

- coffeewithkaran007 May 28, 2016 | Flag Reply
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;
}

- coffeewithkaran007 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 17, 2017 | Flag Reply
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?

- Ridam August 24, 2017 | Flag Reply
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;
	}

- amit August 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?)

- notanexpert August 10, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More