CoreOS Interviews

I will describe some questions that I was asked.

1.) Given a list of negative and positive integers, group all the negative integers together and the positive on the opposite side, in place.

   int pos = 0;
   for (int i = 0; i < n; ++i) {
      if (array[i] < 0) {
         swap(&array[pos++], &array[i]);
      }
   }

2.) Implement strstr() with no libraries.

char *strstr(char *hay, char *need) {
   if (hay == (char *)0 || char == (char *)0)
      return (char *)0;
   int haysz = my_strlen(hay);
   int needsz = my_strlen(need);
   int j = 0;
   for (int i = 0; i < haysz - needsz; ++i) {
      for (j = 0; j < needsz; ++j)
         if (hay[i + j] != need[j])
            break;
      if (j == needsz)
         return &hay[i];
   }
   return (char *)0;  
}

3.) Given 3 buckets labeled B, W, and BW. The labels are wrong, choose a ball out of a bucket to correctly fix the labels. Which bucket must you choose from?
BW, because this will open up the possibilities by process of elimination.
For example, if the ball you choose from BW is white, then that bucket must be W, since it cannot be BW. Moving along, you look at the bucket labeled B, the only alternatives are W or BW. W was already chosen, so the bucket must be labeled BW. Looking at the last bucket labeled W, the only option is B, which satisfies the rules. (This logic works for the ball chosen from the BW bucket is black)

4.) Test the cp command.
Input, type of files, restrictions on non-valid files (i.e., they don't exist).

5.) Find the top six (6) frequencies from 1 - 100, that have the highest strength. You are given a function called int getStrength(int freq); and it will return a value from 1 - 10. 10 is the highest strength.

typedef pair FreqStr;
vector list;
int cmp(FreqStr first, FreqStr next) {
   return first.second >= next.second;
}
for (int i = 1; i <= 100; ++i) {
   list.push_back(make_pair(i, getStrength(i)));
}
sort(list.begin(), list.end(), cmp);
for (int i = 0; i < 6 && i < list.size(); ++i)
   top6[i] = list[i].second;

6.) Given a nxn grid, and '*' represents mine's as in minesweeper. Return the grid with '*' characters remaining, but the blank spaces with numbers, indicating how many mine's are adjacent to that (x,y) position. Adjacent, in this context, means horizontal, vertical, and diagonal from the (x,y) position.

bool inBounds(int x, int y) {
   return (0 <= x && x < n && 0 <= y && y < n);
}
int count(int x, int y) {
   int cnt = 0;
   for (int xoff = -1; xoff <= 1; ++xoff)
      for (int yoff = -1; yoff <= 1; ++yoff)
         if (inBounds(x + xoff, y + yoff)) {
            if (grid[x + xoff, y + yoff] == '*')
               ++cnt;
         }
   return cnt;
}
for (int x = 0; x < n; ++x)
   for (int y = 0; y < n; ++y) {
      if (grid[x, y] != '*') {
         grid[x, y] = '0' + count(x,y);
      }
   }

Linear Tree Traversal

Linear Tree Traversals
This is useful if you want to simulate going through a tree in sorted order, as if the tree was a linear list, and the list was sorted.
There are two mechanisms how this is done, one called "linking," which we will not discuss, and the other is going and finding the lowest element in the tree, and traversing it in such a way, where we go from least to highest. The latter is the one which I will discuss.

So, there are two pieces to this linear traversal.
First, to find the lowest element, this is just a matter of going left, until you can't.
Second, to find the next element, you can do one of two things. You want to go right, and then all the way down to the left most node. If you have no right child node, then you are left to go up. There are two cases, one where you are the left or the right child of your parent.

If you are a left child of your parent, it hasn't been "traversed," therefore pick that element. Else if you are the right child of your parent, the parent node has been "traversed" so keep going up until you are not the right child of your parent.

Before, displaying the code, let's prove that going up (once, if you are the left, and continuously, until you hit NULL, if you are continuously the right) will indeed be the right choise.

Ok, starting off you are the left most node in the tree. This guarantees that you are the "lowest" node in the tree. However, if you look at its parent node, it is still bigger then the "lowest" node's right node. So, instead of going up, you'd want to go right, and then follow its left chain all the way down.
However, if you are a right child, then to even get to that point your parent node has been traversed. Why? This is because to get to the right node, you have had to traverse the parent, to even get to the right node. This is in part due to the fact that, we go right, then all the way down left. And once we bubble up to that "subroot" which is the right child, we "traverse" it, and then go to its right node, and then to the lowest node in that subtree. So, in doing so, when we bubble back up, there is no need to look at the parent node of the right child.

