set a memory location

Given the following function signature, write C code to set the memory location passed in (say, for an embedded system).

#include <stdlib.h>
#include <stdio.h>

void setMemoryLocation(int memoryLocation, int value)
{
    *((int*)memoryLocation) = value;
}

int main()
{
    int *pointer = malloc(sizeof(int));
    setMemoryLocation((int)pointer, 12345);
    printf("%d\n", *pointer);
    return 0;
}

find closest RGB value

Given an RGB value, find the closest match in an 256-element array of RGB values.

Solution: Imagine graphing the values of the RGB table on a 3d coordinate system with R being X, G being Y, and B being Z. Then graph the given RGB value to find. Now all we need to do is find the point with the shortest distance between it and the given RGB.

#include <iostream>
#include <iomanip>
#include <math.h>
#include <float.h>

using namespace std;

struct RGB {
    short r, g, b;
    RGB(short _r, short _g, short _b) : r(_r), g(_g), b(_b) {}
    friend ostream& operator<<(ostream& _out, const RGB& _rgb);
};

ostream& operator<<(ostream& _out, const RGB& _rgb)
{
    return _out << "(" << setw(3) << _rgb.r << ", " 
        << setw(3) << _rgb.g << ", " 
        << setw(3) << _rgb.b << ")";
}

inline
double square(double x)
{
    return x*x;
}

/** 
 * @param[in] _rgb color to match
 * @param[in] _table table to search for closest color
 * @param[in] _tableSize number of elements in _table
 * @return the index to the table element with the closest similarity in color
 */
int findClosest(RGB *_rgb, RGB** _table, size_t _tableSize)
{
    double minDistance = DBL_MAX;
    double distance;
    int retVal;
    for (size_t i=0; i<_tableSize; i++)
    {
        distance = sqrt(
                square(_rgb->r - _table[i]->r) +
                square(_rgb->g - _table[i]->g) +
                square(_rgb->b - _table[i]->b) );
        if (distance < minDistance)
        {
            minDistance = distance;
            retVal = i;
        }
    }
    return retVal;
}

int main()
{
    const int size = 256;
    RGB *table[size];
    srand(time(NULL));
    for (int i=0; i<256; i++)
    {
        table[i] = new RGB(rand()%256, rand()%256, rand()%256);
        cout << *table[i] << endl;
    }
    cout << "closest=" << *table[findClosest(&RGB(0,0,0), table, 256)] << endl;
    return 0;
}

Code atoi

Java code:

class atoi
{
    public static int atoi(String str)
        throws NumberFormatException
    {
        if (str == null) throw new NumberFormatException("null");
        if (str == "-2147483648") return Integer.MIN_VALUE;
        int retVal = 0;
        int i = 0;
        char[] s = str.toCharArray();
        boolean isNegative = s[0] == '-';
        if (isNegative) i++;
        if ((isNegative && str.length() > 11) || (!isNegative && str.length() > 10))
                throw new NumberFormatException(str);

        while (i < s.length)
        {
            retVal *= 10;
            if (s[i] > '9' || s[i] < '0')
                throw new NumberFormatException(str);
            retVal += s[i++] - '0';
            if (retVal < 0)
                throw new NumberFormatException(str);
        }
        if (isNegative)
            retVal *= -1;

        return retVal;
    }
    public static void main(String[] args)
    {
        String s = null;
        System.out.println("atoi="+atoi(s));
        System.out.println("max="+Integer.MAX_VALUE);
        System.out.println("min="+Integer.MIN_VALUE);
        System.out.println("parseInt="+Integer.parseInt(s));
    }
}

Print a binary tree rotated on its side

For example,

    1
   / \
  2   3
 /\
4 5 

Prints out...(Notice the spacing):

 3
1
  5
 2
  4

Notice the order of nodes being printed on each line: C F A E B D. This is a right-first inorder traversal.

java code:

class BinaryTree
{
    int data;
    BinaryTree right;
    BinaryTree left;

