当前位置: 首页 > news >正文

字节跳动(社招)四面算法原题

TikTok 进展

又是一期定时汇报 TikTok 进展的推文。

上周,美国总统拜登签署了价值 950 亿美元的一揽子对外援助法案。

该法案涉及强制字节跳动剥离旗下应用 TikTok 美国业务,即 针对 TikTok 非卖即禁的"强抢行为"开始进入九个月(270 天)的倒计时

签署法案后,TikTok 官号进行了回应:

TikTok 在社交媒体上的回应(原文)
TikTok 在社交媒体上的回应(原文)
TikTok 在社交媒体上的回应(译文)
TikTok 在社交媒体上的回应(译文)

之后的几天,陆续出现过一些谣言,其中不乏「传字节跳动已经在密谋出售 TikTok 事宜」这样的消息。

但很快,就被官号高调辟谣了这些「外媒消息」:

alt

TikTok 代言人,也是现任 CEO 周受资也在海外社交媒体中出镜重申:我们哪儿也不去,准备起诉。事实和宪法都站在我们这一边,期待再次获胜。

alt

...

回归主线。

来一道和「字节跳动(社招)」四面相关的算法题。

据投稿人描述,当时其他问题回答得一般,但该算法题顺利做出,最终通过四面,感觉是被这道题救了一命。

题目描述

平台:LeetCode

题号:1879

给你两个整数数组 nums1nums2,它们长度都为 n

两个数组的 异或值之和 为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (下标从 0 开始)。

比方说,[1,2,3][3,2,1] 的 异或值之和 等于 (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4

请你将 nums2 中的元素重新排列,使得异或值之和最小 。

请你返回重新排列之后的 异或值之和 。

示例 1:

输入:nums1 = [1,2], nums2 = [2,3]

输出:2

解释:将 nums2 重新排列得到 [3,2] 。
异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2 。

示例 2:

输入:nums1 = [1,0,3], nums2 = [5,3,4]

输出:8

解释:将 nums2 重新排列得到 [5,4,3] 。
异或值之和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8 。

提示:

状压 DP

这是一道「状压 DP」模板题。

为了方便,我们令下标从 开始。

「定义 为考虑前 个元素,且对 nums2 的使用情况为 时的最小异或值」。其中 是一个长度为 的二进制数:若 中的第 位为 ,说明 nums2[k] 已被使用;若 中的第 位为 ,说明 nums2[k] 未被使用。

起始时,只有 ,其余均为无穷大 INF 含义为在不考虑任何数,对 nums2 没有任何占用情况时,最小异或值为 。最终 即为答案。

不失一般性考虑 该如何转移,可以以 nums1[i] 是与哪个 nums2[j] 进行配对作为切入点:

  • 由于总共考虑了前 个成员,因此 的数量必然为 ,否则 就不是一个合法状态,跳过转移

  • 枚举 nums1[i] 是与哪一个 nums2[j] 进行配对的,且枚举的 需满足在 中的第 位值为 ,若满足则有

其中 prev 为将 中的第 位进行置零后的二进制数,即 prev = s ^ (1 << j),符号 ⊕ 代表异或操作。

Java 代码:

class Solution {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length, mask = 1 << n, INF = 0x3f3f3f3f;
        int[][] f = new int[n + 10][mask];
        for (int i = 0; i <= n; i++) Arrays.fill(f[i], INF);
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int s = 0; s < mask; s++) {
                if (getCnt(s, n) != i) continue;
                for (int j = 1; j <= n; j++) {
                    if (((s >> (j - 1)) & 1) == 0continue;
                    f[i][s] = Math.min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));
                }
            }
        }
        return f[n][mask - 1];
    }
    int getCnt(int s, int n) {
        int ans = 0;
        for (int i = 0; i < n; i++) ans += (s >> i) & 1;
        return ans;
    }
}

C++ 代码:

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), mask = 1 << n, INF = 0x3f3f3f3f;
        vector<vector<int>> f(n + 10vector<int>(mask, INF));
        f[0][0] = 0;
        auto getCnt = [&](int s, int n) {
            int ans = 0;
            for (int i = 0; i < n; i++) ans += (s >> i) & 1;
            return ans;
        };
        for (int i = 1; i <= n; i++) {
            for (int s = 0; s < mask; s++) {
                if (getCnt(s, n) != i) continue;
                for (int j = 1; j <= n; j++) {
                    if (((s >> (j - 1)) & 1) == 0continue;
                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));
                }
            }
        }
        return f[n][mask - 1];
    }
};

