CareerCup

Your code does not handle if int a[] = {3}
Correct me if I am wrong. Thats a special case.

- anonymous March 31, 2015 | Flag Reply

#include <iostream>
#include <string>

using namespace std;

void parse(string s, bool multiline = false) {
    size_t m_end = s.find("*/");
    if (multiline && m_end == string::npos) {
        return;
    }
    int n = s.size();
    string output = "";
    size_t m_start = s.find("/*");
    if (m_start != string::npos) {
        output += string(s,0,(int)m_start);
    }
    size_t s_start = s.find("//");
    if (m_end != string::npos) {
        int end = s_start!=string::npos? s_start-1: n-1;
        output += string(s,m_end+2,end-m_end-1);
    } else if (s_start != string::npos) {
        output += string(s,0,(int)s_start);
    } else if (m_start == string::npos) {
        output += s;
    }

    cout << "output : " << output << "\n";
}

int main() {
    parse("abc//def");
    parse("abc/*def");
    parse("abc/*def*/ xyz");
    parse("asd*/def", true);
    parse("asd*/def // sd", true);
    parse("asd*/", true);
    parse("// asd");
}

- anonymous March 30, 2015 | Flag Reply

Something similar : {{{ #include <iostream> #include <vector> #include <unordered_map> using namespace std; unordered_map<int, int> getFreqMap(int m, int n) { unordered_map<int, int> freq; vector<int> freq_vec; for (int i = 1; i <= n; ++i) { freq_vec.push_back(i); } for (int i = 2; i <= m; ++i) { vector<int> new_vec; for (int k = 0; k < freq_vec.size(); ++k) { for (int j = 1; j <= n; ++j) { new_vec.push_back(freq_vec[k]+j); } } freq_vec = new_vec; } for (int i = 0; i < freq_vec.size(); ++i) { freq[freq_vec[i]]++; } return freq; } typedef unordered_map<int,int>::iterator It; void printMap(unordered_map<int,int>& freq){ for (It it= freq.begin(); it != freq.end(); ++it) { cout << it->first << " : " << it->second << "\n"; } cout << "************************************\n"; } int main() { unordered_map<int, int > freq = getFreqMap(3,2); printMap(freq); freq = getFreqMap(2,3); printMap(freq); freq = getFreqMap(3,3); printMap(freq); } }} - anonymous March 14, 2015 | Flag Reply

{{{ #include <iostream> #include <vector> #include <unordered_set> using namespace std; void buildHash(string& s, int pos, int n, unordered_set<string>& dict) { dict.insert(s); char c = '*'; for (int i = pos; i < n; ++i) { swap(s[i],c); buildHash(s,i+1, n, dict); swap(s[i],c); } } void printDict(unordered_set<string>& dict) { cout << "Dict has " << dict.size() << "\n"; for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) { cout << *it << "\n"; } } int main() { vector<string> input = {"hazem", "ahmed", "moustafa", "fizo"}; unordered_set<string> dict; // build dict for (int i = 0; i < input.size(); ++i) { buildHash(input[i], 0, input[i].size(), dict); } //printDict(dict); bool res = dict.find("fizoo") != dict.end(); cout << res << "\n"; res = dict.find("fizo") != dict.end(); cout << res << "\n"; res = dict.find("m**stafa") != dict.end(); cout << res << "\n"; res = dict.find("m******") != dict.end(); cout << res << "\n"; res = dict.find("m*******") != dict.end(); cout << res << "\n"; res = dict.find("*****") != dict.end(); cout << res << "\n"; } }} - anonymous March 13, 2015 | Flag Reply

{{ #include <iostream>
#include <ctype.h>

using namespace std;

bool isPalin(string str) {
int n = str.size();
if (n==0) return false;
int s = 0;
int e = n-1;
bool palin = false;
// note the = sign , to handle case like A$ which is a palin
while(s <= e) {
if (!isalpha(str[s]) && !isdigit(str[s])) {
s++;
continue;
}
if (!isalpha(str[e]) && !isdigit(str[e])) {
e--;
continue;
}

palin = true; // handles the case where we have just one alpha num
if (str[e] != str[s]) {
palin = false;
break;
}
s++;
e--;
}
return palin;
}
int main() {
cout << "is palin : " << isPalin("ABA") << "\n";
cout << "is palin : " << isPalin("A$A") << "\n";
cout << "is palin : " << isPalin("A$#A") << "\n";
cout << "is palin : " << isPalin("A11$#12A") << "\n";
cout << "is palin : " << isPalin("A21$#12A") << "\n";
cout << "is palin : " << isPalin("A21$") << "\n";
cout << "is palin : " << isPalin("A$") << "\n";
cout << "is palin : " << isPalin("$*") << "\n";
} }}

- anonymous March 12, 2015 | Flag Reply

{{ #include <iostream>
#include <vector>

using namespace std;

bool sumExists(vector<int>& a, int target) {
int n = a.size();
if (n == 0) return false;
if (a[0] == target) return true;
int s = 0;
int sum = a[0];
int i = 1;
while(i < n) {
if (sum + a[i] < target){
sum += a[i];
i++;
} else if (sum + a[i] > target) {
sum -= a[s];
s++;
} else {
return true;
}
}
return false;
}

int main() {
vector<int> a = {23,5,4,7,2,11};
cout << "sum exists : " << sumExists(a,20) << "\n";
cout << "sum exists : " << sumExists(a,28) << "\n";
cout << "sum exists : " << sumExists(a,11) << "\n";
cout << "sum exists : " << sumExists(a,190) << "\n";
cout << "sum exists : " << sumExists(a,23) << "\n";
a = {1,2};
cout << "sum exists : " << sumExists(a,3) << "\n";
} }}

- anonymous March 12, 2015 | Flag Reply

#include <iostream>
#include <string>
#include <stack>
#include <limits.h>

using namespace std;

bool validate(string s) {
    string& last = s;
    while(last.find("(00)") != string::npos) {
        int i = 0;
        int n = last.size();
        string temp="";
        while(i < n) {
            if (string(last, i, 4) == "(00)") {
                i += 4;
                temp += "0";
            } else {
                temp.append(1,last[i]);
                i++;
            }
        }
        last = temp;
    }

    return (last == "0" ? true : false);
}

int getDepth(string s) {
    if (validate(s) == false) {
        return -1;
    }

    int n = s.size();
    stack<char> st;
    int depth = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            st.push(s[i]);
        } else if (s[i] == ')') {
            st.pop();
        }
        depth = max(depth, (int)st.size());
    }
    return depth;
}

int main() {
    cout << getDepth("(00)") << "\n";
    cout << getDepth("(00)0") << "\n";
    cout << getDepth("((00)0)") << "\n";
    cout << getDepth("((00)00)") << "\n";
    cout << getDepth("((00)(00))") << "\n";
    cout << getDepth("((00)0(00))") << "\n";
    cout << getDepth("((00)(0o))") << "\n";
    cout << getDepth("()") << "\n";
    cout << getDepth("(0)") << "\n";
    cout << getDepth("((0((00)0))(00))") << "\n";
}

- anonymous March 05, 2015 | Flag Reply

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <unordered_set>

using namespace std;

vector<string> getRepeated(string s, int l) {
    int n = s.size();
    vector<string> result;
    if (n < 2 || n < l) {
        return result;
    }

    unordered_set<long long> done_set;
    unordered_set<long long> seen_set;
    long long val = 0;
    for (int i =0; i < n; ++i) {
        if (i < l) {
            val = val + pow(7,l-i-1)*(long)s[i];
        } else {
            cout << "val : " << val << "\tat " << i << "\n";
            if (seen_set.find(val) == seen_set.end()) {
                seen_set.insert(val);
            } else if (done_set.find(val) == done_set.end()) {
                result.push_back(string(s,i-l,l));
                done_set.insert(val);
            }
            val = val*7 - pow(7,l)*(long long)s[i-l] + (long long)s[i];
        }
    }

    //check for the last char
    if (seen_set.find(val) != seen_set.end() && done_set.find(val) == done_set.end()) {
        result.push_back(string(s,n-l,l));
    }
    return result;
}

void printVec(vector<string>& a) {
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << "\t";
    }
    cout << "\n**************\n";
}

int main() {
    vector<string> res;
    res = getRepeated("ABCBCAABC",3);
    printVec(res);
    res = getRepeated("ABCBAABC",2);
    printVec(res);
    res = getRepeated("ACC",1);
    printVec(res);
    res = getRepeated("ACC",3);
    printVec(res);
    res = getRepeated("ACCDC",3);
    printVec(res);
    res = getRepeated("ACCCACCCC",4);
    printVec(res);
    res = getRepeated("ACCCACCCCA",4);
    printVec(res);
}

- anonymous March 04, 2015 | Flag Reply

#include <iostream>
#include <string>
#include <limits.h>
#include <algorithm>

using namespace std;


int getMinDiff(string s, string w1, string w2) {
    int count = 0;
    int n = s.size();
    int p1 = -1;
    int p2 = -1;
    int minDiff = INT_MAX;
    for (int i = 0; i < n; ++i) {
        while(i < n && s[i] == ' ') i++;
        int j = i;
        while(j < n && s[j] != ' ') j++;
        if (j > i) {
            string word = string(s,i,j-i);
            count++;
            //cout << "word : " << word  << "\t" << count << "\n";
            if (word == w1) {
                //cout << "found " << w1 << " at " << count << "\n";
                p1 = count;
            } 
            if (word == w2) {
                //cout << "found " << w2 << " at " << count << "\n";
                p2 = count;
            }
        }
        i = j;

        if (p1 != -1 && p2 != -1) {
            minDiff = min(minDiff, p2-p1);
        }
    }

    return minDiff != INT_MAX ? minDiff : -1;
}

int main() {
    cout << "Min diff : " << getMinDiff("hello how are you", "how", "you") << "\n";
    cout << "Min diff : " << getMinDiff("hello how are you", "you", "you") << "\n";
    cout << "Min diff : " << getMinDiff("hello how are you", "you", "are") << "\n";
    cout << "Min diff : " << getMinDiff("hello how are you", "youkhask", "jare") << "\n";
    cout << "Min diff : " << getMinDiff("h", "youkhask", "jare") << "\n";
    cout << "Min diff : " << getMinDiff("     hello     ", "hello", "hello") << "\n";
    cout << "Min diff : " << getMinDiff("     hello     are   ", "hello", "are") << "\n";
}

- anonymous March 04, 2015 | Flag Reply

#include <iostream>
#include <vector>

using namespace std;

char getSmallest(vector<char>& chars, char c, int l, int h, int n) {
    int m = (l+h)/2;
    if (chars[m] > c) {
        if (m > 0 && chars[m-1] > c) {
            return getSmallest(chars, c, l, m-1,n);
        } else {
            return chars[m];
        }
    } else if (chars[m] < c) {
        if (m == n-1) {
            return chars[0];
        } else {
            return getSmallest(chars, c, m+1,h,n);
        }
    } else {
        if (m == n-1) {
            return chars[0];
        } else {
            return chars[m+1];
        }
    }
}

int main() {
    vector<char> chars;
    chars.push_back('c');
    chars.push_back('f');
    chars.push_back('j');
    chars.push_back('p');
    chars.push_back('v');
    cout << "Smallest : " << getSmallest(chars, 'c',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'z',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'k',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'a',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'v',0,4,5) << "\n";
    cout << "Smallest : " << getSmallest(chars, 'j',0,4,5) << "\n";

    vector<char> chars2;
    chars2.push_back('c');
    cout << "Smallest : " << getSmallest(chars2, 'j',0,0,1) << "\n";
    cout << "Smallest : " << getSmallest(chars2, 'a',0,0,1) << "\n";
    cout << "Smallest : " << getSmallest(chars2, 'c',0,0,1) << "\n";

    chars2.push_back('d');
    cout << "Smallest : " << getSmallest(chars2, 'c',0,1,2) << "\n";
    cout << "Smallest : " << getSmallest(chars2, 'd',0,1,2) << "\n";
}

- anonymous March 04, 2015 | Flag Reply

#include <iostream>
#include <vector>
#include <math.h>
#include <queue>

using namespace std;

struct Point {
    int x,y;
    Point(int a,int b) : x(a), y(b) {}
};

struct PointWithDist {
    int id;
    double dist;
    PointWithDist(int i, double d) : id(i),  dist(d) {}
};

class Compare {
    public :
    bool operator() (const PointWithDist& a, const PointWithDist& b) const {
        return a.dist < b.dist;
    }
};

double calcDist(Point& a, Point& b) {
    double x = abs(a.x-b.x);
    double y = abs(a.y-b.y);
    return sqrt(pow(x,2)+pow(y,2));
}

vector<Point> findNearest(Point c, int m, vector<Point>& points) {
    priority_queue<PointWithDist, vector<PointWithDist>, Compare> pq;
    for (int i = 0; i < points.size(); ++i) {
        double d = calcDist(c,points[i]);
        if (pq.size() < m) {
            pq.push(PointWithDist(i,d));
        } else if (pq.size() > 0 && d < pq.top().dist) {
            pq.pop();
            pq.push(PointWithDist(i, d));
        }
        cout << "pq.top : " << pq.top().dist << "\n";
    }

    vector<Point> result;
    while(!pq.empty()) {
        result.push_back(points[pq.top().id]);
        pq.pop();
    }
    return result;
}

int main() {
    vector<Point> points;
    points.push_back(Point(0,1));
    points.push_back(Point(0,2));
    points.push_back(Point(0,4));
    points.push_back(Point(0,2));
    points.push_back(Point(2,4));
    vector<Point> result = findNearest(Point(0,0),3, points);
    for (int i =0; i < result.size(); ++i) {
        cout << "x : " << result[i].x << "\ty : " << result[i].y << "\n";
    }
}

- anonymous March 04, 2015 | Flag Reply

int getPalin(vector<int>& num) {
int n = num.size();
if (n == 0) {
return 0;
}
vector<vector<bool> > palin;
for (int i = 0; i < n; ++i) {
cout << "n : " << n << "\n";
vector<bool> cur_vec(n+1,false);
cout << "cur vec size : " << cur_vec.size() << "\n";
cur_vec[1] = true;
palin.push_back(cur_vec);
}

int max = 1;
for (int l = 2; l <= n; ++l) {
for (int i = 0; i <= n-l; ++i) {
if (palin[i+1][l-2] == true && num[i] == num[i+l-1]) {
palin[i][l] = true;
max = l;
}
}
}
return max;
}

- anonymous March 03, 2015 | Flag Reply

Make a vector <pair<number, count>> (O(n) - space and O(n) time)
then do quickselect on this vector with k = size of the vector, size - 1, size - 2. (all 3 take O(n) time).

Thus, O(n) space and O(n) time

- anonymous January 08, 2013 | Flag Reply