Google Interview Hacks

How do we use XOR to cancel out matching numbers? Start with 0, and XOR every number you come across. If there are multiple pairs and only one unique number, the remaining number will be the unique number.

How do we know when to use bit manipulation to solve a problem? 2 things to watch out for: 1. We want to multiply or divide by 2 (use a left shift to multiply by 2, right shift to divide by 2) 2. We want to cancel out matching numbers. (Using XOR)

How do we reduce the likelihood of Integer Overflow in C#? Use larger integer types, such as long. There are also libraries built to handle arbitrarily large numbers. C# also has a checked keyword, which enables runtime overflow detection.

How does C# handle Integer Overflow? The processor will sort of "do its best" with the bits it has, taking the true result and throwing out any bits that don't fit. So in our example above, when adding 01 to 11, the processor would take the true result 100 and throw out the highest bit, leaving 00.

What is Integer Overflow? Sometimes we have a number that does fit in 32 or 64 bits, but if we add to it (or multiply it by something, or do another operation) the result might not fit in the original 32 or 64 bits. This is Integer Overflow.

When you create an integer variable, what does your computer actually do? The computer allocates a fixed number of bits for storing it. Most modern computers use 32 or 64 bits, but some numbers are so big they don't fit even in 64 bits, like sextillion, which requires 70 digits in binary.

If a number is encoded using Two's Complement, then an Arithmetic Right Shift ___ the number's sign, while a Logical Right Shift makes the number ___. Preserves Positive

In C#, a Right Shift Operator automatically does ___ on signed types, but ___ on unsigned types. Arithmetic Right Shift (copies the most significant bit) Logical Right Shift (The reverse of a Left Shift. Moves everything 1 space to the right and adds a 0 as the leftmost bit.)

What is an Arithmetic Right Shift? With an Arithmetic Right Shift, the Least Significant Bit is lost, and the Most Significant Bit is COPIED and placed in the leftmost spot. // -5 Arithmetically Right Shifted = -3 1011 >> 1 -> 1101 // -5 Arithmetically Right Shifted 3 times = 1011 >> 3 -> 1111 = -1

For positive numbers, a single Logical Right Shift does what to a number? Divides a number by 2, throwing out any remainders. 0101 >> 1 -> 0010 = 2

What is a Logical Right Shift? When shifting right with a Logical Right Shift, the least-significant bit is lost and a 0 is inserted on the other end. // -5 with a logical right shift = 5 1011 >> 1 -> 0101 = 5 // -5 with 3 logical right shifts = 1 1011 >> 3 -> 0001 = 1

What is a Left Shift? When shifting left, the most significant bit is lost, and a 0 bit is inserted on the other end. The left shift operator is usually written as "<<". A single left shift multiplies a binary number by 2. // 2 bit shifted left by 1 space = 4 0010 << 1 -> 0100 = 4 // 2 bit shifted left by 2 spaces = 8 0010 << 2 -> 1000 = 8

What is a Bit Shift? Bit Shift moves each digit in a number's binary representation left or right. There are 3 main types of shifts: 1. Left Shift 2. Logical Right Shift 3. Arithmetic Right Shift

What bitwise operation can make positive numbers negative, and vice versa? ~ the NOT operator. ~5 -> -6 0101 -> 1010 = -8 + 2 This is the same when you involve multiple zeroes, because the leftmost Bit will be a negative number. 0000 0101 -> 1111 1010 = -128 + 64 + 32 + 16 + 8 + 2 = -128 + 122 = -6

What does the bitwise NOT operator do? The NOT operation INVERTS BITS. A 0 becomes a 1. A 1 becomes a 0. It is written as the tilde character ~ which goes before the 2 numbers. ~ 0000 0101 -> 1111 1010

When performing the XOR operation on two integers, how is it calculated? The Exclusive OR operation is calculated on each pair of bits (the two bits at the same index in each number.) 5 ^ 6 -> 3 0101 ^ 0110 -> 0011

What does the bitwise XOR operation do? The Exclusive OR operation takes two bits and returns 1 if EXACTLY ONE bit is 1. Otherwise it returns 0. 1 ^ 1 -> 0 1 ^ 0 -> 1 0 ^ 1 -> 1 0 ^ 0 -> 0

When performing the OR operation on two integers, how is it calculated? The OR operation is calculated on each pair of bits (the two bits at the same index in each number.) 5 | 6 -> 7 0101 | 0110 -> 0111

What does the bitwise OR operation do? Takes two bits and returns 1 if EITHER of the bits are 1. Otherwise it returns a 0. 1 | 1 -> 1 1 | 0 -> 1 0 | 1 -> 1 0 | 0 -> 0

When performing the AND operation on two integers, how is it calculated? The AND operation is calculated on each pairs of bits (the two bits at the same index in each number) 5 & 6 would return 4, because 5 = 101 and 6 = 110, so it returns the 4 because that is the index that is a 1 in both.