CareerCup

similar to "sort using two stacks" problem from "cracking..." book. treat the linked list as stack, and add another stack (linked list) to keep sorted results.

I would consider using template method pattern: www . newthinktank . com/2012/10/template-method-design-pattern-tutorial/

Firstly, need to ask interviewer to clarify:
- # of log entries/day, # of pages and # of users? can the data fit into a traditional DB or requires distributed storage. I assume the analyzed results can be loaded into an RDBMS.
- is this real-time analysis or can we use a Hadoop job to ETL? I assume ETL is allowed.
- should we optimize for query performance or write performance? I assume query performance is more critical.

The solution is to write raw log data to HDFS, using Apache Flume to support multiple data centers. Use Hadoop job to analyze the raw data and load results into an RDBMS for query.

In RDBMS, to support the first two queries, we can use a table with columns "page, user-count, visit-count". For third query, we can create a table with "page, user-id, count".

that's a good answer, however uses O(n) space. Any suggestion on the follow up question to limit space usage?

I was thinking they may try to test agile / scrum process. or communication skills. Any other suggestions?

please ignore, sorry about the dup. Got an error when posting.

for (int i = 0; i < tgt.length; i++) {
	if (tgt[i] == 0) continue;
	int pos = findPos(src, tgt[i]);
	if (i == pos) continue;
	int posZero = findPos(src, tgt[i]);
	if (posZero != i) {
		swap(src[posZero], src[i]);
	}
	swap(src[pos], src[i]);
}

an improvement maybe to cache zero position in src to avoid an lookup.

I would use recursion to solve this problem:

public static boolean IsKPalindrom(char[] arr, int k) {
	int match = 0;
	if (arr.length <= 1) return true;
	// try to match front and back of the string
	for (match = 0; match < (arr.length / 2); match ++) {
		if (arr[match] != arr[arr.length - match - 1]) {
			break;
		}
	}

	if (match >= (arr.length / 2) {
		// Yeah!
		return true;
 	} else if (k == 0) {
		// not palindrom, and we cannot remove any more characters
		return false;
	} else {
		// remove 1 char and call recursively
		return isKPalindrom(arr.subarray(match + 1, arr.length - match - 1), k - 1) ||
			  isKPalindrom(arr.subarray(match, arr.length - match - 2), k - 1);
	}
}

correction...

void rearrange(int *arr, int count)
{
    for (int i = 0; i < count - 1; i++)
    {
        bool fFound = false;
        for (int j = i; j < count; j ++)
        {
            if ((arr[j] > 0) == (i%2==0))
            {
                if (i != j) swap(arr, i, j);
                fFound = true;
		break;
            }
        }
        if (!fFound) break;
    }
}

correction...

public static void Arrange(int[] arr)
{
int pos = 0;
int neg = 0;
for (int i = 0; i < arr.length; i ++) {
if (i%2 == 0) {
for (pos = max(pos, i); pos < arr.length; pos ++) {
if (arr[pos] > 0) break;
}
if (pos >= arr.length) break; // all remaining numbers are negative, exit
if (pos != i) {
swap(arr, pos, i);
pos ++;
}
} else {
for (neg = max (neg, i); neg < arr.length; neg ++) {
if (arr[neg] < 0) break;
}
if (neg >= arr.length) break;
if (neg != i) {
swap (arr, neg, i);
neg ++;
}
}
}
}

public static void Arrange(int[] arr)
{
	int pos = 0;
	int neg = 0;
	for (int i = 0; i < arr.length; i ++) {
		if (i%2 == 0) {
			for (pos = max(pos, i); i < arr.length; i ++) {
				if (arr[pos] > 0) break;
			}
			if (pos >= arr.length) break; // all remaining numbers are negative, exit
			if (pos != i) {
				swap(arr, pos, i);
				pos ++;
			}
		} else {
			for (neg = max (neg, i); i < arr.length; i ++) {
				if (arr[neg] < 0) break;
			}
			if (neg >= arr.length) break;
			if (neg != i) {
				swap (arr, neg, i);
				neg ++;
			}
		}
	}
}

void rearrange(int *arr, int count)
{
    for (int i = 0; i < count - 1; i++)
    {
        bool fFound = false;
        for (int j = i; j < count; j ++)
        {
            if ((arr[j] > 0) == (i%2==0))
            {
                if (i != j) swap(arr, i, j);
                fFound = true;
            }
        }
        if (!fFound) break;
    }
}