Here comes one interesting problem with interesting story to relate the work issues & challenges.
Problem :
Manager A of yours, contacts a manager B in iron/steel company to get the iron beams. A’s requirements are clear regarding the strength of iron beams, these need to be super strong. And he demands for certain set of such iron beams but doesn’t tell of what size. So B doesn’t know of what size he needs to send. Being a manager, B also sends a set of iron beams of random size.
Let us suppose B sends a set of N beams of various sizes.
A contacts his employee C to use these beams to hold some advertising banner & it should be visible to all.
C asks A about the height, he needs to achieve to put the banner on these beams. A does the calculation on the beams & tells to create 2 poles from these beams of height ‘H’ & put the banner on that. C checks for its feasibility & tells A, that some beams need to be cut to have 2 poles of height ‘H’.
A, being the manager tells C to cut the beams if required. C does the analysis on work/cost & tells A that it will need ’M’ more money to cut the beams as these are strong & not easy to cut. A, again being a manager not willing to put more money & clueless about the solution & the required height for the 2 poles. A asks C to find the maximum possible heights can be achieved for the 2 poles from the given set of iron beams without extra cost of cutting, as joining them is not taking any significant cost.
C, being an intelligent employee, knows that such scenarios will occur in future also or may be multiple times with such manager. So he thinks to write an efficient code to calculate such values quickly to avoid any manual work for this in future.
Now, just think that intelligent employee is you & write the efficient code which will take the inputs from the command line such that –
First line: Number of beams (N)
Second Line: Space separated size of each N beams
Now your code needs to return the maximum possible height of the 2 poles can be achieved using the provided beams. If it is not possible to get 2 poles of equal maximum height then return 0.
Conditions :
a) All the beams can be of different size or of the same size.
b) Once a beam is used in one pole, it can’t be used for other pole.
c) All beams not required to be used to achieve the maximum height.
d) 1 <= N <= 1000000
e) 1 <= size of each beam <= 1000
Example :
5
2 3 4 1 6
Ans : 8 (Pole1=(2,6) Pole2=(3,4,1))
4
5 3 10 1
Ans : 0 (As no 2 poles of equal heights can be created)
Note:
Depending on the expectations, you can be given number of test cases in single shot & there you may need to print the answer for every case like –
#1: <ans>
#2: <ans>
#3: <ans>
#4: <ans>
And that you can modify at the same time accordingly, here I am just expecting one case in one time.
Approach I took:
1) Sort list of heights of beams
2) Take the sum ‘S’ of all the heights in the list.
3) Maximum possible heights for the 2 poles of equal height can be H = S/2.
4) Start building the pole of height H, first & call the method in step 5 which will provide Boolean value.
5) Build 1 pole of height H, if not possible then return false, else remove all the used beams in Pole1 from the list.
6) Build 2 pole of height H from the remaining list of heights, if not possible then return false else return true to step 4.
7) In step 4 if you can get true for any height H, then this the maximum height & print that on console. Else repeat steps
from (5) for another height H=H-1
8) Keep reducing the height till you either get true for some height or height is less than the lowest height in the list. If for no
height you get true then print 0 on console.
Above approach, I think should work for general cases but need improvement to improve the performance & may need changes also, to handle the other corner cases. As I tested it for just 5-6 cases.
Sometimes it becomes tricky & you lose focus from the actual problem.
If you can share a better approach, please do share which will help others also. If can share the code also, will be good.
Below is the code but it is not same as I wrote for the implementation of above algorithm. Meanwhile you can check & suggest the improvements -
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
* Program to find the maximum height can be achieved by combining
* the given number of iron bars & without cutting any bar.
* It find the equal maximum heights for the given number of poles
* & given number of bars of various lengths.
* @author nitin
*
*/
public class Samsung {
static int sum = 0;
static Scanner sc = new Scanner(System.in);
static int roll = 1;
public static void main(String[] args) {
/*
* Below lines are used to read the input test cases from command line
* in the decided format & calls the method to find the maximum
* height for each test case.
*/
System.out.print("Number of Test Cases : ");
int testCases = Integer.parseInt(sc.nextLine());
ArrayList<Integer> results = new ArrayList<>();
while(testCases > 0) {
System.out.print("Number of iron beams : ");
int count = Integer.parseInt(sc.nextLine());
System.out.print("Number of poles to create : ");
int poles = Integer.parseInt(sc.nextLine());
System.out.println("Provide space separated size of each beam below -");
String[] lens = sc.nextLine().split(" ");
ArrayList<Integer> lengths = new ArrayList<>();
for(String str : lens) {
lengths.add(Integer.parseInt(str));
}
results.add(getMaximumHeight(poles, count, lengths));
testCases--;
}
results.forEach(a -> {
System.out.println("#"+roll+" : " + a);
});
}
/**
* Method to find the maximum equal heights for the number of poles
* given using the provided list of bars of various lengths.
* This method was made public to test it from other class, else it can be kept private.
* @param poles
* @param count
* @param lengths
* @return int as maximum height possible
*/
public static int getMaximumHeight(int poles, int count, ArrayList<Integer> lengths) {
lengths.forEach(a -> sum+=a);
// Below is the maximum height possible for each pole.
int maxHeightPossible = sum/poles;
// Sort the list to enable binary search later to find the bar of required length.
Collections.sort(lengths);
// Only copy of the list of bar lengths will be passed for the calculation.
// As during the calculation in one iteration, the list will be modified.
ArrayList<Integer> copy = new ArrayList<>();
copy.addAll(lengths);
// Checks possibility for each height value & if any height is possible
// then that value will be returned as the answer, else it will continue to check
// for next lower value till it is 0.
while(maxHeightPossible > 0) {
if(checkFeasibility(poles, maxHeightPossible, count, copy))
return maxHeightPossible;
maxHeightPossible--;
copy.clear();
copy.addAll(lengths);
}
return maxHeightPossible;
}
/**
* Returns true or false for the particular height value after checking if the given number of poles
* can be created with the given height value using the list of bars of various lengths.
* It is the core to check the feasibility & one has to check the code to see the logic.
* @param poles
* @param height
* @param count
* @param lengths
* @return boolean
*/
private static boolean checkFeasibility(int poles, int height, int count, ArrayList<Integer> lengths) {
int h = height;
ArrayList<Integer> org = new ArrayList<>();
org.addAll(lengths);
int counts = poles;
int found = 0;
while(!lengths.isEmpty() && poles > 0 && h >= lengths.get(0)) {
int start = lengths.size()-1;
ArrayList<Integer> backup = new ArrayList<>();
int pos = -1;
int next = start;
int cur = 0;
while(h > 0) {
if((pos=Collections.binarySearch(lengths, h)) >= 0) {
h = 0;
lengths.remove(pos);
found++;
break;
}
while(next >= 0 && (cur = lengths.get(next)) > h)
next--;
if(next < 0 && start > 0) {
lengths.addAll(backup);
lengths.remove(lengths.size()-1);
backup.clear();
h = height;
start--;
next = start;
continue;
} else if(next < 0 && start <= 0) {
return false;
}
h-=cur;
backup.add(lengths.get(next));
lengths.remove(next);
next--;
}
poles--;
h = height;
}
return found == counts;
}
}
Now it becomes frustrating to test such code for different cases & I wrote the test class in my own way, though it is not the right way to do in your organisation but here I have done it. After this, I have written the JUnit class also, which is more elegant & removes all the boilerplate code to read a file & I am using CSV file there.
Below is the class I used to test the above class against a list of test cases written in separate file, that file I have attached after below test class.
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* This class test the class Samsung against the given test data & expected results in some file.
* @author nitin
*
*/
class SamsungTest {
public static void main(String[] args) throws Exception {
List<String> results = readAndTest("Complete path of test cases file.");
results.forEach(System.out::println);
}
/**
* Reads the test cases for their input values. Reads the expected answer for each test case.
* It compares the resulted answer with expected answer for each test case.
* Then returns the list of answers for the test cases like :
* Expected : 8 <--> Actual Answer : 8 <--> Result : true
* @param file
* @return
* @throws Exception
*/
private static List<String> readAndTest(String file) throws Exception {
int cases = 0;
boolean start = false;
boolean caseStart = false;
Path path = Paths.get(file);
// If the test cases file is in classpath, then no need to give complete path above.
// Path path = Paths.get(SamsungTest.class.getResource(file).toURI());
List<String> data = Files.readAllLines(path);
int counter = 3;
int orgCount = 0;
ArrayList<TestCase> testCases = new ArrayList<>();
ArrayList<Integer> results = new ArrayList<>();
ArrayList<String> status = new ArrayList<>();
for(String line : data) {
if(line.contains("INPUT")) {
start = true;
continue;
} else if(line.contains("RESULTS")) {
start = false;
if(cases != orgCount-1) {
throw new Exception("Number of cases mentioned & actually given are not same, so ending the test here only...");
}
continue;
}
if(start) {
if(!caseStart) {
cases = Integer.parseInt(line);
orgCount = cases;
if(cases == 0) {
System.out.println("No case to test as number of cases are given 0...");
return Collections.emptyList();
}
caseStart = true;
while(cases > 0) {
TestCase test = new TestCase();
test.lengths = new ArrayList<Integer>();
testCases.add(test);
cases--;
}
continue;
}
if(counter == 0) {
cases++;
counter = 3;
}
if(cases == orgCount) {
throw new Exception("Number of cases mentioned & actually given are not same, so ending the test here only...");
}
TestCase test = testCases.get(cases);
switch(counter) {
case 3 : test.bars = Integer.parseInt(line);
break;
case 2 : test.poles = Integer.parseInt(line);
break;
case 1 : {
String[] lens = line.split(" ");
for(String len : lens)
test.lengths.add(Integer.parseInt(len));
}
break;
}
counter--;
}
if(!start)
results.add(Integer.parseInt(line));
}
if(cases+1 != results.size()) {
throw new Exception("Number of cases & the count of expected results is not same, so ending the test here only...");
}
counter = 0;
for(TestCase tc : testCases) {
int res = Samsung.getMaximumHeight(tc.poles, tc.bars, tc.lengths);
int act = results.get(counter);
String ans = "Expected : " + act + " <--> Actual Answer : " + res + " <--> Result : " + (res == act);
status.add(ans);
counter++;
}
return status;
}
}
/*
* Class to store the data for each test case.
*/
class TestCase {
public int bars;
public int poles;
public ArrayList<Integer> lengths;
}
Use the below test cases file, update it with your test cases & provide its complete path in above test program.
In below file you need to provide both input data & the expected results. Provide the test cases data under INPUTS only,
update the number of test cases after it. Then provide the same number of expected results under RESULTS.
Manager A of yours, contacts a manager B in iron/steel company to get the iron beams. A’s requirements are clear regarding the strength of iron beams, these need to be super strong. And he demands for certain set of such iron beams but doesn’t tell of what size. So B doesn’t know of what size he needs to send. Being a manager, B also sends a set of iron beams of random size.
Let us suppose B sends a set of N beams of various sizes.
A contacts his employee C to use these beams to hold some advertising banner & it should be visible to all.
C asks A about the height, he needs to achieve to put the banner on these beams. A does the calculation on the beams & tells to create 2 poles from these beams of height ‘H’ & put the banner on that. C checks for its feasibility & tells A, that some beams need to be cut to have 2 poles of height ‘H’.
A, being the manager tells C to cut the beams if required. C does the analysis on work/cost & tells A that it will need ’M’ more money to cut the beams as these are strong & not easy to cut. A, again being a manager not willing to put more money & clueless about the solution & the required height for the 2 poles. A asks C to find the maximum possible heights can be achieved for the 2 poles from the given set of iron beams without extra cost of cutting, as joining them is not taking any significant cost.
C, being an intelligent employee, knows that such scenarios will occur in future also or may be multiple times with such manager. So he thinks to write an efficient code to calculate such values quickly to avoid any manual work for this in future.
Now, just think that intelligent employee is you & write the efficient code which will take the inputs from the command line such that –
First line: Number of beams (N)
Second Line: Space separated size of each N beams
Now your code needs to return the maximum possible height of the 2 poles can be achieved using the provided beams. If it is not possible to get 2 poles of equal maximum height then return 0.
Conditions :
a) All the beams can be of different size or of the same size.
b) Once a beam is used in one pole, it can’t be used for other pole.
c) All beams not required to be used to achieve the maximum height.
d) 1 <= N <= 1000000
e) 1 <= size of each beam <= 1000
Example :
5
2 3 4 1 6
Ans : 8 (Pole1=(2,6) Pole2=(3,4,1))
4
5 3 10 1
Ans : 0 (As no 2 poles of equal heights can be created)
Note:
Depending on the expectations, you can be given number of test cases in single shot & there you may need to print the answer for every case like –
#1: <ans>
#2: <ans>
#3: <ans>
#4: <ans>
And that you can modify at the same time accordingly, here I am just expecting one case in one time.
Approach I took:
1) Sort list of heights of beams
2) Take the sum ‘S’ of all the heights in the list.
3) Maximum possible heights for the 2 poles of equal height can be H = S/2.
4) Start building the pole of height H, first & call the method in step 5 which will provide Boolean value.
5) Build 1 pole of height H, if not possible then return false, else remove all the used beams in Pole1 from the list.
6) Build 2 pole of height H from the remaining list of heights, if not possible then return false else return true to step 4.
7) In step 4 if you can get true for any height H, then this the maximum height & print that on console. Else repeat steps
from (5) for another height H=H-1
8) Keep reducing the height till you either get true for some height or height is less than the lowest height in the list. If for no
height you get true then print 0 on console.
Above approach, I think should work for general cases but need improvement to improve the performance & may need changes also, to handle the other corner cases. As I tested it for just 5-6 cases.
Sometimes it becomes tricky & you lose focus from the actual problem.
If you can share a better approach, please do share which will help others also. If can share the code also, will be good.
Below is the code but it is not same as I wrote for the implementation of above algorithm. Meanwhile you can check & suggest the improvements -
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
/**
* Program to find the maximum height can be achieved by combining
* the given number of iron bars & without cutting any bar.
* It find the equal maximum heights for the given number of poles
* & given number of bars of various lengths.
* @author nitin
*
*/
public class Samsung {
static int sum = 0;
static Scanner sc = new Scanner(System.in);
static int roll = 1;
public static void main(String[] args) {
/*
* Below lines are used to read the input test cases from command line
* in the decided format & calls the method to find the maximum
* height for each test case.
*/
System.out.print("Number of Test Cases : ");
int testCases = Integer.parseInt(sc.nextLine());
ArrayList<Integer> results = new ArrayList<>();
while(testCases > 0) {
System.out.print("Number of iron beams : ");
int count = Integer.parseInt(sc.nextLine());
System.out.print("Number of poles to create : ");
int poles = Integer.parseInt(sc.nextLine());
System.out.println("Provide space separated size of each beam below -");
String[] lens = sc.nextLine().split(" ");
ArrayList<Integer> lengths = new ArrayList<>();
for(String str : lens) {
lengths.add(Integer.parseInt(str));
}
results.add(getMaximumHeight(poles, count, lengths));
testCases--;
}
results.forEach(a -> {
System.out.println("#"+roll+" : " + a);
});
}
/**
* Method to find the maximum equal heights for the number of poles
* given using the provided list of bars of various lengths.
* This method was made public to test it from other class, else it can be kept private.
* @param poles
* @param count
* @param lengths
* @return int as maximum height possible
*/
public static int getMaximumHeight(int poles, int count, ArrayList<Integer> lengths) {
lengths.forEach(a -> sum+=a);
// Below is the maximum height possible for each pole.
int maxHeightPossible = sum/poles;
// Sort the list to enable binary search later to find the bar of required length.
Collections.sort(lengths);
// Only copy of the list of bar lengths will be passed for the calculation.
// As during the calculation in one iteration, the list will be modified.
ArrayList<Integer> copy = new ArrayList<>();
copy.addAll(lengths);
// Checks possibility for each height value & if any height is possible
// then that value will be returned as the answer, else it will continue to check
// for next lower value till it is 0.
while(maxHeightPossible > 0) {
if(checkFeasibility(poles, maxHeightPossible, count, copy))
return maxHeightPossible;
maxHeightPossible--;
copy.clear();
copy.addAll(lengths);
}
return maxHeightPossible;
}
/**
* Returns true or false for the particular height value after checking if the given number of poles
* can be created with the given height value using the list of bars of various lengths.
* It is the core to check the feasibility & one has to check the code to see the logic.
* @param poles
* @param height
* @param count
* @param lengths
* @return boolean
*/
private static boolean checkFeasibility(int poles, int height, int count, ArrayList<Integer> lengths) {
int h = height;
ArrayList<Integer> org = new ArrayList<>();
org.addAll(lengths);
int counts = poles;
int found = 0;
while(!lengths.isEmpty() && poles > 0 && h >= lengths.get(0)) {
int start = lengths.size()-1;
ArrayList<Integer> backup = new ArrayList<>();
int pos = -1;
int next = start;
int cur = 0;
while(h > 0) {
if((pos=Collections.binarySearch(lengths, h)) >= 0) {
h = 0;
lengths.remove(pos);
found++;
break;
}
while(next >= 0 && (cur = lengths.get(next)) > h)
next--;
if(next < 0 && start > 0) {
lengths.addAll(backup);
lengths.remove(lengths.size()-1);
backup.clear();
h = height;
start--;
next = start;
continue;
} else if(next < 0 && start <= 0) {
return false;
}
h-=cur;
backup.add(lengths.get(next));
lengths.remove(next);
next--;
}
poles--;
h = height;
}
return found == counts;
}
}
Now it becomes frustrating to test such code for different cases & I wrote the test class in my own way, though it is not the right way to do in your organisation but here I have done it. After this, I have written the JUnit class also, which is more elegant & removes all the boilerplate code to read a file & I am using CSV file there.
Below is the class I used to test the above class against a list of test cases written in separate file, that file I have attached after below test class.
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* This class test the class Samsung against the given test data & expected results in some file.
* @author nitin
*
*/
class SamsungTest {
public static void main(String[] args) throws Exception {
List<String> results = readAndTest("Complete path of test cases file.");
results.forEach(System.out::println);
}
/**
* Reads the test cases for their input values. Reads the expected answer for each test case.
* It compares the resulted answer with expected answer for each test case.
* Then returns the list of answers for the test cases like :
* Expected : 8 <--> Actual Answer : 8 <--> Result : true
* @param file
* @return
* @throws Exception
*/
private static List<String> readAndTest(String file) throws Exception {
int cases = 0;
boolean start = false;
boolean caseStart = false;
Path path = Paths.get(file);
// If the test cases file is in classpath, then no need to give complete path above.
// Path path = Paths.get(SamsungTest.class.getResource(file).toURI());
List<String> data = Files.readAllLines(path);
int counter = 3;
int orgCount = 0;
ArrayList<TestCase> testCases = new ArrayList<>();
ArrayList<Integer> results = new ArrayList<>();
ArrayList<String> status = new ArrayList<>();
for(String line : data) {
if(line.contains("INPUT")) {
start = true;
continue;
} else if(line.contains("RESULTS")) {
start = false;
if(cases != orgCount-1) {
throw new Exception("Number of cases mentioned & actually given are not same, so ending the test here only...");
}
continue;
}
if(start) {
if(!caseStart) {
cases = Integer.parseInt(line);
orgCount = cases;
if(cases == 0) {
System.out.println("No case to test as number of cases are given 0...");
return Collections.emptyList();
}
caseStart = true;
while(cases > 0) {
TestCase test = new TestCase();
test.lengths = new ArrayList<Integer>();
testCases.add(test);
cases--;
}
continue;
}
if(counter == 0) {
cases++;
counter = 3;
}
if(cases == orgCount) {
throw new Exception("Number of cases mentioned & actually given are not same, so ending the test here only...");
}
TestCase test = testCases.get(cases);
switch(counter) {
case 3 : test.bars = Integer.parseInt(line);
break;
case 2 : test.poles = Integer.parseInt(line);
break;
case 1 : {
String[] lens = line.split(" ");
for(String len : lens)
test.lengths.add(Integer.parseInt(len));
}
break;
}
counter--;
}
if(!start)
results.add(Integer.parseInt(line));
}
if(cases+1 != results.size()) {
throw new Exception("Number of cases & the count of expected results is not same, so ending the test here only...");
}
counter = 0;
for(TestCase tc : testCases) {
int res = Samsung.getMaximumHeight(tc.poles, tc.bars, tc.lengths);
int act = results.get(counter);
String ans = "Expected : " + act + " <--> Actual Answer : " + res + " <--> Result : " + (res == act);
status.add(ans);
counter++;
}
return status;
}
}
/*
* Class to store the data for each test case.
*/
class TestCase {
public int bars;
public int poles;
public ArrayList<Integer> lengths;
}
Use the below test cases file, update it with your test cases & provide its complete path in above test program.
In below file you need to provide both input data & the expected results. Provide the test cases data under INPUTS only,
update the number of test cases after it. Then provide the same number of expected results under RESULTS.
| samsungtestcase |
One way, to write the test class was above & it is not the correct way to write the test cases as I said above.
Now let us look bit differently, as we just need to test the method which will take the test data & not the number of test cases.
But number of test cases are required when you execute the actual class 'Samsung.java' which we again tweak to remove that requirement from the main(), but will see that later.
For now to test the method, let us make it simpler using JUnit5, & test data file I am using in below test class, I have attached after that. Use that in the same format or change the test class accordingly, else you just need to update it with your test data.
import static org.junit.Assert.assertTrue;
import java.util.ArrayList;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvFileSource;
class SamsungTest {
@ParameterizedTest
@CsvFileSource(resources = "SamsungTestData.csv", numLinesToSkip = 1)
void testGetMaximumHeight(String p, String c, String b, String e) {
int poles = Integer.parseInt(p);
int count = Integer.parseInt(c);
String[] lens = b.split(":");
ArrayList<Integer> lengths = new ArrayList<>(lens.length);
for(String len : lens)
lengths.add(Integer.parseInt(len));
int expected = Integer.parseInt(e);
assertTrue(expected == Samsung.getMaximumHeight(poles, count, lengths));
}
}
Yes, it looks good, elegant & concise. Go ahead & try it, it will execute the above test method against all the test cases you give in below attached file. By default line separator is 'new line' & if you use different then add that as parameter to @CsvFileSource. Also lengths of bars are separated by ':' & if you change that update above code for split().
All looks good now. Will try to find other way to write test class. Till then use it or you get any other way then please post in Views section. A word of caution : When updating the .csv file, do it using notepad or Notepad++, else if you update using Excel, then you will get the warning during save & it will change the format or csv file & your cases will fail as above code will not be able to parse the data in it.
Now let us look bit differently, as we just need to test the method which will take the test data & not the number of test cases.
But number of test cases are required when you execute the actual class 'Samsung.java' which we again tweak to remove that requirement from the main(), but will see that later.
For now to test the method, let us make it simpler using JUnit5, & test data file I am using in below test class, I have attached after that. Use that in the same format or change the test class accordingly, else you just need to update it with your test data.
import static org.junit.Assert.assertTrue;
import java.util.ArrayList;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvFileSource;
class SamsungTest {
@ParameterizedTest
@CsvFileSource(resources = "SamsungTestData.csv", numLinesToSkip = 1)
void testGetMaximumHeight(String p, String c, String b, String e) {
int poles = Integer.parseInt(p);
int count = Integer.parseInt(c);
String[] lens = b.split(":");
ArrayList<Integer> lengths = new ArrayList<>(lens.length);
for(String len : lens)
lengths.add(Integer.parseInt(len));
int expected = Integer.parseInt(e);
assertTrue(expected == Samsung.getMaximumHeight(poles, count, lengths));
}
}
Yes, it looks good, elegant & concise. Go ahead & try it, it will execute the above test method against all the test cases you give in below attached file. By default line separator is 'new line' & if you use different then add that as parameter to @CsvFileSource. Also lengths of bars are separated by ':' & if you change that update above code for split().
All looks good now. Will try to find other way to write test class. Till then use it or you get any other way then please post in Views section. A word of caution : When updating the .csv file, do it using notepad or Notepad++, else if you update using Excel, then you will get the warning during save & it will change the format or csv file & your cases will fail as above code will not be able to parse the data in it.
| samsungtestdata.csv |
