CareerCup

The answer is to traverse the tree (DFS or BFS) while keeping track of the number of nodes we've seen so far (with the first one indexed 1). Each time we see a new node pick a random number from 0 to index-1. If the random number is equal to 0 then remember the node to be returned (replace the previous one if necessary).

Because all integers are positive and the array is long enough we can exploit the sign of the integer to mark which integer was encountered before:

private static int findDuplicated(int[] array) {
        if (array == null || array.length < 1) {
            return -1;
        }
        int result = -1;
        for (int i = 0; i < array.length; i++) {
            if (Math.abs(array[i]) < 1 || array.length - 1 < Math.abs(array[i])) {
                result = -1;
                break;
            }
            if (array[Math.abs(array[i])] >= 0) {
                array[Math.abs(array[i])] = -array[Math.abs(array[i])];
            } else {
                result = Math.abs(array[i]);
            }
        }
        // Undo
        for (int i = 0; i < array.length; i++) {
            array[i] = Math.abs(array[i]);
        }
        return result;
    }

One way is to create a hash table with frequency of each integer and then search though it to find the non-compliant integer:

private static int find(int[] array) {
        HashMap<Integer, Integer> frequencies = new HashMap<>();
        for (int value : array) {
            Integer frequency = frequencies.get(value);
            if (frequency == null) {
                frequencies.put(value, 1);
            } else {
                if (frequency == 3) {
                    return value;
                }
                frequencies.put(value, 1 + frequency);
            }
        }
        for (int value : frequencies.keySet()) {
            if (frequencies.get(value) != 3) {
                return value;
            }
        }
        return 0;
    }

Simple solution counting the number of bits set:

private static boolean slow(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>= 1;
        }
        return count == 1;
    }

Better solution exploiting the properties of two's complement representation of and integer:

private static boolean fast(int n) {
        return ((n & -n) == n);
    }

If the strings are character arrays one can sort both - O(n log n) - and compare the result:

private static boolean check(String a, String b) {
        char[] aa = a.toCharArray();
        char[] bb = b.toCharArray();
        Arrays.sort(aa);
        Arrays.sort(bb);
        return Arrays.equals(aa, bb);
    }

public class NthOfSortedArrays {
    private static int nth(int[] a, int a1, int a2, int[] b, int b1, int b2, int n) {
        if (a2 < a1) {
            return b[b1 + n];
        }
        if (b2 < b1) {
            return a[a1 + n];
        }

        int midA = (a1 + a2) / 2;
        int midB = (b1 + b2) / 2;
        if (midA - a1 + midB - b1 < n) {
            // Middle is too little to reach n
            // Get rid of the quarter which is surely smaller - it can't contain nth
            if (a[midA] > b[midB]) {
                // Lower b values are certainly below nth
                return nth(a, a1, a2, b, midB + 1, b2, n - (midB - b1 + 1));
            } else {
                // Lower a values are certainly below nth
                return nth(a, midA + 1, a2, b, b1, b2, n - (midA - a1 + 1));
            }
        } else {
            // Middle is enough to reach n
            // Get rid of the quarter which is surely bigger - it can't contain nth
            if (a[midA] > b[midB]) {
                // Upper a values are certainly above nth
                return nth(a, a1, midA - 1, b, b1, b2, n);
            } else {
                // Upper b values are certainly above nth
                return nth(a, a1, a2, b, b1, midB - 1, n);
            }
        }
    }

    private static int nth(int[] a, int[] b, int n) {
        return nth(a, 0, a.length - 1, b, 0, b.length - 1, n);
    }

    public static int[] random() {
        Random random = new Random();
        int[] array = new int[1 + Math.abs(random.nextInt()) % 9];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt();
        }
        Arrays.sort(array);
        return array;
    }

    private static int[] join(int[] a, int[] b) {
        int[] joined = new int[a.length + b.length];
        System.arraycopy(a, 0, joined, 0, a.length);
        System.arraycopy(b, 0, joined, a.length, b.length);
        Arrays.sort(joined);
        return joined;
    }

    public static void main(String[] arguments) {
        int[] a = random();
        int[] b = random();
        Random random = new Random();
        int n = 1 + Math.abs(random.nextInt()) % (a.length + b.length - 2);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));
        System.out.println(Arrays.toString(join(a, b)));
        System.out.println(n);
        System.out.println(nth(a, b, n));
    }
}

private static class Tree {
        public Tree left;
        public double value;
        public Tree right;

