一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2234|回复: 30
收起左侧

Linkedin 新鲜面经

[复制链接] |试试Instant~ |关注本帖
NANA1123 发表于 2014-10-3 06:00:01 | 显示全部楼层 |阅读模式

2014(7-9月) 码农类 硕士 全职@Linkedin - 网上海投 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚刚面完Linkedin,发面经求RP~
question1:.1point3acres缃
/**
* Given two words as Strings, determine if they are isomorphic. Two words are called isomorphic
* if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all
* occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters
* may map to the same letter, but a letter may map to itself.
*
* Example:.鐣欏璁哄潧-涓浜-涓夊垎鍦
*   given "foo", "app"; returns true. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
*     we can map 'f' -> 'a' and 'o' -> 'p'. 1point3acres.com/bbs
*
*   given "foo", "boa"; returns false
*     we can map 'f' -> 'b', 'o' -> 'o', we can't map 'o' -> 'a'. from: 1point3acres.com/bbs
*
*   given "bar", "foo"; returns false
*     we can't map both 'a' and 'r' to 'o'. From 1point 3acres bbs
*
*   given "turtle", "tletur"; returns true
*     we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' ->'r'
*
*   given "ab", "ca"; returns true
*     we can map 'a' -> 'c', 'b' -> 'a'
*/
question2:
public interface FirstCommonAncestor {

    /**
     * Given two nodes of a tree,
. 鍥磋鎴戜滑@1point 3 acres     * method should return the deepest common ancestor of those nodes.
     *
     *          A
     *         / \
     *        B   C
     *       / \
     *      D   E
     *         / \
     *        G   F
     *
     *  commonAncestor(D, F) = B
     *  commonAncestor(C, G) = A
     *  commonAncestor(E, B) = B
     */
    Node commonAncestor(Node one, Node two);
}
. 1point3acres.com/bbs
class Node {

    final Node parent;
    final Node left;
    final Node right;


    public Node(Node parent, Node left, Node right) {
        this.parent = parent;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        this.left = left;
        this.right = right;
    }. 1point 3acres 璁哄潧

    bool isRoot() {

        return parent == null;
    }
}

评分

1

查看全部评分

北美农民 发表于 2014-10-4 01:50:35 | 显示全部楼层
不要把买买提的风气带到地里来。

就算lz是女的,这俩题男生也不见得能一次bug free。
回复 支持 1 反对 0

使用道具 举报

tjmd 发表于 2014-10-3 08:54:22 | 显示全部楼层
第一太简单了:.鐣欏璁哄潧-涓浜-涓夊垎鍦

int GetAlphaPos(char c)
        {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(c>= 'A' && c<='Z')
                        return c-'A';
               
                if(c>= 'a' && c<='z')
                        return c-'a';
        . more info on 1point3acres.com
                throw exception("Check the possible input");
        }

        bool IsIsomorphic(const string& str1, const string& str2)
        {
                if(str1.empty() || str2.empty() || str1.length() != str2.length())
                        return false;

                int numOfNewCharacter1 = 0, numOfNewCharacter2 = 0;. more info on 1point3acres.com
                unsigned char record1[26], record2[26];
                memset(record1, 0, 26);
                memset(record2, 0, 26);

                for(int i = 0; i < str1.length(); i++)
                {
                        int pos1 = GetAlphaPos(str1[i]);. 1point3acres.com/bbs
                        if(record1[pos1] == 0)        
                                record1[pos1] = ++numOfNewCharacter1;

                        int pos2 = GetAlphaPos(str2[i]);
                        if(record2[pos2] == 0)        
                                record2[pos2] = ++numOfNewCharacter2;

                        if(numOfNewCharacter1 != numOfNewCharacter2)
                                return false;     
                }               
                return true;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        }
回复 支持 反对

使用道具 举报

eecsece 发表于 2014-10-3 09:35:37 | 显示全部楼层
用了两个map

