• 谢工在GitChat 11推荐

    忘我之乘积;及蓄水池抽样精妙解法

    今日面试题:忘我之乘积 给你一个数组A[1..n],请你在O(n)的时间里构造一个新的数组B[1..n],使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。 蓄水池抽样(Reservoir Sampling)问题分析 问题: 要求从N个元…...

  • 谢工在GitChat 4推荐

    单链表和之恋和海枯石烂题之分析

    两个单链表(singly linked list),每一个节点里面一个0-9的数字,输入就相当于两个大数了。然后返回这两个数的和(一个新list)。这两个输入的list长度相等。 要求是: 不用递归; 要求算法在最好的情况下,只遍历两个list一次 ,最差的情况下两遍。…...

  • 谢工在GitChat 3推荐

    编程面试题发布

    在微博上与@陈利人 神交已久,一直希望有机会把他的微博内容整理出来,最近他的微信公众账号“待字闺中”发布了。这样如果能把这些编程面试题按专题一一展现出来,让更多程序员受益,是我觉得非常有意义的事了。所以经@陈利人 老师同意,我试着整理出来,听听大家的反馈意见。 《待字闺中:编…...

  • 谢工在GitChat 3推荐

    最多连续数的子集及单链表和之恋分析及解答

    给一个整数数组, 找到其中包含最多连续数的子集,比如给:15, 7, 12, 6, 14, 13, 9, 11,则返回: 5:[11, 12, 13, 14, 15] 。 最简单的方法是sort然后scan一遍,但是要 o(nlgn) , 有什么 O(n) 的方法吗? 单链…...

  • 谢工在GitChat 3推荐

    颠倒乾坤;及忘我之乘积题的分析

    今日面试题:颠倒乾坤 在一棵二叉搜索树中,有两个节点颠倒了顺序。要求实现一个算法,在不改变树结构的前提下,恢复正确的二叉搜索树。给出一个空间为O(n)的实现很容易,那该如何给出一个空间O(1)的实现呢? 忘我之乘积分析 题目: 给你一个数组A[1..n],请你在O(n…...

  • 谢工在GitChat 2推荐

    蓄水池抽样及Google搜索之星分析

    今日面试题,蓄水池抽样,又称随机抽样问题,表示如下: 要求从N个元素中随机的抽取k个元素,其中N无法确定。 这种应用的场景一般是数据流的情况下,由于数据只能被读取一次,而且数据量很大,并不能全部保存,因此数据量N是无法在抽样开始时确定的;但又要保持随机性,于是有了这个问题。…...

  • 谢工在GitChat 2推荐

    Magic Index;及鸡蛋挺住体分析

    今日面试题: 给定一个数组A,其中有一个位置被称为Magic Index,含义是:如果i是Magic Index,则A[i] = i。假设A中的元素递增有序、且不重复,请给出方法,找到这个Magic Index。更进一步,当A中允许有重复的元素,该怎么办呢? 鸡蛋挺住体分析…...

  • 紫凤 2推荐

    熟悉的陌生人;及又见Google搜索之星分析

    今日面试题:熟悉的陌生人 大家都知道facebook用户都是双向的好友,a是b的好友,那么b一定是a的好友,现在给定一个用户列表,其中有些用户是好友,有些不是,请判断,这些用户是否可以划分为两组,并且每组内的用户,互相都不是好友。如果能,请给出这个划分。 例子1: 用户:…...

  • 紫凤 2推荐

    构造最大数;及熟悉的陌生人分析

    今日面试题:构造最大数 给定只包含正数的数组,给出一个方法,将数组中的数拼接起来,得到的数,是最大的。 例如: [4, 94, 9, 14, 1] 拼接之后,所得最大数为:9944141 =============================== 熟悉的陌生人分析…...

  • 紫凤 2推荐

    绳子的长度;及找数组的波谷分析

    今日面试题:绳子的长度 一根一米长的绳子,随机断成三段;求最短的一段的期望长度以及最长的一段的期望长度。 ================================ 找数组的波谷分析: 原题 一个数组A[1...n],满足A[1]>=A[2], A[n] …...

  • 紫凤 2推荐

    字母表;及查询提示分析

    今日面试题:字母表 每一种语言,都有自己的字母表,类似英文的a-z,但是顺序不相同。例如,有的语言可能是z是第一个之类的。现在给定这个语言的字典,请分析这个字典,得到这个语言的字母表的顺序。 例如:有如下的字母: 1. C 2. CAC 3. CB 4. BCC 5. BA…...

  • 紫凤 2推荐

    又见排序;及数组和分析

    今日面试题:又见排序 给定大小为n的数组A,A中的元素有正有负。请给出方法,对其排序,保证: 1. 负数在前面,正数在后面 2. 正数之间相对位置不变 3. 负数之间相对位置不变 能够做到时间复杂度为O(n),空间复杂度为O(1)么? ==============…...

  • 紫凤 2推荐

    Google前工程经理王忻:如何准备软件工程师的面试

    作者:王忻 我在 Google(以前是微软)工作期间面试了不下 300人,其中某些应聘者确实表现非凡,但有些却显得准备不足。当然许多面试准备不足的人最后依然获得了录用通知,因为他们本身确实才华出众。但如果应聘 者能提前准备妥当,那么面试过程将更为保险和轻松。以下所列出的就是我…...

  • 紫凤 1推荐

    括号匹配;及找数字续分析

    今日面试题:括号匹配 给定字符串,输出括号是否匹配,例如, 1. "()" yes; 2. ")(" no; 3. "(abcd(e)" no; 4. "(a)(b)" yes。 要求…...

  • 紫凤 1推荐

    interleave字符串;及括号匹配分析

    今日面试题:interleave字符串 3个字符串a,b,c。判断c是否是a和b的interleave,也就是c中应该有a,b中所有字 符,并且c中字符顺序和a,b中一样。比如,a = "ef" b = "gh" c = "e…...

  • 紫凤 1推荐

    加油站;及拷贝链表分析

    今日面试题:加油站 城市的环形路有n个加油站,第i个加油站的油量用gas[i]来表示,你有如下的一辆车: 1. 它的油缸是无限量的,初始是空的 2. 它从第i个加油站到第i+1个加油站消耗油量为cost[i] 现在你可以从任意加油站开始,路过加油站可以不断的加油,问是…...

  • 紫凤 1推荐

    灯;及数组统计分析

    今日面试题:灯 有100盏灯,依次编号1-100,初始都是关着的。第1次遍历,打开全部的灯;第2次遍历,关掉第2盏、第4盏等被2整除的灯;第3次打开被3整除的灯;第i次,对被i整除的灯做如下操作 如果灯开着,就关掉 如果灯关着,就打开 如此交替进行,知道100次遍历完…...

  • 紫凤 1推荐

    缺失的数字;及找数字分析

    今日面试题:缺失的数字 给定一个无序的整数数组,怎么找到第一个大于0,并且不在此数组的整数。比如[1,2,0] 返回 3, [3,4,-1,1] 返回 2。最好能O(1)空间和O(n)时间。 ========================================…...

  • 紫凤 1推荐

    找数字续;及缺失的数字分析

    今日面试题:找数字续 一个数组A,数字出现的情况,只有以下三种: 1. 一些数字只出现一次 2. 一些数字出现两次 3. 只有一个数字出现三次 请给出方法,找到出现三次的数字h 缺失的数字分析 原题 给定一个无序的整数数组,怎么找到第一个大于0,并且不在此数组…...

  • 紫凤 1推荐

    兄弟数字;及修理栅栏分析

    今日面试题:兄弟数字 给定一个数X,他的兄弟数Y定义为:是由X中的数字组合而成,并且Y是大于X的数中最小的。例如,38276的兄弟数字为38627。给定X,求Y。 ======================================= 修理栅栏 分析 原题为了…...