Python 代码:

class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n, mask, INF = len(nums1), 1 << len(nums1), 0x3f3f3f3f
        f = [[INF] * mask for _ in range(n + 10)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for s in range(mask):
                if sum([1 for i in range(n) if (s >> i) & 1]) != i:
                    continue
                for j in range(1, n + 1):
                    if ((s >> (j - 1)) & 1) == 0:
                        continue
                    f[i][s] = min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]))
        return f[n][mask - 1]

TypeScript 代码:

function minimumXORSum(nums1: number[], nums2: number[]): number {
    const n = nums1.length, mask = 1 << n, INF = 0x3f3f3f3f;
    const f: number[][] = new Array(n + 10).fill([]).map(() => new Array(mask).fill(INF));
    f[0][0] = 0;
    const getCnt = (s: number, n: number): number => {
        let ans = 0;
        for (let i = 0; i < n; i++) ans += (s >> i) & 1;
        return ans;
    };
    for (let i = 1; i <= n; i++) {
        for (let s = 0; s < mask; s++) {
            if (getCnt(s, n) !== i) continue;
            for (let j = 1; j <= n; j++) {
                if (((s >> (j - 1)) & 1) === 0continue;
                f[i][s] = Math.min(f[i][s], f[i - 1][s ^ (1 << (j - 1))] + (nums1[i - 1] ^ nums2[j - 1]));
            }
        }
    }
    return f[n][mask - 1];
};
  • 时间复杂度:
  • 空间复杂度:

模拟退火

事实上,这道题还能使用「模拟退火」进行求解。

由于我们可以无限次对 nums2 进行打乱互换,先来思考如何衡量一个 nums2 排列的“好坏”。

一个简单的方式:固定计算 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) 作为衡量当前 nums2 的得分,得分越小,当前的 nums2 排列越好。

迭代开始前先对 nums2 进行一次随机打乱,随后每个回合随机选择 nums2 的两个成员进行互换,并比较互换前后的得分情况,若互换后变好,那么保留该互换操作;若变差,则以一定概率进行重置(重新换回来)。

重复迭代多次,使用一个全局变量 ans 保存下最小异或值之和。

即「模拟退火」的单次迭代基本流程:

  1. 随机选择两个下标,计算「交换下标元素前对应序列的得分」&「交换下标元素后对应序列的得分」
  2. 如果温度下降(交换后的序列更优),进入下一次迭代
  3. 如果温度上升(交换前的序列更优),以「一定的概率」恢复现场(再交换回来)

对于一个能够运用模拟退火求解的问题,最核心的是如何实现 calc 方法(即如何定义一个具体方案的得分),其余均为模板内容。

Java 代码(2024/04/29 可过):

class Solution {
    int N = 400;
    double hi = 1e5, lo = 1e-5, fa = 0.90;
    Random random = new Random(20230823);
    void swap(int[] n, int a, int b) {
        int c = n[a];
        n[a] = n[b];
        n[b] = c;
    }
    int calc() {
        int res = 0;
        for (int i = 0; i < n; i++) res += n1[i] ^ n2[i];
        ans = Math.min(ans, res);
        return res;
    }
    void shuffle(int[] nums) {
        for (int i = n; i > 0; i--) swap(nums, random.nextInt(i), i - 1);
    }
    void sa() {
        shuffle(n2);
        for (double t = hi; t > lo; t *= fa) {
            int a = random.nextInt(n), b = random.nextInt(n);
            int prev = calc();
            swap(n2, a, b);
            int cur = calc(); 
            int diff = cur - prev; 
            if (Math.log(diff / t) >= random.nextDouble()) swap(n2, a, b);
        }
    }
    int[] n1, n2;
    int n;
    int ans = Integer.MAX_VALUE;
    public int minimumXORSum(int[] nums1, int[] nums2) {
        n1 = nums1; n2 = nums2;
        n = n1.length;
        while (N-- > 0) sa();
        return ans;
    }
}
  • 时间复杂度:启发式搜索不讨论时空复杂度
  • 空间复杂度:启发式搜索不讨论时空复杂度

