Given three sorted arrays, A, B, C, each of length n (assume odd), with all 3n elements distinct, find the median of the 3n elements.

Given three sorted arrays, A, B, C, each of length n (assume odd), with all 3n elements distinct, find the median of the 3n elements.

Iteratively find arrays having max median and min median of three arrays, then discard the max-end part of the max median array, and discard the min-end part of the min median array, the lengths of max/min end part are equal to half length of shorter one of max/min median arrays

Find the subvector with the sum closest to 0 , whats the best algorithm [O(nlgn)] you can design for this ?

Find the subvector with the sum closest to 0 , whats the best algorithm [O(nlgn)] you can design for this ?

Use prefix sum array, you should consider the first element
So after you get the minimum pair, you should compare it with a[0]…

How can we shift an array circularly in optimal way? Suppose we have an array a1,a2,.......,am,b1,b2,....,bn and we want the final array as b1,b2,....

How can we shift an array circularly in optimal way?
Suppose we have an array a1,a2,.......,am,b1,b2,....,bn and we want the final array as b1,b2,.......,bn,a1,a2,....,am.
Is O(n) time and O(1) space algorithm possible??
Do 3 time reverse like:
1234567
5432176
6712345

Explain in place merging of two sorted arrays? In place merge sort O(N^2), anyway, you can use binary search instead of brute force iteration, but whe

Explain in place merging of two sorted arrays?
In place merge sort O(N^2), anyway, you can use binary search instead of brute force iteration, but when you find the position, you still need to move all elements before the inserted element

insert(int i,int len,int b[])
{
int val=b[i];
for(int j=i+1;j<len;j++)
{
if(val>b[j])
{
int temp=val;
val=b[j];
b[j]=val;
}
else break;
}
}
void InPlcaeMergeSort(int a[],int b[], int len)
{
for(int i=0;i<len;i++)
{
if(a[i]>b[i])
{
int temp=a[i];
a[i]=b[i];
b[i]=temp;
insert(i,len,b);
}
else
{
if(a[i+1]<b[i])
{
int temp=a[i+1];
a[i+1]=b[i];
b[i]=temp;
insert(i+1,len,a);
}
}
cout<<a[i]<<" "<<b[i]<<endl;
}
}

or
If one array is big enough to contain all elements of two arrays, you can merge the small array into big one in O(n)

given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array. complexity should be in o(n).

given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array. complexity should be in o(n).

s(i)=max{s(i-1),s(i-2)+a[i]} if(a[i]>0)
s(i)=s(i-1) if(a[i]<0)

int f(int* a,int n)//this is recursive way, which is O(2^n)
{
 if(n<0) return 0;
 if(a[n]>0)
  return max(f(a,n-1),f(a,n-2)+a[n]);
 return f(a,n-1);
}

int b[9]={0};
int f2(int* a,int n)//this is dp, which is O(n)
{
 if(n<0) return 0;
 if(a[n]>0)
 {
  //if(b[n-1]&&b[n-2])
  // return max(b[n-1],b[n-2]+a[n]);
  //if(b[n-1])
  // return max(b[n-1],f(a,n-2)+a[n]);
  //if(b[n-2])
   return max(f(a,n-1),b[n-2]+a[n]);
 }
 else
 {
  if(b[n-1]) return b[n-1];
  else return f(a,n-1);
 }
}

int main()
{
 int a[9]={1,-2,3,4,-1,6,5,2,4};
 cout<<f(a,8)<<endl;
}

find 3 numbers in one array [1...n] to make a+b=c.

find 3 numbers in one array [1...n] to make a+b=c.
besides hash table method, we can also do it like this
The O(n^2) solution is a bit less intuitive - you have to solve the "2SUM" problem in O(n) for a sorted set.

bool ThreeSum(vector nums)
{
    std::sort(nums.begin(), nums.end());
    for (size_t i = 0; i < nums.size(); i++)
    {
        size_t j = 0;
        size_t k = nums.size() - 1;
        while ( j < k )
        {
            int result = nums[j] + nums[k] - nums[i];
            if ( (result < 0) || (i == j) )
                j++;
            else if ( (result > 0) || (i == k) )
                k--;
            else
                return true;
        }
    }
    return false;
}

