## Facebook Interview Question for Software Engineers

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

Idea is to create trie of binary representation if all given numbers. Now for each number in set traverse trie

``````for (a : set){
for(bit in binary(a)) {
if(bit == 0) {
// traverse all nodes in current root( since 0 & x = 0)
} else {
// traverse only nodes with value 1
}
// if found such a number add to result (please also note a&a = a excldue this result)
}
}``````

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

There are C(k, b) numbers with b bits set to 0. So we will traverse 2^b * C(k, b) for each b in range [0, 16]
It is known that sum b=0 to b=16 (2^b * C(k, b)) is 3^k.
log(3)/log(2) < 2
So this algorithm is faster than (2^k)^2, it is ~ (2^k)^(1.58496).

Though I wonder, if there are algorithms that work faster than this, than don't enumerate all pairs

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

"traverse all nodes in current root( since 0 & x = 0) " Where does x come from. Do we need to loop through all possible values for x?

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

what's a solution faster than O(n^2)?

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

yo supa how's troopa ?

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

I don't know whether this is correct:
For a pair (a, b) that fulfill a & b == a: the following must hold:
a0 & b0 == a0, a0 & b1 == a1, a1 & b1 == a1.
So for all pairs of (a, b) in 2^k - 1, we have (a0, b0), (a0, b1), (a1, b1) in 2^(k+1) - 1.
k = 0: 0
k = 1: (0, 1): 1
k = 2: (0, 1), (00, 10), (00, 11), (01, 11): 1 + 3
k = 3: 1 + 3 + 3^2
...
So for k, the total count is: 3^0 + 3^1 + ... + 3^k-1 = (3^k-1)/2

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

If you meant "total number of pairs in {0, ..., 2^k - 1} then it is 3^n - 2^n. You were close: each bit in pair (a, b) where a & b = a could be in 3 states: 0 in both a b, 1 in both a b, 0 in a and 1 in b. So total number of pairs is 3^n. But we also counted pairs where both numbers are equal. There are 2^n of such numbers, subtract them. And answer is 3^n - 2 ^ n (or in terms of question: 3^k - 2^k)

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

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

I think I've found an O((k^2)*(2^k)) algorithm, with keeping k sets for each digit of binary representations of integers. Afterall, in order to achieve (a & b == a), b must have 1's in every digit a has a 1. This solution is not space efficient but then again, considering k <= 16, extra space complexity shouldn't be an issue.
Here's the java code :

``````public int findPairs(int k) {
Set<Integer> all_ints = new HashSet<Integer>();
List<Set<Integer>> digits = new ArrayList<Set<Integer>>();
initSets(k, all_ints, digits);

int count = 0;
for (int i = 0; i < Math.pow(2, k) - 1; i++) {
Set<Integer> intersection = new HashSet<Integer>(all_ints);

for (int j = 0; j < digits.size(); j++) {
if (digits.get(j).contains(i))
intersection.retainAll(digits.get(j));
}
count += intersection.size();
}

return count;
}

private void initSets(int k, Set<Integer> all_ints, List<Set<Integer>> digits) {
for (int i = 0; i < k; i++)

for (int i = 0; i < Math.pow(2, k) - 1; i++) {
String bin = Integer.toBinaryString(i);
int length = bin.length();

for (int j = 1; j <= digits.size(); j++) {
if (length >= j && bin.charAt(length - j) == '1')
}
}
}``````

retainAll method = O(k), iterating over digits = O(k), iterating over all numbers ~ 2^k;
Overall time complexity = O((k^2)*(2^k)).

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

If I understood correctly, for each bit set in i you are retaining only elements with this bit set.
I'm afraid, time complexity is O((2^k)^2) here since size of digits[j] is 2^(k-1) since digits[j] contains all numbers from 0 to 2^k - 1 for which j-th bit is set.

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

Please notice that there is no looping through the digits[j] at any point, the inner loop only loops through the list which is a list of sets that are size 2^(k-1) but the list is only of the size k since there are k digits. The only point this code goes into the set of size 2^(k-1) is when the get method is called however get in an ArrayList runs in O(1).

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

