Directi Interview Question
Software DevelopersCountry: India
Interview Type: Phone Interview
import java.lang.*;
import java.util.*;
public class removeallbarsbuttwo{
public static int getmax(int[] arr){
int n = arr.length;
int[][] dp = new int[n][n];
for(int i=0; i < n; i++){
dp[i][i] = 0;
}
dp[0][1] = 0;
for(int i=1; i < n-1; i++){
dp[i][i+1] = 0;
}
int max = 0;
for(int i=0; i < n-2; i++){
for(int j=i+2; j < n; j++){
dp[i][j] = Math.max(dp[i][j-1], (Math.min(arr[i], arr[j]) * (j - i -1)));
if(dp[i][j] > max){
max = dp[i][j];
}
}
}
return max;
}
public static void main(String[] args){
int[] arr = {10, 5, 6, 12, 14};
System.out.println(getmax(arr));
}
}
import java.lang.*;
import java.util.*;
public class removeallbarsbuttwo{
public static int getmax(int[] arr){
int n = arr.length;
int[][] dp = new int[n][n];
for(int i=0; i < n; i++){
dp[i][i] = 0;
}
dp[0][1] = 0;
for(int i=1; i < n-1; i++){
dp[i][i+1] = 0;
}
int max = 0;
for(int i=0; i < n-2; i++){
for(int j=i+2; j < n; j++){
dp[i][j] = Math.max(dp[i][j-1], (Math.min(arr[i], arr[j]) * (j - i -1)));
if(dp[i][j] > max){
max = dp[i][j];
}
}
}
return max;
}
public static void main(String[] args){
int[] arr = {10, 5, 6, 12, 14};
System.out.println(getmax(arr));
}
}
- Create a array of bars sorted by height (e.g., Y coordinate).
- Use a 'sweep-line' going from the top-most bar down to '0' from bar to bar in the array maintaining 'leftmost' and 'rightmost' intersected bars and max volume.
O(sort time) + O(n).
Sorting can be done in O(N) for integers using radix sort.
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX 100005
using namespace std;
int Height[MAX];
bool cmp(const pair<int,int> &a,const pair<int,int> &b){
return (a.first<=b.first);
}
int main()
{
int n,ans=0;
cin>>n;
for(int i=0;i<n;++i){
cin>>Height[i];
}
vector<pair<int,int> > L,R;
R.push_back(make_pair(Height[n-1],n-1));
for(int i=n-2;i>=0;i--){
vector<pair<int,int> >::iterator low=lower_bound(R.begin(),R.end(),make_pair(Height[i],-1),cmp);
if(low!=R.end()){
ans=max(ans,((*low).second-i-1)*Height[i]);
}
if(Height[i]>((R.back())).first){
R.push_back(make_pair(Height[i],i));
}
}
L.push_back(make_pair(Height[0],0));
for(int i=1;i<n;i++){
vector<pair<int,int> >::iterator low=lower_bound(L.begin(),L.end(),make_pair(Height[i],-1),cmp);
if(low!=L.end()){
ans=max(ans,(i-(*low).second-1)*Height[i]);
}
if(Height[i]>((L.back())).first){
L.push_back(make_pair(Height[i],i));
}
}
cout<<ans<<endl;
return 0;
}
Complexity : O(n*logn)
package Practice;
public class MaxCapacitybwBar {
/**
* @param args
*/
public static int getmax(int[] arr){
int n = arr.length;
int maxvalue =0;
int curvalue = 0;
for (int i=0;i<n-2;i++)
for(int j=i+2;j<n;j++)
{
curvalue =Math.max(maxvalue ,(Math.min(arr[i],arr[j]) *(j-i-1)));
//System.out.println("curvalue"+curvalue);
if(curvalue>maxvalue)
maxvalue=curvalue;
}
return maxvalue;
}
public static void main(String[] args){
int[] arr = {10, 5, 6, 12, 14};
System.out.println(getmax(arr));
}
}
package Practice;
public class MaxCapacitybwBar {
/**
* @param args
*/
public static int getmax(int[] arr){
int n = arr.length;
int maxvalue =0;
int curvalue = 0;
for (int i=0;i<n-2;i++)
for(int j=i+2;j<n;j++)
{
curvalue =Math.max(maxvalue ,(Math.min(arr[i],arr[j]) *(j-i-1)));
System.out.println("curvalue"+curvalue);
if(curvalue>maxvalue)
maxvalue=curvalue;
}
return maxvalue;
}
public static void main(String[] args){
int[] arr = {10, 5, 6, 12, 14};
System.out.println(getmax(arr));
}
}
package Practice;
public class MaxCapacitybwBar {
/**
* @param args
*/
public static int getmax(int[] arr){
int n = arr.length;
int maxvalue =0;
int curvalue = 0;
for (int i=0;i<n-2;i++)
for(int j=i+2;j<n;j++)
{
curvalue =Math.max(maxvalue ,(Math.min(arr[i],arr[j]) *(j-i-1)));
System.out.println("curvalue"+curvalue);
if(curvalue>maxvalue)
maxvalue=curvalue;
}
return maxvalue;
}
public static void main(String[] args){
int[] arr = {10, 5, 6, 12, 14};
System.out.println(getmax(arr));
}
}
Complexity - O(n)
- atulmishra1996 June 14, 2017