Samsung Interview Question for Java Developers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
2
of 2 vote

It can be solved easily using dynamic programming in O(n^4) time and O(2*n^3) space.

The 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

- Namit September 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Professional test at bangalore

- sunny.agrawal@s2ar.com May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

#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;
}

- Shivanshu March 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ignore the debug function.

- Shivanshu March 14, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please can I know when this code was asked in Samsung? Date and location.

- Tim April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please can I know that in which event of samsung, this question was asked? Date and location.

- Tim April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please can I know that in which event of samsung, this question was asked? Date and location.

- Tim April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please can I know that in which event of samsung, this question was asked? Date and location.

- Tim April 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Professional test again

- Flag May 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

could you please tell me the input and output format . I am not able what is 2 and 4 here

- pratiksha June 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What are the constraints for n & m?

- anonymous June 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what are the constraints for n and m??

- abc June 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

constraints for n and m

- chandra June 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Geek June 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Anonymous July 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

wont work on
4 9
4 3 2 9 5 6 4 8 3

- devbishnoi July 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- vk_rt July 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- vk_rt July 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- vk_rt July 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- vk_rt July 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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 ;
}

}

}

- Murali February 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Anonymous February 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please explain me first test case.

- Ron August 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For any kind of assistance in Samsung Interviews the link for all the solutions of questions asked previously – pastebin.com/u/ann8497
I have prepared the solutions myself. The questions are verified and solved in the least complexity time.
Hope it helps.

- annmittal8497 April 18, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;

}

- Anonymous June 09, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Anonymous June 09, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{#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;
}}}

- Anonymous January 25, 2023 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- sonesh March 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;		
	}
}

- Anonymous November 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;		
	}
}

- Anonymous November 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#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;
}

- Anonymous June 09, 2020 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More