CareerCup

Keep low, mid, and high indices. Low and high are the points at which everything to the left of low has low importance, and everything to the right of high has high importance (a.k.a. the indices at which new low/high will be insert). Mid is the index you're currently checking. Step through mid and swap until mid and high converge.
Space: O(1)
Time: O(n)

enum Importance
{
	LOW = 0,
	MED = 1,
	HIGH = 2
};

void importancesort(vector<Importance> &patients)
{
	int low = 0, mid = 0, high = patients.size() - 1;
	while (mid <= high)
	{
		switch (patients[mid])
		{
			case LOW: swap(patients[mid++], patients[low++]); break;
			case HIGH: swap(patients[mid], patients[high--]); break;
			default: mid++; break;
		}
	}
}

This is the same algorithm I implemented in C++. Note that I'm using ints for start and end times for simplification.

#include <algorithm>
#include <vector>

struct Event
{
	int start, end;
};

bool mySort(Event a, Event b)
{
	return a.end < b.end;
}

// Note: Events are sorted
void removeIntersecting(std::vector<Event> &events, Event e)
{
	std::vector<Event>::iterator it = events.begin();
	while (it != events.end() && it->start < e.end)
	{
		++it;
	}
	events.erase(events.begin(), it);
}

int maxEvents(std::vector<Event> events)
{
	int result = 0;
	std::sort(events.begin(), events.end(), mySort);
	while (!events.empty())
	{
		++result;
		removeIntersecting(events, events[0]);
	}
	return result;
}

Update: This solution is not optimal for multiple reasons.
1) I used a map, which is typically implemented as a binary tree, so every age insertion is O(log n). I should have used an unordered_map, as the question did not say the output must be sorted, only that the input was.
2) I'm doing a binary search for every age barrier. In worst case, where none of the ages are repeated, that means there will be a binary search for every age. The overall algorithm is O(n log n). (Considering that the worst case would only lead to a little over 100 binary searches, that's not the end of the world, but still, CT's answer above is better.)

Here is CT's answer, replicated in C++ with an unordered_map:

#include <iostream>
#include <unordered_map>

using namespace std;

void countAges(const int ages[], int first, int last, unordered_map<int, int> &ageCounts)
{
	if (ages[first] == ages[last])
	{
		if (ageCounts.find(ages[first]) == ageCounts.end())
		{
			ageCounts[ages[first]] = 0;
		}
		ageCounts[ages[first]] += last - first + 1;
	}
	else
	{
		countAges(ages, first, first + (last - first) / 2, ageCounts);
		countAges(ages, first + (last - first) / 2 + 1, last, ageCounts);
	}
}

void printAgeCounts(const int ages[], int size)
{
	unordered_map<int, int> ageCounts;
	countAges(ages, 0, size - 1, ageCounts);
	for (unordered_map<int, int>::const_iterator it = ageCounts.begin(); it != ageCounts.end(); ++it)
	{
		cout << it->first << ": " << it->second << endl;
	}
}

