Victor
BAN USER 2of 2 votes
AnswersGiven an array of integers.
 Victor in United States
Move all nonzero elements to the left of all zero elements. Report Duplicate  Flag  PURGE
Facebook Software Engineer Intern Algorithm  2of 2 votes
AnswersThere's a new language which uses the latin alphabet. However, you don't know the order among letters.
 Victor in United States
It could be:
a b c d ...
as it could also be:
b e z a m i ...
You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language. Report Duplicate  Flag  PURGE
Facebook Software Engineer Intern Algorithm  1of 3 votes
AnswersImplement a vectorlike data structure from scratch.
 Victor in Brazil
This question was to be done in C or C++.
Discussion topics:
1. Dealing with out of bounds accesses.
2. What happens when you need to increase the vector's size?
3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back Report Duplicate  Flag  PURGE
Google Software Engineer Intern Data Structures
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;
}

Victor
February 12, 2015 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;
}

Victor
February 11, 2015 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;
}

Victor
February 11, 2015 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, m1, 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, m1, x);
}

Victor
February 11, 2015 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;
}

Victor
February 11, 2015 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.
 Victor February 08, 2015In 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, n1);
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, n1);
}
}
void print_anagrams(const std::string &w)
{
std::string word = w;
anagram(word, word.length()1);
}

Victor
February 06, 2015 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 (ji+1) < length:
length = ji+1
while valid(M):
if seq[i] in S:
if M[seq[i]] == 1:
break
M[seq[i]] = 1
i += 1
if (ji+1) < length:
print seq[i:j+1]
length = ji+1
j += 1
print length

Victor
February 06, 2015 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
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 shouldbe 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();
}

Victor
January 27, 2015 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(Ns+1):
m[i][i+s1] = 0
for j in range(i, i+s):
c = 1
if i <= (j1):
c *= m[i][j1]
if (j+1) <= (i+s1):
c *= m[j+1][i+s1]
m[i][i+s1] += c
print m[0][N1]

Victor
January 26, 2015 I implemented binary search tree iterator and reverse iterator in this pseudocode. 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 inorder 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 inorder 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)

Victor
January 26, 2015 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], lendotidx[i]);
}
int decimal = atoi(byte.c_str());
if (decimal > 255) {
return false;
}
}
return true;
}

Victor
January 24, 2015 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.
BronKerbosch'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.
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.
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;
}
}

Victor
January 21, 2015 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;
}

Victor
January 21, 2015 Hash table with an interface to code/decode the hash values as "browserfriendly" 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.
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.
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 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 = (n1)/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  (n1)/2  1);
mid>prev = makeBST(head, (n1)/2);
return mid;
}

Victor
January 12, 2015 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);
}

Victor
January 12, 2015 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.
 Victor January 12, 2015Sort 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)

Victor
December 05, 2014 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 & (a1);
return a == 0;
}

Victor
December 05, 2014 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_idx1]+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_idx1, delta_deltas, offset, missing);
}
}
missingNumbers(V, mid_idx+1, e, new_m  delta_deltas, new_offset, missing);
}

Victor
December 05, 2014 Open Chat in New Window
Solution in C++:
 Victor February 24, 2015