最后

给大伙通知一下 📢 :

全网最低价 LeetCode 会员目前仍可用 ~

📅 年度会员:有效期加赠两个月!!; 季度会员:有效期加赠两周!!

🧧 年度会员:获 66.66 现金红包!!; 季度会员:获 22.22 现金红包!!

🎁 年度会员:参与当月丰厚专属实物抽奖(中奖率 > 30%)!!

专属链接:leetcode.cn/premium/?promoChannel=acoier

我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。

欢迎关注,明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

相关文章:

字节跳动(社招)四面算法原题

TikTok 进展 又是一期定时汇报 TikTok 进展的推文。 上周&#xff0c;美国总统拜登签署了价值 950 亿美元的一揽子对外援助法案。 该法案涉及强制字节跳动剥离旗下应用 TikTok 美国业务&#xff0c;即 针对 TikTok 非卖即禁的"强抢行为"开始进入九个月&#xff08;27…...

车道线检测交通信号识别车辆实时检测

系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 TODO:写完再整理 文章目录 系列文章目录前言车道线检测机器学习前言 认知有限,望大家多多包涵,有什么问题也希望能够与大家多交流,共同成长! 本文先对车道线检测&交通信号识别&…...

用正则表达式打造免费代理IP池

爬虫的过程中&#xff0c;当对方服务器发现你屡次爬取它&#xff0c;可能会遇到被封IP的苦痛&#xff0c;这时IP就应该换啦&#xff0c;打造IP池的意义十分重要&#xff0c;提供免费IP网站有很多&#xff0c;本次用的是西刺代理IP # -*- coding: utf-8 -*- """…...

【每日刷题】Day35

【每日刷题】Day35 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 844. 比较含退格的字符串 - 力扣&#xff08;LeetCode&#xff09; 2. 2487. 从链表中移除节点 - 力…...

Python数据清洗与可视化实践:国际旅游收入数据分析

文章目录 概要整体流程名词解释NumPyPandasMatplotlibre 技术细节数据清洗可视化 小结 概要 在本篇博客中&#xff0c;我们将通过一个实际的案例&#xff0c;演示如何使用Python进行数据清洗和可视化&#xff0c;以分析国际旅游收入数据。我们将使用Python中的Pandas库来进行数…...

前置知识储备

基本认知 什么是模式 在一定环境中解决一些问题的方案&#xff08;通俗来说&#xff1a;特定环境中用固定的套路解决问题&#xff09; 什么是设计模式 设计模式是一套反复被人使用&#xff0c;多数人知晓的&#xff0c;经过分类编目的代码设计经验的总结 设计模式最终的目…...

六月品牌互动营销方案的作用是什么

品牌需要借势营销&#xff0c;六月的六个节日热点&#xff0c;是企业商家不能错过的&#xff0c;如何运用合适的工具/方法借势也同样重要。 互动h5游戏/传单页面发挥不同效果&#xff0c;这份《六月品牌互动营销方案》看看有哪些内容吧~ 1、儿童节 宜&#xff1a;回忆欢乐营销…...

dummy_worker C++ 预占用部分比例cpu资源,人为创造cpu资源紧张

背景 有时候为了C测试程序在cpu资源紧张情况下是否正常&#xff0c;需要人为创造cpu资源紧张 编译方法 g -o dummp_worker dummp_worker.cpp -stdc11 -pthread 使用方法 ./dummp_worker 4 0.2 占用4个cpu核的20%比例的cpu资源 源码 // dummp_worker.cpp #include <c…...

电脑缺失opencl.dll怎么办,轻松解决opencl.dll的多种方法分享

当我们在操作电脑过程中遇到系统提示“由于找不到opencl.dll&#xff0c;无法继续执行代码”&#xff0c;这个错误会导致软件应用无法正常运行。OpenCL.dll作为一个与Open Computing Language&#xff08;开放计算语言&#xff09;相关的动态链接库文件&#xff0c;它在执行需要…...

el-select 点击按钮滚动到选择框顶部