The code follows:

typedef struct node {
   struct node * left;
   struct node * right;
   struct node * parent;
   int val;
} uwf_node_t;

// Find the first node in the tree.
uwf_node_t * findFirst(uwf_node_t * root) {
   if (!root) {
      return (uwf_node_t *)NULL;
   }
   while (root->left)
      root = root->left;
   // Return the left most node.
   return (root);
}
uwf_node_t * findNext(uwf_node_t * subRoot) {
   if (!subRoot) 
      return (uwf_node_t *)NULL;
   // Let's suppose, we are the left most node
   // instead of bubbling up, we need to go right,
   // and then left as far as possible.
   if (subRoot->right) {
      subRoot = subRoot->right;
      while (subRoot->left)
         subRoot = subRoot->left;
   } else {
      uwf_node_t * oldRoot = subRoot;
      // Find the parent node that is "valid"
      while (subRoot = subRoot->parent) {
         if (subRoot->left == oldRoot)
            break;
         oldRoot = subRoot;
      }
   }
   return (subRoot);
}

Find the Missing Number

Suppose you have a list of N-1 integers, and they are from 1-N.
Each number is used at most once.
Therefore, there is a missing number.

To add more complexity, assume you can only look at one bit at any given time.
Let's call this function:

boolean isSet(int index, int bitPosition) { 
   return array[index] & pow(2, bitPosition); 
}

The answer is to view the 0th bit, counting up how many are supposed to be odd
and how many are supposed to be even, we can analyze that the missing number is
in one of these sets, and therefore, one of the sets can be removed completely.
Therefore, the next bit check is reduced from N to N/2, and doing so, will be
something similar to N + N/2 + N/4 + ... smaller than N*lg(N).
The trick is when the number is in the set that is "odd" or that has the bit "set",
then that bit will be set, and you increment and look at the next bit, else, look
at the next bit + 1.

        for (i = 0; i < 8; ++i) { // log(N)
                memset(bitSetList, 0, N);
                memset(bitNotSetList, 0, N);
                bitSet = bitNotSet = 0;
                if (N <= 1) {
                        printf("Printing the value ...\n");
                        printf("%d\n", set);
                        break;
                }
                for (j = 0; j < N; ++j) // N + N/2 + N/4 + ... 
                // Roughly N * lg(N) since 1 + 1/2 + 1/3 + ... + 1/N -> lg(N+1)
                // and N * (1 + 1/2 + ... + 1/N) > N + N/2 + N/4 + ...
                        if (f(array[j], i))
                                bitSetList[bitSet++] = array[j];
                        else
                                bitNotSetList[bitNotSet++] = array[j];

                // Update the index counter.
                if (N%2) {
                        if (N/2 == bitSet)
                                set |= pow(2, i),
                                updateBitSet(&i, &N, bitSet, bitSetList, BIT_SET);
                        else
                                updateBitSet(&i, &N, bitNotSet, bitNotSetList, BIT_NOT_SET);
                } else { // even
                        if (N/2 == bitSet)
                                set |= pow(2, i),
                                updateBitSet(&i, &N, bitSet, bitSetList, BIT_SET);
                        else
                                updateBitSet(&i, &N, bitNotSet, bitNotSetList, BIT_NOT_SET);
                }
        }

Factorial n!

Computing n!

There are many ways to compute n!, but I will introduce a divide and conquer method.
Using these rules below:
f(n,m) = 1 if n == m,
f(n,m) = 0 if n > m,
f(n,m) = f(n,x) * f(x+1,m) where x = (n + m)/2, otherwise

int f(int n, int m)
{
   if ( !(n < m) ) return n == m;
   int x = (n + m) / 2
   return f(n,x) * f(x+1,m);   
}

Project Euler - Prime Generation

