CareerCup

Solution in C++:

#include <vector>

int pmean(const std::vector<int> &V)
{
	int n = V.size();
	int i;
	int sum = 0;
	int pmean = 0;
	int best = 0;
	
	for (i = 0; i < n; ++i) {
		sum += V[i];
	}

	for (i = 0; i < n; ++i) {
		pmean += V[i] * (i+1);
	}
	best = pmean;

	for (i = 0; i < (n-1); ++i) {
		pmean -= sum;
		pmean += V[i] * n;
		if (pmean > best) {
			best = pmean;
		}
	}

	return best;
}

Could you clarify this? I didn't understand.

Solution in C++. It's pretty much the same algorithm as posted by the other people.

#include <vector>
#include <string>
#include <iostream>
#include <set>

typedef std::vector<int> IntVector;
typedef std::vector<IntVector> IntVecVector;

IntVecVector powerset(const IntVector &V)
{
	IntVecVector S;
	int i;
	
	S.push_back(IntVector());

	for (i = 0; i < V.size(); ++i) {
		IntVecVector s = S;
		int j, n = s.size();
		for (j = 0; j < n; ++j) {
			s[j].push_back(V[i]);
		}
		S.insert(S.end(), s.begin(), s.end());
	}

	return S;
}

bool colorful(const IntVecVector &S)
{
	std::set<int> mults;
	int i;

	for (i = 0; i < S.size(); ++i) {
		int j, n = S[i].size();
		int m = 1;
		for (j = 0; j < n; ++j) {
			m *= S[i][j];
		}

		std::pair<std::set<int>::iterator, bool> x = mults.insert(m);
		if (x.second == false) return false;
	}

	return true;
}

int main(int argc, char *argv[])
{
	std::string word = argv[1];
	int i, n = word.length();

	IntVector V;
	V.reserve(n);

	for (i = 0; i < n; ++i) {
		int d = (int)(word[i] - '0');
		V.push_back(d);
	}

	const IntVecVector S = powerset(V);

	bool r = colorful(S);

	if (r) {
		std::cout << "Colorful\n";
	}
	else {
		std::cout << "Not colorful\n";
	}

	return 0;
}

typedef std::vector<std::string> Expression;
typedef std::stack<std::string> Stack;

float solve_rpn(const Expression &E)
{
	float total = 0.0f;
	Stack st;
	std::string t;

	for (const std::string &w: E) {
		if (w == "+" or w == "-" or w == "*" or w == "/") {
			t = st.top();
			st.pop();
			float o2 = strtof(t.c_str(), 0);
			t = st.top();
			st.pop();
			float o1 = strtof(t.c_str(), 0);
			float res;
			if (w == "+") {
				res = o1 + o2;
			}
			else if (w == "-") {
				res = o1 - o2;
			}
			else if (w == "*") {
				res = o1 * o2;
			}
			else {
				if (o2 == 0) throw "ArithmeticException";
				res = o1 / o2;
			}
			st.push(std::to_string(res));
		}
		else {
			float v = strtof(w.c_str(), 0);
			if (v == 0.0F) throw "IllegalArgumentException";
			st.push(w);
		}
	}

	t = st.top();
	st.pop();

	if (!st.empty()) throw "IllegalArgumentException";

	total = strtof(t.c_str(), 0);

	return total;
}

In C++. Pretty straightforward.

typedef std::vector<std::string> Expression;
typedef std::stack<std::string> Stack;

float solve_rpn(const Expression &E)
{
	float total = 0.0f;
	Stack st;
	std::string t;

	for (const std::string &w: E) {
		if (w == "+" or w == "-" or w == "*" or w == "/") {
			t = st.top();
			st.pop();
			float o2 = strtof(t.c_str(), 0);
			t = st.top();
			st.pop();
			float o1 = strtof(t.c_str(), 0);
			float res;
			if (w == "+") {
				res = o1 + o2;
			}
			else if (w == "-") {
				res = o1 - o2;
			}
			else if (w == "*") {
				res = o1 * o2;
			}
			else {
				if (o2 == 0) throw "ArithmeticException";
				res = o1 / o2;
			}
			st.push(std::to_string(res));
		}
		else {
			float v = strtof(w.c_str(), 0);
			if (v == 0.0F) throw "IllegalArgumentException";
			st.push(w);
		}
	}

	t = st.top();
	st.pop();

	if (!st.empty()) throw "IllegalArgumentException";

	total = strtof(t.c_str(), 0);

	return total;
}