主要代码是在visibleChange 在这个 popper 里面找到 .el-select-dropdown__list let popper ref.$refs.popper const ref this.$refs.select let dom popper.querySelector(.el-select-dropdown__list) setTimeout(() > { dom.scrollIntoView() }, 800) <templat…...

vue 钩子函数updated什么时候触发

触发时机 updated是Vue生命周期钩子函数之一&#xff0c;在组件的数据变化导致虚拟DOM重新渲染并应用到实际DOM之后触发。具体来说&#xff0c;updated会在以下几种情况下被触发&#xff1a; 初始渲染完成后&#xff1a;当组件首次渲染完成并将虚拟DOM渲染到实际DOM之后&#…...

消息队列使用常见问题

一、消息丢失的时机&#xff1f; 生产端消息丢失 问题&#xff1a;因为网络异常导致消息发送失败&#xff0c;此时可能会产生消息丢失的情况&#xff0c;重试后可能产生消息重复生产的情况。 解决&#xff1a;超时重试&#xff0c;并在消费端保证幂等性。 消息队列中消息丢失 …...

常用SQL命令

应用经常需要处理用户的数据&#xff0c;并将用户的数据保存到指定位置&#xff0c;数据库是常用的数据存储工具&#xff0c;数据库是结构化信息或数据的有序集合&#xff0c;几乎所有的关系数据库都使用 SQL 编程语言来查询、操作和定义数据&#xff0c;进行数据访问控制&…...

【neteq】tgcall的调用、neteq的创建及接收侧ReceiveStatisticsImpl统计

G:\CDN\P2P-DEV\Libraries\tg_owt\src\call\call.cc基本是按照原生webrtc的来的:G:\CDN\P2P-DEV\tdesktop-offical\Telegram\ThirdParty\tgcalls\tgcalls\group\GroupInstanceCustomImpl.cpptg对neteq的使用 worker 线程创建call Call的config需要neteqfactory Call::CreateAu…...

使用Python读取las点云,写入las点云,无损坐标精度

目录 1 为什么要写这个博文2 提出一些关键问题3 给出全部代码安装依赖源码&#xff08;laspy v2.x&#xff09; 1 为什么要写这个博文 搜索使用python读写las点云数据&#xff0c;可以找到很多结果。但是&#xff01; 有些只是简单的demo&#xff0c;且没有发现/说明可能遇到的…...

python开发二

python开发二 requests请求模块 requests 是一个常用的 Python 第三方库&#xff0c;用于发送 HTTP 请求。它提供了简洁且易于使用的接口&#xff0c;使得与 Web 服务进行交互变得非常方便。 发送 GET 请求并获取响应 import requestsresponse requests.get("https:/…...

部署JVS服务出现上传文件不可用,问题原因排查。

事情的起因是这样的&#xff0c;部门经理让我部署一下JVS资源共享框架&#xff0c;项目的地址是在这里 项目资源地址 各位小伙伴们做好了&#xff0c;我要开始发车了&#xff0c;全新的“裂开之旅” 简单展示一下如何部署JVS文档 直达链接 撕裂要开始了 本来服务启动的好好…...

机器视觉检测为什么是工业生产的刚需?

机器视觉检测在工业生产中被视为刚需&#xff0c;主要是因为它具备以下几个关键优势&#xff1a; 提高精度与效率&#xff1a;机器视觉系统可以进行高速、高精度的检测。这对于保证产品质量、减少废品非常关键。例如&#xff0c;在生产线上&#xff0c;机器视觉可以迅速识别产品…...

Adobe系列软件安装

双击解压 先运行Creative_Cloud_Set_Up.exe。 完毕后&#xff0c;运行AdobeGenP.exe 先Path&#xff0c;选路径&#xff0c;如 C:\Program Files\Adobe 后Search 最后Patch。 关闭软件&#xff0c;修图&#xff01;...

【FX110】2024外汇市场中交易量最大的货币对是哪个?

作为最大、最流动的金融市场之一&#xff0c;外汇市场每天的交易量高达几万亿美元&#xff0c;涉及到数百种货币。不同货币对的交易活跃程度并不一样&#xff0c;交易者需要根据货币对各自的特点去进行交易。 全年外汇市场中涉及美元的外汇交易超过50%&#xff01; 实际上&…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...