Bit Algorithm - How to Succeed in Algorithms Interview Series
Bit String
Write a function to generate the generalized abbreviations of a word.
Example:
Given "word"
Return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
private String abbr(String word, int x) {
StringBuilder builder = new StringBuilder();
int m = 0;
for (int i = 0; i < word.length(); ++i, x >>= 1) {
if ((x & 1) == 0) {
if (m > 0) builder.append(m);
m = 0;
builder.append(word.charAt(i));
}
m += x & 1;// change to else m++;
}
if (m > 0) builder.append(m);//\\
return builder.toString();
}
O(32N) - bit count
- Compute every bit separately, build the answer bit by bit
- count the sum of each 32 bits separately and compare the expected answer to get the result
- the result is one value: missing/redundant
- less efficient than nlgn
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Now your job is to find the total Hamming distance between all pairs of the given numbers.
- Compute every bit separately
public int totalHammingDistance(int[] nums) {
int total = 0, n = nums.length;
for (int j=0;j<32;j++) {
int bitCount = 0;
for (int i=0;i<n;i++)
bitCount += (nums[i] >> j) & 1;
total += bitCount*(n - bitCount);
}
return total;
}
int maxAND (int arr[], int n)
{
int res = 0, count;
// iterate over total of 30bits from msb to lsb
for (int bit = 31; bit >= 0; bit--)
{
// find the count of element having set msb
count = checkBit(res | (1 << bit), arr, n); // key: res | (1 << bit
// if count >= 2 set particular bit in result
if ( count >= 2 )
res |= (1 << bit);
}
return res;
}
- Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
- 32n
- ones, twos, threes
public int singleNumber(int[] nums) {
int ans = 0;
for(int i = 0; i < 32; i++) {
int sum = 0;
for(int j = 0; j < nums.length; j++) {
if(((nums[j] >> i) & 1) == 1) {
sum++;
sum %= 3;
}
}
if(sum != 0) {
ans |= sum << i;
}
}
return ans;
}
public int majorityElement(int[] num) {
int ret = 0;
for (int i = 0; i < 32; i++) {
int ones = 0, zeros = 0;
for (int j = 0; j < num.length; j++) {
if ((num[j] & (1 << i)) != 0) {
++ones;
}
else
++zeros;
}
if (ones > zeros)
ret |= (1 << i);
}
return ret;
}
public int findDuplicate(int[] nums) {
int n = nums.length-1, res = 0;
for (int p = 0; p < 32; ++ p) {
int bit = (1 << p), a = 0, b = 0;
for (int i = 0; i <= n; ++ i) {
if (i > 0 && (i & bit) > 0) ++a;
if ((nums[i] & bit) > 0) ++b;
}
if (b > a) res += bit;
}
return res;
}
- limited set: power of 2
- normalized: when order doesn’t matter: sort or count array/map
public boolean reorderedPowerOf2(int N) {
char[] a1 = String.valueOf(N).toCharArray();
Arrays.sort(a1);
String s1 = new String(a1);
for (int i = 0; i < 31; i++) {
char[] a2 = String.valueOf((int)(1 << i)).toCharArray();
Arrays.sort(a2);
String s2 = new String(a2);
if (s1.equals(s2)) return true;
}
return false;
}
Bit Trie
- prefix xor, xor[i,j]=prefix-xor[i]^prefix-xor[j]
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
// search from left to right, find out for each bit is there
// two numbers that has different value
for(int i = 31; i >= 0; i--){
// mask contains the bits considered so far
mask = mask | (1 << i);
Set<Integer> set = new HashSet<>();
// store prefix of all number with right i bits discarded
for(int num : nums){
set.add(num & mask);// reserve Left bits and ignore Right bits
}
// now find out if there are two prefix with different i-th bit
// if there is, the new max should be current max with one 1 bit at i-th position, which is candidate
// and the two prefix, say A and B, satisfies:
// A ^ B = candidate
// so we also have A ^ candidate = B or B ^ candidate = A
// thus we can use this method to find out if such A and B exists in the set
int tmp = max | (1 << i); //in each iteration, there are pair(s) whoes Left bits can XOR to max
for(int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
}
return max;
}
Prefix Xors
Use bit to store info
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
Example:
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
public List<String> findRepeatedDnaSequences(String s) {
Set<Integer> words = new HashSet<>();
Set<Integer> doubleWords = new HashSet<>();
List<String> rv = new ArrayList<>();
char[] map = new char[26];
//map['A' - 'A'] = 0;
map['C' - 'A'] = 1;
map['G' - 'A'] = 2;
map['T' - 'A'] = 3;
for(int i = 0; i < s.length() - 9; i++) {
int v = 0;
for(int j = i; j < i + 10; j++) {
v <<= 2;
v |= map[s.charAt(j) - 'A'];
}
if(!words.add(v) && doubleWords.add(v)) {
rv.add(s.substring(i, i + 10));
}
}
return rv;
}
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
public static int maxProduct(String[] words) {
if (words == null || words.length == 0)
return 0;
int len = words.length;
int[] value = new int[len];
for (int i = 0; i < len; i++) {
String tmp = words[i];
value[i] = 0;
for (int j = 0; j < tmp.length(); j++) {
value[i] |= 1 << (tmp.charAt(j) - 'a');
}
}
int maxProduct = 0;
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++) {
if ((value[i] & value[j]) == 0 && (words[i].length() * words[j].length() > maxProduct))
maxProduct = words[i].length() * words[j].length();
}
return maxProduct;
}
Bit tricks
