TCS CodeVita Interview Question

Country: United States

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

#include<stdio.h>
2
3 void two_1s_no_generator(unsigned int num)
4
5 {
6 int count=0,bol_val;
7
8 int i,j;
9
11
12 for(j=1;j<=num;j++)
13
14 {
16 count=0;
17
18 for(i=1;i<=32;i++)
19
20 {
22
23 if(bol_val==1)
24 count++;
25
27
28
29 }
30
31 if(count == 2)
32 {
33 printf("%d ",j);
34
35 }
36 }
37 printf("\n\n");
38 }
39 int main()
40
41 {
42 unsigned int num;
43
44 printf("Enter the Range :");
45
46 scanf("%d",&num);
47
48 two_1s_no_generator(num);
49
50 }

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

You know, there is C(n, 2) such n-bit integers, so with N ~ 10^14 output value can be order of 2^(10^7), so problem is not just about "bit manipulation".

Solution: lets look at numbers MSB. There is exactly k numbers in this sequence with MSB at position k (1 for MSB = 2^1 (3), 2 for MSB = 2^2 (5,6) and so on). Inside of this blocks of increasingly larger sizes, LSB goes from 0 to k-1.
So, formal solution is following:
- define k = min x : x*(x+1)/2 >= N
- define p = k*(k+1)/2 - N
Answer is 2^k + 2^(k - p - 1).

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

``````#include<stdio.h>
2
3 int print_two_ones_no(int x)
4
5 {
6
7     int count=0;
8
9     int num = x;
10
11     while(x)
12
13     {
14         x = x&(x-1);
15
16             count++;
17
18     }
19
20     if(count == 2)
21
22         printf("%d ",num);
23
24 }
25
26 int main()
27
28 {
29
30     int num,i;
31
32     printf("Enter the Range :");
33
34     scanf("%d",&num);
35
36     for(i=1;i<=num;i++)
37
{
39
40     print_two_ones_no(i);
41
42     }
43
44 }
17,0-1        Top``````

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

``````// NOT FOR Competitive stuff - it is meaningless for practical purposes.
// but cool...
/*
Given S is then sorted sequence of numbers such that
Binary representation contains only 2 bits set to 1.
Find S(n).
We solve it by creating an iterator.
*/
s = seq( 3 ) -> {
bs = str(\$.p[-1],2)
li = rindex(bs.value, _'1' )
if ( li == 1 ){
r = 2 ** #|bs| + 1
} else {
bs.value[li] = _'0'
bs.value[li-1] = _'1'
r = int(bs,2,0)
}
r
}
fold ( [1:9] ) -> { println( s.next ) }``````

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

``````#Consider the following sequence: 3, 5, 6, 9, 10, 12, 17, 18, 20....
#Write a function that takes n in range(1, 10**14) and returns the
#nth term of the sequence

import math

def a(n):
a = .5; b = .5; c = -n
#use the quadratic formula to find the first i s.t. n <= i*(i+1)/2
i = int(math.ceil( ( -b - math.pow( (b**2 - 4*a*c), .5 ) )/(2*a) ))
if not (0 < i and i < n):
i = int(math.ceil( ( -b + math.pow( (b**2 - 4*a*c), .5 ) )/(2*a) ) )
#sum of first i numbers
s = (i*(i+1)/2)
offset = i - (s - n) - 1
return (1 << i) + (1 << offset)

def b(n):
s = 0; i = 0
#use a loop to find the first i s.t. n <= i*(i+1)/2
#the time to find such an i will grow according like O(sqrt(n))
while True:
if s >= n:
break
else:
i += 1
s += i
offset = i - (s - n) - 1
return (1 << i) + (1 << offset)``````

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

``````import math

def how_many_bits(x):
count = 0
while x:
x = x & (x - 1)
count += 1
return count

def how_many_bit(x):
return 1 + int(math.log(x,2))

def foo(x):
top_bit = x&-x
higher_bit_set = top_bit + x

