Facebook Interview Question for Software Engineers


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)
}
}

Please share your thoughts on this in reply to this answer.

- kbrajesh176 December 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- emb December 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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?

- bigflagellum December 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- supatroopa December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

yo supa how's troopa ?

- gen-x-s December 15, 2015 | Flag
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

- Richard December 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- emb December 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh s/n/k/g in previous reply

- emb December 14, 2015 | Flag
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++)
            digits.add(new HashSet<Integer>());

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

            all_ints.add(i);

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

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

- clekili December 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- emb December 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- clekili December 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- emb December 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- clekili December 14, 2015 | Flag
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++) {
s.add(i);
}
return s;
}

- Arun Kumar December 15, 2015 | Flag Reply
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.

- Joshi of Vatsa December 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- emb December 20, 2015 | Flag
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.

- Joshi of Vatsa December 15, 2015 | Flag Reply
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.

- venkatesh.duggirala December 20, 2015 | Flag Reply
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")

- emb December 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- venkatesh.duggirala December 21, 2015 | Flag
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 :)

- Anonymous December 22, 2015 | Flag Reply
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++){
            list.add(random.nextInt(1<<k));
        }
        list2.addAll(list);
        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>();
                    }
                    l.add(v);
                    map.put(i, l);
                }
            }
        }
        int sum = 0;
        for(Integer v : list2){
            Set<Integer> set = new HashSet<Integer>();
            set.addAll(list2);
            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);
    }
}

- Anonymous December 24, 2015 | Flag Reply
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++){
            list.add(random.nextInt(1<<k));
        }
        list2.addAll(list);
        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>();
                    }
                    l.add(v);
                    map.put(i, l);
                }
            }
        }
        int sum = 0;
        for(Integer v : list2){
            Set<Integer> set = new HashSet<Integer>();
            set.addAll(list2);
            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);
    }
}

- Anonymous December 24, 2015 | Flag Reply
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++){
            list.add(random.nextInt(1<<k));
        }
        list2.addAll(list);
        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>();
                    }
                    l.add(v);
                    map.put(i, l);
                }
            }
        }
        int sum = 0;
        for(Integer v : list2){
            Set<Integer> set = new HashSet<Integer>();
            set.addAll(list2);
            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);
    }
}

- Paras December 24, 2015 | Flag Reply
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);

- mehraz December 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer is

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

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

- Virupaksha Swamy January 06, 2016 | Flag Reply
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)

- Sean January 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- carlos January 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- dukehoops February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 03, 2016 | Flag
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

- anonymous January 16, 2016 | Flag Reply
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).

- anon January 27, 2016 | Flag Reply
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!

- dukehoops February 01, 2016 | Flag Reply
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):
			add e to S1
		else:
			add e to S2
	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.

- siddharth.bhadkamkar February 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pujun February 18, 2016 | Flag
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):
            mask = 1 << j
            if i & mask == i:
                continue
            if i & mask > 0:
                if D.has_key(i & mask):
                    D[i & mask].add(i)
                else:
                    D[i & mask] = set()
                    D[i & mask].add(i)
    return D



def count_sat_pairs(A, D, k):
    count = 0
    s = set()
    for a in A:
        for i in range(0, k+1):
            mask = 1 << i
            if mask & a > 0:
                tmp = D[mask & a]
                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

- fox July 11, 2016 | Flag Reply
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];
    addToTrie(trie, entry);
  }
  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']));

- Takhti October 01, 2016 | Flag Reply
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[2];

	TrieNode()
	{
		Children[0] = Children[1] = NULL;
	}

	TrieNode(int i)
		:
		V(i)
	{
		Children[0] = Children[1] = NULL;
	}

} *Root = new TrieNode;

void Add(TrieNode *R, int N)
{
	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[0] != NULL)
		{
			Res = Count(Root->Children[0], Num, K - 1);
		}

		if (Root->Children[1] != NULL)
		{
			Res += Count(Root->Children[1], Num, K - 1);
		}
	}
	else if (Root->Children[0] != NULL)
	{
		Res = Count(Root->Children[0], 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);
		Add(Root, n);
	}

	return (Res);
}

- Guy November 21, 2016 | Flag Reply
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;
    }

- Lucidio August 10, 2017 | Flag Reply
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;
}

- zr.roman December 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- emb December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zr.roman December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zr.roman December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- emb December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zr.roman December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zr.roman December 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- emb December 13, 2015 | Flag


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