2019年暑期GooGle SWE 凉经

ゞ浴缸里的玫瑰 2022-03-09 04:27 140阅读 0赞

今天刚刚面了Google的SWE实习生，面试官人很好。也没有自我介绍和介绍项目的环节，上来就刚算法了。

题目：

有两个字符串str1和str2,两个字符串中可能出现'a'-'z'，‘\*’，‘？’字符。其中？可以匹配任意字符。\*可以匹配任意字符串，包括空串。提问两个字符串能否匹配。我用了特别复杂的迭代。但是应该可以用动态规划

Q1. s1, s2
    a-z?*  a:a, ?:a, *:, *:a, *:abc
    public boolean s(String str1,String str2){
        if(str1.equals(“”)&&str2.equals(“”)||str1==null&&str2==null){
            return true;
    }
    else{
        int pre_i=0;
        int pre_j=0;
            for(int j=0,i=0;j<str2.length()&&i<str1.length();){
            if(str1.charAt(i)==’?’||str2.charAt(i)==’?’||str1.charAt(i)
            ==str2.charAt(i)){
                i++;
                j++;
                continue;
            }
    if(str1.charAt(i)==’*’){
        for(int k=j;k<=str2.length();k++){
        if(i+1==str1.length()) {
            if(s(“”,str2.substring(k,str2.length()){return true;}
    
    }else     if(s(str1.substring(i+1,str1.length()),str2.substring(k,str2.length()){return true;}else return false;
        }
    
    }
    if(str2.charAt(j)==’*’){
        for(int k=i;k<=str1.length();k++){
    if(i+1==str1.length()) {
            if(s(“”,str2.substring(k,str2.length()){return true;}
    
    }else if(s(str1.substring(i+1,str1.length()),str2.substring(k,str2.length()){return true;}else return false;
        }
    
    }
        }
        if(i==str1.length()){return true;}
    else return false;
    }
    }
    
    Length O(n), * O(m)
    Time complexity
    
    O(n^m) -> (n * n)

最后迭代复杂度也没有算出来，凉。。。

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019年CVTE凉

pring的特点 mysql oracle区别 redis,数据库不一致的情况 redis的持久化策略登陆模块怎么实现，登陆到一台服务器，另外两台怎么知...

r囧r小猫/ 2024年04月20日 11:01/ 0 赞/ 23 阅读

相关 2019暑期集训总结

在你经历过风吹雨打之后，也许会伤痕累累，但是当雨后的第一缕阳光投射到你那苍白、憔悴的脸庞时，你应该欣喜若狂，并不是因为阳关的温暖，而是在苦了心志，劳了筋骨，饿了体肤之后，...

系统管理员/ 2024年04月17日 23:14/ 0 赞/ 32 阅读

相关豹趣凉经

豹趣一面： 1. 自我介绍 2. C++智能指针 3. 链表和数组 4. 内存管理 5. 项目 6. 计算量 7. 实现2D碰撞 8. 自动规划路径（建模

╰半橙微兮°/ 2023年08月17日 15:39/ 0 赞/ 82 阅读

相关九鼎无双一面面经【凉】

> 题主在BOSS直聘投的简历自我介绍项目+实习介绍垃圾回收垃圾的起源判断垃圾垃圾算法垃圾收集器（三色标记-STAB）

左手的ㄟ右手/ 2022年12月30日 10:41/ 0 赞/ 157 阅读

相关【面经】已凉：小米一面

自我介绍项目问题 AJAX HTTP-报文结构单例模式-双端检锁 Cookie和Session,如果客户禁用了Cookie，怎么

以你之姓@/ 2022年12月09日 02:24/ 0 赞/ 205 阅读

相关 2019年暑期GooGle SWE 凉经

今天刚刚面了Google的SWE实习生，面试官人很好。也没有自我介绍和介绍项目的环节，上来就刚算法了。题目：有两个字符串str1和str2,两个字符串中可能出现'

ゞ浴缸里的玫瑰/ 2022年03月09日 04:27/ 0 赞/ 141 阅读

相关蚂蚁金服凉经

第一次面试第一次面试就面了蚂蚁金服，首先先感谢内推的学姐。但是我表现得真的很不好emmmm，下面说一下凉经过程手机震动！显示杭州面试官：你好，请问

水深无声/ 2022年02月26日 03:38/ 0 赞/ 374 阅读

相关面经~2019年找工作

鄙人找的是Java开发工作,简单记录一下找工作中的几个要点: 1.找工作首先要做的第一件事情就是调整心态,很重要,心态的状态对自身能力的发挥有很大的影响!

快来打我*/ 2022年02月12日 11:09/ 0 赞/ 206 阅读

相关 2019暑期训练

牛客多校： <table> <tbody> <tr> <td style="text-align:center;"> </td> <td

Myth丶恋晨/ 2021年10月23日 09:49/ 0 赞/ 289 阅读

相关阿里凉经

1.自我介绍 2.C++容器的使用场景和底层 3.泛型编程（模板如何是不同对象传入的时候产生的结果是不一样的） 4.四次挥手的过程以及状态的改变 5.链表是否有

迷南。/ 2021年10月19日 05:20/ 0 赞/ 308 阅读