Google Interview Question Software Engineer / Developers
Country: United States
This is the way to do it. Even though the underlying representation is only binary in an abstract sense, it's totally trivial to serialize the number in binary form from the compressed representation that the OP suggests. See my Python implementation on this page for more details.
"If the Infinite binary Stream is of form 1010101010 ????"
it's not a problem, as incement operation effects digits up to the right most 0, so it will still be constant time. building this long number is done on run time. with constant time at each step
Theoretically speaking, this is not O(1), even in the WORD RAM model. (Of course, this is probably what the interviewer had in mind, and is a bad interview question, IMO).
Incrementing/decrementing counters (which you use for the run lengths) will not be O(1)...
Yep, it "stops" being O(1) as soon as the number of bits in the binary number can't be stored in a word. While not theoretically O(1), the algorithm does allow you to increment numbers up to 2 ** (2**32) very quickly, whereas a 32-bit machine only increments numbers up to 2**32 quickly.
It takes 10 times as long to increment a 10-word-long number as it does to increment a 1-word long number, which is why this algorithm is O(log(log(N)). On a 32-bit machine, you can represent the longest run of 1s in your number in a 32-bit word if the number is less than 2**(2**32). After that you need multi-words. It's rare that operations are truly O(1). Even "normal" addition is O(number of bits in the word), but for practicality sake, we we call it O(1) with the constraint that we'll never exceed our word size.
Why not just use grey code? It is designed in such a way so as to only need a single bit flip between consecutive numbers. The question never needed a constant time algorithm for reading the number, only adding.
This is not for the faint of heart. :)
# In this completely contrived problem, we represent a binary
# number as a list of runs of zeros and ones, and we minimize
# bit flipping and storage insertion/deletion by having the
# number of bits in a run represent the number of bits to
# jump in the array. Incrementing a binary number, no matter
# how large, involves only modifying up to three tuples in place
# and possibly appending a sentinel to the end of the list.
def test():
numbers = {
0: [None],
1: [(1,1), None],
2: [(1,0), (1,1), None],
3: [(2,1), None, None],
4: [(2,0), None, (1,1), None],
5: [(1,1), (1,0), (1,1), None],
6: [(1,0), (2,1), None, None],
7: [(3,1), None, None, None],
8: [(3,0), None, None, (1,1), None],
9: [(1,1), (2,0), None, (1,1), None],
10: [(1,0), (1,1), (1,0), (1,1), None],
}
for k, v in numbers.items():
assert k == to_decimal(v)
num = [None] # zero
for i in range(1024 * 128 + 5):
assert i == to_decimal(num)
incr_bin(num)
print i
print num
print to_binary(num)
print 'DONE!'
def incr_bin(num):
if num[0] is None:
# 0 -> 1
num[0] = (1, 1)
num.append(None)
return
num_bits, bit = num[0]
if bit == 0:
num_zeros = num_bits
if num_zeros == 1:
# 011 -> 111
num_ones, _ = num[1]
num[0] = (num_ones+1, 1)
else:
# 0001 -> 1001
num[0] = (1,1)
num[1] = (num_zeros-1, 0)
else:
num_ones = num_bits
if num[num_ones] is None:
# 1111 -> 00001
num[0] = (num_ones, 0)
num[num_ones] = (1,1)
# We only need to allocate storage
# when we reach a power of 2!
num.append(None)
else:
num_zeros, _ = num[num_ones]
if num_zeros == 1:
# 11101111 -> 0001111
num_higher_ones, _ = num[num_ones+1]
num[0] = (num_ones, 0)
num[num_ones] = (num_higher_ones+1, 1)
else:
# 1001xxx -> 0101xxx
num[0] = (num_ones, 0)
num[num_ones] = (1, 1)
num[num_ones+1] = (num_zeros-1, 0)
# helper function for testing
def to_decimal(num, i=0):
if num[i] is None:
return 0
result = 0
num_bits, bit = num[i]
if bit == 1:
result = 2 ** num_bits - 1
return result + (2 ** num_bits) * to_decimal(num, i+num_bits)
# another helper function
def to_binary(num):
s = ''
i = 0
while num[i]:
num_bits, bit = num[i]
s = str(bit) * num_bits + s
i += num_bits
return s
test()
The reason there's a gap in the representation for 4 (the None as the second value) is to facilitate the transformation to 5 without having to shift values. For small numbers this seems overkill, but think about incrementing b1011111001 to b1011111010. When the number of runs change, you don't want to shift over all the runs, because that would be O(N).
Java implementation.
package google;
import org.junit.Test;
import java.util.Iterator;
import java.util.LinkedList;
import static org.junit.Assert.assertEquals;
public class BinaryCounterInConstantTime {
@Test
public void test() {
Counter c = new Counter();
for (int i = 1; i < 10; i++) {
c.incr();
assertEquals(i, c.toDecimal());
}
}
public static class Counter {
// Group of repeated 0's and 1's. For example, 1101110 will be (1, 2), (0, 1), (1, 3), (0, 1).
private LinkedList<BitSeq> counter = new LinkedList<>();
public Counter() {
counter.add(new BitSeq(false, 1));
}
public void incr() {
if (counter.getLast().ones) {
// One(s) in the end -> last ones become zeros. If one zero before them it inverts and, possibly, adds to
// ones at the left of it. If several zeros, their count decrements and new single one appears.
// 0 11 -> 1 00
// 11 0 11 -> 111 00
// 11 00 11 -> 11 0 1 00
BitSeq lastOnes = counter.removeLast();
BitSeq zerosBeforeOnes = counter.getLast();
if (zerosBeforeOnes.count == 1) {
if (counter.size() == 1) {
zerosBeforeOnes.ones = true;
} else {
counter.removeLast();
counter.getLast().count++;
}
} else {
zerosBeforeOnes.count--;
counter.addLast(new BitSeq(true, 1));
}
lastOnes.ones = false;
counter.addLast(lastOnes);
} else {
// Zero(s) in the end - decrement zeros count (or delete if only one), add one "1" (possibly adding
// to ones before it).
// 0 -> 1
// 111 0 -> 1111
// 111 000 -> 111 00 1
if (counter.getLast().count == 1) {
BitSeq lastZero = counter.removeLast();
if (counter.isEmpty()) {
lastZero.ones = true;
counter.addLast(lastZero);
} else {
counter.getLast().count++;
}
} else {
counter.getLast().count--;
counter.addLast(new BitSeq(true, 1));
}
}
// Most significant bit is also 0.
if (counter.getFirst().ones) {
counter.addFirst(new BitSeq(false, 1));
}
}
public int toDecimal() {
int bitVal = 1;
int result = 0;
Iterator<BitSeq> it = counter.descendingIterator();
while(it.hasNext()) {
BitSeq bs = it.next();
for (int i = 0; i < bs.count; i++) {
if (bs.ones) {
result += bitVal;
}
bitVal *= 2;
}
}
return result;
}
public String toString() {
StringBuilder sb = new StringBuilder();
for (BitSeq bs : counter) {
for (int i = 0; i < bs.count; i++) {
sb.append(bs.ones ? '1' : '0');
}
}
return sb.toString();
}
private static class BitSeq {
public boolean ones;
public int count;
private BitSeq(boolean ones, int count) {
this.ones = ones;
this.count = count;
}
}
}
}
AFAIK normal n+1 is O(1) amortized, just everytime adding +1 bit, save extra space for needing to count with carry.
So now assume every 1 bit has saved extra time for being carried. Now 111 +1 -> use 3rd extra time to 110 -> use 2nd extra to -> 100 use first extra -> 1000 and now save extra time for the new 1. Now from 1000 -> 1001 and save extra time for the last 1..
we keep an aggregation on consecutive 1 or 0.
- adam2008 February 21, 2013meaning 111000111 is <3,1> <3,0> <3,1>
1) if the first bulk is of 1's. it turns to bulk of 0`s and turn the very next 0 to 1.
we now check if we can aggregate bulks of 1's.
2) if the first bulk is of 0's, we make the first digit 1. and see if we can aggregate 1's.