Range is from 1~N and we have n+1 numbers, so we must have one duplicate in the range 1~N

Range is from 1~N and we have n+1 numbers, so we must have one duplicate in the range 1~N

int f(int* a, int N)
{
int dup=0;
for(int i=1;i<=N;i++)
{
dup=(dup) xor (i) xor (a[i]);
}
//dup=dup xor a[n+1]
return dup;
}

An unsorted array[1…n], range is from 1…N+1，a number is missing, find it. performance。

An unsorted array[1…n], range is from 1…N+1，a number is missing, find it. performance。

Unsorted array use xor besides sum up method and bit vector in msb method. O(n)

int F(int* a, int N)
{
int s=0;
for(int i=1;i<=N;i++)
{
s=s xor i xor a[i];
}
return s xor n+1;
}

A sorted integer Array[1...N], the range is from 1...N+1. a number is missing, find out it

A sorted integer Array[1...N], the range is from 1...N+1. a number is missing, find out it

Sorted integer array uses binary search O(logn)

int foo(int* a, int low, int up) //note the index is from 1 to N
{
if(low=up-1) return a[low]+1;
int mid=(low+up)/2;
if(a[mid]>mid) up=mid;
else low=mid;
foo(a,low,up);
}

give you an array a, now you need to rearrange its sequence, such that a[i]>a[i-1] && a[i]>a[i+1] for i=1,3,5,...,

give you an array a, now you need to rearrange its sequence, such that a[i]>a[i-1] && a[i]>a[i+1] for i=1,3,5,...,
Note there might be many sequence of equal elements. of course it may be not able to be rearranged like that.

O(n) time and O(1) space

for(i = 1; i < n; i += 2) //this cannot handle 3 equal numbers consequential 
{
  if((a[i-1] == a[i]) && (a[i] == a[i+1]))
      continue;
  maximum = max3(a[i-1],a[i],a[i+1]);
  if(maximum == a[i])
      continue;
  else if(maximum == a[i-1])
      swap(input[i-1],input[i]);
  else
      swap(input[i],input[i+1]);
}

Suppose we wish to find the subvector with the sum closest to zero

Suppose we wish to find the subvector with the sum closest to zero

1. First calculate curr[i]=curr[i-1]+a[i];
2. Find the curr[u]-curr[l] which is 0 or close to 0
3. So from a[l+1] to a[u] is the subvector we want
Can be done nlogn, if you sort the array curr on the 2 step

Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array i

Given an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like.
N number has n msb, we take these msbs as bit vector to check the duplicate number

bool func(int* a, int len) //len=n+1
{
 for(int i=1;i<len;i++)
 {
  int idx=a[i]<0?(-1*a[i]):a[i];
  if(a[idx]<0) {cout<<"duplicate "<<-1*a[idx]<<endl;
return false; }
  a[idx]*=-1;
 }
 return true;
}

Find the median value of two sorted arrays.

Find the median value of two sorted arrays.

int foo(int* a, int* b, int a_min, int a_max, int b_min, int b_max)
{
 if((a_max-a_min==1)&&(b_max-b_min==1)) return median of a[a_min],a[a_max],b[b_min],b[b_max];
  
 int a_mid=(a_min+a_max)/2;
 int b_mid=ceil((b_min+b_max)/2);
 if(a[a_mid]==b[b_mid]) return a[a_mid];
 else if(a[a_mid] else return foo(a,b,a_min,a_mid,b_mid,b_max);
}


or

Int foo(int* a, int* b, int a_s, int b_s, int len)//recursively half the len
{
If(len==1) return a[a_s] or b[b_s];
Int m_a=a[a_s+(len-1)/2];
Int m_b=b[b_s+(len-1)/2];
If(m_a>m_b) return foo(a,b,a_s,b_s+len/2,ceil(len/2));
Else return foo(a,b,a_s+len/2,b_s,ceil(len/2));//note when len is ood, ceil is necessary
}

You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. F

You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).
Combinea all msb of each integer as bit vector, traverse the array, and set corresponding msb, if you find the msb is set, you get duplicate number. After traversal, scan all msbs again, if the msb is unset, the number is missing