x = 3
for i in range(20):
y = foo(x)
print(y)
if how_many_bits(y) != 2:
print("something wrong", y, how_many_bits(y), bin(y))
x = y``````

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

Boils down to solving arithmetic series and bit manipulation... but tricky

``````//C#
public static int GetTwoBitSequenceValue(int sequenceNumber)
{
int bit2Position = (int) Math.Round(Math.Sqrt(sequenceNumber * 2), 0) - 1;
int bit1Position = sequenceNumber - ((int)((bit2Position * (bit2Position + 1)) / 2) + 1);

return (2 << bit2Position) | (1 << bit1Position);
}

public static void Test()
{
for (int i = 1; i < 20; i++)
{
int y = GetTwoBitSequenceValue(i);
Console.WriteLine("x {0} => y {1}",i, y);
}
}``````

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

Quite easy, solution in java in O(1) time working for any input

``````public static BigInteger getNthNumber(long n){
int a = (int)Math.floor((1 + Math.sqrt(1 + 8 * n - 8)) / 2);
int b = n - a * (a - 1) / 2 - 1;
}``````

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

public class BitWise {
public static void main(String...strings) {
int k = 2;
int currNo = 1, extra = 1, pow =1, base = (int) Math.pow(2, pow);
int seriesNo = base + extra;

while(true) {
System.out.println(seriesNo);
if(currNo == k)
break;

extra = extra << 1;
if(base == extra) {
pow++;
extra = 1;
base = (int) Math.pow(2, pow);
}
seriesNo = base + extra;
currNo++;
}
}
}

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

``````#include <stdio.h>

int main()
{
int i,j,n,k;
//n bits number
n=8;
//kth number
k=6;
int count=0;
i=1;
int allones=~0;

while(i<n)
{
for(j=0;j<i;j++)
{
count++;
//this is the number. i.e. i+1 are total number of bits with ith bit as 1 and jth bit as 1.

}
i++;
}

return 0;
}``````

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

1 #include<stdio.h>
2
3 int print_two_ones_no(int x)
4
5 {
6
7 int count=0;
8
9 int num = x;
10
11 while(x)
12
13 {
14 x = x&(x-1);
15
16 count++;
17
18 }
19
20 if(count == 2)
21
22 printf("%d ",num);
23
24 }
25
26 int main()
27
28 {
29
30 int num,i;
31
32 printf("Enter the Range :");
33
34 scanf("%d",&num);
35
36 for(i=1;i<=num;i++)
37
38 {
39
40 print_two_ones_no(i);
41
42 }
43
44 }

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

``````1 #include<stdio.h>
2
3 int print_two_ones_no(int x)
4
5 {
6
7     int count=0;
8
9     int num = x;
10
11     while(x)
12
13     {
14         x = x&(x-1);
15
16             count++;
17
18     }
19
20     if(count == 2)
21
22         printf("%d ",num);
23
24 }
25
26 int main()
27
28 {
29
30     int num,i;
31
32     printf("Enter the Range :");
33
34     scanf("%d",&num);
35
36     for(i=1;i<=num;i++)
37
38     {
39
40     print_two_ones_no(i);
41
42     }
43
44 }``````

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

O(n) solution.

``````int Next2BitsNum(int n)
{
int bit0 = 0;
int bit1 = 1;
int i;
for (i = 0; i < n; i++)
{
bit0++;
if (bit0 == bit1)
{
bit0 = 0;
bit1++;
}
}

return (1 << bit0) | (1 << bit1);
}``````

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

Some modification required???????

#include<stdio.h>
int main()
{
int N;
scanf("%d",&N);
int b,c,i;
int a[N];
a[0]=3;
int j=0;
for(i=1;i<N;i=i+2)
{
a[i]=(2*a[j])-1;
a[i+1]=2*(a[j]);
j=j+1;
}
printf("%d",a[N-1]);

}

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

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.