        public Tree(Tree left, double value, Tree right) {
            this.left = left;
            this.value = value;
            this.right = right;
        }
    }

    public static double closest(Tree root, double value) {
        double delta = Math.abs(root.value - value);
        if (value < root.value && root.left != null) {
            double left = closest(root.left, value);
            if (Math.abs(left - value) < delta) {
                return left;
            }
        }
        if (root.value < value && root.right != null) {
            double right = closest(root.right, value);
            if (Math.abs(right - value) < delta) {
                return right;
            }
        }
        return root.value;
    }

I'm not trying to achieve anything, just posting the questions I was asked during on-sites (I tried couple times with Google, once at Facebook and Amazon).

I also collected questions from a few friends who went (successfully) through their round of interviews.

And, yes, the folks at Google do ask open ended questions as part of the System Design interview

@eng.ahmed.moustafa - I can't remember exactly anymore but I think I asked the same question and got reply to assume the elements are distinct. It's a good question though.

@guilhebl - the trick is that the order of the listing determines that - elements in the "before" lists go to the left, elements in the "after" lists go to the right (i.e. it was still assumed that the in/pre-order take the left child first)

Came up with the same algorithm, here's the code in Python:

DECREASING = 0
INCREASING = 1

def prepare(A, function, direction):
    Z = [0] * len(A)
    Y = [None] * len(A)
    indices = range(len(A))
    if DECREASING == direction:
        indices.reverse()
        first = 2
        second = 1
        seed = len(A) - 1
        delta = 1
    elif INCREASING == direction:
        first = 1
        second = 2
        seed = 0
        delta = -1
    for i in indices:
        if i == indices[0]:
            Z[i] = A[i]
            Y[i] = (A[i], seed, seed)
        else:
            previous = i + delta
            Z[i] = function(A[i], Z[previous] + A[i])
            if Z[i] == A[i]:
                start = i
            else:
                start = Y[previous][first]
            result = function(Y[previous][0], Z[i])
            if result == Z[i]:
                stop = i
            else:
                stop = Y[previous][second]
            Y[i] = [result, 0, 0]
            Y[i][first] = start
            Y[i][second] = stop
    return Y

def check(U, V):
    for i in range(len(U) - 1):
        diff = abs(U[i + 1][0] - V[i][0])
        if i == 0:
            maximum = diff
            index = 0
        elif diff > maximum:
            maximum = diff
            index = i
    return (maximum, index)

def find(A):
    C = prepare(A, min, INCREASING)
    B = prepare(A, max, DECREASING)
    (maximum1, index1) = check(B, C)
    D = prepare(A, max, INCREASING)
    E = prepare(A, min, DECREASING)
    (maximum2, index2) = check(E, D)
    if maximum1 < maximum2:
        print('From %d to %d' % (D[index2][1], D[index2][2]))
        print('From %d to %d' % (E[index2 + 1][1], E[index2 + 1][2]))
    else:
        print('From %d to %d' % (C[index1][1], C[index1][2]))
        print('From %d to %d' % (B[index1 + 1][1], B[index1 + 1][2]))

A = [2, -1, -2, 1, -4, 2, 8]
find(A)
A = [2, 2, 2, 2, -1, -1, -1, -1]
find(A)

The answer is yes and the solution is:
1. Take the first element of the pre-order list
2. Find that element in in-order list and split that list into two lists - in-order before and in-order after
3. Similarly, for the pre-order list remove the first element and split it into two parts of the same length as in point 2 - pre-order before and pre-order after
4. Apply this function recursively to "before" and "after" lists

The answer is yes and the solution is:
1. Take the first element of the pre-order list
2. Find that element in in-order list and split that list into two lists - in-order before and in-order after
3. Similarly, for the pre-order list remove the first element and split it into two parts of the same length as in point 2 - pre-order before and pre-order after
4. Apply this function recursively to "before" and "after" lists

First step is to calculate the distance for each point = sqrt(x * x + y * y).
Next step is to fint the K points with the smallest distance.

One way is just to sort the points by their distance and list K first items in the resulting list - this would obviously have a complexity of O(N log N).

Another way would be to insert the points into a binary min heap of length K while calculating the distances - this would have a complexity of O(N log K) which might be beneficial (in terms of time and space) if K is much smaller than N.

Part 1 is easy - just go through all records and list the record if the ManagerID is equal to the given ID