Good solution. Couple notes in node_level function though:
- Should check if node is NULL before looping (so you don't dereference a NULL pointer on the first iteration of the loop)
- Need to add "return level;" at the end

Time complexity: O(n)
Space complexity: O(n) if you include the result set, O(1) otherwise
Basically, we keep a running total of how many times we've consistently hit the current character, as well as the maximum streak we've had thus far. Whenever we hit a new character, we check if our current streak is better than max, if so, clear the results and update the max streak; if it is the same, just add the current character to it (and if less, do nothing). Then restart the current streak. This doesn't require us to store a previous char because we look forward one character rather than backward, as the null terminator will be recognized as the end of our current streak. Note the isspace check, as the first result set in the example implies that we only want non-space characters in the result.

#include <vector>
#include <string>

using namespace std;

vector<char> getLongestConsecutiveChar(string str)
{
	int curStreak = 0, maxStreak = 0;
	vector<char> results;

	for (int i = 0; i < str.length(); ++i)
	{
		while (isspace(str[i])) // Skip over spaces
		{
			++i;
		}
		++curStreak;
		if (str[i] != str[i + 1])
		{
			if (curStreak > maxStreak)
			{
				maxStreak = curStreak;
				results.clear();
				results.push_back(str[i]);
			}
			else if (curStreak == maxStreak)
			{
				results.push_back(str[i]);
			}
			curStreak = 0;
		}
	}
	return results;
}

I've seen this question on here before. Here's the solution I have typed up from the previous time I saw it (IIRC this isn't the original way I solved it, but rather someone else's answer that had a better solution than mine):

void convertToCircularDLL(Node *root)
{
	static Node *prev;
	static Node *head;

	if (root == NULL)
	{
		return;
	}
	convertToCircularDLL(root->left);
	if (prev == NULL)
	{  // first node in list
		head = root;
	}
	else
	{
		prev->right = root;
		root->left = prev;
	}
	prev = root;
	convertToCircularDLL(root->right); 
	if (prev->right == NULL)
	{ // last node in list
		head->left = prev;
		prev->right = head;
	}
}

EDIT: Thinking about it again, this is wrong. It works...once. If you made tried to convert more than one tree, it wouldn't work because the prev and head pointers are static, so they would still contain data from the previous run. This can be fixed by making them Node** parameters to the function. The initial call can be made with the addresses of two Node pointers initialized to NULL.

Node *prev = NULL, *head = NULL;
convertToCircularDLL(root, &prev, &head);

Implemented your solution in C++:

#include <vector>
using namespace std;

struct Range
{
	int begin, end;
	Range(int a, int b) : begin(a), end(b) {}
};

vector<Range> mergeRanges(vector<Range> input, Range newRange)
{
	vector<Range> output;
	for (vector<Range>::const_iterator it = input.begin(); it != input.end(); ++it)
	{
		if (newRange.end < it->begin || newRange.begin > it->end)
		{
			output.push_back(*it);
		}
		else
		{
			if (it->begin < newRange.begin)
			{
				newRange.begin = it->begin;
			}
			if (it->end > newRange.end)
			{
				newRange.end = it->end;
			}
		}
	}
	output.push_back(newRange);
	return output;
}

It wasn't until I read your answer that I realized the question never stated the output had to be sorted.

@Eric - The solution using regex varies depending on language, but in general, to form the regular expression you would just replace the asterisk (*) with a period (.) because a period matches any single character. However, the regex solution would not meet the O(1) lookup requirement, so it's kind of a moot point.

The O(1) requirement is a very important element to the problem, as it tests your ability to make tradeoffs of memory for speed (or in some cases, speed for memory). With a company like Facebook, a lot of problems they would want to solve would require very fast computation/lookups with large data sets, and would very much be worth storing extra data in order to speed things up.

Just need a recursive function that calls itself with 1 and 2 stairs (if there are enough remaining). Below, my recursive function is called "step", and I also have a "stairs" function which calls it to satisfy the interface.

#include <vector>
#include <string>

using namespace std;

void step(string currentSolution, int remaining, vector<string> &allSolutions)
{
	if (remaining == 0)
	{
		allSolutions.push_back(currentSolution);
		return;
	}

	step(currentSolution + "1", remaining - 1, allSolutions);
	if (remaining > 1)
	{
		step(currentSolution + "2", remaining - 2, allSolutions);
	}
}

vector<string> stairs(int steps)
{
	vector<string> allSolutions;
	step(string(""), steps, allSolutions);
	return allSolutions;
}

Without a space constraint, we can insert all the elements into a binary search tree, then pull them out in order
(Note: std::set is typically implemented as a BST)
O(m * n * log(m * n))

void printSortedWithHeap(int **data, int m, int n)
{
	std::set<int> tree;
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			tree.insert(data[i][j]);
		}
	}
	for (std::set<int>::const_iterator it = tree.begin(); it != tree.end(); ++it)
	{
		printf("%d ", *it);
	}
	printf("\n");
}

With the space constraint, we can keep an array of indices to indicate the position in each row of the lowest value that hasn't been printed, then continuously pull out the lowest value of the current indices until you have printed all the numbers
(Note: I am keeping n indices, which technically is a column, not a row, but it will always be ints, even if the data represents objects of a different kind)
O(m * n * n)