    public BinaryTree(int data)
    {
        this.data = data;
        this.left = this.right = null;
    }
    public BinaryTree(int data, BinaryTree left, BinaryTree right)
    {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void printInorder()
    {
        printInorder(this, 0);
    }

    private void printInorder(BinaryTree BinaryTree, int level)
    {
        if (BinaryTree == null)
            return;
        printInorder(BinaryTree.right, level+1);
        StringBuffer buf = new StringBuffer();
        for (int i=0; i<level; i++)
            buf.append(' ');
        System.out.println(buf.append(BinaryTree.data));
        printInorder(BinaryTree.left, level+1);
    }

    public static void main(String[] args)
    {
        BinaryTree tree = 
                    new BinaryTree(1, 
                        new BinaryTree(2, 
                            new BinaryTree(4), 
                            new BinaryTree(5)),
                        new BinaryTree(3));
        tree.printInorder(); 
    }
}

Design a data structure with...

Design a data structure with

1. O(1) searching
2. O(n) printing in the order the elements are received
3. O(1) insertion

Answer: This data structure will keep a combination of two other data structures

1. a hash table
2. linked list

When searching, use the hash table. Since there's no guarantee of order in a hash table, when printing, use the linked list. Insertion into both data structures is O(1). Notice there are no restrictions on deleting elements. Also, keep pointers instead of the actual objects to reduce redundancy and save memory space.

Do two elements in a sorted array sum up to a value?

#include <vector>
#include <iostream>

using namespace std;

pair* find2Elems(vector& a, size_t len, int findme)
{
    int iFront = 0, iBack = len-1, sum;
    while (iFront < iBack)
    {
        sum = a[iFront] + a[iBack];
        // sum is too large
        if (sum > findme)
        {
            iBack--;
        }
        // sum is too small
        else if (sum < findme)
        {
           iFront++;
        }
        else // if (sum == findme)
        {
            return new pair(iFront,iBack);
        }
    }
    return NULL;
}

int main() {
    const size_t size = 20;
    vector a(size);
    srand(time(NULL));
    // make a vector with random elements
    for (int i=0; i < size; i++)
    {
        a[i] = rand()%50;
    }
    sort(a.begin(), a.end());
    for (int i=0; i < size; i++)
        cout << a[i] << " ";
    cout << endl;
    pair *p = find2Elems(a, size, 20);
    if (p)
    {
        cout << a[p->first] << ", " << a[p->second] << endl;
    }
    else
        cout << "not found" << endl;
    return 0;
}

Find the mth element from the end of a linked list

One way would be to iterate to the end of the list to get its size N then subtract m from N. Then iterator (N - m) elements from the beginning. This can potentially yield 2n complexity if m was small.

Another method could be from each node iterate to the next m elements and see if that element is has a next element that is null. This can also yield 2N if m is small.

Consider iterating from the first node m elements and keeping a pointer to the first node and the one at that node + m elements. Increment both pointers at the same time. Thus, when the latter pointer reaches the last node, the first node is the mth node from the last node. This gives N - m complexity.

Discuss StrToUpper code

Discuss the following code:

/*
 * Converts an lower case letter into an upper case letter.
 * If the letter is not lower case, it does nothing.
 * In ASCII, upper case letters come before lower case
 * letters ('A' is 65, 'a' is 97) so we need to subtract
 * to convert.
 */
#define MAKE_UPPER_CASE(c) \
 (((c > 'a') && (c < 'z')) ? (c - ('a' - 'A')) : c)

/*
 * StrToUpper -
 * Converts a string to be in all upper case. Returns a pointer
 * to the new, null-terminated, all-upper-case string.
 */
char *StrToUpper(const char* str)
{
    char upperCaseString[1000];
    int i = 0;

    while (i < strlen(str)) {
        upperCaseString[i] = MAKE_UPPER_CASE(str[i++]);
    }

    return upperCaseString;
}

Macro

• Does not evaluate expressions before passing to macro. Thus, i++ will get executed for each appearance of c in MAKE_UPPER_CASE.


• Better to use inline function for type-checking


• (c - ('a' - 'A')) could be replaced by c + 32 for performance


• c > 'a' and c < 'z' should be that and equal to

Function

• Uses local storage: May be garbage because program may overwrite later on. Should either dynamically allocate return string or have input a string buffer as a parameter.


• Does not append '\0' (null) character


• upperCaseString[1000] can only contain 1000 chars and a large input str will cause buffer overflow.


• int i may overflow if str is large


• strlen() can be pulled out of the while statement so it won't be executed each time through the loop

Find a value in a sorted 2D array

A sorted 2D array has rows and columns that contain increasing values.

For example, find 85 in the following sorted 2D array.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

The general strategy is to eliminate rows and columns by comparing the target value to corner points.

Let's look at the right-most element in the first row. This element is the largest element in the row since it is sorted. In the example, 85 is greater than 80 so we know that it cannot be in this row; thus, we can effectively eliminate the first row.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

At the same time, we can see if the last column can be eliminated by checking if the target value against the aforementioned element in the context of the column. The top-most element in a column is the smallest since it is sorted. Hence, if the target value is less than the top-most element, we can eliminate the column. In this case, it is not because 85 is not less than 80, so we keep the last column.

Now, examine the bottom-most element in the last column. 85 is less than 110 so we must save the last column and last row.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

How about the left-most element in the last row. 85 is greater than 50 so we cannot remove the last row. However, we can remove the first column since 85 is greater than 50.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Now, the top-most element in the new first column... 85 is not less than 55 so we cannot remove this column. We cannot remove the row either because again, 85 not less than 55.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Look at the right-most element in the first row. 85 is not greater than 95 so cannot strike this row, but it is less than 85 so we can remove the column.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Next, check the bottom-most element in the last column, 90. We cannot cross the row nor column because 85 is not greater than 90.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

Examine the left-most in the last row. For the row, 85 is not less than 70. For the column, it is greater than 70; thus, we can eliminate the column.

20 40 60 80
35 55 75 95
45 65 85 105
50 70 90 110

When we have 1 row or column left, we can perform a binary search for the value.

Find the least common ancestor of two nodes in a binary tree

From the root, traverse until the current node value is between the value of the two nodes.

