2019年暑期GooGle SWE 凉经

ゞ浴缸里的玫瑰 2022-03-09 04:27 180阅读 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 条评论，180人围观）

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

相关阅读

相关 2019年CVTE凉

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

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

相关豹趣凉经

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

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

相关【2019秋招】面凉经汇总

面经汇总：网易笔试、三汇笔试、大华二面、传化智联一面、核新同花顺复面、浙江移动初面文章目录 1.Web基础 1.1 Ajax了解吗？

灰太狼/ 2023年06月06日 08:09/ 0 赞/ 20 阅读

相关华为面试凉经

吐槽贴！华为果然如传说中的没有面经，哈哈。合肥专场的面试，一面等了两小时，进行一面面试官让做了一个简单的自我介绍，然后开始给我一道题目，用自己熟悉的语言在纸上写出来

深藏阁楼爱情的钟/ 2023年06月05日 12:39/ 0 赞/ 6 阅读

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

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

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

相关 2019年暑期GooGle SWE 凉经

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

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

相关蚂蚁金服凉经

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

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

相关面经~2019年找工作

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

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

相关 2019暑期训练

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

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

相关阿里凉经

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

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