First I discover which half is correctly ordered. If the desired value is within the range of this correct half, call the binary search into it. Otherwise, call into the other half. When the binary search comes into a subvector that has a correct ordering, it behaves as the regular binary search.

int f(const std::vector<int> &V, int s, int e, int x)
{
	if (e < s) return -1;
	
	int m = (s+e)/2;
	int mid = V[m];

	if (mid == x) return m;

	if (V[s] <= mid) {
		if (x >= V[s] and x <= mid) {
			return f(V, s, m-1, x);
		}
		return f(V, m+1, e, x);
	}

	if (x >= mid and x <= V[e]) {
		return f(V, m+1, e, x);
	}
	return f(V, s, m-1, x);
}

typedef std::pair<int, int> n10;

n10 numberOfOnesAndZeroes(int n)
{
	if (n == 0) return n10(0, 1);
	if (n == 1) return n10(1, 0);

	n10 _2 = n10(0, 1);
	n10 _1 = n10(1, 0);
	n10 res;

	int i;

	for (i = 1; i < n; ++i) {
		res.first = _1.first + _2.first;
		res.second = _1.second + _2.second;
		_2 = _1;
		_1 = res;
	}

	return res;
}

Is it possible to do better than O(n^2)?

Max heap also works, but it will use O(n) space, unfortunately.

Question 1 is really about out of bounds access, I was the person interviewed. Most of the big languages do not grow the vector until an access becomes inbounds, if you think about it. In C++ this leads to an invalid read of memory, and in Java an exception is thrown.

In C++:

#include <string>
#include <iostream>

void anagram(std::string &word, int n)
{
	if (n <= 0) {
		std::cout << word << "\n";
		return;
	}

	if (word[n] < 'a' or word[n] > 'z') {
		anagram(word, n-1);
		return;
	}

	int i;
	for (i = n; i >= 0; --i) {
		if (word[i] < 'a' or word[i] > 'z')
			continue;

		char tmp = word[i];
		word[i] = word[n];
		word[n] = tmp;
		anagram(word, n-1);
	}
}

void print_anagrams(const std::string &w)
{
	std::string word = w;
	anagram(word, word.length()-1);
}

Implementation in Python

def valid(M):
    for k, v in M.iteritems():
        if v == 0:
            return False

    return True

seq = "abbcbcba"

S = set(['a', 'b', 'c'])

M = dict()
for i in S:
    M[i] = 0

i = 0
j = 0
n = len(seq)
length = n+1

while j < n:
    if seq[j] in S:
        M[seq[j]] += 1

    if valid(M) and (j-i+1) < length:
        length = j-i+1

    while valid(M):
        if seq[i] in S:
            if M[seq[i]] == 1:
                break
            M[seq[i]] -= 1

        i += 1

        if (j-i+1) < length:
            print seq[i:j+1]
            length = j-i+1

    j += 1

print length

Put numbers in a hash table with their frequency. After, extract them to a vector and sort.

O(nlogn) time, O(n) space.

Alternative:
Build a max heap with pairs of <number, frequency> and maintain handlers so that updates to the frequencies are easy. Then, remove k items from the heap.

O(nlogn) time, O(n) space

Incredible solution, autoboli. Probabilities are indeed equal. I'd never have thought it myself.

Keep a list that contains pairs of sets.
1. set of elements that are in a sequence.
2. set of elements that should be neighbours of the elements in the sequence (their left and right pointers).

For every pointer in the pointer array, iterate through this list of ours checking if this pointer is in the set of should-be neighbours. If it is, we merge both sets.

At the end, our defined list will have one structure element for each sequence.

I know my description wasn't very good. I hope you can understand it.

m: size of pointer array
d: number of sequences of elements
Complexity: O(m*d) time

#include <vector>
#include <unordered_set>
#include <list>

class Node {
	public:
	Node *left;
	Node *right;
};

typedef std::vector<Node*> PointerArray;
typedef std::unordered_set<Node*> NodeSet;
typedef std::pair<NodeSet, NodeSet> NodeSetPair;
typedef std::list<NodeSetPair> NPList;

