Primitive Types

Question 1

parity check for binary word. 1 when the number of 1s in the word is odd 0 when the number of 1s in the word is even ex./ 1011 is 1 (three 1s), 10001000 is 0 (two 1s)

Answer 1

parity(long x){ short result = 0; while(x != 0){ result ^=1; // counting 1 if only 1 exists, result is 1, if two 1 exists, result would be 0 x &= (x - 1) // drops the lowest set bit of x } return result; }

Question 2

how to extract lowest set bit of input x

Answer 2

x & ~(x-1)

Question 3

how to drop the lowest set bit of input x

Answer 3

x & (x - 1)

Question 4

swap bits at index i and index j for the input x time complexity is O(1)

Answer 4

long swapBits(long x, int i, int j){ if(((x >>> i) & 1) != ((x >>> j) & 1)){ long bitMask = (1L << i ) | (1L << j); x ^=bitMask; } }

Question 5

closest int same bit count time complexity O(n) ex./ (111 in bit)(7 in decimal)-> (1011)(11) and not (1110)(14)

Answer 5

closestIntSameBitCount(long x){ final int NUM_UNSIGNED_BITS = 63; for (int i = 0; i < NUM_UNSIGNED_BITS - 1; ++1){ if((((x >>> i ) & 1) != ((x >>> (i + 1)) & 1))){ x ^= (1L << i) | (1L << (i + 1)); return x; } } throw new IllegalArgumentException(“All bits are 0 or 1”); }

Question 6

multiplication without arithmetical operators. O(n^2)

Answer 6

long multiply(long x, long y){ long sum = 0; while( x != 0){ if((x & 1) != 0){ sum = add(sum, y) } x >>>= 1; y <<= 1; } return sum; } private long add(long a, long b){ return b == 0 ? a : add(a ^ b, (a & b) << 1); }

Question 7

division without arithmetical operators. O(n)

Answer 7

(2^k) * y <= x iterating through k int divide(int x, int y){ int result = 0; int power = 32; long yPower = (long)y << power; // y and 32 zeroes follow ex./ if y = 1, yPower = 1 + 32 0s while(x >= y){ while(yPower > x){ // get the largest power value less than x yPower >>>= 1; // removing LSB one by one –power; } result += 1 << power; // add 2^k to the result x -= yPower; } return result; }

Question 8

compute power O(n)

Answer 8

double power(double x, int y){ double result = 1.0; long power = y; if(y <0){ power = -power; x = 1.0 / x; } while(power != 0){ if((power & 1) != 0){ // if the LSB of y is 0, the result is (x^y/2)^2, otherwise x * (x^y/2)^2 result *=x; } x *= x; power >>>=1; } return result; }

Question 9

reverse digits time complexity O(n)

Answer 9

long reverse (int x) { long result = 0; while ( x != 0) { result = result * 10 + ( x % 10); x /= 10; } return result; }

Question 10

check is a decimal integer is a palindrome time complexity O(n) space complexity O(1)

Answer 10

boolean isPalindromeNumber( int x ){ if ( x <= 0){ return x == 0; } final int numDigits = (int)(Math.floor(Math.log10(x))) + 1; // get the number of the digits of the input int msdMask = (int) Math.pow(10, numDigits -1 ); //to get MSB, 10^numDigits-1 used to divide the input for(int i = 0; i < (numDigits /2);++1){ if(x / msdMask != x % 10){ // comparing MSB and LSB return false; } x %= msdMask; // removing MSB x /= 10; // removing LSB msdMask /= 100; // remove 2 digits from the mask to match the number of the digits of x } return true; }

Question 11

Generate Uniform Random Numbers O(log(b-a+1))

Answer 11

int uniformRandom(int lowerBound, int upperBound){ int numberOfOutcomes = upperBound - lowerBound + 1; int result = 0; do{ for(int i = 0; (1 << i) < numberOfOutcomes; ++1){ result= (result << 1) | zeroOneRandom(); } }while (result >= numberOfOutcomes); //result could be bigger than the numberOfOutcomes return result + lowerBound; }

Question 12

Rectangle intersection

Answer 12

public static class Rect { int x, y, width, height; public Rect(int x, int y, int width, int height) { this.x = x; this.y = y; this.width = width; this.height = height; } public static Rect intersectRectangle(Rect r1, Rect r2) { if (!isIntersect(r1, r2)) { return new Rect(0, 0, -1, -1); // No intersection. } return new Rect( Math.max(r1.x, r2.x), Math.max(r1.y, r2.y), Math.min(r1.x + r1.width, r2.x + r2.width) - Math.max(r1.x, r2.x), Math.min(r1.y + r1.height, r2.y + r2.height) - Math.max(r1.y, r2.y)); } private static boolean isIntersect(Rect r1, Rect r2) { return r1.x <= r2.x + r2.width && r1.x + r1.width >= r2.x && r1.y <= r2.y + r2.height && r1.y + r1.height >= r2.y; } }