Facebook Interview Question Software Engineers
Country: United States
Interview Type: In-Person
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
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
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)
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)).
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.
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).
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...
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;
}
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.
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.
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.
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")
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 :)
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);
}
}
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);
}
}
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);
}
}
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);
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)
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.
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}
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).
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!
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.
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. :(
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
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']));
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);
}
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;
}
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;
}
Read once more please. You are given a subset S of set {0, 1, ..., 2^k - 1}, not just an integer k.
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.
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.
then clarify the task, it's unclear.
If we are given subset {1, 3, 5, 10 }, why than we need k ?
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.
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