Missing one value or duplicate one value: (n+1)*n/2
Missing one value and duplicate one values:
(n+1)*n/2
n(n+1)(2n+1)/6
m-d=
(m+d)(m-d)=
…
Missing two values or duplicate two values
(n+1)*n/2
n(n+1)(2n+1)/6
m1+m2
m1*m2
…

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no.

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no. of 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.
input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }

idea: p0 point a[0] (even), p1 point to a[1] (odd)
if(*p0==0&&*p1==1) {p0=p0+2;p1=p1+2;}
else if(*p0==1&&*p1==0) {swap(*p0,*p1),p0=p0+2;p1p1+2;}
else if(*p0==1&&*p1==1) p1=p1+2;
else if(*p0==0&&*p1==0) p0=p0+2;

given an array of integer size N.

given an array of integer size N.
a) find all pairs whose sum is some given value X. array is not sorted & values are distinct. in o(log n)
b) array is sorted. & values can repeat. in o(n) & space compl o(1)
a) hash table O(n) time, better idea???
b) two pointers, p1 points to start, p2 points to end, if equal to sum, p1++;p2--; else if bigger than sum, p2--; else p1++

Numbers are generated randomly and stored in an array. Write a program to find the median value of the array as soon as new numbers are generated. Imp

Numbers are generated randomly and stored in an array. Write a program to find the median value of the array as soon as new numbers are generated. Improve your solution.

We can optimise this by first using quick sort. The question states you must determine the median as new numbers are generated. Once sorted, you could add that doing a binary search O(log n), insert O(n) and returning the middle index 0(1) would make subsequent calculations 0(n), hence better than O(nlogn) if its done all the time.
Insertion sort (n^2)
Dynamic statistic, refer to clrs

Given an array of integers sorted in ascending order and a positive inte

Given an array of integers sorted in ascending order and a positive inte
ger ‘n’, return an array where in the elements are shifted to the righ
t by ‘n’ positions. Ensure, you perform the rotation in place without
the use of a new array.

STL reverse()
reverse(A, 0, n,);
reverse(A, n+1, A.size()- 1))
reverse(A, 0, A.size() - 1);
space complexity O(1)

You are given an array A of size n.Give an algorithm to find i and j such that 1) i < j and 2) A[j] - A[i] is maximum among all such A[x] - A[y] where

You are given an array A of size n.Give an algorithm to find i and j such that
1) i < j and
2) A[j] - A[i] is maximum among all such A[x] - A[y] where x > y.

Intention is: given j, how to choose i in order to achieve a maximum subtraction. The answer is to choose the minimum value in A[0]..A[j-1] so that A[j]-A[i] is maximized.

int max = MIN_INT;            // max subtraction
int max_i = 0, max_j;      // max corresponding i, j
int min = A[0], min_i = 0; // min value since so far

for (int i = 1; i < n; i++) {
  if (A[i] - min > max) {
    max = A[i] - min;
    max_i = min_i;
    max_j = i;
  }
  if (A[i] < min) {
    min = A[i];
    min_i = i;
  }
}

There is an array A[n], to create another array B[n], every element in B has B[i]=A[0]*A[1]*...*A[n-1]/A[i].

There is an array A[n], to create another array B[n], every element in B has B[i]=A[0]*A[1]*...*A[n-1]/A[i].
Don't use division how to create B[n] in O(n).

b[0] = 1;
for (int i = 1; i < size; i++)
    b[i] = b[i-1] * a[i-1];
for (int i = size-2; i > 0; i--)
    a[i] = a[i] * a[i+1];
for (int i = 0; i < size-1; i++)
    b[i] *= a[i+1];