谷歌(Google)技术面试——在线评估问题(一)

news/2024/4/19 17:35:05/

谷歌(Google)面试过程的第一步,你可能会收到一个在线评估链接。 评估有效期为 7 天,包含两个编码问题,需要在一小时内完成。 以下是一些供你练习的在线评估问题

在本章结尾处,还提供了有关 Google 面试不同阶段的更多详细信息。

重复叠加字符串匹配

给定两个字符串 a 和 b,寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1。

注意:字符串 “abc” 重复叠加 0 次是 “”,重复叠加 1 次是 “abc”,重复叠加 2 次是 “abcabc”。

示例 1

输入:a = “abcd”, b = “cdabcdab”
输出:3
解释:a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b是其子串。

示例 2

输入:a = “a”, b = “aa”
输出:2

示例 3

输入:a = “a”, b = “a”
输出:1

示例 4

输入:a = “abc”, b = “wxyz”
输出:-1

提示

  • 1 <= a.length <= 104
  • 1 <= b.length <= 104
  • a 和 b 由小写英文字母组成

我们可以通过模拟的方式来解决这个问题。具体来说,可以不断叠加字符串 a 直到 b 成为叠加后的字符串 a 的子串,或者叠加次数达到一定的限制。

示例代码

def repeatedStringMatch(a, b):n = len(b) // len(a) + 2 # 计算叠加次数的上限for i in range(1, n + 1):if b in a * i:return ireturn -1# 示例 1
a = "abcd"
b = "cdabcdab"
print(repeatedStringMatch(a, b)) # 输出:3# 示例 2
a = "a"
b = "aa"
print(repeatedStringMatch(a, b)) # 输出:2# 示例 3
a = "a"
b = "a"
print(repeatedStringMatch(a, b)) # 输出:1# 示例 4
a = "abc"
b = "wxyz"
print(repeatedStringMatch(a, b)) # 输出:-1

这个函数首先计算叠加次数的上限 n,然后在循环中,依次尝试叠加 1 到 n 次字符串 a,检查叠加后的字符串是否包含 b,如果包含,则返回当前叠加次数。如果循环结束后仍然没有找到符合条件的叠加次数,则返回 -1。

K 个空花盆

n 个灯泡排成一行,编号从 1 到 n 。最初,所有灯泡都关闭。每天 只打开一个 灯泡,直到 n 天后所有灯泡都打开。

给你一个长度为 n 的灯泡数组 blubs ,其中 bulbs[i] = x 意味着在第 (i+1) 天,我们会把在位置 x 的灯泡打开,其中 i 从 0 开始,x 从 1 开始。

给你一个整数 k ,请返回恰好有两个打开的灯泡,且它们中间 正好 有 k 个 全部关闭的 灯泡的 最小的天数 。如果不存在这种情况,返回 -1 。

示例 1

输入: bulbs = [1,3,2],k = 1
输出:2
解释
第一天 bulbs[0] = 1,打开第一个灯泡 [1,0,0]
第二天 bulbs[1] = 3,打开第三个灯泡 [1,0,1]
第三天 bulbs[2] = 2,打开第二个灯泡 [1,1,1]
返回2,因为在第二天,两个打开的灯泡之间恰好有一个关闭的灯泡。

示例 2

输入:bulbs = [1,2,3],k = 1
输出:-1

提示

  • n == bulbs.length
  • 1 <= n <= 2 * 104
  • 1 <= bulbs[i] <= n
  • bulbs 是一个由从 1到 n 的数字构成的排列
  • 0 <= k <= 2 * 104

我们可以通过模拟的方式来解决这个问题。具体来说,我们可以遍历数组 bulbs,记录每个灯泡打开的位置,然后查找其中间有 k 个全部关闭的最小天数。

示例代码

def kEmptySlots(bulbs, k):n = len(bulbs)days = [0] * n # 记录每个位置上灯泡打开的天数for i in range(n):days[bulbs[i] - 1] = i + 1 # 记录每个灯泡的打开天数left, right = 0, k + 1min_days = float('inf')# 循环查找最小天数while right < n:for i in range(left + 1, right):if days[i] < days[left] or days[i] < days[right]:left, right = i, i + k + 1breakelse:min_days = min(min_days, max(days[left], days[right]))left, right = right, right + k + 1return min_days if min_days != float('inf') else -1# 示例 1
bulbs1 = [1,3,2]
k1 = 1
print(kEmptySlots(bulbs1, k1)) # 输出:2# 示例 2
bulbs2 = [1,2,3]
k2 = 1
print(kEmptySlots(bulbs2, k2)) # 输出:-1

