## ThoughtWorks Interview Question for Interns

• 0
of 0 votes

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
of 0 votes

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

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

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

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

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.

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

@Balamurugan:
Please elaborate your concept

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

@ 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
of 0 votes

2,3,4 and other too.

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

how do we get 1 den??

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

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,mark;
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;i++)
{
mark[i]=1;
for (j=i+1;j<=four_num;j++)
{
mark[j]=1;
mark[i+j]=1;
for (k=j+1;k<four_num;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
of 0 votes

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
of 0 votes

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++) {
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));
}
}``````

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

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
of 0 votes

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
of 0 votes

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
of 0 votes

Please also follow my post on July 23 2012

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

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
of 0 votes

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

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

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
of 0 votes

hey 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 votes

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.

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