## ThoughtWorks Interview Question for Interns

Country: India
Interview Type: In-Person

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

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,8... upto 2^y

Comment hidden because of low score. Click to expand.
0

When N>=8 there will be more than 3 elements in list B.

Comment hidden because of low score. Click to expand.
0

consider this input:
1,4,8,64,65,97,125

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

Comment hidden because of low score. Click to expand.
0

consider this input:
1,4,8,64,65,97,125

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.

Comment hidden because of low score. Click to expand.
0

@Balamurugan:

Comment hidden because of low score. Click to expand.
0

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

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

what if input is 1 5 7 9?

Comment hidden because of low score. Click to expand.
0

2,3,4 and other too.

Comment hidden because of low score. Click to expand.
0

how do we get 1 den??

Comment hidden because of low score. Click to expand.
0

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?

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

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

Comment hidden because of low score. Click to expand.
0

input 2 4 6 7
ouput:

Results are: 1 2 4
Results are: 2 3 4
Results are: 2 4 5

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

if there is element a,b,c,d such that
a+b=d or a+b+c=d then u are done remove d from clone of A, first one is of n^2 and 2nd one is O(n).
.
.

what if Input : 1 2 4 8/9/10

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

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

Comment hidden because of low score. Click to expand.
0

logic??

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

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

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

ex:- 2 4 5 9
write first two no.s as it is
ie 2 4
then
then third no will be
either 9-first no.=4
or 9-second no.=5
or 9-third no.=7
in this case it will be 9-4=5
ie B list will contain 2 4 5

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

``````List<Integer> sortedArr = new ArrayList<Integer>();
List<String> resultList = new ArrayList<String>();
for(int i = 1; i < 11; 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) {
+" 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));
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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

what if the input is 1,4,2,8????

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

solution is 1,2,4,8.. there is no better solution

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

what about 2 3 4 8

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

we can consider 1 2 4 8 also

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

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

Comment hidden because of low score. Click to expand.
0

hey can you suggest code for the same in C?
thanks for the approach.

Comment hidden because of low score. Click to expand.
0

can you suggest code for the same in C.

thanks for the approach.

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

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;

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

How about prime factor of each input and then keep unique prime factor in second list and that should do it ... what you say ?

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

1 Sort the array
2 substraction smallest from second smallest and so on. Add difference to the new list. If the smallest number is smaller than the smallest number in the new list then add it.
3 print the list

Comment hidden because of low score. Click to expand.

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.

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