void printSortedSpaceConstrained(int **data, int m, int n)
{
	int toPrint = m * n;
	int index[m];
	for (int i = 0; i < m; ++i)
	{
		index[i] = 0;
	}

	while (toPrint > 0)
	{
		int minValue = INT_MAX;
		int minIndex = 0;
		for (int i = 0; i < m; ++i)
		{
			if (index[i] < n && data[i][index[i]] < minValue)
			{
				minValue = data[i][index[i]];
				minIndex = i;
			}
		}
		printf("%d ", minValue);
		++index[minIndex];
		--toPrint;
	}
	printf("\n");
}

One problem: The function returns void, but you are passing a pointer into it, so if you print out the original string after you call this function, you'll find that it will only print "I". This is because you're replacing every space with a null terminator. You can test this by simply changing your main function to:

int main() 
{ 
	char arr[] = "I wish you a merry Christmas"; 
	inplace_reverse( arr, strlen(arr)); 
	printf("After function call: %s\n", arr); // Note this added print statement
	return 0; 
}

Your output looks like this:

Christmas merry a you wish I
After function call: I

Side note: The question asks for the sentence to be reversed in place, which means you are to modify the original array so that it contains the reversed sentence.

@StrategicCoderForce - I would be surprised to hear someone ask for this without recursion, but if so, I would say probably use a queue - at each node you visit, pull it out of the queue and add its children, and keep doing so until the queue is empty. Of course, you would need to keep track of the depth of each node, so you'd probably want a queue of QNode, where QNode is a struct containing a Node and a depth.

Not the most elegant solution, but like I said, I'd be surprised if they asked you to do this question without recursion.

I went ahead and wrote up some C++ code to test it:

#include <iostream>
#include <queue>

using namespace std;

struct Node
{
	Node *left, *right;
	char data;
	Node(char d) : left(NULL), right(NULL), data(d) {}
};

struct QNode
{
	Node *node;
	int depth;
	QNode(Node *n, int d) : node(n), depth(d) {}
};

int findMaxDepth(Node *head)
{
    queue<QNode> q;
    int depth = 1;
    int maxDepth = 0;
    QNode root(head, depth);
    q.push(root);
    while (!q.empty())
    {
        QNode n = q.front();
        if (n.depth > maxDepth)
        {
        	maxDepth = n.depth;
        }
        if (n.node->left != NULL)
        {
            QNode left(n.node->left, n.depth + 1);
            q.push(left);
        }
        if (n.node->right != NULL)
        {
            QNode right(n.node->right, n.depth + 1);
            q.push(right);
        }
        q.pop();
    }
    return maxDepth;
}

// Note: A-G represent a 3-level balanced binary tree, and H just hangs off to the right of G
int main()
{
	Node *A = new Node('A'); 
	Node *B = new Node('B'); 
	Node *C = new Node('C'); 
	Node *D = new Node('D'); 
	Node *E = new Node('E'); 
	Node *F = new Node('F'); 
	Node *G = new Node('G');
	Node *H = new Node('H');
	B->left = A;
	B->right = C;
	D->left = B;
	D->right = F;
	F->left = E;
	F->right = G;
	G->right = H;
	int max = findMaxDepth(D);
	cout << "Max depth = " << max << endl;
}

Here's what the tree looks like:
    D
 B     F
A C   E G
          H

By splitting the sentence into an array of strings, you're allocating some amount of memory that is dependent on the length of the string, so it's using O(n) space, rather than O(1). Also, I'm not extremely familiar with C#, so I'm not positive, but I assume StringBuilder is duplicating the memory as well.

@Sudhir - The list is generated as you go. node->left becomes the pointer to the previous node in the list, and node->right becomes the pointer to the next node in the list.

More compact, using more STL:

#include <algorithm>
#include <string>

void reverseSentenceString(std::string &str)
{
	int len = str.length();
	for (int i = 0; i < len; ++i)
	{
		int j = i + 1;
		// Find the end of the current word
		while (j < len && str[j] != ' ')
		{
			++j;
		}
		std::reverse(str.begin() + i, str.begin() + j);
		i = j;
	}
	std::reverse(str.begin(), str.end());
}

