google onsite

第一轮 求2Dmatrix中最长的increasing length

第二轮 给一堆01组成的字符串 所有字符串都是相同长度 这些字符串表示安全的pattern,每个pattern之间可以通过flip任意一个bit进行互相转换 ,给定起始pattern和终止pattern,判断能不能成功转换,所有intermediate状态必须是安全的,非常类似word ladder。follow up:给多个起始状态和多个终止状态

第三轮 给一个字符串 让你计算它的得分 得分计算规则方式如下:每有两个相邻字符是一样的元音字母,则得分加一。follow up1: 给一个字符长度 计算所有长度为该给定长度的字符串的组合方式数量使得该字符串得分为0。follow up2: 如果不是0分而是k分,计算有多少种组合方式。

第四轮 一个奇怪的设计题,给你一个城市,每户人家都有自己的邻居,并且所有人都只能直接访问自己的邻居,有一户人准备写一本族谱,他应该在书上写什么instruction能够把所有住户的名字写在族谱里,注意:住户之间可能重名,并且没有unique identifier。大概就是这个initiator要把书传给自己的邻居,并且在书上为后续拿到书的人写下一些指导,然后最后当这个人拿回书时,书上已经写了所有住户的名字

感觉题都比较常规

follow up1这个可以用滑动窗口做吗 找到得分为0的窗口 然后把窗口里的长度为给定长度的加到结果中

他不是找得分为0的子串 是找所有得分为0的字符串的数量,所以用dp,类似于lc上一道paint house的题

请问楼主 第三轮字符串的组合方式 指的是找到所有的子字符串嘛?还是什么组合?

就是找到所有长度为n并且得分为0的字符串的数量

请问第四题lz怎么做的呢?建一个图 然后dfs吗?

我做的时候设计个好几个类 关键是一个住户只能被访问一次 你可以用一个标志位表示 这一轮主要是聊怎么work 感觉code不是重点

整个流程其实就是一个dfs 你要做的只是避免无限循环

第三题dfs+mem吗?

用dp 类似于paint house