`

Google面试题(八)

阅读更多
1. 给你一个长度为N的链表。N很大,但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个,且它们是完全随机的(出现概率均等)。

2. 给你一个数组A[1..n],请你在O(n)的时间里构造一个新的数组B[1..n],使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。

Solution:
1. 由于不知道N多大,因此不能使用[0, n]之间的等概率随机整数。遍历链表,给每个元素赋一个0到1之间的随机数作为权重(像Treap一样),最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍,然后从后往前再扫一遍。也就是说,线性时间构造两个新数组,P[i]=A[1]*A[2]*...*A[i],Q[i]=A[n]*A[n-1]*...*A[i]。于是,B[i]=P[i-1]*Q[i+1]。
分享到:
评论

相关推荐

    GOOGLE面试题集锦

    GOOGLE面试题集锦 在 IT 行业中,面试是企业选拔人才的重要步骤之一,而 Google 作为全球顶尖的科技公司,其面试方式也备受关注。Google 面试题集锦就是一个集合了 Google 面试题的资源,涵盖了逻辑、数学、算法等...

    11谷歌面试题精讲

    11谷歌面试题精讲

    程序员面试题精选 C++ 算法 微软 google

    程序员面试题精选 C++ 算法 微软 google 程序员面试题精选 C++ 算法 微软 google

    微软面试题解答google微软等大公司面试题

    微软公司面试人员的面试题解答,google微软等大公司面试题,软件架构师的设计。

    15个Google面试题以及答案

    15个Google面试题以及答案。对于的相关职位产品经理、软件工程师等。

    08-谷歌面试题-08-谷歌面试题

    谷歌面试题解析 本资源摘要信息中,我们将对谷歌面试题进行详细的解析和知识点总结。 知识点1:数据库基本操作 在面试题中,我们可以看到基本的数据库操作命令,如create database、use database、create table、...

    google面试题.pdf

    ### Google面试题解析 #### 一、一辆校车能装下多少个高尔夫球? **职位:** 产品经理 **解析:** 这类问题考察应聘者的逻辑思维能力和数学估算能力。解题步骤如下: 1. **估计尺寸:** 先估计一辆标准校车的...

    BAT谷歌微软等各IT公司互联网C++ JAVA 计算机笔试面试真题复习资料108个文档合集.zip

    C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案.docx c++笔试题汇总.pdf C++经典面试题库 附带参考答案.docx C++语言程序设计试题.docx C++面试题笔试题 CC+...

    google面试题题及数学趣题

    标题《Google面试题及数学趣题》涉及的内容主要涵盖了两大部分:Google的面试题目分析以及一些锻炼思维能力的数学趣题。Google面试题作为IT行业求职者关注的焦点,它们不仅是面试的门槛,更被视为衡量应聘者技术水平...

    google公司笔试面试题合集

    以下是对"google公司笔试面试题合集"中可能包含的知识点的详细解析: 1. **算法与数据结构**: - 面试中常见的算法题包括排序(快速排序、归并排序、堆排序等)、查找(二分查找、哈希表查找)、图论(最短路径、...

    google(谷歌)笔试面试题

    根据给定文件的信息,我们可以提炼出一系列与Google(谷歌)笔试面试相关的知识点,涉及编程、算法、计算机系统原理等多个方面。 ### 1. 递归函数的理解与应用 #### 标题:`int cal(int x)` 函数分析 **描述**: ...

    各个公司面试题 面试题

    在IT行业的面试中,面试题通常涵盖了广泛的领域,包括但不限于编程语言、数据结构、算法、操作系统、计算机网络、数据库管理、软件工程、项目管理、云计算、人工智能、前端开发、后端开发等。以下是对这些常见面试题...

    mit 教授整理的google 面试题

    【谷歌面试题解析】 在科技巨头谷歌的面试过程中,算法和数据结构的掌握是至关重要的。这份由MIT(麻省理工学院)教授整理的资料,旨在帮助求职者充分准备谷歌的面试挑战。以下是对其中核心知识点的详细解读。 1. ...

    最新微软谷歌Google面试题怪题

    【微软和谷歌面试题解析】 微软和谷歌等顶级科技公司的面试题目往往别具一格,旨在测试应聘者的逻辑思维、创新能力和快速反应能力。这些题目并非寻找标准答案,而是评估应聘者的思维方式和解决问题的策略。 1. **...

    网络管理员面试题,IT技术支持面试题

    这里是两份详细的面试资料和习题,在很多公司的面试中,都是以此两份面试题作为模板,其中有很多经典的提问,答案不唯一,希望有心的读者能够自己去BAIDU,GOOGLE查找。这里不提供答案。

    程序员面试题精选100题-何海涛

    《程序员面试题精选100题—何海涛》是一份详实的IT面试准备资料,由何海涛整理发布,旨在帮助应届毕业生和求职者准备面向微软、谷歌等知名科技公司的面试。此资料不仅收录了精选的100道面试题目,还提供了详细的解题...

    微软、Google等面试题

    从给定的文件信息来看,这里探讨的主题是程序员面试题,特别是那些来自知名科技公司如微软、Google等的面试题目。文件中提到的“程序员面试题精选100题”显然是一个精心挑选的集合,旨在帮助应届毕业生和求职者更好...

    Google的15道面试题与答案

    1. **递归问题解决**:在第一道面试题中,涉及的是一个逻辑推理和递归的问题。妻子们需要通过观察其他丈夫的行为来判断自己的丈夫是否偷情。这个问题展示了递归思维的应用,即解决问题的过程可以分解为更小的相同或...

    Google面试题

    在准备Google面试的过程中,了解和掌握相关技术和面试技巧至关重要。Google作为全球领先的科技公司,其面试过程往往涉及广泛的计算机科学基础知识、编程技能以及问题解决能力。对于Java开发者来说,尤其需要扎实的...

Global site tag (gtag.js) - Google Analytics