Interview Preparation

Given an array find the contiguous subarray with maximum sum: I) If the array consists of both positive and negative elements:  We will have the sum initialize the sum to zero. If we find the sum greater then zero then we will update the sum. In successive steps we will update the maximum sum only when it is greater than previous sum. Code: import java.util.*; public class Solution {          public static void main(String[] args) {                  int[] a = {-2, -3, 4, -1, -2, 1, 5, -3};         int n = a.length;         int sum = 0;         int newsum = 0;         for(int i=0; i<n; i++){             newsum += a[i];             if(newsum<0){                 newsum = 0;           ...

Given a sorted array of positive integers, rearrange the array alternately i.e first element should be the maximum value, second minimum value, third-second max, fourth-second min and so on. Naive Solution: Here we will use an auxiliary array to store the elements in correct order. For even indices of the array  Large numbers from the given array are added. For odd indices small numbers are added. Code: import java.util.*; public class Test{        public static void main(String[] args) {          Scanner in = new Scanner(System.in);     int[] a = {1,2,3,4,5,6,7,8,9};     int n = a.length;     int[] temp = new int[n];     int small = 0;     int large = n-1;     for(int i=0; i<n; i++){         if(i%2 == 0){             temp[i] = a[large--];         }  ...

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. Naive Solution: This solution has time complexity O(n^2). The outer loop selects the index, 0...n-1. The inner loop iterates through all elements and calculates leftsum if the index is to the left (index less than outer index) . It calculates rightsum if the index is to the right(index greater than outer index). Code: import java.util.*; public class Test{        public static void main(String[] args) {          Scanner in = new Scanner(System.in);     int[] a = {-7,1,5,2,-4,3,0};     int n = a.length;     int leftsum = 0;     int rightsum = 0;     for(int i=0; i<n; i++){         leftsum = 0;         rightsum = 0;         for(int j=0; j<n; j++){  ...

Move All elements to end of array This problem can be solved by maintaining counter for non-zero elements. If a non-zero element is found it is inserted to next of previous non-zero element. And the index where the element is found is set to zero. Code: import java.util.*; public class Test{        public static void main(String[] args) {          Scanner in = new Scanner(System.in);     int[] a = {1, 2, 0, 0, 0, 3, 6};     int n = a.length;     int positivecount = -1;     for(int i=0; i<n; i++){         if(a[i]!=0){             positivecount++;             if(i!=positivecount ){                 a[positivecount] = a[i];                 a[i] = 0;             }         } ...