What is the size of digits.get(0) ? For every integer we will be doing intersection.retainAll(digits.get(0))
And if I understand correctly, digits.get(0) is of size 32768

``````>>> print sum(1 for i in xrange(2 ** 16) if i & 1)
32768``````

Or I'm missing something very important...

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

Yes, you're right I miscalculated there. Thank you for pointing that out.

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

public static Integer returnCount(Set<Integer> s) {
Integer count = 0;
Integer previous = -1;
for (Integer next : s) {
System.out.println(next);
if (previous >= 0) {
if ((previous & next) == previous)
count++;
}
previous = next;
}
return count;
}

public static Set<Integer> returnSubSet(Integer k) {
Set<Integer> s = new HashSet<Integer>();
for (int i = 0; i < Math.pow(2, k); i++) {
}
return s;
}

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

1. We know that we are given a complete set. i.e. from all 0s to all 1s for a given k. Assume 2^k -1 = N. Also we don't need to enumerate all the pairs.
2. For each number, it contains a 0 or 1 in some combination.
3. Now we observe that there are k total arrangements for a number in N, that contains only one binary 1. Then there are (k*k-1)/2 for 2 1s, k*k-1*k-2/6 for 3 1s. etc.
4. For each of those pairs, with x 1s digits, we have (k-1) 0 digits, each of those could be 1s or 0s, and we don't care about those digits. Therefore, (k-x)^2 -1 is the number of unique pairs a number with x 1 bits is going to make.
5. Simply multiply the above term with the number of digits, and you'd get the total number of pairs.

So it would take O(k) time. But I am quite certain if we expand this further we may be able to do it in constant time.

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

>We know that we are given a complete set
In this case answer is 3^k - 2^k
But we are given some subset of set {0, 1, ... 2^k - 1}, not the complete set.

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

1. We know that we are given a complete set. i.e. from all 0s to all 1s for a given k. Assume 2^k -1 = N. Also we don't need to enumerate all the pairs.
2. For each number, it contains a 0 or 1 in some combination.
3. Now we observe that there are k total arrangements for a number in N, that contains only one binary 1. Then there are (k*k-1)/2 for 2 1s, k*k-1*k-2/6 for 3 1s. etc.
4. For each of those pairs, with x 1s digits, we have (k-1) 0 digits, each of those could be 1s or 0s, and we don't care about those digits. Therefore, (k-x)^2 -1 is the number of unique pairs a number with x 1 bits is going to make.
5. Simply multiply the above term with the number of digits, and you'd get the total number of pairs.

So it would take O(k) time. But I am quite certain if we expand this further we may be able to do it in constant time.

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

If interviewer says that "Do it faster than O(N^2), N= 2^K", then I feel that he is giving me a clue, do not think too hard to come up with a O(N) solution, just an algorithm that does not involve comparing each pair will satisfy him.

Hence I am thinking in the following lines

Lets assume there is a function that gives us next higher possible value that satisfies the condition i.e., a> b and a & b == a, then we can write code like

``````for (all 'a' s in the given set)
{
int i=0;
while ( b < maxValueoftheSet)
{
b= Give_me_i_th_next_of(a)
if ( b is part of the set )
print (a, b);
}
}``````

For the part of "b is part of given set" , can be done in O(1) many ways , provided that we have enough space , for eg: hash table(std::map)

Now coming to the main part implementation of Give_me_i_th_next_of(a) in O(1)

1) Lets say you identified number of '0's in the binary representation and lets assume
lets say K=8 and a= 10100110=> 7th, 5th, 4th, 1st bits are '0's.
changing these four bits (7th, 5th, 4th and 1st) to
0001 will give 1st next value,
0010 will give 2nd next value
0011 will give 3rd next value
.....
1111 will give me 15th next value.

We can implement Give_me_i_th_next_of(a) in O(1) and while loop will repeat for
2 ^ (number of zero bits)

lets assume avg number of zero bits in all the numbers is z which will be < k

Order of the algorithm : ( 2 ^ k ) * ( 2 ^ z) which is less ( 2 ^ K) * ( 2 ^ K )