int sequences(const PointerArray &A)
{
	int n = A.size();
	int i;

	NPList l;

	for (i = 0; i < n; ++i) {
		Node *p = A[i];
		NodeSetPair newpair;

		// create sets for this new element
		newpair.first.insert(p);
		newpair.second.insert(p->left);
		newpair.second.insert(p->right);

		NPList::iterator lit, lend;
		for (lit = l.begin(), lend = l.end(); lit != lend; ) {
			const NodeSet &key = lit->first;
			const NodeSet &neighbours = lit->second;

			// merge sets
			if (neighbours.count(p)) {
				newpair.first.insert(key.begin(), key.end());
				newpair.second.insert(neighbours.begin(), neighbours.end());
				
				lit = l.erase(lit);
			}
			else {
				++lit;
			}
		}
		l.push_back(move(newpair));
	}

	return l.size();
}

I believe your solution assumes nodes in the linked list reside in consecutive memory addresses, which is very likely not true.

You actually don't need to recurse. You can iterate over nodes in in-order traversal in O(1) space. Check the first two solutions in this page.

Yes, you are right. Thanks for pointing out. Will fix it

Dynamic programming in Python. Results are in accordance with the Catalan number function.

import sys

N = int(sys.argv[1])

m = [N * [0] for i in range(N)]

for i in range(N):
    m[i][i] = 1

for s in range(2, N+1):
    for i in range(N-s+1):
        m[i][i+s-1] = 0

        for j in range(i, i+s):
            c = 1
            if i <= (j-1):
                c *= m[i][j-1]
            if (j+1) <= (i+s-1):
                c *= m[j+1][i+s-1]

            m[i][i+s-1] += c


print m[0][N-1]

I implemented binary search tree iterator and reverse iterator in this pseudo-code. I still need to put a check of p->parent == null.

Logic is the same as finding two value sum in an array.

// find next node in in-order traversal from left to right
next_l(node p):
	if (p->right) {
		p = p->right;
		while (p->left) {
			p = p->left;
		}
		return p;
	}

	if (p->parent->left == p)
		return p->parent;

	do {	
		p = p->parent;
	} while (p->parent->left != p);

	return p->parent;

// find next node in in-order traversal from right to left
next_r(node q):
	if (p->left) {
		p = p->left;
		while (p->right) {
			p = p->right;
		}
		return p;
	}

	if (p->parent->right == p)
		return p->parent;

	do {	
		p = p->parent;
	} while (p->parent->right != p);

	return p->parent;


findNodes(arg k):

p = root;
q = root;

while (p->left) {
	p = p->left;
}
while (q->right) {
	q = q->right;
}

int sum = p->item + q->item;

while (p != q and sum != k) {
	if (sum > k) {
		q = next_r(q);
	}
	else {
		p = next_l(p);
	}
	sum = p->item + q->item;
}

if (p == q) return false

return (p, q)

In C++:

bool isValidIp(const std::string &ip)
{
	int dotidx[3];
	int idx, len = ip.length();
	int currdot = 0;

	for (idx = 0; idx < len; ++idx) {
		if (ip[idx] == '.') {
			// string has more than 3 dots
			if (currdot > 2) {
				return false;
			}

			dotidx[currdot] = idx+1;
			++currdot;
		}
		else if (ip[idx] < '0' or ip[idx] > '9') {
			// non numeric
			return false;
		}
	}

	// less than 3 dots
	if (currdot != 3)
		return false;

	int i;

	// empty bytes
	for (i = 0; i < 2; ++i) {
		if (dotidx[i]+1 == dotidx[i+1]) {
			return false;
		}
	}
	if (dotidx[2] >= len) {
		return false;
	}

	for (i = 0; i < 3; ++i) {
		std::string byte;
		if (i < 2) {
			byte = ip.substr(dotidx[i], dotidx[i+1]-dotidx[i]-1);
		}
		else {
			byte = ip.substr(dotidx[i], len-dotidx[i]);
		}
		int decimal = atoi(byte.c_str());
		if (decimal > 255) {
			return false;
		}
	}

	return true;
}

This problem seems too complex for being asked in an interview. But I may be wrong and there's a much simpler solution.

Construct a graph where nodes correspond to employees and edges connect employees that are not directly related (i.e. can attend the party together).

