fd Interview Question
SDE1sCountry: India
Hi.
i think this is nothing but counting number of inversion in the array..
please correct me if i am wrong
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 ?.
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 ?.
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++];
}
}
}
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;
}
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
Yeah, that was a bit naive. That's why you shouldn't be allowed to post late at night! :))
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.
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;
}
I have submitted following code Using merge sort. But I am getting TLE
- Anonymous April 05, 2015