Please let me know if you have any opinions on this algorithm.

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

yes, this looks ok, see @kbrajesh176 answer and my reply to it. (you explicitly enumerate next numbers and he uses tries to find the set of all "next")

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

In my case, the number of comparisons between the set members are zero. But ofcourse the time penalty is somewhere else (finding out next value), hence the time complexity is almost same.

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

I got a complexity O(2^k) algorithm but saw your comment about how it should actually be faster than O(size ^ 2) which it can't do, so depending on the exact complexity requirement this might or might not work.

The idea is to first insert all the numbers we're given to a hash set. Then, we start with 2^k - 1 as the number (that is, all bit are 1) and do a DFS over all possible combinations of the bits (a total of 2^k combinations). While doing the DFS, we keep a counter. Each time we encounter a number which is in the set while doing the DFS, we add the value of the counter to the total and increment a counter by one. Each time we exit a number in the set, we decrease the counter by one.

You could argue it's actually O(k*2^k) since calculating the hash takes O(k) but we could also replace the hash with a simple boolean vector.

I like your problems, they're always interesting and challenging, though I still doubt these are actually from FB/Google interviews since in my experience they tend to ask somewhat easier questions, at least onsite :)

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

O((2^k)log(2^k)) solution.
1. create map of <Integer, List<Integer>> which maintains list of integers where i'th bit is 1.
2. for each value v in lists : find intersect of lists from map where bits are set as 1 in v. this interest -1 is the number of elements which are > v and v&(any integer in list) = v

``````public class Main {

static Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
static int k = 4, n = 10;
static Set<Integer> list = new HashSet<Integer>();
static List<Integer> list2 = new ArrayList<Integer>();

public static void main(String s[]){
Random random = new Random(System.currentTimeMillis());
//random.nextInt(1>>k);
for(int i = 0;i<n;i++){
}
Collections.sort(list2);
for(Integer v : list2){
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);

if(l == null){
l = new HashSet<Integer>();
}
map.put(i, l);
}
}
}
int sum = 0;
for(Integer v : list2){
Set<Integer> set = new HashSet<Integer>();
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);
set.retainAll(l);
}
}
if(set.size() >= 1){
sum += set.size()-1;
}
}
System.out.println(sum);
}
}``````

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

``````public class Main {

static Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
static int k = 4, n = 10;
static Set<Integer> list = new HashSet<Integer>();
static List<Integer> list2 = new ArrayList<Integer>();

public static void main(String s[]){
Random random = new Random(System.currentTimeMillis());
//random.nextInt(1>>k);
for(int i = 0;i<n;i++){
}
Collections.sort(list2);
for(Integer v : list2){
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);

if(l == null){
l = new HashSet<Integer>();
}
map.put(i, l);
}
}
}
int sum = 0;
for(Integer v : list2){
Set<Integer> set = new HashSet<Integer>();
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);
set.retainAll(l);
}
}
if(set.size() >= 1){
sum += set.size()-1;
}
}
System.out.println(sum);
}
}``````

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

``````public class Main {

static Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
static int k = 4, n = 10;
static Set<Integer> list = new HashSet<Integer>();
static List<Integer> list2 = new ArrayList<Integer>();

public static void main(String s[]){
Random random = new Random(System.currentTimeMillis());
//random.nextInt(1>>k);
for(int i = 0;i<n;i++){
}
Collections.sort(list2);
for(Integer v : list2){
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);

if(l == null){
l = new HashSet<Integer>();
}
map.put(i, l);
}
}
}
int sum = 0;
for(Integer v : list2){
Set<Integer> set = new HashSet<Integer>();
for(int i = 0;i<k;i++){
if((v & (1<<i)) > 0){
Set<Integer> l = map.get(i);
set.retainAll(l);
}
}
if(set.size() >= 1){
sum += set.size()-1;
}
}
System.out.println(sum);
}
}``````

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

There is an O(n) solution. more accurately, O(32n) using bitwise operation.

