epic 电面 与 online test 面经

readman 发表于 2014-7-29 18:38
第三个都是搜索的枚举吧..你怎么证明你的是最短路径?

补充内容 (2014-7-29 18:52):

说下第三题，其实思路和lc的word ladder 类似。直接上个c++代码吧，大家凑合看一下：

class word {
public:
        string content;
        word *father;
        word(string s) {
                this->content = s;
                father = NULL;
        }
};

vector<string> transform(string s1, string s2) {
        vector<string> path;
        set<string> visited;
        int size = s1.size();
        word *w = new word(s1);
        queue<word*> q;
        q.push(w);
        visited.insert(s1);
        while (!q.empty()) {
                word *cur = q.front();
                q.pop();
                if (cur->content == s2) {
                        while (cur) {
                                path.push_back(cur->content);
                                cur = cur->father;
                        }
                        reverse(path.begin(),path.end());
                        return path;
                }
                for (int i = 0; i < size-1; i++) {
                        string temp = cur->content;
                        swap(temp[i],temp[i+1]);
                        if (visited.find(temp) == visited.end()) {
                                visited.insert(temp);
                                word *w = new word(temp);
                                w->father = cur;
                                q.push(w);
                        }
                }
        }
        return path;
}

EMC 发表于 2014-7-30 08:46
说下第三题，其实思路和lc的word ladder 类似。直接上个c++代码吧，大家凑合看一下：

class word {

哦...不一定是回文 明白了

楼主请问下从online test 到onsite用了多久啊？

doraemonmeng 发表于 2014-8-15 05:16
楼主请问下从online test 到onsite用了多久啊？

onlinetest 两个星期后通知onsite

恭喜楼主！ 等楼主入职内推 木哈哈

楼主你好，第三题career cup上面用了个类似冒泡的算法。
我实现了下：
class Solution {
public :
        // idea: bubble sort
        void convertString( string from_str, string to_str){
              cout << from_str << endl;
               for( unsigned i = 0; i < from_str.size(); i++){
                      if( from_str[i] == to_str[i])
                            continue;
                      // find the same char in target string
                      unsigned j = i;
                      while( from_str[j] != to_str[i]) j++; // will find for sure
                      // move target char at "j" to "i" in str
                      while(j > i){
                            char tmp = from_str[j];
                            from_str[j] = from_str[j-1];
                            from_str[j-1] = tmp;
                           cout << from_str << endl;
                           j--;
                     }
              }
       }
};

马上要Epic Onsite了 楼主能介绍一下onsite的情况吗？