#include <algorithm> // Gives us std::swap to swap two elements in the array

void reverseWord(char *str, int len)
{
	for (int start = 0, end = len - 1; start < end; ++start, --end)
	{
		std::swap(str[start], str[end]);
	}
}

void reverseSentence(char *str, int len)
{
	// Reverse each word in the sentence
	for (int i = 0; i < len; ++i)
	{
		int j = i + 1;
		// Find the end of the current word
		while (j < len && str[j] != ' ')
		{
			++j;
		}
		reverseWord(&str[i], j - i);
		i = j;
	}
	// Reverse the entire sentence
	reverseWord(str, len);
}

C++ code for this solution:

#include <algorithm> // For std::swap

void reverseWord(char *str, int len)
{
	for (int start = 0, end = len - 1; start < end; ++start, --end)
	{
		std::swap(str[start], str[end]);
	}
}

void reverseSentence(char *str, int len)
{
	// Reverse each word in the sentence
	for (int i = 0; i < len; ++i)
	{
		int j = i + 1;
		// Find the end of the current word
		while (j < len && str[j] != ' ')
		{
			++j;
		}
		reverseWord(&str[i], j - i);
		i = j;
	}
	// Reverse the entire sentence
	reverseWord(str, len);
}

Simple in-place O(n) solution in C++:

#include <string>
#include <algorithm>

void reverseWords(std::string &str)
{
	int len = str.length();
	for (int i = 0; i < len; ++i)
	{
		int j = i + 1;
		// Find the end of the current word
		while (j < len && str[j] != ' ')
		{
			++j;
		}
		// Reverse the word
		for (int start = i, end = j - 1; start < end; ++start, --end)
		{
			std::swap(str[start], str[end]);
		}
		i = j;
	}
}

#include <unordered_map>
#include <vector>

using namespace std;

typedef pair<int, int> Pair;

vector<int> foursum(int in[], int len)
{
	unordered_map<int, Pair> map;
	vector<int> v;
	for (int i = 0; i < len - 1; ++i)
	{
		for (int j = i + 1; j < len; ++j)
		{
			unordered_map<int, Pair>::iterator match = map.find(in[i] + in[j]);
			if (match != map.end())
			{
				v.push_back(match->second.first);
				v.push_back(match->second.second);
				v.push_back(in[i]);
				v.push_back(in[j]);
				return v;
			}
			map[in[i] + in[j]] = Pair(in[i], in[j]);
		}
	}
	return v;
}

#include <unordered_set>

using namespace std;

bool threesum(int in[], int len)
{
	unordered_set<int> set;
	for (int i = 0; i < len; ++i)
	{
		set.insert(in[i]);
	}
	
	for (int i = 0; i < len; ++i)
	{
		for (int j = 0; j < len; ++j)
		{
			if (set.find(-(in[i] + in[j])) != set.end())
			{
				return true;
			}
		}
	}
	return false;
}

I see what you're trying to do here, and there is a way to make it work out. Essentially, using your setup, the way you would remove all rolls that include a 6 would be to remove the bottom row *and* the rightmost column, as each of those represent any pair of rolls that contain a 6. What you're then left with is a 5x5 matrix, which is 25 possibilities out of your original 36.

+	1 2 3 4 5   | 6
                         
1	2 3 4 5 6   | 7
2	3 4 5 6 7   | 8 
3	4 5 6 7 8   | 9 
4	5 6 7 8 9   | 10
5	6 7 8 9 10  | 11
--------------------
6	7 8 9 10 11 | 12

25 / 36 = ~0.69

The more straightforward way to think of it is to consider the dice entirely independent of each other, because the second roll does not depend on the first. So you need only consider the probabilities of each, multiplied together. That is, the probability of not rolling a 6 with each die is 5/6. Then you have:

5/6 * 5/6 = 25/36 = ~.69

#include <map>
#include <string>

using namespace std;

struct Node
{
	string data;
	Node *next;
	Node *random;
};