Project Euler - Mathematics/CS competition site (http://www.projecteuler.net)
I want to show an alternate way than S of E, currently, that I know of.
The space required is just the array of primes.
I used to perform the Seives (of Erasothenes) which is N * lg lg N, which is quite fast.
However, a better technique (in terms of space) is used in the following example.
This code will be python, and I will show the implementation below.
I can find the 10,001st prime number in under one second.

#! /usr/bin/python
# This program computes 
#       10,001st prime.
# count of how many primes
nprimes = 1
# current value 
n = 1
# current primes list with
# its value squared
primes = [ (2,4) ]
while nprimes < 10001:
        # Gen all primes
        n += 2
        for prime, primeSquared in primes:
                if n < sq:
                        primes.append((n, n**2))
                        nprimes += 1
                        if nprimes == 10001:
                                print n 
                        break;
                if n % prime == 0:
                        break;

The Sieve Of Erasothenes (S of E) follows (which is much faster for large inputs):

#!/usr/bin/python
# O(N lg lg N)
import Numeric
primes = [2]
N = 2000000
p = Numeric.ones(N,Numeric.Int)
n = 3
c = 1
while n < N:
        if p[n] == 1:
                c += 1
                primes.append(n);
                j = n + n;
                while j < N:
                        p[j] = 0
                        j += n
        n += 2

Generating all subsets

Generating all subsets

I am not really going to dive into much detail here.
But assume you are representing a set with a bitmask within a uint32_t (or the like).
To generate all the subsets is quite easy if you desire to do it within a couple of loops, however, doing it in one loop is conceivably hard, and even harder to prove that it works.

The following code is using recursion to identify and prints out all subsets of the set (bitmask).

void f(int bitmask) {
   cout << bitmask << endl;
   for (int j = 0; j < n; ++j)
      if (bitmask & (1 << j))
         f(bitmask ^ (1 << j));
}

However, a better solution and one that avoids recursion is the following:

for (int subset = bitmask;; subset = (subset - 1) & bitmask)
   cout << subset << endl;

To prove this, we first need to know what exactly happens when you perform
(subset - 1) & bitmask
Basically, the & bitmask identifies that it is a subset of bitmask.
But does this guarantee all of them?
(subset - 1) will remove the lowest one-bit that is set, and replace it with a zero, and set all the lower bits to one.

The reasoning that this proves that all subsets are conceivably generating with this single for loop is certain. Every time you update subset, you are un-setting the lowest bit within bitmask. Once you have exhausted the lower bit. It goes to the next lowest bit that is set, since the lowest one has been exhausted already.

For example,
X = 11010111
Y = X (this is valid)
Y = (Y - 1) & X = 11010110 (removes lowest bit)
Y = (Y - 1) & X = 11010101 (removes 2nd lowest bit)
Y = (Y - 1) & X = 11010100 (removes 2 lowest bits)
Y = (Y - 1) & X = 11010011 (removes 3rd lowest bit)
Y = (Y - 1) & X = 11010010 (removes 3rd and 1st lowest bit)
Y = (Y - 1) & X = 11010001 (removes 3rd and 2nd lowest bit)
Y = (Y - 1) & X = 11010000 (removes 3 lowest bits)
This follows for all Y, such that Y > 0.
The bitwise-AND with X, guarantees it's always a subset of X.
q.e.d.

Therefore, the invariant of this process, is that the lowest bit is unset (within X), then proceeding with higher bits, it sets all remaining bits to being set, and then it proceeds to unset that bits along with the current bit that is being proceeded to be unset. This will guarantee all subsets.

Word Numbers

Question:
"If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?"

To be precise: if the integers from 1 to 999,999,999 are expressed in words (omitting spaces, 'and', and punctuation[1]), and sorted alphabetically so that the first six integers are

* eight
* eighteen
* eighteenmillion
* eighteenmillioneight
* eighteenmillioneighteen
* eighteenmillioneighteenthousand

and the last is

* twothousandtwohundredtwo

then reading top to bottom, left to right, the 28th letter completes the spelling of the integer "eighteenmillion".

The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?

Solution:
The solution to this problem involves noticing that you can skip many words if the order is not important. Notice the 999,999 numbers after eightmillion. They include 8,000,001 - 8,999,999 in some sorted order. Thus, it's easy to count the numbers (sum) as well as the sum.

The hard part is when you have to drill down on the problem. However, it's the same problem over again. Except there are fewer number that are involved. Let's look at eightthousand. What are the next 999 numbers involved? 8,001 - 8,999 in some sorted order.

So if we have 3 lists of numbers, and place them in orders, relative to 10^3 then we only have roughly 3000 numbers to sort and go through at any time before drilling down. The trick is to count the sum quickly as well as the number of letters while skipping over many letters and numbers in the process.

However, it boils down to only needing to keep track of the lower order categories.

We need to know the sum from 1 - 999, and the sum from 1 - 999,999.
(n*(n+1)/2)
We need to know the sum of letters from 1 - 999, and 1 - 999,999.
This is easy, but not that straight-forward. I approached it differently, so I kept a list of number (spelled out) from 1 - 999. So that part was just looping through and summing all entries in that list.

However, to get the other sum from 1 - 999,999. I looped the higher order list that contained the thousand list of numbers 1,000 - 999,000. And added that sum of characters plus the sum of 1 - 999, and then added it with the sum of characters multiplied by 999.

Therefore, all that's left is to sort all categories and walk through the list, updating the current sum of numbers and the current sum of letters.