        50
      /    \
    40      60
   /  \    /  \
  30  45  55  65
 /  \
20  35

For example, find the least common ancestor (LCA) of 20 and 45 in the above tree. The root node, 50, is not between 20 and 45. We traverse left because both target nodes are less than 50. Now since 40 is between 20 and 45, this is the LCA.

Spirally traverse a 2D array.

General idea:

Call the following, which traverse a row or column then update global variables: xmin,xmax,ymin,ymax

moveRight();
moveDown();
moveLeft();
moveUp();

Write a function that if run on different systems that tells the endianess of the system

Write a single function that if run on different systems that tells if it is little endian or big endian.

/** @return True if this machine has little endian byte order */
bool isLittleEndian() {
  int i = 1;
  char *c = &i; // get the address of i

  // true if the first byte contains the least significant byte
  return (*c == 1);
}

Note: bit shifts and masking do not work because they should work the same way on every system.

Difference between char* and char[] string?

What's the difference between
char *a = "hello";
and
char b[] = "hello";

Several differences:

"a" makes a pointer to an anonymous char array. "b" creates an array of chars.

     +-+-+-+-+-+
a -> |h|e|l|l|o|
     +-+-+-+-+-+

 b
+-+-+-+-+-+
|h|e|l|l|o|
+-+-+-+-+-+

sizeof(a) = 4 (on a 32-bit system)
sizeof(b) = 6 (5 chars and '\0')

The pointer "a" is changeable, i.e. it can be set to point to something else. Whereas, "b" cannot change.

The array that pointer "a" points to cannot change. Chars of "b" can change.

a[3] = 'H'; // illegal
b[3] = 'H'; // OK

What functions do virtual (and non virtual) declarations call in multi-level inheritance?

Depends on the type of the object.

Lock questions

Given the following C++ code, what ways can release not be called?

Lock lock; //global

void function() {
  lock.grab();
  ...
  lock.release();
}

1) a return statement is called
2) a exception is thrown but caught in a calling function

How would you guarantee that release() is called?

Since destructors are always called on local objects, construct a wrapper class that holds a reference to the lock and call release() on that lock in the wrapper class's destructor. Thus, when the function goes out of scope for either of the above cases, the wrapper class's destructor will always get called.

class LockWrapper {
private:
  Lock& lock;
public:
  LockWrapper(Lock& _lock) : lock(_lock) {}
  ~LockWrapper() { lock.release(); }
};

Lock lock; //global

void function() {
  LockWrapper wrapper(lock);
  lock.grab();
  ...
  lock.release();
}

What's the difference between malloc and new?

new calls constructors

How to traverse to next sorted element in a binary tree?

#include <iostream>

using namespace std;

template <typename T>
class Node {
public:
Node* left;
Node* right;
T data;
Node(T data) : data(data), left(NULL), right(NULL) {}
Node(T data, Node* left, Node* right) : data(data), left(left), right(right) {}
};

template <typename T>
T traverseNext(Node<T>* n) {
Node<T>* itr = NULL;
if (n->right) {
itr = n->right;
while (itr->left) {
itr = itr->left;
}
}
return itr ? itr->data : NULL;
}

int main() {
Node<int> n6(6);
cout << traverseNext(&n6) << endl; //0

Node<int> n9(9), n11(11);
Node<int> n10(10, &n9, &n11);
Node<int> n14(14);
Node<int> n12(12, &n10, &n14);
n6.right = &n12;
cout << traverseNext(&n6) << endl; //9
cout << traverseNext(&n12) << endl; //14
cout << traverseNext(&n10) << endl; //11
}

What is the difference between rm and unlink?

unlink is a system call, rm is a shell utility that calls unlink

What is perserved when calling exec()?

Open file descriptor table, signal handlers

What is a timer interrupt?

Hardware generated interrupt used for process/thread scheduling.

Design user space threads