Node *copyLinkedList(Node *head)
{
	map<Node *, Node *> m;
	Node *it;
	Node *_head = NULL;
	Node *prev = NULL;
	for (it = head; it; it = it->next)
	{
		Node *n = new Node();
		n->data = string(it->data);
		n->next = NULL;
		n->random = NULL;
		m[it] = n;
	}

	for (it = head; it; it = it->next)
	{
		Node *orig = m[it];
		orig->next = m[it->next];
		orig->random = m[it->random];
	}
	return m[head];
}

For my solution, I stored the dictionary as a map of lists, where the key is the first letter of the word, and the list contains all the words that start with that letter.
Using the first letter in the input word, I grab the list from my map, and iterate until I find one that matches. If I find it, I recursively call the same function over the remainder of the input string, until there is no remainder left.

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

map<char, vector<string> > dict;

bool constructible(string word)
{
	if (word.length() == 0)
		return true;

	vector<string> &list = dict[word[0]];
	for (string &w : list)
	{
		if (word.compare(0, w.length(), w) == 0 
		  && constructible(word.substr(w.length())))
			return true;
	}
	return false;
}

int main()
{
	string dictinput[] = {"world","hello","super","hell"};
	for (string str : dictinput)
	{
		dict[str[0]].push_back(str);
	}
	string input[] = {"helloworld","superman","hellohello"};
	for (string str : input)
	{
		cout << str << " : " << constructible(str) << endl;
	}
}

Output:

helloworld : 1
superman : 0
hellohello : 1

Here's the easy-to-read, clean cut approach:

bool offByOneEdit(string s1, string s2)
{
	switch (s1.length() - s2.length())
	{
		case 0:  return offByUpdate(s1, s2);
		case -1: return offByInsert(s1, s2);
		case 1:  return offByInsert(s2, s1);
		default: return false;
	}
}

bool offByUpdate(string s1, string s2)
{
	short errors = 0;
	for (int i = 0; i < s1.length(); ++i)
	{
		if (s1[i] != s2[i] && errors++)
			return false;
	}
	return errors == 1; // A perfect match has 0 errors, there should be 1
}

bool offByInsert(string s1, string s2)
{
	short offset = 0;
	for (int i = 0; i < s1.length(); ++i)
	{
		if (s1[i] != s2[i+offset] && offset++)
			return false;
	}
	return true; // We already checked the length, so we know it's off by 1
}

And here's the one where I get rid of the separate functions and jam everything together, just for fun:

bool offByOne(string s1, string s2)
{
	int s1off = 0, s2off = 0, errors = 0, l1 = s1.length(), l2 = s2.length();
	int slen = l1 < l2 ? l1 : l2;
	if (abs(l1 - l2) > 1)
		return false;
	for (int i = 0; i < slen; ++i)
	{
		if (s1[i+s1off] != s2[i+s2off])
		{
			if (errors++ || s1off || s2off)
				return false;
			if (l1 < l2)
				++s2off;
			else if (l1 > l2)
				++s1off;
		}
	}
	return errors == 1 || (l1 != l2);
}

bool isPalindrome(string str)
{
	for (int a = 0, b = str.length() - 1; a < b; ++a, --b)
	{
		while (!isalpha(str[a]))
			++a;
		while (!isalpha(str[b]))
			--b;
		if (tolower(str[a]) != tolower(str[b]))
			return false;
	}
	return true;
}

This solution handles line breaks without adding extraneous null nodes to the queue.

#include <iostream>
#include <queue>

using namespace std;

struct Node
{
	Node *left;
	Node *right;
	char c;
};

void printTree(Node *root)
{
	queue<Node *> q;
	q.push(root);
	while (!q.empty())
	{
		int max = q.size();
		for (int i = 0; i < max; ++i)
		{
			Node *cur = q.front();
			cout << cur->c;
			if (cur->left) q.push(cur->left);
			if (cur->right) q.push(cur->right);
			q.pop();
		}
		cout << endl;
	}
}

As someone with very little experience with Python, I really enjoy how short and simple this solution looks. However, I'm also curious as to the time complexity (again, I'm not very familiar with Python, so I don't know how efficient these operations are.)

#include <string>

using namespace std;

