Nick
BAN USERThis 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;
}

Nick
March 18, 2015 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;
}
}

Nick
March 16, 2015 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 nonspace 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;
}

Nick
March 15, 2015 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);

Nick
March 14, 2015 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;
}

Nick
March 14, 2015 @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;
}

Nick
March 14, 2015 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");
}

Nick
March 13, 2015 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.
 Nick January 19, 2015@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: AG represent a 3level 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

Nick
January 18, 2015 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.
 Nick January 18, 2015More 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());
}

Nick
January 17, 2015 #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);
}

Nick
January 17, 2015 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);
}

Nick
January 17, 2015 Simple inplace 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;
}
}

Nick
January 14, 2015 #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;
}

Nick
January 14, 2015 #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;
}

Nick
January 13, 2015 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];
}

Nick
January 12, 2015 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

Nick
January 11, 2015 Here's the easytoread, 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);
}

Nick
January 10, 2015 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;
}
}

Nick
January 08, 2015 #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;
}

Nick
January 06, 2015 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;
}

Nick
January 04, 2015 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;
}

Nick
January 04, 2015 #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);
}
}

Nick
January 02, 2015 Open Chat in New Window
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)
 Nick March 22, 2015