Samsung Interview Question
Java DevelopersCountry: India
Interview Type: Written Test
#include <iostream>
using namespace std;
#define lim 50
int N,M;
int oilMines[2*lim];
int DP_max[lim][lim][lim];
int DP_min[lim][lim][lim];
int verbose=0;
void debug(){
cout<<"\nOIL MINES : \n";
for(int i=0; i<M; i++){
cout<<oilMines[i]<<"\t";
}
cout<<endl;
for(int x=0; x<=N; x++){
cout<<"\nDP_MAX FOR NUMBER OF PARTITIONS = "<<x<<endl;
for(int i=0; i<M; i++){
for(int j=0; j<M; j++){
if(DP_max[i][j][x]==-1)
cout<<"N\t";
else
cout<<DP_max[i][j][x]<<"\t";
}
cout<<endl;
}
cout<<"\nDP_MIN FOR NUMBER OF PARTITIONS = "<<x<<endl;
for(int i=0; i<M; i++){
for(int j=0; j<M; j++){
if(DP_min[i][j][x]==999999)
cout<<"N\t";
else
cout<<DP_min[i][j][x]<<"\t";
}
cout<<endl;
}
}
}
void DP(){
// Always j>=num_part
// j => Length of array starting from i 0<=j<=M
for(int i=0; i<M; i++){
for(int num_part=1; num_part<=N; num_part++){
DP_max[i][i][num_part]=oilMines[i];
DP_min[i][i][num_part]=oilMines[i];
}
}
for(int i=0; i<M; i++){
for(int j=i+1; j<M; j++){
int sum=0;
for(int x=i; x<=j; x++)
sum+=oilMines[x];
DP_max[i][j][1]=sum;
DP_min[i][j][1]=sum;
}
}
for(int num_part=2; num_part<=N; num_part++){
for(int i=0; i<M; i++){
for(int j=i+1; j<M; j++){
int num_elems = j-i+1;
if(num_elems<num_part)
continue;
int absMax=-1,absMin=999999, minDiff = 999999;
if(verbose){
cout<<"\n FOR num_part = "<<num_part<<"\ti = "<<i<<"\tj = "<<j;
}
for(int x=1; x<=num_elems-num_part+1; x++){
int start_ind = i;
int end_ind = i+x-1;
int maxV = max(DP_max[end_ind+1][j][num_part-1], DP_max[i][end_ind][1]);
int minV = min(DP_min[end_ind+1][j][num_part-1], DP_min[i][end_ind][1]);
int diff = maxV-minV;
if(verbose){
cout<<"\n\tFOR x = "<<x<<"\n";
cout<<"\t\tstart_ind = "<<start_ind<<"\tend_ind = "<<end_ind<<"\tmaxV = "<<maxV<<"\tminV = "<<minV<<"\t diff = "<<diff<<endl;
}
if(diff<minDiff){
minDiff=diff;
absMax=maxV;
absMin=minV;
if(verbose)
cout<<"\t\tdiff<minDiff\t UPDATED minDiff = "<<minDiff<<"\tabsMax = "<<absMax<<"\tabsMin = "<<absMin<<endl;
}
}
if(verbose){
cout<<"\n UPDATED DP_max and DP_min for i, j, num_part = "<<i<<" "<<j<<" "<<num_part<<"\t TO : "<<absMax<<" "<<absMin<<endl;
}
DP_max[i][j][num_part]=absMax;
DP_min[i][j][num_part]=absMin;
}
}
}
if(verbose)
debug();
return;
}
int main(){
int t;
cin>>t;
int ctr=1;
while(t>0){
t--;
cin>>N>>M;
for(int i=0; i<M; i++){
int x;
cin>>x;
oilMines[i]=x;
oilMines[M+i]=x;
}
M*=2;
for(int i=0; i<M; i++){
for(int j=0; j<M; j++){
for(int k=1; k<M; k++){
DP_max[i][j][k]=-1;
DP_min[i][j][k]=999999;
}
}
}
DP();
//debug();
int minDiff=999999;
M/=2;
for(int i=0; i<M; i++){
int diff = DP_max[i][M+i-1][N]-DP_min[i][M+i-1][N];
if(diff<minDiff)
minDiff=diff;
}
cout<<"#"<<ctr<<" "<<minDiff<<endl;
ctr+=1;
}
return 1;
}
This is how I tried to solve this in C.
#include <stdio.h>
#include <stdlib.h>
int MinimumDifference(int n, int* pOilmines, int nNoOfMines)
{
if (nNoOfMines < n)
{
return -1;
}
if (pOilmines != nullptr && nNoOfMines > 0 && n > 0)
{
double nMeanVal = 0.0;
for (int i = 0; i < nNoOfMines; i++)
{
nMeanVal += pOilmines[i];
}
nMeanVal /= n;
int *pCurrentAllocation = (int*)malloc(n * sizeof(int));
int j = 0;
int nMaxAllocation = 0, nMinAllocation = 0;
for (int i = 0; i < n; i++)
{
pCurrentAllocation[i] = 0;
if (n == nNoOfMines)
{
pCurrentAllocation[i] = pOilmines[i];
}
else
{
while (j < nNoOfMines && pCurrentAllocation[i] < nMeanVal)
{
pCurrentAllocation[i] += pOilmines[j];
j++;
}
if (j < nNoOfMines)
{
if ((pCurrentAllocation[i] - nMeanVal) > (nMeanVal - (pCurrentAllocation[i] - pOilmines[j - 1])))
{
pCurrentAllocation[i] = pCurrentAllocation[i] - pOilmines[j - 1];
j--;
}
}
}
if (pCurrentAllocation[i] > nMaxAllocation)
{
nMaxAllocation = pCurrentAllocation[i];
}
if (0 == i)
{
nMinAllocation = pCurrentAllocation[i];
}
if (pCurrentAllocation[i] < nMinAllocation)
{
nMinAllocation = pCurrentAllocation[i];
}
}
free(pCurrentAllocation);
return nMaxAllocation - nMinAllocation;
}
return -1;
}
int main()
{
int nNoOfCompanies = -1;
int nNoOfMines = -1;
printf("\n No. Of companies : ");
scanf("%d", &nNoOfCompanies);
if (nNoOfCompanies < 1)
{
printf("-1"); // Error
return -1;
}
printf("\n No. Of oil mines : ");
scanf("%d", &nNoOfMines);
if (nNoOfMines < nNoOfCompanies)
{
printf("-1"); // Error
return -1;
}
int *pArr = (int*)malloc(nNoOfMines * sizeof(int));
if (!pArr)
{
printf("Failed to allocate memory");
return -1;
}
for (int i = 0; i < nNoOfMines; i++)
{
scanf("%d", &pArr[i]);
if (pArr[i] < 1)
{
printf("-1"); // Error
return -1;
}
}
/**************************************************************************
Run MinimumDifference Algo
**************************************************************************/
printf("\n Min Diff = %d\n", MinimumDifference(nNoOfCompanies, pArr, nNoOfMines));
free(pArr);
return 0;
}
There is an island surrounded by oil mines. You will be given n companies and m oil mines having values. You have to distribute the mines to "n" companies in fair manner. Remember the companies can have oil mines adjacent to each other and not in between of each others.After distributing them compute the differnce of oil mines from the company getting highest and company getting lowest. This number should be minimum.(then only the distribution can be termed as fair).
I think instead of --
while(j < oilmines.Length && companyMineAllocation[i] < mediumMineValue)
you should try to make group of such mines sum of which is as close as possible to the mediumMineValue i.e sum_of_mines/total_companies.
if(abs(sumOfCurrentMines - mediumMineValue) > (sumOfCurrentMines+nextMine - mediumMineValue))
sumOfCurrentMine += nextMine
and since the oil mines are arranged in a circular fashion. you need to try with different starting points.
for that u can choose all the values that are subset of closest sum of mines to the mediumMineValue containing max value from the mines.
I think instead of --
while(j < oilmines.Length && companyMineAllocation[i] < mediumMineValue)
you should try to make group of such mines sum of which is as close as possible to the mediumMineValue i.e sum_of_mines/total_companies.
if(abs(sumOfCurrentMines - mediumMineValue) > (sumOfCurrentMines+nextMine - mediumMineValue))
sumOfCurrentMine += nextMine
and since the oil mines are arranged in a circular fashion. you need to try with different starting points.
for that u can choose all the values that are subset of closest sum of mines to the mediumMineValue containing max value from the mines.
I think instead of --
while(j < oilmines.Length && companyMineAllocation[i] < mediumMineValue)
you should try to make group of such mines sum of which is as close as possible to the mediumMineValue i.e sum_of_mines/total_companies.
if(abs(sumOfCurrentMines - mediumMineValue) > (sumOfCurrentMines+nextMine - mediumMineValue))
sumOfCurrentMine += nextMine
and since the oil mines are arranged in a circular fashion. you need to try with different starting points.
for that u can choose all the values that are subset of closest sum of mines to the mediumMineValue containing max value from the mines.
I think instead of --
while(j < oilmines.Length && companyMineAllocation[i] < mediumMineValue)
you should try to make group of such mines sum of which is as close as possible to the mediumMineValue i.e sum_of_mines/total_companies.
if(abs(sumOfCurrentMines - mediumMineValue) > (sumOfCurrentMines+nextMine - mediumMineValue))
sumOfCurrentMine += nextMine
and since the oil mines are arranged in a circular fashion. you need to try with different starting points.
for that u can choose all the values that are subset of closest sum of mines to the mediumMineValue containing max value from the mines.
{
package spf;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Mines {
public static int nComp;
public static int mMines;
public static int x[] = new int[20];
public static int CompAlloc[] = new int[20];
public static int findFairness (int x[]) {
int nAverage = 0;
for (int i = 0; i < mMines; i++)
{
nAverage += x[i];
}
nAverage = nAverage/nComp;
int iStart = findStartPoint (nAverage);
findMinimum (iStart, nAverage);
System.out.println("Allocation");
for (int k =0; k < nComp; k ++)
{
System.out.print(CompAlloc[k] + ",");
}
System.out.println("");
return 0;
}
public static int findStartPoint (int nAverage)
{
int nMin = 100000000;
int iStart = 0;
for (int k =0; k < mMines; k++)
{
int nfinMin = findMinimum (k, nAverage);
if (nMin >= nfinMin)
{
nMin = nfinMin;
iStart = k;
}
}
System.out.println("Start Point: " + iStart);
return iStart;
}
public static int findMinimum (int iStart, int nAverage)
{
int nthComp = 0;
int Sum = 0;
int nMinimum = 100000000;
for (int j = iStart, k= 0; k < mMines; k++)
{
Sum += x[j];
if ((nComp -1 - nthComp) == (mMines-1-k))
{
int sum = Math.abs(Sum - nAverage);
if (sum < nMinimum)
{
nMinimum = sum;
}
CompAlloc[nthComp++] = Sum;
Sum = 0;
}
else if (nthComp == nComp - 1)
{
if (k == mMines -1)
{
int sum = Math.abs(Sum - nAverage);
if (sum < nMinimum)
{
nMinimum = sum;
}
CompAlloc[nthComp++] = Sum;
}
}
else if (Sum >= nAverage)
{
int sum1 = 0;
int sum2 = 0;
sum1 = Math.abs(Sum - nAverage);
sum2 = Math.abs(Sum -x[j] - nAverage);
if (sum1 < sum2)
{
CompAlloc[nthComp++] = Sum;
if (sum1 < nMinimum)
{
nMinimum = sum1;
}
}
else
{
CompAlloc[nthComp++] = (Sum - x[j]);
j--;
k--;
if (sum2 < nMinimum)
{
nMinimum = sum2;
}
}
Sum =0;
}
j++;
if (j >= mMines)
{
j =0;
}
}
return nMinimum;
}
public static void main(String args[]) throws FileNotFoundException {
Scanner sc = new Scanner(new File ("sample3.txt"));
int testcasecount = sc.nextInt();
for (int i = 0; i < testcasecount; ++i) {
nComp = sc.nextInt();
mMines = sc.nextInt();
for (int j = 0; j < mMines; ++j) {
x[j]= sc.nextInt();
}
findFairness (x);
}
sc.close();
return ;
}
}
}
#include<iostream>
using namespace std;
int an;
void calculateDiff(int comp[],int n)
{
int maxa=0,mina=1000;
for(int i=0;i<n;i++)
{
maxa = max(maxa,comp[i]);
mina = min(mina,comp[i]);
}
an = min(an,maxa-mina);
}
void calculateTotal(int end,int curr,int oil[],int comp[],int n,int m,int compNo)
{
if((curr+1)%m==end)
{
for(int j = compNo;j<n;j++)
{
comp[j]+=oil[curr];
calculateDiff(comp,n);
comp[j]-=oil[curr];
}
return;
}
if(compNo==n)
return;
comp[compNo]+=oil[curr];
calculateTotal(end,(curr+1)%m,oil,comp,n,m,compNo);
calculateTotal(end,(curr+1)%m,oil,comp,n,m,compNo+1);
comp[compNo]-=oil[curr];
calculateTotal(end,curr,oil,comp,n,m,compNo+1);
}
int main()
{
int n,m;
an = 10000;
scanf("%d%d",&n,&m);
int oil[m];
for(int i=0;i<m;i++)
scanf("%d",&oil[i]);
int comp[n];
for(int i=0;i<n;i++)
comp[i]=0;
for(int i=0;i<m;i++)
{
calculateTotal(i,i,oil,comp,n,m,0);
}
printf("%d",an);
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
int companies, mines, ANS;
int MIN(int x, int y){
return (x>=y) ? y : x;
}
int MAX(int x, int y){
return (x>=y) ? x : y;
}
void calculateOilMines(int i, int *oilMines, bool *visited, int minV, int maxV, int sum,
int nodes, int &ANS){
// Base Case
if(visited[i]){
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
if(nodes == companies - 1){
ANS = min(ANS, newMax - newMin);
}
return;
}
// Main Case
visited[i] = 1;
int j = (i + 1) % mines;
calculateOilMines(j, oilMines, visited, minV, maxV, sum + oilMines[i], nodes, ANS);
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
calculateOilMines(j, oilMines, visited, newMin, newMax, oilMines[i], nodes + 1, ANS);
visited[i] = 0;
return;
}
int main() {
// your code goes here
int t=1;
while(t--){
companies = 3;
mines = 5;
int oilMines[] = {1,2,3,4,5};
bool *visited = new bool[mines + 1];
for(int i=0; i<mines; i++){
visited[i] = 0;
}
ANS = INT_MAX;
for(int i=0; i<1; i++)
calculateOilMines(i, oilMines, visited, INT_MAX, INT_MIN, 0, 0, ANS);
cout << ANS <<endl;
}
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
int companies, mines, ANS;
int MIN(int x, int y){
return (x>=y) ? y : x;
}
int MAX(int x, int y){
return (x>=y) ? x : y;
}
void calculateOilMines(int i, int *oilMines, bool *visited, int minV, int maxV, int sum,
int nodes, int &ANS){
// Base Case
if(visited[i]){
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
if(nodes == companies - 1){
ANS = min(ANS, newMax - newMin);
}
return;
}
// Main Case
visited[i] = 1;
int j = (i + 1) % mines;
calculateOilMines(j, oilMines, visited, minV, maxV, sum + oilMines[i], nodes, ANS);
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
calculateOilMines(j, oilMines, visited, newMin, newMax, oilMines[i], nodes + 1, ANS);
visited[i] = 0;
return;
}
int main() {
// your code goes here
int t=1;
while(t--){
companies = 3;
mines = 5;
int oilMines[] = {1,2,3,4,5};
bool *visited = new bool[mines + 1];
for(int i=0; i<mines; i++){
visited[i] = 0;
}
ANS = INT_MAX;
for(int i=0; i<1; i++)
calculateOilMines(i, oilMines, visited, INT_MAX, INT_MIN, 0, 0, ANS);
cout << ANS <<endl;
}
return 0;
}
{{#include <iostream>
#include <climits>
using namespace std;
int companies, mines, ANS;
int MIN(int x, int y){
return (x>=y) ? y : x;
}
int MAX(int x, int y){
return (x>=y) ? x : y;
}
void calculateOilMines(int i, int *oilMines, bool *visited, int minV, int maxV, int sum,
int nodes, int &ANS){
// Base Case
if(visited[i]){
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
if(nodes == companies - 1){
ANS = min(ANS, newMax - newMin);
}
return;
}
// Main Case
visited[i] = 1;
int j = (i + 1) % mines;
calculateOilMines(j, oilMines, visited, minV, maxV, sum + oilMines[i], nodes, ANS);
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
calculateOilMines(j, oilMines, visited, newMin, newMax, oilMines[i], nodes + 1, ANS);
visited[i] = 0;
return;
}
int main() {
// your code goes here
int t=1;
while(t--){
companies = 3;
mines = 5;
int oilMines[] = {1,2,3,4,5};
bool *visited = new bool[mines + 1];
for(int i=0; i<mines; i++){
visited[i] = 0;
}
ANS = INT_MAX;
for(int i=0; i<1; i++)
calculateOilMines(i, oilMines, visited, INT_MAX, INT_MIN, 0, 0, ANS);
cout << ANS <<endl;
}
return 0;
}}}
Classical example of how a medium of something can be utilized to solve many complex problems
Idea is to stay as close ass possible to medium.
Here is how we will solve it
public static int MinimumDifference(int n, int[] oilmines)
{
if(oilmines != null && oilmines.Length > 0 && n > 0)
{
int mediumMineValue = oilmines.Sum()/n;
int[] companyMineAllocation = new int[n];
int j = 0;
int maxallocation = 0, minallocation=0;
for(int i = 0 ; i < n;i++)
{
companyMineAllocation[i] = 0
while(j < oilmines.Length && companyMineAllocation[i] < mediumMineValue)
{
companyMineAllocation[i]+ = oilmines[j];
j++;
}
if(j < oilmines.Length)
{
if((companyMineAllocation[i] - mediumMineValue) > (mediumMineValue - (companyMineAllocation[i] - oilmines[j-1]))) // making sure we stay as close as possible to medium
{
companyMineAllocation[i] = companyMineAllocation[i]- oilmines[j-1];
j--;
}
}
else if((companyMineAllocation[i] - mediumMineValue) > (mediumMineValue - (companyMineAllocation[i] - oilmines[j-1]))) // making sure we stay as close as possible to medium
{
companyMineAllocation[i] = companyMineAllocation[i]- oilmines[j-1];
j--;
}
else
{
break;
}
if(companyMineAllocation[i] > maxallocation)
{
maxallocation = companyMineAllocation[i];
}
if(companyMineAllocation[i] < minallocation)
{
minallocation = companyMineAllocation[i];
}
}
return maxallocation-minallocation;
}
throw new Exception("invalid input")
}
Complexity : O(N) in time and O(1) in space. It is of type Greedy Algorithms
Can you please check if this code work on given constraints or not ?
Thanks!!
#include <bits/stdc++.h>
using namespace std;
bool vis[10000];
int main()
{
int t; cin>>t;
while(t--)
{
int n,m,lim; cin>>n>>m>>lim;
vector<int> v,o;
queue<pair<int,int> > q;
for(int i=0;i<n;++i)
{
int x; cin>>x;
v.push_back(x);
q.push(make_pair(x,1));
}
for(int i=0;i<m;++i)
{
int x; cin>>x;
o.push_back(x);
}
int y; cin>>y;
pair<int,int> re;
while(!q.empty())
{
int x = q.front().first;
int l = q.front().second;
if(x==y)
{
re.first = y;
re.second = l;
break;
}
q.pop();
if(!vis[x])
{
for(int i=0;i<n;++i)
{
q.push(make_pair(x*10 + v[i],l+1));
}
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
if(o[i]==1)
{
q.push(make_pair(x+v[j],l+3));
}
else if(o[i]==2)
{
q.push(make_pair(x-v[j],l+3));
}
else if(o[i]==3)
{
q.push(make_pair(x*v[j],l+3));
}
else if(o[i]==4)
{
q.push(make_pair(x/v[j],l+3));
}
}
}
vis[x] = true;
}
}
cout<<re.second<<endl;
}
}
Can you please check if this code work on given constraints or not ?
Thanks!!
#include <bits/stdc++.h>
using namespace std;
bool vis[10000];
int main()
{
int t; cin>>t;
while(t--)
{
int n,m,lim; cin>>n>>m>>lim;
vector<int> v,o;
queue<pair<int,int> > q;
for(int i=0;i<n;++i)
{
int x; cin>>x;
v.push_back(x);
q.push(make_pair(x,1));
}
for(int i=0;i<m;++i)
{
int x; cin>>x;
o.push_back(x);
}
int y; cin>>y;
pair<int,int> re;
while(!q.empty())
{
int x = q.front().first;
int l = q.front().second;
if(x==y)
{
re.first = y;
re.second = l;
break;
}
q.pop();
if(!vis[x])
{
for(int i=0;i<n;++i)
{
q.push(make_pair(x*10 + v[i],l+1));
}
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
if(o[i]==1)
{
q.push(make_pair(x+v[j],l+3));
}
else if(o[i]==2)
{
q.push(make_pair(x-v[j],l+3));
}
else if(o[i]==3)
{
q.push(make_pair(x*v[j],l+3));
}
else if(o[i]==4)
{
q.push(make_pair(x/v[j],l+3));
}
}
}
vis[x] = true;
}
}
cout<<re.second<<endl;
}
}
#include <iostream>
#include <climits>
using namespace std;
int companies, mines, ANS;
int MIN(int x, int y){
return (x>=y) ? y : x;
}
int MAX(int x, int y){
return (x>=y) ? x : y;
}
void calculateOilMines(int i, int *oilMines, bool *visited, int minV, int maxV, int sum,
int nodes, int &ANS){
// Base Case
if(visited[i]){
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
if(nodes == companies - 1){
ANS = min(ANS, newMax - newMin);
}
return;
}
// Main Case
visited[i] = 1;
int j = (i + 1) % mines;
calculateOilMines(j, oilMines, visited, minV, maxV, sum + oilMines[i], nodes, ANS);
int newMin = MIN(sum, minV);
int newMax = MAX(sum, maxV);
calculateOilMines(j, oilMines, visited, newMin, newMax, oilMines[i], nodes + 1, ANS);
visited[i] = 0;
return;
}
int main() {
// your code goes here
int t=1;
while(t--){
companies = 3;
mines = 5;
int oilMines[] = {1,2,3,4,5};
bool *visited = new bool[mines + 1];
for(int i=0; i<mines; i++){
visited[i] = 0;
}
ANS = INT_MAX;
for(int i=0; i<1; i++)
calculateOilMines(i, oilMines, visited, INT_MAX, INT_MIN, 0, 0, ANS);
cout << ANS <<endl;
}
return 0;
}
It can be solved easily using dynamic programming in O(n^4) time and O(2*n^3) space.
- Namit September 08, 2018The idea is first double the size of array and append a copy of it in back..
now the idea is
dividing array from i to any index j in k groups and store its min and max value....
If you still need help mail me at namit.pasrija@gmail.com