Employees with negative value can be discarded in this phase because there's no point in inviting them.

The problem now is to find which clique in the graph gives the highest sum of values. Since we only have positive values in the graph, we can consider only maximal cliques, given larger cliques are always better.

Bron-Kerbosch's algorithm enumerates maximal cliques in graphs, so there you have it.

If all versions have the same probability of having started the bug, I believe binary search is a better solution than linear search.

Test cases can be: 1. no bugs at all. 2. code was buggy, became clean and then got buggy again. 3. bug has been present since the beginning.

Great solution. Bucketing seems to be the best strategy.

To find M subarrays with K elements each to maximize sum(M), you can pick the M*K largest numbers of the array and divide them into M subarrays. The total sum will be the largest possible.

For this, sort the array in descending order and pick the first M*K numbers.

If I undestood it correctly, the question doesn't allow using a new array.

Can you clarify this question? Isn't it just a matter of finding the MxK largest numbers in the array?

The trick is to store values into the empty end of the larger array inwards. This way you'll never store to a position whose value hasn't been evaluated. Assuming arrays are in ascending order and the empty end of the array A is at the right.

void merge(int * restrict A, int nA, int * restrict B, int nB)
{
	int k = nA - 1;
	int j = nB - 1;
	int i = nA - nB - 1;

	while (k >= 0) {
		if (i < 0) {
			A[k] = B[j];
			--j;
		}
		else if (j < 0) {
			A[k] = A[i];
			--i;
		}
		else if (A[i] > B[j]) {
			A[k] = A[i];
			--i;
		}
		else {
			A[k] = B[j];
			--j;
		}
		--k;
	}
}

Keep a map storing the last occurrence of each character in the original sequence.

Whenever you stumble upon a character that is already present in the subsequence you are considering, reset the start position of the subsequence to the index right after the last occurrence of this conflicting character.

Every time you find a character that can be added to the subsequence, check if the new length is better than the best length so far.

#include <string>
#include <map>

int longest(const std::string &word)
{
	if (word.empty()) return 0;

	std::map<char, int> last_occurrence;

	for (const char &c: word) {
		last_occurrence[c] = -1;
	}

	int i, start = 0, length = 1, best_length = 1;
	last_occurrence[word[0]] = 0;

	int n = word.length();
	for (i = 1; i < n; ++i) {
		int c = word[i];
		int lo = last_occurrence[c];

		if (lo >= start) {
			start = lo + 1;
			length = i - start + 1;
		}
		else {
			++length;
			if (length > best_length)
				best_length = length;
		}

		last_occurrence[c] = i;
	}

	return best_length;
}

Hash table with an interface to code/decode the hash values as "browser-friendly" ASCII strings. Base64 or Base56 are good choices for this.

Speed can be improved by using caching. The most visited URLs and their hashes would be maintained in a caching hash table that is kept in main memory.

Yes, you are correct. A* does seem to the better. Also the problem provides a very good heuristic, which makes things easier.

Skorpius: I divided it into multiple hash tables because one table wouldn't fit into memory. Technically they might be the same thing, since you can read only the desired chunk of the big table file.

Bharat: check if strings whose hashes collided are indeed equal or not, as every hash table in history.

gameboy1024: I agree that loading chunks is demanding, but I don't see any alternative. You still need to read the original file one time in the first place.

Great solution. But A* is overkill in this case, since there'd be no edges with cost more than 1. BFS would then give the shortest path with lower complexity than Dijkstra and A*, if I recall correctly.

Backtracking also works well.

Assuming each URL has 20 characters, the file would have 800 GB.

Divide it in chunks of 8 GB (taking measures to not cut an URL halfway through) and create one hash table for each on a first run. These hash tables need to be stored to files, naturally.

On the second run, for each URL, look for collisions in each of the 100 hash tables. The first URL with no collisions is the first unique.

This is the best solution. O(n) in time and O(1) in space.

Very nice!

This solution is very similar to the ones already posted, but no one has given a working findMid function (as far as I believe).

n is the length of the list. I use it to calculate how far I should iterate until I reach the mid.

Node *getMid(Node *first, int n) {
	Node *p = first;
	int m = (n-1)/2;
	int i;
	for (i = 0; i < m; ++i) {
		p = p->next;
	}
	return p;
}

