ThoughtWorks Interview Question Interns
Country: India
Interview Type: In-Person
consider this input:
1,4,8,64,65,97,125
Your solution is : 1,2,4,8,16,32,64
But the ans can be obtained using: 1,4,8,16,32,64
The key is : In the binary conversion of any of the input --> 2nd least sign bit is not set.. so that is not needed at all .
The solution will be to do bitwise OR on all numbers and find 2^(bit no from the left minus 1). All these no.s will be the result
consider this input:
1,4,8,64,65,97,125
Your solution is : 1,2,4,8,16,32,64
But the ans can be obtained using: 1,4,8,16,32,64
The key is : In the binary conversion of any of the input --> 2nd least sign bit is not set.. so that is not needed at all .
The solution will be to do bitwise OR on all numbers and find 2^(bit no from the left minus 1). All these no.s will be the result.
The input itself will for the output if the no. of results formed above is greater than the number of elements in the input.
@ pankaj
the solution goes like this :
take the test case i've mentioned above:
1,4,8,64,65,97,125
binary of each input are :
00000001
00000100
00001000
01000000
00100001
11000001
11111101
1 = 2^0
4 = 2^2
8 = 2^3
64 = 2^6
65 = 2^6 + 2^0
97 = 2^6 + 2^5 + 2^0
125 = 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^0
so, 2^0, 2^2, 2^3, 2^4 , 2^5 , 2^6, 2^7--> the combo of sum of these are enuf to represent the numbers.
the above is the union of all numbers (Bitwise OR).
11111101
Exclude the Zero here and compute the solution..
If the count of numbers is greater than the count of input, the input forms the solution.
I hope it is clear now .
I wrote a brute-force O(n^3) program where each of i,j,k can range from -100 to 100 and that our goal is to check whether the inputs can be covered by any of these:
(1) i
(2) j
(3) k
(4) i+j
(5) i+k
(6) j+k
(7) i+j+k
My program couldn't find any, so I am convinced that no such 3 integers exist. The question should have mentioned that possibility, but I guess it's our job to prove or disprove whether such 3 integers will always exist?
Basic Idea: given b1<b2<b3 in B, a1<a2<a3<a4 in A, then b1<=a1, b2<=a2 and b3<=a4
#include<iostream>
int main ()
{
//assume imput is sorted
int four_num[]={2,4,6,7};
char num[11],mark[31];
int i,j,k,l;
memset(num,0,11);
memset(mark,0,31);
for (i=0;i<4;num[four_num[i++]]=1);
for (i=1;i<=four_num[0];i++)
{
mark[i]=1;
for (j=i+1;j<=four_num[1];j++)
{
mark[j]=1;
mark[i+j]=1;
for (k=j+1;k<four_num[3];k++)
if (k!=i+j)
{
mark[k]=1;
mark[i+k]=1;
mark[j+k]=1;
mark[i+k+j]=1;
int t=0;
for (l=1;l<=10;l++)
t+=(mark[l]&num[l]);
if (t>=4)
printf("Results are: %d %d %d\n",i,j,k);
mark[k]=0;
mark[i+k]=0;
mark[j+k]=0;
mark[i+k+j]=0;
}
mark[i+j]=0;
mark[j]=0;
}
mark[i]=0;
}
}
it's just a case of binary conversion.
1. find largest element in list A (assume N is largest)
2. Y = (floor) log N (over base 2)
3. ans is 1,2,4... upto 2^y
There may be 3 kind of sets
Set 1 will have subsets as{ {1,2,3},.....{1,2,7},{1,3,4},.....,{1,3,6},{1,4,5},{2,3,4},....{2,3,5}}
Set 2 will have subsets as{{1,2},.....,{1,9},{2,3}.....,{2,8},{3,4},....,{3,7},{4,5},{4,6}}
Set 3 will have subsets {1,2,3,4,5,6,7,8,9,10}
Each number may have a set of subsets which add up the number.
Like number 6 will have set as {{1,2,3},{1,5},{2,4},{6}}
3 will have set as {{1,2},{3}}
5 will have set as {{1,4},{2,3},{5}}
This may be the approach.... This way the logic may be designed....
List<Integer> sortedArr = new ArrayList<Integer>();
List<String> resultList = new ArrayList<String>();
for(int i = 1; i < 11; i++) {
sortedArr.add(i);
}
for(int k = 0; k <= 6; k++) {
for(int j = k+1; j <= 6; j++) {
for(int i = j+1; i <= 6; i++) {
int a = sortedArr.get(i);
int b = sortedArr.get(j);
int c = sortedArr.get(k);
int d = a+b+c;
if(d <= 10) {
resultList.add("Parent String: "+a+", "+b+", "+c
+" Result String: "+(a+b)+", "+(b+c)+", "+(a+c)+", "+d);
}
}
if(sortedArr.get(k) + sortedArr.get(j) + sortedArr.get(j+1) > 10) {
break;
}
}
if(sortedArr.get(k) + sortedArr.get(k+1) + sortedArr.get(k+2) > 10) {
break;
}
}
for(int i = 0; i < resultList.size(); i++) {
System.out.println(resultList.get(i));
}
}
the basic idea is that since we have to form 4 numbers out of 3 numbers, one of the numbers will have to be the addition of all 3 numbers. Since, this addition should not be greater than 10, that gives us the limits on how long can we iterate.
Hence, no list of the 3 numbers can contain 10, 9 and 8. Thus, the possible range is 1 - 7.
Parent String: 3, 2, 1 Result String: 5, 3, 4, 6
Parent String: 4, 2, 1 Result String: 6, 3, 5, 7
Parent String: 5, 2, 1 Result String: 7, 3, 6, 8
Parent String: 6, 2, 1 Result String: 8, 3, 7, 9
Parent String: 7, 2, 1 Result String: 9, 3, 8, 10
Parent String: 4, 3, 1 Result String: 7, 4, 5, 8
Parent String: 5, 3, 1 Result String: 8, 4, 6, 9
Parent String: 6, 3, 1 Result String: 9, 4, 7, 10
Parent String: 5, 4, 1 Result String: 9, 5, 6, 10
Parent String: 4, 3, 2 Result String: 7, 5, 6, 9
Parent String: 5, 3, 2 Result String: 8, 5, 7, 10
1 has subsets {{1}}
4 has subsets {{1,3}, {4}}
2 has subsets {{2}}
8 has subsets {{1,2,5},{1,3,4},{1,7},{2,6},{3,5},{8}}
So there should be a set {x,y,z} where at least one subset will be found for each 1, 2, 4 and 8.
But it is evident that the only subsets available for 1 and 2 are {1} and {2}. So {x,y,z} may be written as {1,2,z}.
So to satisfy 8 it may be either {1,2,5} or {1,2,8}. But this does not satisfy 4.
So no solution is possible.
Please follow my post on 23rd July 2012
2 has subsets as {{2}}
3 has subsets as {{1,2},{3}}
4 has subsets {{1,3}, {4}}
8 has subsets {{1,2,5},{1,3,4},{1,7},{2,6},{3,5},{8}}
So there should be a set {x,y,z} where at least one subset will be found for each 2, 3, 4 and 8.
As there is 2 as one of the numbers it is evident that the set must be {2,y,z}
As there is 3 as one of the numbers the set must be one amongst the below
{2,1,z} or {2,3,z}
As there is 4 as one of the numbers the set now must be either {2,1,4} or {2,3,1}
But as there is 8, none of the above 2 sets satisfy it because we cannot find a summation which is 8.
So there is no solution
1. take all numbers and do a bitwise OR on all.
2. No of 1's binary value of the result is the number of items in the output
3. If the resultant binary is 1100011, the output will be 2^0,2^1,2^5,2^6
I think that will do
Solution will be :-
1)we will obtain all the sets of 3 no.s using combinations of the 4 no.s .which is like generating all the subsets of a given set subjected to size 3 ;
2)we can limit the above generated nos. using dynamic programming .(like sum of all the elements generated should be greater than the largest no in the given set );
3)and the rest is like change making problem in which we will assume change to be generated as each element of set A, using the set generated by permutation.
which involves using recursion and when we get a possible solution we will output it
else no solution is possible;
it's just a case of binary conversion.
- Arpit Gupta July 21, 20121. find largest element in list A (assume N is largest)
2. Y = (floor) log N (over base 2)
3. ans is 1,2,4,8... upto 2^y