the idea is behind a&b==a. What numbers have this characteristic?
Only those 'b' are acceptable that have exactly '1' at b[i] when a[i]=1. So, the rest of the bits can be either 1 or 0. If the rest of bits are all zero, then b is equal a (which is not acceptable). if any other bit is '1', then b will be greater than a.
Here is the algorithm:

``````int result = 0;
for( int d : array){
int noOfOnes = countOnes(d);
result+= Math.power(2, k- noOfOnes)-1; // reduce by one since a==b is not acceptable.
}
print(result);``````

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

Signma(i = 1 to k) (nCi * 2^i)

Time complexity O(k^2)
Space complexity O(k^2)

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

Since S is { 0, 1, 2, ..., ( (2^k) - 1 ) } the way i understand the questions is,

if k is 2 then S is { 0, 1, 2, 3 }
if k is 3 then S is { 0, 1, 2, 3, 4, 5, 6, 7 }

Observations:
(1) Set S contains 2^k integers
(2) k bits required to represent the last number
(3) there are k distinct numbers in set S where all the least significant bits are 1's. For example, when k=3, they are 1(001), 3 (011), 7 (111)
(4) numbers listed in observation (3) will be of the form (2^i) -1 where 1 <= i <= k
(5) there will be (2^i)-1 numbers in S that are less than the number (2^i)-1 mentioned in observation (4). For example, for i = 2 the numbers will be 0, 1, and 2.

To satisfy the first condition, which is a < b, for any given number b in S we need to look all the numbers a that are less than it. In other words number of bits used to represent a will be less than or equal to b. For example if b is 3, then we need to look at combinations (0,1), (0,2), (0,3), (1,2), (1,3), (2,3).

To satisfy second condition, which is (a AND b) == a, b should be all 1's. This is because 0 AND 1 is 0. 1 AND 1 is 1. So ANDing with 1 will retain whatever the other bit is. From observation (3) we see that there are k such numbers in S. The possibilities for number b can be any of these k numbers. The possibility for a is any number that is less than b. That is for k = 3, b can be either 1, 3, 7. The corresponding a’s have to be less that, making the complete set as below -

Possibilities when b = 1 are (0, 1)
Possibilities when b = 3 are (0, 3) (1, 3) (2, 3)
Possibilities when b = 7 are (0, 7) (1, 7) (2, 7) (3, 7) (4, 7) (5, 7) (6, 7)

Based on observation (5),
Possibilities when b = 1 are 1
Possibilities when b = 3 are 3
Possibilities when b = 7 are 7
Possibilities when b = (2^k)-1 are (2^k)-1

Adding them all together we get a series like
1 + 3 + 7 + … + ((2^k) - 1)
i.e. ((2^1) - 1) + ((2^2) - 1) + ((2^3) - 1) + … + ((2^k) - 1)
i.e. (2^1) + (2^2) + (2^3) + (2^k) - k { geometric series }
i.e. (2^(k+1)) - 3 - k

To summarize, we can say that for a given k (where k > 0) and S of the form { 0, 1, 2, 3, … , ( (2^k) - 1 ) } the number of pairs a, b that satisfy the conditions a < b ; ( a AND b ) == b will be (2^(k+1)) - 2 - k

Lets verify for few :
k = 3 : 11 : (0, 1), (0, 3) (1, 3) (2, 3), (0, 7) (1, 7) (2, 7) (3, 7) (4, 7) (5, 7) (6, 7)
k = 2 : 4 : (0, 1), (0, 3) (1, 3) (2, 3)
k = 1 : 1 : (0, 1)

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

Wouldn't the first example with k = 3 be missing (1,5)? I think the following assumption you are making is not correct: "To satisfy second condition, which is (a AND b) == a, b should be all 1's." If a = 1 (001) and b = 5 (101), a & b = 1 (001) so it should be included in the solution.

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

The question is saying that given S is *subset* of a set of {0,1,2... 2^k-1} for some k.

So if k = 2, S is a *subset* of {0,1,2,3}

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

Carlos, I think you are right. That assumption does not hold true.

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

what about a=001 and b=101 where a&b = 001 =>a

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