Node *makeBST(Node *head, int n) {
	if ((n == 0) || !head) return 0;

	Node *mid = getMid(head, n);
	mid->next = makeBST(mid->next, n - (n-1)/2 - 1);
	mid->prev = makeBST(head, (n-1)/2);
	return mid;
}

I believe your findMin has the logic wrong. You are going all the way to the end instead of stopping at the middle, no?

Yes, I can read. This is why the very first sentence of my answer says I only covered the simple case

My solution works for the case where each list node contains only one character.

The idea is to recurse all the way to the end, and then compare each character from the end to the beginning (by the ways of returning from recursion) with the character pointed by p. This pointer p is advanced by each recursive function call. For this to work, p needed to be a pointer to pointer. So yeah, not very simple.

I didn't code the check to end the algorithm when the middle of the list is reached.

bool pal(Node**p, Node *q) {
	if (!q) return true;

        // recurse to the end
	if (pal(p, q->next) == false) {
		return false;
	}

	if ((*p)->item != q->item) {
		return false;
	}

        // this is where the pointer p is advanced
	*p = (*p)->next;
	return true;
}

bool palindrome(const List &l) {
	Node *p = l.head->next;
	return pal(&p, p);
}

You can't copy the elements to an auxiliary structure, though.

For every node in B, check if the subtree rooted at this node is equal to the tree A.

Solution in C.

bool subset(Node *A, Node *B) {
	if (!A) return true;
	bool check = check_subset(A, B);
	if (check) return true;
	return subset(A, B->left) || subset(A, B->right);
}

bool check_subset(Node *p, Node *q) {
	if (!p) return true;
	if (!q) return false;
	if (p->id != q->id) return false;
	return check_subset(p->left, q->left) && check_subset(p->right, q->right);
}

That trick of comparing graph traversal strings (present in the book) doesn't seem to work in this case, in which we look for subsets and not subtrees.

Sort the elements of B present in A by counting sort. Sort the remaining using whatever sorting algorithm you want.

In Python 3:

A = [4,2,7,6,8,9,1,3,2,5,6]
B = [6,3,4,1]

Bdict = dict()

for i in B:
    Bdict[i] = 0

for j in A:
    if j in Bdict:
        Bdict[j] += 1

Output = []

for i in B:
    count = Bdict[i]
    for k in range(count):
        Output.append(i)

A.sort()

for j in A:
    if j not in Bdict:
        Output.append(j)

print(Output)

A power of 2, when represented as binary number, is one bit 1 with all the remaining bits 0.

This code below flips the rightmost bit 1 of an integer. If the resulting number becomes zero, you know it had only one bit 1 before, thus a power of 2.

int power2(int a)
{
	a = a & (a-1);

	return a == 0;
}

This is O(n) if you want the largest number.

I liked your idea to check whether there are missing numbers in each half (by subtracting one end from another and comparing to the number of elements). Clever and simple.

It works, but it's not O(logn)

This solution only recurses into one half of the array. There may be missing numbers in both halves at the same time, though.

Your solution is O(nlogn) and isn't correct if there are consecutive missing number. For instance:

[1, 3, 5, 6, 8, 9]

Solution in C++. It's O(logn) by performing binary search. It always controls how many missing numbers there are in each half in order to avoid unnecessary searches.

void missingNumbers(const IntVector &V, int s, int e, int m, int offset, IntVector *missing)
{
	if (m == 0) return;
	if (s > e) return;

	int mid_idx = (s+e)/2;
	int mid_element = V[mid_idx];

	int new_offset = mid_element - (mid_idx+1);
	int delta_offset = new_offset - offset;

	int new_m = m;
	int delta_m = 0;
	int delta_deltas = delta_offset - delta_m;

	if (delta_offset > 0) {
		int j = (mid_idx > 0) ? V[mid_idx-1]+1 : 1;

		for (; j < mid_element; ++j) {
			missing->push_back(j);
			--new_m;
		}

		delta_m = m - new_m;
		delta_deltas = delta_offset - delta_m;

		if (delta_deltas > 0) {
			missingNumbers(V, s, mid_idx-1, delta_deltas, offset, missing);
		}
	}

	missingNumbers(V, mid_idx+1, e, new_m - delta_deltas, new_offset, missing);
}