ThoughtWorks Interview Question
Applications DevelopersCountry: United States
Interview Type: In-Person
wouldn't it be easier if you just pick the last m integers from n-1,n-2...etc
like in case of n=20 m=5
[19, 18, 17, 16, 15]
This is the best solution I could come up with
1. from 2 to n-1 add one number to set
2. for each new added number find sum with existing from set
note: step two is important if you want to maximise a+b=c triplets
public static void main(String[] args) {
ArrayList<Integer> set = new ArrayList<>();
Scanner in = new Scanner(System.in);
System.out.print("Enter limit n : ");
int n = in.nextInt();
System.out.print("Enter limit m : ");
int m = in.nextInt();
outer:
for (int i = 2; i < n && set.size() < m; i++) {
int size = set.size();
if (set.contains(i)) continue;
set.add(i);
inner:
for (int j = size; j < set.size(); j++) {
for (int k = 0; k < j; k++) {
int sum = set.get(j) + set.get(k);
if (sum >= n) continue inner;
if (set.contains(sum)) continue;
if (set.size() < m)
set.add(sum);
else break outer;
}
}
}
System.out.println("the set is " + set.toString());
}
the check num>=n checks if the num has exceeded the n limit
to ensure a num is added only once we check for set contains num
Isn't the output wrong 3+14 = 17 but as of question no two integers should prode integer in set but 17 is in set
- upendra July 16, 2019