Ad
BAN USER- 0of 0 votes
AnswersI recently had a take home assignment for a optimization engineer position at FB. I got 24 hours to finish it however it was suggested to finish under 90 minutes. The problem was to calculate the dot product of sparse matrix (optimize for speed). I wrote following code but got dinged. Not sure what's wrong to not clear even first stage!
- Ad in United States for Advertisement optimization#include <iostream> #include <string> #include <map> #include <sstream> using namespace std; class SparseVector{ private: map<int, double> m_map; int m_size; public: SparseVector(int size){ this->m_size = size; this->m_map = *new map<int, double>(); } void setValue(int i, double value){ if( i < 0 || i > m_size) return; if(value == 0.0){ map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) m_map.erase(it); } else m_map[i] = value; } double getValue(int i){ if( i < 0 || i > m_size) return 0.0; else { map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) return it->second; else return 0.0; } } int getSize(){ return m_size; } static double s_dotProduct(SparseVector a, SparseVector b){ if (a.m_size != b.m_size) return 0.0; double sum = 0.0; if (a.m_map.size() <= b.m_map.size()) { for (map<int, double>::iterator it = a.m_map.begin() ; it != a.m_map.end(); it++) if ((b.m_map.find(it->first)) != b.m_map.end()) sum += a.getValue(it->first) * b.getValue(it->first); } else { for (map<int, double>::iterator it = b.m_map.begin() ; it != b.m_map.end(); it++) if ((a.m_map.find(it->first)) != a.m_map.end()) sum += a.getValue(it->first) * b.getValue(it->first); } return sum; } template <typename T> static string s_ToString(T val) { stringstream stream; stream << val; return stream.str(); } static string s_printSparseVector(SparseVector a) { string s = ""; for (map<int, double>::iterator it = a.m_map.begin(); it!= a.m_map.end(); it++) s += "(" + s_ToString(it->first) + ", " + s_ToString(it->second) + ") "; return s; } }; int main(int argc, char *argv[]){ int lenA = 0, lenB = 0, setValA = 0, setValB = 0; cout << "Enter length for Sparse vector A : " << endl; cin>> lenA; cout << "Enter length for Sparse vector B : " << endl; cin>> lenB; SparseVector v1 = SparseVector(lenA); SparseVector v2 = SparseVector(lenB); double y; int x; cout << "Enter number of set values for Sparse vector A : " << endl; cin >> setValA; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int i = 0; i < setValA; i++){ cin >> x; cin >> y; v1.setValue(x, y); } cout << "Enter number of set values for Sparse vector B : " << endl; cin >> setValB; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int j = 0; j < setValB; j++){ cin >> x; cin >> y; v2.setValue(x, y); } cout <<"Sparse Vector1 = " << SparseVector::s_printSparseVector(vectorA) << endl ; cout <<"Sparse Vector2 = " << SparseVector::s_printSparseVector(vectorB) << endl; cout <<"Dot product of two sparse vectors is = " << SparseVector::s_dotProduct(vectorA, vectorB) << endl; return 0; }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm
void addnum(vector<int> &input, int num)
{
if(input.size() < 1)
return;
int carry = 0; int length = (int)input.size() -1;
int start = length;
while (start >= 0 && (carry > 0 || start == length)){
if(start == length)
input[start] = input[start] + num;
else
input[start] = input[start] + carry;
if(input[start] > 9){
carry = input[start] / 10;
input[start] = input[start] % 10;
}
else
carry = 0;
start--;
}
if(start < 0 && carry >= 1)
input.insert(input.begin(), carry);
}
int main (int argc, char *argv[])
{
vector<int> input = {1, 9, 2, 9, 9, 9};
int num = 9;
addnum(input, num);
for(int i = 0; i < input.size() ; i++)
cout << input[i] << " " ;
return 0;
}
void reverse(string &s, int i, int j)
{
int left = i;
int right = j;
while(left< right)
{
int temp;
temp = s[left];
s[left]= s[right];
s[right] = temp;
left++;
right--;
}
}
int main (int argc, char *ARgv[])
{
string input = "Tiger eats boy and space leftover#@# ";
reverse(input, 0,(int)input.size()-1); //master reverse
int lindex = 0;
int rindex = 0;
while(rindex < (int)input.size())
{
while(input[rindex]!= ' ' && rindex < input.size())
rindex++;
reversestring(input, lindex, rindex-1);
rindex++;
while(input[rindex] == ' ' && rindex < input.size())
rindex++;
lindex = rindex;
}
cout << input << endl;
return 0;
}
int findplus(vector<vector<int>> input, int i , int j, int direction)
{
if(i >= input.size() || i < 0)
return 0;
if(j >= input[0].size() || j < 0)
return 0;
if(input[i][j] == 0)
return 0;
int sum = 1;
if(direction == flat){
sum += findplus(input, i, j+1, horizright) + findplus(input, i, j-1, horizleft) +
findplus(input, i-1, j, verticalup) + findplus(input, i+1, j, verticaldown);
}
else if (direction == horizleft)
sum += findplus(input, i, j-1, horizleft);
else if (direction == horizright)
sum += findplus(input, i, j+1, horizright);
else if(direction == verticalup)
sum += findplus(input, i-1, j, verticalup) ;
else
sum+= findplus(input, i+1, j, verticaldown);
return sum;
}
int main (int argc, char *argv[])
{
vector<vector<int>> matrix= {
{0, 0, 1, 0, 0, 1, 0},
{1, 0, 1, 0, 1, 0, 1 },
{1, 1, 1, 1, 1, 1, 1 },
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}
};
int retval = 0; int maxretval = INT_MIN;
int maxindexx = -1; int maxindexy = -1;
for(int i = 1; i < matrix.size() -1; i++) // rows
for(int j = 1; j < matrix[0].size() -1; j++) //columns
{
if(matrix[i][j] == 1 && matrix[i-1][j] ==1 && matrix[i+1][j] ==1 && matrix[i][j-1] ==1 && matrix[i][j+1] ==1) {
retval = findplus(matrix, i, j, flat);
if(retval > maxretval)
{ maxretval = retval;
maxindexx = i;
maxindexy = j;
}
}
}
cout << "Largest Plus Sign In The Sparse Matrix is = " << retval << " At ( " << maxindexx << " " <<maxindexy << " )" << endl;
return 0;
}
RepSpent 2001-2004 selling UFOs for the government. Have some experience with Internet Marketing Services New York. Set new standards for ...
I also wrote on my comments before submitting to FB that I could have used hash table as well, but map allows me to keep sparse vectors sorted and would help when two vectors are of largely different sizes. I have done some research on this topic before and had read several articles but I guess did not help.
- Ad February 07, 2017Any suggestions would help me improve my performance. Thank you people!