fd Interview Question for SDE1s


Country: India




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

I have submitted following code Using merge sort. But I am getting TLE

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Choco {
	static void mergesort(int array[], int pos[], int result[], int start, int end)
	{
	    if (start >= end)
	    {
	        return;
	    }
	    int mid = start + (end - start) / 2;
	    mergesort(array, pos, result, start, mid);
	    mergesort(array, pos, result, mid + 1, end);
	    merge(array, pos, result, start, mid, end);
	}
	static void merge(int array[], int pos[], int result[], int start, int mid, int end)
	{
	    int temp[]= new int[array.length];
	    for (int i = start; i <= end; ++i)
	    {
	        temp[i] = pos[i];
	    }
	    int cur = start;
	    int leftcur = start;
	    int rightcur = mid + 1;
	    while (leftcur <= mid && rightcur <= end)
	    {
	        if (array[temp[leftcur]] <= array[temp[rightcur]])
	        {
	            pos[cur] = temp[leftcur];
	            result[pos[cur]] += rightcur - mid - 1;
	            ++leftcur;
	            ++cur;
	        }
	        else
	        {
	            pos[cur] = temp[rightcur];
	            ++cur;
	            ++rightcur;
	        }
	    }
	    while (leftcur <= mid)
	    {
	        pos[cur] = temp[leftcur];
	        result[pos[cur]] += end - mid;
	        ++cur;
	        ++leftcur;
	    }
	    while (rightcur <= end)
	    {
	        pos[cur] = temp[rightcur];
	        ++cur;
	        ++rightcur;
	    }
	}

	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.parseInt(line);
        int[] a = new int[N];	
        String line2 = br.readLine();
        String array[]= line2.split(" ");
        int pos[] = new int[a.length];
        int result[] = new int[a.length];
        for (int i = 0; i < N; i++) {
        	a[i]= Integer.parseInt(array[i]); 
        	 pos[i] = i;
        }
		
       
       mergesort(a,pos,result,0, N-1);
       int max = 0;
       for(int i=0;i<result.length;i++){
    	   if(max<result[i]){
    		 max= result[i];  
    	   }
    	  
       }
       System.out.println(max);
	}
}

- Anonymous April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modified merge sort with an extra array to keep track of values. I like it.

- SK April 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please explain the algorithm a bit?

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

Hi.
i think this is nothing but counting number of inversion in the array..
please correct me if i am wrong

- sumit.polite April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

yes this is counting number of inversions and complexity is o(nlogn). But still I am getting TLE during submission .

One of the method to solve this problem is AVL (Balance Tree).

Can anyone suggests better method to solve this problem ?.

- Anonymous April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

yes this is counting number of inversions and complexity is o(nlogn). But still I am getting TLE during submission .

One of the method to solve this problem is AVL (Balance Tree).

Can anyone suggests better method to solve this problem ?.

- Anonymous April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Counting inversions is exactly what it is.

- SK April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same solution, I just implemented the mergesort differently. It takes less space.

public static void mergeSort(int[] input, int[] inversions, int begin, int end){
        if(begin==end)
            return;
        if(begin+1==end)
            return;
        int mid=(begin+end)/2;
        mergeSort(input, inversions, begin, mid);
        mergeSort(input, inversions, mid, end);
        merge(input, inversions, begin, mid, end);
    }
    public static void merge(int[] input, int[] inversions, int begin, int mid, int end){
        if(mid==end)
            return;
        if(mid==begin)
            return;
        int[] inputFirst= Arrays.copyOfRange(input, begin,mid);
        int[] inversionsFirst=Arrays.copyOfRange(inversions, begin, mid);
        int leftIndex=0;
        int rightIndex=mid;
        int index=begin;
        for(;index<end;index++){
            if(rightIndex==end){
                input[index]=inputFirst[leftIndex];
                inversions[index]=inversionsFirst[leftIndex++]+end-mid;
                continue;
            }
            if(leftIndex==mid-begin){
                input[index]=input[rightIndex];
                inversions[index]=inversions[rightIndex++];
                continue;
            }
            if(inputFirst[leftIndex]<=input[rightIndex]){
                input[index]=inputFirst[leftIndex];
                inversions[index]=inversionsFirst[leftIndex++]+rightIndex-mid;
            }else{
                input[index]=input[rightIndex];
                inversions[index]=inversions[rightIndex++];
            }
            
        }
    }

- amirtar April 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n) complexity, simple for loop:

#include <cstdlib>
#include <iostream>

using namespace std;

int main() {

	int a[] = {7,6,10,5,2,8,1,9,3,4};
	int n = 10, index = 0, win = 0;
	
	for (int i=1; i<n; ++i) {
		if (a[i] > a[index]) 
			index = i;
		if (win < i-index) 
			win = i-index;
	}
	cout << win << endl;
	
	return 0;
}

- nikolay.dimitrov April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This wont work for example for {7,6,6,6,6,10,5,2,8,1,9,3,4}, where the answer should be 9 put your code outputs 7

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

Could you explain the logic behind this?

- Skor April 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code will not work .

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

Yeah, that was a bit naive. That's why you shouldn't be allowed to post late at night! :))

- nikolay.dimitrov April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I reckon there's no way to make it in O(n). The only way is to sort it and keep the indexes... So best case would be O(n*logn)

- nikolay.dimitrov April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if he is going through a very bad phase of his life, he can sort the chocolates in ascending order ...so that she cannot pick any chocolate :-) .... btw, he may have to look for some other girlfriend after this...

- sumesh.nb April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone help me to solve this problem ?

- Anonymous April 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think there O(N) solution, I've only been able to come up with O(NlogN), and even that requires an order statictic tree which isn't built into any popular language that I'm aware of, meaning that you might have to code it in the interview, which sounds bad. Basically the solution is to start from the right side and inspect how many of the already inserted elements are smaller than the current one being inserted, and take the maximum of those. However, this feels like a problem where there's O(N) solution, but I guess you have to be smarted than me to see it.

- Anonymous April 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the cognate problem of "caculate the number of inversion pair", as to
1 <= A[i] <= 100000, we can use the Binary Indexed Tree.

const int SIZE = 100001;

class BIT
{
public:
	BIT()
	{
		memset(a, 0, SIZE * sizeof(int));
	}

	void update(int i, int x)
	{
		while (i <= SIZE)
		{
			a[i] += x; i += i & -i;
		}
	}

	int query(int i)
	{
		int ans = 0;

		while (i > 0)
		{
			ans += a[i]; i -= i & -i;
		}

		return ans;
	}

private:
	int a[SIZE];

};

int Optimal(int A[], int n)
{
	assert(A != NULL && n > 0);

	BIT bit; int ans = 0;

	for (int i = n - 1; i >= 0; --i)
	{
		ans = max(ans, bit.query(A[i])); bit.update(A[i], 1);
	}

	return ans;
}

- malinbupt May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

This is a programming questions .

- Anonymous April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wait, this isn't where I parked my car?!

- Anonymous April 05, 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