The solution as posted above sum_{i = 1}^k (combinations(k, i) * 2^i).
Let n be in S.
Then i represents the number of set bits in n, and combinations(k, i) represents how many ways there are to arrange i set bits (that is, how many such n exist). 2^i is the number of subsets of i (that is, the number of m < n s.t. m & n == m).

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

Struggling to find a < O(n^2) (where n = 2^k) solution. If someone has one, could you please post a hint?

FWIW it does not seem like storing nums in S in a trie improves runtime, since querying the trie would take the same O(n) per number worst case (when number is all 1-bits and thus both subtrees of a trie have to be explored)...

Thanks!

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

``nlog(n) solution  where n =2^k``

``````solve(S'):
if Sizeof(S') == 1:
return 0
x = smallest_element(S')
for every element e in S' (other than x):
if(x&e == x):
else:
ans = size_of(S1)+solve(S1)+solve(S2)
return ans
end Solve

main program:
print Solve(S) //where S is the given input set``````

Explaination:
for the smallest member of a set we get all those elements that hold true(x&e==x) and put in set S1, and put those which hold false in S2. Sizeof(S1) are the matches for x.
Now we recursively call same function on S1 and S2 because we know that no member of S1 can pair up with a member of S2 and vice versa.

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

Sadly, this would not give the correct answer. Here is an example:
we are given three numbers: {2,5,7}
we know that 2 & 7 = 2 and 5 & 7 = 5 so the answer should be 2.

However, using the approach you described, 2 will be chosen as the smallest element and 7 is added to S1 and 5 is added to S2. Now, during the recursive call, these belong to different sets and hence 5 and 7 would never be checked.
Which gives us the wrong answer. :(

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

Can be solved in O(k(2^k)). a & b == a for any b such that all the bits set in 'a' are also set in 'b'. For each bit set in 'a' find values in range [0,2^k-1] other than 'a' itself will result in 'a' if done a bitwise '&' operation. Then add this sets of values into a Hash table keyed by such single set bit values (there should be 16 such keys when k=16).

Ex:-

``{1: set([3, 5, 7]), 2: set([3, 6, 7]), 4: set([5, 6, 7])}``

For each value in given input array find the intersect of values in above mentioned Hash table. For instance value 3 has following bits set 010, 001. So the intersect would be {3,7}. These are the possible b values, now if both of these values are in input array and greater than 3 (because these are the possible b values) increment the pair counter by two, if only one then by 1 etc.

It take O(k(2^k)) to prepare the Hash table. To process the input array it takes O(k(2^k))

``````def prep(k):
if k > 16:
return None

D = {}
maxnum = (1 << k) - 1
for i in range(0, maxnum + 1):
for j in range(0, k):
if i & mask == i:
continue
if i & mask > 0:
else:
return D

def count_sat_pairs(A, D, k):
count = 0
s = set()
for a in A:
for i in range(0, k+1):
if mask & a > 0:
if len(s) == 0:
s = s.union(tmp)
else:
s = s.intersection(tmp)
for v in s:
if v > a and v in A:
count += 1
s = set()
return count``````

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

``````function addToTrie(trie, entry) {
if(!entry) return;
var i, node = trie, parent;
for(i =0; i < entry.length && node; i++) {
parent = node;
node = parent[entry[i]];
}
if(i === entry.length || !parent) {
return;
}
i--;
for(; i < entry.length; i++) {
parent = parent[entry[i]] = {};
}
parent.isLeaf = true;
}

function getTrieCount(trie, entry, index, isExactMatch) {
var value, node = trie;
if(index >= entry.length && trie) {
return (isExactMatch ? 0 : 1);
}
if(!trie) {
return 0;
}
index = index || 0;
value = entry[index];
// if value is zero, find in all sub-tries, otherwise exact match is required
if(value !== '0') {
if(trie[value]) {
return getTrieCount(trie[value], entry, index + 1, isExactMatch);
} else {
return false;
}
}
// look into all sub children;
var key, count = 0;
for(key in trie) {
count += getTrieCount(trie[key], entry, index + 1, (isExactMatch && key === '0'));
}
return count;
}

function buildTrie(entryList) {
var trie = {};
var i, entry;
for( i = 0; i < entryList.length; i++) {
entry = entryList[i];
}
var count =0;
for( i = 0; i < entryList.length; i++) {
entry = entryList[i];
count += getTrieCount(trie, entry, 0, true);
}
return count;
}
console.log(buildTrie(['0b111', '0b101', '0b010']));``````

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

A solution leveraging a Trie DS

``````struct TrieNode
{
int V;
TrieNode *Children;

TrieNode()
{
Children = Children = NULL;
}

TrieNode(int i)
:
V(i)
{
Children = Children = NULL;
}

} *Root = new TrieNode;

{
for (int i = 31; i >= 0; i--)
{
if (R->Children[(N & (1 << i)) != 0] == NULL)
{
R->Children[(N & (1 << i)) != 0] = new TrieNode((N & (1 << i)) != 0);
}

R = R->Children[(N & (1 << i)) != 0];
}
}

int Count(TrieNode *Root, int Num, int K)
{
if (Root == NULL)
{
return (0);
}

if (K == 0)
{
if ((Num & 1) == 1)
{
return (1);
}

return ((Root->V) & 1) == 0;
}

int Res = 0;

if ((Num & (1 << K)) != 0)
{
if (Root->Children != NULL)
{
Res = Count(Root->Children, Num, K - 1);
}

if (Root->Children != NULL)
{
Res += Count(Root->Children, Num, K - 1);
}
}
else if (Root->Children != NULL)
{
Res = Count(Root->Children, Num, K - 1);
}

return (Res);
}

int CountAnds(vector<int> S)
{
if (S.empty())
{
return (0);
}

sort(S.begin(), S.end());

int Res = 0;

for (auto &n : S)
{
Res += Count(Root, n, 31);
}

return (Res);
}``````

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

This solution is O(k):

``````private static int countOfPairsWhereAndAndBAreFromSAnAgtBAndAandBisA(int k) {
int count = 0;
for (int numberOfSetBits =0; numberOfSetBits < k; numberOfSetBits++) {
final int combinationsWithThisNumberOfSetBits = combinations(k, numberOfSetBits);
final int countOfPairs = (int)Math.pow(2, k-numberOfSetBits) - 1;
count += countOfPairs * combinationsWithThisNumberOfSetBits;
}
return count;
}

private static int combinations(int n, int r) {
return factorial(n) / (factorial(r) * factorial(n - r));
}

private static int factorial(int n) {
int f = 1;
for (int i = 2; i <= n; i++) f *= i;
return f;
}``````

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

c#.
O(2^k).

``````static private int Get( int k ) {

int res = 0;

for ( int i = 1; i <= Math.Pow( 2, k ) - 1; i++ ) {

string bin = Convert.ToString( i, 2 );
int cnt = 0;
foreach ( var ch in bin ) {
if ( ch == '0' ) {
cnt++;
}
}
res += (int)Math.Pow( 2, cnt ) - 1;
}
return res + (int)Math.Pow(2, k) - 1;
}``````

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

Read once more please. You are given a subset S of set {0, 1, ..., 2^k - 1}, not just an integer k.

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

sorry, got to understand your notice, let me to correct.

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

in fact, the idea is the same, the only difference is that the for loop will be in bounds of given subset and ret value without compulsory pairs of "0".
And in loop the will be restriction not to exceed the boundaries of subset, while calculating combinations.

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

no, this won't work since you won't know how much would you add to res on each iteration. subset is not contiguous also, it may be 1, 3, 5, 10 for example.

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

then clarify the task, it's unclear.
If we are given subset {1, 3, 5, 10 }, why than we need k ?

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

if we are given {1, 3, 5, 10 } and k = 16, then brute force will be faster than O((2^k)^2). It will be O(n*n), where n = 4.
In case of given subset time complexity does not depend on k.
It depends on the length of array.

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

Yes, the question could be reformulated - there is no k, you are given a array of unique uint16_t of size <= 65536 and you need to find count of pairs from the top question faster than in O(size ^ 2)

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.