Part 2 - one solution is to build a (hierarchy) tree of all employees, search for the entry for employee with the given ID and then list its subtree depth-first. This is no problem for 250 employees, but if there were more then we might want to explore different solution.

Let's assume that the organization of pixels is: a line of pixels (from left to right) is a consecutive sequence of bytes (each byte holding 8 pixels - bit 0 is the leftmost pixel, bit 7 the rightmost) and then lines are a consecutive sequence from top to bottom. It is important to ask the interviewer if this is the right assumption.

One can iterate pixel-by-pixel but this would potentially access the same byte multiple times. This can be improved by dividing drawing of the line into three parts: drawing the head - first byte of the line where only the high part of the bits is affected, then the body - the part of the line where a full bytes are affected, and finally the tail - last byte of the line where only the low part of the bits is affected.

import math

def blank(width, height):
    return [0] * int(math.ceil(width * height / 8.0))

def line(bitmap, width, height, x1, x2, y):
    a_full = width * y + x1
    z_full = width * y + x2
    a_head = a_full >> 3
    a_bits = a_full & 0x7
    a_body = a_head + (1 if 0 != a_bits else 0)
    z_tail = z_full >> 3
    z_bits = (z_full & 0x7) + 1
    z_body = z_tail - (1 if 8 != z_bits else 0)
    # Head
    if a_head != a_body:
        bitmap[a_head] |= (0xFF << a_bits) & 0xFF
    # Body
    for i in range(a_body, z_body + 1):
        bitmap[i] = 0xFF
    # Tail
    if z_tail != z_body:
        bitmap[z_tail] |= ~(0xFF << z_bits) & 0xFF

def hexed(bitmap):
    return ''.join(['%02X' % byte for byte in bitmap])

width = 32
height = 3
bitmap = blank(width, height)
line(bitmap, width, height, 7, 22, 1)
print(hexed(bitmap))

Nice catch, seems like a better solution. Good thing though that my solution was good enough to pass to the on-site

Part 1: The arrays need to be sorted first and then the function can be applied. This can be accomplished by splitting the sorting between the machines, then merging the results and then exchanging the parts of the arrays for application of the function (a form of a map-reduce algorithm). Heap sort would be particularly useful as it produces consecutive (and sorted) elements during sorting which could already be used for application of the function.

Part 2: Either run a small subset first to get an idea if it is linear distribution and then divide statically according to that or try to adapt during processing depending on the load of the machines.

Part 3: Use master election algorithms (gossip algorithms, etc.).

The solution to this question is a decorate-sort-undecorate algorithm. The characters of the string T are supposed to be decorated with values which are indices of those characters in the string O or value -1 if they are absent in string O. Since the order of the characters decorated with -1 is not important we are free to use any sorting algorithm (i.e. not necessarily a stable one).

def reorder(t, o):
    # Build a decorating hash table
    lut = {}
    for i in range(len(o)):
        lut[o[i]] = i
    # Reorder
    return ''.join(sorted(t, key=lambda character: lut[character] if lut.has_key(character) else -1))

print reorder('hello world', 'wrled')

While iterating through A use a look up table to figure out the indices of the elements to be swapped.

Algorithm (pseudocode):

Build a look up table LUT from the array A mapping a value to its position in the array A
Iterate through the array A{
  If value at current index I is misplaced then{
    Find the index J of the element which should be placed at the current index I
    If A[I] == 0 or A[J] == 0 then{
      Do one swap between A[I] and A[J]
    }Else{
      Find the position of zero K
      Do three swaps between A[I], A[J] & A[K]
    }
    Update the LUT
  } 
}

Code (Python):

def reorder(a, b):
    # Check input
    if len(a) != len(b):
        print('Mismatched array length')
        return
    print('A = %s' % str(a))
    print('B = %s' % str(b))
    N = len(a)
    # Building LUT
    lut = N * [None]
    for i in range(N):
        lut[a[i]] = i
    print('LUT = %s' % str(lut))
    # Reordering
    for i in range(N):
        impostor = a[i]
        expected = b[i]
        if impostor != expected:
            j = lut[expected]
            if 0 in [expected, impostor]:
                print('Swapping %d and %d' % (i, j))
            else:
                print('Swapping %d and %d through %d' % (i, j, lut[0]))
            a[j] = impostor
            a[i] = expected
            lut[impostor] = j
            lut[expected] = i
            print('A = %s' % str(a))

reorder([1, 3, 2, 4, 0], [4, 0, 3, 2, 1])