bool isIsomorphic(string s1, string s2){
        if(s1.length()==0&&s2.length()==0)
                return true;
        if(s1.length()==0||s2.length()==0||s1.length()!=s2.length())
                return false;
        map<char,char> mapping;
        map<char,char> reverse_map;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        for(int i=0;i<s1.length();i++){
                if(mapping.find(s1[i])!=mapping.end()||reverse_map.find(s2[i])!=reverse_map.end()){
                        if(mapping[s1[i]]!=s2[i]||reverse_map[s2[i]]!=s1[i])
                                return false;. Waral 鍗氬鏈夋洿澶氭枃绔,
                }else{
                        mapping[s1[i]]=s2[i];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        reverse_map[s2[i]]=s1[i];
                }
        }
        return true;
}
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-3 09:38:55 | 显示全部楼层
这两道是挺简单呀,恭喜lz
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-3 10:47:53 | 显示全部楼层
eecsece 发表于 2014-10-3 09:35
用了两个map
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
bool isIsomorphic(string s1, string s2){

我也是用的这个方法~
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-3 10:49:29 | 显示全部楼层
austurela 发表于 2014-10-3 09:38
这两道是挺简单呀,恭喜lz

嗯...半个小时写完了两题剩下时间都在跟interviewer唠嗑...
回复 支持 反对

使用道具 举报

eecsece 发表于 2014-10-3 12:21:14 | 显示全部楼层
NANA1123 发表于 2014-10-3 10:47
我也是用的这个方法~

期待楼主下文!楼主加油
回复 支持 反对

使用道具 举报

tjmd 发表于 2014-10-3 17:27:17 | 显示全部楼层
NANA1123 发表于 2014-10-3 10:47
我也是用的这个方法~

算法面试能随便用map,hash, sort 的库函数吗? 第一个题算法很简单,时间复杂度就是O(n),用map时间复杂度是O(n*logn) 吧?感觉国外大公司的面试题比想象的简单多了,楼主是面实习生?
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2014-10-3 19:20:21 | 显示全部楼层
eecsece 发表于 2014-10-3 09:35
用了两个map

bool isIsomorphic(string s1, string s2){

对, 我觉得这个方法是最简单最明了的把
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2014-10-3 19:22:06 | 显示全部楼层
NANA1123 发表于 2014-10-3 10:49
嗯...半个小时写完了两题剩下时间都在跟interviewer唠嗑...

第二题就是记录两个节点回溯到根的路径, 然后比较这两个路径分叉的地方吗?
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-3 21:43:58 | 显示全部楼层
tjmd 发表于 2014-10-3 17:27
算法面试能随便用map,hash, sort 的库函数吗? 第一个题算法很简单,时间复杂度就是O(n),用map时间复杂 ...

hash map 是O(n), 这题应该还是要map吧,仅仅count是不够的
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-3 21:45:42 | 显示全部楼层
lhh_NJU 发表于 2014-10-3 19:22
第二题就是记录两个节点回溯到根的路径, 然后比较这两个路径分叉的地方吗?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
嗯嗯,我是用hash set存一个回溯路径再回溯另一个找重复
回复 支持 反对

使用道具 举报

TonyJang 发表于 2014-10-3 22:03:56 | 显示全部楼层
tjmd 发表于 2014-10-3 17:27. 1point3acres.com/bbs
算法面试能随便用map,hash, sort 的库函数吗? 第一个题算法很简单,时间复杂度就是O(n),用map时间复杂 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
LZ是个女的,不具有普适性,你就老老实实刷题吧
回复 支持 反对

使用道具 举报

readman 发表于 2014-10-3 22:45:29 | 显示全部楼层
TonyJang 发表于 2014-10-3 22:03
LZ是个女的,不具有普适性,你就老老实实刷题吧

这题的难度 一看就是给萌妹纸的
回复 支持 反对

使用道具 举报

readman 发表于 2014-10-3 22:45:59 | 显示全部楼层
TonyJang 发表于 2014-10-3 22:03
LZ是个女的,不具有普适性,你就老老实实刷题吧

我一看第二题有父节点就笑了
回复 支持 反对

使用道具 举报

eecsece 发表于 2014-10-3 23:28:12 | 显示全部楼层
tjmd 发表于 2014-10-3 17:27
算法面试能随便用map,hash, sort 的库函数吗? 第一个题算法很简单,时间复杂度就是O(n),用map时间复杂 ...

只要把map换成unordered_map就是O(n)了~
回复 支持 反对

使用道具 举报

fate7612 发表于 2014-10-4 00:07:50 | 显示全部楼层
恭喜LZ!. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
问一个小问题…如果用两个map去做,那么foo ap应该也是可以return true的。不需要考虑字母个数的问题吗?谢谢!
回复 支持 反对

使用道具 举报

 楼主| NANA1123 发表于 2014-10-4 01:44:38 | 显示全部楼层
fate7612 发表于 2014-10-4 00:07
恭喜LZ!
问一个小问题…如果用两个map去做,那么foo ap应该也是可以return true的。不需要考虑字母个数的 ...

刚开始要判断两个string长度是否相等
回复 支持 反对

使用道具 举报

fate7612 发表于 2014-10-4 03:05:35 | 显示全部楼层
NANA1123 发表于 2014-10-3 12:44
刚开始要判断两个string长度是否相等

了解了。。多谢LZ,祝顺利!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表