string pattern(int index)
{
	string last("1"), cur;
	int i = 0;
	while (++i <= index)
	{
		cur.clear();
		char c = last[0];
		int j = 0, count = 1;
		while (++j < last.length())
		{
			if (last[j] == c)
			{
				++count;
			}
			else
			{
				cur += (count + '0');
				cur += c;
				c = last[j];
				count = 1;
			}
		}
		cur += (count + '0');
		cur += c;
		last = cur;
	}
	return cur;
}

Note: This assumes the question meant that you must reach *past* the last element (i.e. if you get to the last element, and it's a 0, you didn't make it). To have it return true for simply reaching the last element, we just need to subtract 1 from the length.

bool canhop(uint data[], uint start, uint length)
{
	for (uint i = data[start]; i > 0; --i)
	{
		if (start + i >= length || canhop(data, start + i, length))
		{
			return true;
		}
	}
	return false;
}

C++ code:

#include <vector>
using namespace std;

void findmissing(vector<int> data, int start, int end, vector<int> &result)
{
	int expected = start + result.size() + 1;
	if (start == end)
	{
		if (data[start] != expected)
		{
			result.push_back(expected);
		}
		return;
	}
	if (data[start] == expected && end - start == data[end] - data[start])
	{
		return;
	}
	int mid = start + (end - start) / 2;
	findmissing(data, start, mid, result);
	findmissing(data, mid + 1, end, result);
}

Explanation:

In the base case, we have a single integer. If that integer does not match what is expected at that index (accounting for missing integers already in the result set), we know that we are missing the number that *is* expected at that index.

In the next case, we can ignore this entire set of numbers if we know the first number is correct, and the difference between the first number and the last number is the same as the difference between the first index and the last index. If the initial data set is complete, this will keep us from ever having to iterate over the data.

Finally, we split the data in half, and recurse on each half. Note: It's very important that we recurse on the left half first, as the two cases above depend on all missing numbers to the left of our current starting index to already exist in the result set.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

void printsorted(vector<string> input)
{
	map< string, vector<string> > list;
	for (vector<string>::const_iterator it = input.begin(); it != input.end(); ++it)
	{
		string str(*it);
		sort(str.begin(), str.end());
		list[str].push_back(*it);
	}
	cout << "{ ";
	for (map< string, vector<string> >::const_iterator it = list.begin(); it != list.end(); ++it)
	{
		if (it != list.begin())
		{
			cout << ", ";
		}
		vector<string> sublist = it->second;
		cout << "{";
		for (int i = 0; i < sublist.size(); ++i)
		{
			if (i != 0)
			{
				cout << ", ";
			}
			cout << sublist[i];
		}
		cout << "}";
	}
	cout << " }" << endl;
}

#include <vector>

struct Point
{
	int x;
	int y;
	Point(int _x, int _y) : x(_x), y(_y) {}
};

struct PointDist
{
	float distsq;
	Point p;
	PointDist(float _distsq, Point _p) : distsq(_distsq), p(_p) {}
};

const Point REF_POINT(5, 5);

void printclosestpoints(Point input[], int inputsize, int k);

int main()
{
	Point input[] = { Point(-2, -4), Point(0, 0), Point(10, 15), Point(5, 6), Point(7, 8), Point(-10, -30) };

	printclosestpoints(input, sizeof(input) / sizeof(input[0]), 2);
}

void printclosestpoints(Point input[], int inputsize, int k)
{
	std::vector<PointDist> results;
	std::vector<PointDist>::const_iterator it;

	for (int i = 0; i < inputsize; ++i)
	{
		int dx = input[i].x - REF_POINT.x;
		int dy = input[i].y - REF_POINT.y;
		float distsq = dx * dx + dy * dy;
		it = results.begin();
		while (it != results.end() && distsq > it->distsq)
		{
			++it;
		}
		if (it != results.end() || results.size() < k)
		{
			results.insert(it, PointDist(distsq, input[i]));
			if (results.size() > k)
			{
				results.erase(results.begin() + k);
			}
		}
	}

	for (it = results.begin(); it != results.end(); ++it)
	{
		printf("(%d, %d)\n", it->p.x, it->p.y, it->distsq);
	}
}