这个函数首先遍历数组 bulbs,记录每个灯泡打开的天数,并初始化左右指针。然后在循环中,遍历数组找到两个灯泡之间有 k 个全部关闭的情况,更新左右指针。如果找到了这样的情况,则更新最小天数;否则继续查找。最后返回最小天数,如果不存在这样的情况,则返回 -1。


http://www.ppmy.cn/news/1404974.html

相关文章

最新AI工具系统ChatGPT网站运营源码SparkAi系统V6.0版本,GPTs应用、AI绘画、AI换脸、垫图混图、Suno-v3-AI音乐生成大模型全支持

一、前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持GPT…

酷开科技智慧AI让酷开系统大显身手!

时代的浪潮汹涌而至&#xff0c;人工智能作为技术革新和产业变革的重要引擎&#xff0c;正深刻地影响着各行各业。在科技的海洋中&#xff0c;AI技术正逐渐渗透到我们的日常生活中&#xff0c;为我们带来前所未有的便捷和智慧。酷开科技用技术探索智慧AI&#xff0c;别看它只是…

微服务(基础篇-007-RabbitMQ部署指南)

目录 05-RabbitMQ快速入门--介绍和安装_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1LQ4y127n4?p65&vd_source60a35a11f813c6dff0b76089e5e138cc 1.单机部署 1.1.下载镜像 1.2.安装MQ 2.集群部署 2.1.集群分类 2.2.设置网络 视频地址&#xff1a; 05-Rab…

达梦数据库用户与权限管理

达梦数据库用户与权限管理 用户管理口令策略管理用户资源限制 权限管理一般权限特殊权限 角色管理 用户管理 达梦数据库安装后创建的内置用户&#xff1a; SYS&#xff1a;内置用户&#xff0c;不允许登录。该用户下有常用的数据字典&#xff1b;SYSDBA&#xff1a;系统管理员…

Linux(05) Debian 系统修改主机名

查看主机名 方法1&#xff1a;hostname hostname 方法2&#xff1a;cat etc/hostname cat /etc/hostname 如果在创建Linux系统的时候忘记修改主机名&#xff0c;可以采用以下的方式来修改主机名称。 修改主机名 注意&#xff0c;在linux中下划线“_”可能是无效的字符&…

elment UI el-date-picker 月份组件选定后提交后台页面显示正常,提交后台字段变成时区格式

需求&#xff1a;要实现一个日期的月份选择<el-date-picker :typeformData.dateType :value-formatdateFormat v-modelformData.leaveFactoryDateplaceholder选择月份></el-date-picker>错误示例&#xff1a;将日期显示类型(type)dateType或将日期绑定值的格式(val…

Linux网络编程一(协议、TCP协议、UDP、socket编程、TCP服务器端及客户端)

文章目录 协议1、分层模型结构2、网络应用程序设计模式3、ARP协议4、IP协议5、UDP协议6、TCP协议 Socket编程1、网络套接字(socket)2、网络字节序3、IP地址转换4、一系列函数5、TCP通信流程分析 第二次更新&#xff0c;自己再重新梳理一遍… 协议 协议&#xff1a;指一组规则&…

Android Studio学习7——常用控件view

Android控件 双击shift键——>搜索想要找的文件 Ctrlshift回车——>补全“&#xff1b;”号 CtrlX——>删除一行&#xff0c;只需把鼠标放在那一行 windows自带字体

深入探索Linux的lsof命令

在Linux系统中&#xff0c;了解哪些文件被哪些进程打开对于系统管理和问题诊断是极其重要的。这正是lsof命令&#xff0c;即List Open Files&#xff0c;发挥其强大功能的场景。本文旨在详细介绍lsof的起源、底层原理、参数意义&#xff0c;常见用法&#xff0c;并详解其返回结…

Hive初始化元数据库(默认是derby数据库)时候出现缺少方法的错误com.google.common.base.Preconditions

错误的出现&#xff1a; 下载好hive后&#xff0c;初始化元数据库&#xff08;使用内置derby数据测试&#xff09;&#xff0c;出现报错 初始化hive元数据&#xff1a;schematool -dbType derby -initSchema 这个原因是与 Hive 和 Hadoop 版本的 Guava 版本不一样导致的。 解决…

CSS层叠样式表学习(2)

&#xff08;大家好&#xff0c;今天我们将继续来学习CSS&#xff08;2&#xff09;的相关知识&#xff0c;大家可以在评论区进行互动答疑哦~加油&#xff01;&#x1f495;&#xff09; 目录 二、CSS基础选择器 2.1 CSS选择器的作用 2.2 选择器分类 2.3 标签选择器 2.…

动态规划(Dynamic Programming)详解

动态规划&#xff08;Dynamic Programming&#xff0c;简称DP&#xff09;就像是个聪明的厨师&#xff0c;他懂得怎样把一道复杂的菜肴分成一小块一小块来做&#xff0c;而且他知道怎么利用之前做好的部分&#xff0c;避免重复劳动&#xff0c;最后拼凑成美味佳肴。 比如&…

Debian 配置国内软件源

为什么需要&#xff1f; Debian安装好之后默认是没有软件源的&#xff0c;只能通过本身的光盘上的软件进行安装&#xff0c;这样明显是不能够满足我们的需要的&#xff0c;考虑到国内的上网速度以及环境&#xff0c;配置一个国内的阿里镜像源是最好的选择。 使用 sudo vim /…

更高效、更简洁的 SQL 语句编写丨DolphinDB 基于宏变量的元编程模式详解

元编程&#xff08;Metaprogramming&#xff09;指在程序运行时操作或者创建程序的一种编程技术&#xff0c;简而言之就是使用代码编写代码。通过元编程将原本静态的代码通过动态的脚本生成&#xff0c;使程序员可以创建更加灵活的代码以提升编程效率。 在 DolphinDB 中&#…

Python中主要数据结构的使用

文章目录 数组队列 queue双端队列 deque栈 stack优先队列 priority_queue集合 set映射/字典 map 数组 使用内置类型list实现&#xff0c;主要有如下操作&#xff1a; array [] array.append(1) length len(array) if not array:# 列表为空print("array is empty"…

QT使用数据库和proC数据库

一&#xff0c;QT使用数据库 数据库就是保存数据的文件。可以存储大量数据&#xff0c;包括插入数据、更新数据、截取数据等。用专业术语来说&#xff0c;数据库是“按照数据结构来组织、存储和管理数据的仓库”。 什么时候需要数据库&#xff1f;在嵌入式里&#xff0…

Zookeeper脑裂解决方案

Zookeeper脑裂原因&#xff1a; 主要原因是Zookeeper集群和Zookeeper client判断超时并不能做到完全同步&#xff0c;也就是说可能一前一后&#xff0c;如果是集群先于client发现&#xff0c;那就会出现上面的情况。同时&#xff0c;在发现并切换后通知各个客户端也有先后快慢…

【C++】哈希之位图

目录 一、位图概念二、海量数据面试题 一、位图概念 假如有40亿个无重复且没有排序的无符号整数&#xff0c;给一个无符号整数&#xff0c;如何判断这个整数是否在这40亿个数中&#xff1f; 我们用以前的思路有这些&#xff1a; 把这40亿个数遍历一遍&#xff0c;直到找到为…

隐私计算实训营第七讲-隐语SCQL的架构详细拆解

隐私计算实训营第七讲-隐语SCQL的架构详细拆解 文章目录 隐私计算实训营第七讲-隐语SCQL的架构详细拆解1.SCQL Overview1.1 多方数据分析场景1.2 多方数据分析技术路线1.2.1 TEE SQL方案1.2.2 MPC SQL方案 1.3 Secure Collaborative Query Language(SCQL)1.3.1 SCQL 系统组件1.…

C#字典学习笔记

using System; using System.Collections.Generic;class Program {private static Dictionary<string, string> myDictionary new Dictionary<string, string>();//字典索引必须是唯一的&#xff0c;值可以不是static void Main(){// 向静态成员 myDictionary 添加…