面试题分析:我的Twitter技术面试失败了

确认我返回亚马逊实习的截止期限是10月28日,但是我的朋友Daniel说服我如果我被Twitter录取,我就不用参加任何面试了。所以我去Twitter面试了。

首先他们让我在一个小时内完成两道编程能力的问题。问题很有意思:“这是回文(译注:正着读和倒着读是一样的)吗?”以及“计算二维数组的平衡点”。我不是很有自信,但是Twitter的一个招聘人员Judy给我发了email并安排了周三5:30的电话甄选。

我不知道你怎么样,反正我在面试前是很紧张的。我觉得这主要是因为我不想让面试官认为我很蠢。所以你可以想象,5:20我清空了桌子,记事本上标注了“Twitter面试,十月23日,周三”,还有为涂画准备的两只削尖的铅笔。然后5:30到了,我开始盯着我的电话。

5:35我去google了一下“加利福尼亚时间”来确定我的时差计算是正确的。没问题:Google说是太平洋标准时间2:30,美国东部时间5:30。

5:48我给Judy发了email,请她看下情况。10分钟后我接到了一个来自旧金山的电话。Judy对她搞砸了这件事情道歉,并告诉我Justin现在可以面试我。

深呼吸

“棒极了,我们开始吧!”

Justin同样对这个行程安排错误道歉,并很快深入到编程问题中:

“看下面这个图片”

“在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表,数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6]”

“假如开始下雨了,那么墙之间的水坑能够装多少水呢?”

“以1×1的方块为单位计算容积。所以,在上边的图中下标为1以左的都会漏掉。下标7以右的也会漏掉。剩下的只有在1和6之间的一坑水,容积是10”

_______

// 给好奇的读者的旁注:我在底部附上了正确答案的要点。你可以继续阅读而不怕剧透。:)

_______

我首先试图做的事情是搞清楚在给定的两个下标之间到底有多少水。这个过程跟微积分很像,所以我立即想起可以用极大值。实际上在上边的图片中,下标2以上的水是由周围的两个极大值下标1和6约束的。

我把我的想法说了出来:“如果我们找到所有的极大值,然后在他们之间填水。这样做有用么?”

“恩,这样应该有用” Justin回复。

我去给这个解答写代码。然后Justin让我提供一套测试用例。我们讨论的所有测试用例似乎也挺好。

“你有问题问我吗?”Justin问我。“我做的怎么样?”“还算不错。你的方法用了两次遍历,但有一个更有意思的方法只用一次遍历。”

然后我们聊了一小会关于在twitter的生活。

我挂掉电话的那一秒我意识到了我的答案是错的。

想想这个输入:

我的答案计算的是极大值之间的水,就像这样。

但是答案应该是在两个高塔之间只有一池水:

第二天我把这个问题给我的技术支持看,他是理论计算科学的博士生。40分钟之后他还是卡在这个问题上。

今天早上我带着口臭和灵光一闪起床。答案是简单而漂亮的。

现在我扪心自问:在这件事我学到了什么?客观地说——不多。对于面试官没有问我正确的问题来引导我向正确的方向思考,我很难过。当我的解答实际上不正确的时候,我不知道为什么Justin告诉我“这应该有用”。我知道解答中的问题应该在他要求的测试用例中显示出来,但既然我在思考算法的时候没有考虑到,我就不可能想到要测试它。

我跟亚马逊签了合约明年夏天上班,并且对此我很兴奋。同时,我也禁不住问一句“如果我通过了面试会怎么样?”

这里是答案的概要。

逻辑如下:

如果我们从左至右遍历列表,每个下标水的量最多是到现在为止最大的数。这表示如果我们已知右边有相等或更大的,我们可以知道存下的水有多少。反向遍历的时候也一样:如果我们知道左边有比右边最大的数更大的,我们装水是毫无问题的。

基于这个想法,一个解决方法是:先找到最大值,从左遍历到最大值,然后从右遍历到最大值。这个方法需要两次遍历:一次找到最大值,另一次分成了两个子遍历。

一次遍历的方法通过两端的指针相向移动避免了寻找最大值。如果(左指针找到的左指针以左的最大值)小于(右指针找到右指针以右的最大值),将左指针向右移动一位。否则右指针向左移动一位。重复过程直到两个指针相遇。(解释起来很麻烦,但是代码很简单)

 

译者注:

这是我用python实现的作者的最终算法:

https://github.com/CuGBabyBeaR/Interview-questions/tree/master/twitter-puddle

用了3个不同的测试用例,其中两个是文中给出的:

输出如下:

1 3 收藏 51 评论

关于作者:熊铎

野生业余程序员搞搞Android 玩玩前端 仅此而已 个人主页 · 我的文章 · 19 ·     

相关文章

可能感兴趣的话题



直接登录
最新评论
  • LL   2013/11/01

    卤煮最后给的答案也是有问题的吧?
    我觉得应该以max为分界. f(1,n) = f(1,max -1) + f(max +1 ,n);
    这是一个divide and conquer.

    • 熊铎 古生物学者 2013/11/01

      那还是需要先找到max啊
      于是就是两次遍历 正如作者在最后提供的第一个答案
      一次遍历的算法你再琢磨一下就明白了

    • jason   2013/11/03

      不用,没接触过python竟然看懂了,双向遍历,很巧妙

  • 虽然没怎么看懂楼主怎么做的,但是自己觉得蛮好玩的就编了一个。
    放个链接吧。
    https://github.com/jxzhuge12/interview
    大致思想已经在README文件里说明了

  • 熊铎 古生物学者 2013/11/01

    烦请更新一下文中的代码 昨晚的代码有点冗繁
    代码已上传至Github: https://github.com/CuGBabyBeaR/Interview-questions/tree/master/twitter-puddle

  • Kation   2013/11/01

    • Kation   2013/11/01

      擦,漏了一种可能性……

      • ped   2013/11/04

        我也觉得漏了一种可能。如果数组是3,1,1,4,1,2,3,3,6这样的呢

        • esyrt   2013/11/09

          注意題意,題意不是求水最多的兩個坑,而是所有坑中的水相加之和。

        • 我也觉得是少了[3,1,1,4,1,2,3,3,6]这种可能性,按照文中的算法,会少算3和4之间的水的。
          我想到的算法是从左到右遍历,先找到第一个坑。如果右边比左边高,则第一个坑的水量确定了;如果右边比左边矮,则第一个坑的水量还可能会抬高,所以继续以右边为新坑的左边,继续找坑。新坑找到以后,再看两边那个高,如果还是右边矮,则重复找新坑,如果右边高了,则和之前找到的旧坑的左边比,看哪个旧坑的左边终于比它高了,那之间的坑就都被水淹了,成为了个大坑。之后继续往右找新坑,继续以上算法。

      • bighammer   2013/11/08

        没有漏,这个算法很巧妙

  • WYD   2013/11/01

    很好的算法,首先求得两边各自的第一个极大值,然后根据那个极大值大确定遍历方向,顺便更新最大值

  • 赞,左边的一旦高于右边的就由右边决定蓄水量,木桶原理呀。。

  • piecehealth   2013/11/04

    Ruby版 12行
    https://gist.github.com/piecehealth/7297766

    • 熊铎 古生物学者 2013/11/04

      很简练 但是...
      不太懂Ruby 不过调用数组切片的max方法而不是自己维护一个max值
      会不会导致时间复杂度从O(n)提高到O(nlog(n))?

      • piecehealth   2013/11/04

        是的,这种写法执行不是很效率,都消耗在max这个方法上了,楼主的解法是最优的,只遍历一遍就解决了。

  • kidd   2013/11/04

    试试test case
    【10,9,8,7,6,5,4,3,2,1】

    • 熊铎 古生物学者 2013/11/04

      case [2, 5, 1, 2, 3, 4, 7, 7, 6] total volume : 10
      case [2, 5, 1, 3, 1, 2, 1, 7, 7, 6] total volume : 17
      case [6, 1, 4, 6, 7, 5, 1, 6, 4] total volume : 13
      case [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] total volume : 0

    • 太赞了。。开始还有点怀疑作者的逻辑,仔细推敲过后感觉很巧妙,长知识了,学到了东西。。谢谢

  • x   2013/11/04

    “如果我们从左至右遍历列表,每个下标水的量最多是到现在为止最大的数。”
    他这里是否表述有误:在计算时,需要考虑左侧所经历过的最大值。这样在有多个凹坑的时候,按照左侧经历过的最大值计算积水量。

    • 熊铎 古生物学者 2013/11/04

      诶?我感觉这样翻译没问题啊
      在前边从左侧遍历的语境下"到现在为止最大的数" 难道不就是 "到现在为止左侧所经历过的最大值"

  • Lithos   2013/11/04

    Java版本的两个不同实现:
    oneAndhalf是我自己想的,one是根据提示写的。

  • 乱世闲人   2013/11/05

    先找最大值,再次大值,次大值依次减去两数之间的数字得到水量,然后在数组中去掉次大值和两数之间的数字,在新数组里找次大值,重复上一过程。

  • starkjavac   2013/11/06

  • guest   2013/11/13

    twitter面试这么简单。。。

  • lw   2013/11/15

    2, 5, 1, 2, 3, 4, 7, 1, 6这种情况考虑了吗?

  • Ezio   2013/11/18

    这好像是LeetCode上的原题呀

  • 求凸包的变种

    • 军军@HUST   2013/11/29

  • xujiazhe   2013/12/06

    这个问题就是一个栈的问题吧~

    • chen   2013/12/09

      我只能想到最蠢的方法

  • Bixiaopeng   2013/12/10

    唔,我的第一反映是从下往上遍历,第一个接触到的两边有墙的凹槽是一定可以装水的,然后这个体积加上这几个凹槽被土填充的形状可以装水的体积就是能装水的最大体积。递归写,,,应该可以吧?
    晚上回去写一个看看,,,,

  • mrjob   2013/12/25

    没看懂代码,不过我觉得思想应该是这样的:选定n/2的数据为标记,然后查找左边和右边的最大值,有相同的就选离中间近的,然后用较小值减去两者之间的全部数据并把差相加得到结果。如果某一边的最大值小于中间值,就分成两块再算下去,是个递归算法。

  • al   2015/01/26

    墙……能蓄水吗?

  • clark.li   2015/01/26

    leetcode上已收录,另外leetcode上有另外一道类似的题目Container With Most Water

    • delight   2015/01/28

      • delight   2015/01/28

        // #10
        testcase_1 = [2, 5, 1, 2, 3, 4, 7, 7, 6];
        // #17
        testcase_2 = [2, 5, 1, 3, 1, 2, 1, 7, 7, 6];
        // #13
        testcase_3 = [6, 1, 4, 6, 7, 5, 1, 6, 4];
        // #11
        testcase_4 = [4, 1, 3, 2, 4, 1, 5, 4, 6, 5, 1, 2, 1];
        // #11
        testcase_5 = [3, 1, 1, 4, 1, 2, 3, 3, 6]
        // #0
        testcase_6 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];

        function main(arr) {
        function findMaxNode(ar, start, end) {
        var max = 0;
        var index = -1;
        for (var i = start; i max) {
        max = ar[i];
        index = i;
        }
        }
        return [index, max];
        }

        function caulat_1(ar,start,end) {
        if((end - start) < 3)return 0;

        var loaded = 0;

        var maxNode = findMaxNode(ar, start, end);

        var maxLeft = findMaxNode(ar, start, maxNode[0]);

        var maxRight = findMaxNode(ar, maxNode[0] + 1, end);

        if(maxLeft[0]!=-1){
        loaded += caulat_2(ar, maxLeft[0], maxNode[0], maxLeft[1]);
        loaded += caulat_1(ar, start, maxLeft[0] + 1);
        }

        if(maxRight[0]!=-1) {
        loaded += caulat_2(ar, maxNode[0] + 1, maxRight[0], maxRight[1]);
        loaded += caulat_1(ar, maxRight[0], end);
        }
        return loaded;

        }

        function caulat_2(arr,start,end,max2){
        var loaded =0;
        for (var i = start; i < end; i++) {
        loaded += max2 - arr[i];
        }
        return loaded
        }

        var loaded = caulat_1(arr,0,arr.length);

        console.log(loaded);

        }

        main(testcase_1);
        main(testcase_2);
        main(testcase_3);
        main(testcase_4);
        main(testcase_5);
        main(testcase_6);

  • 魂祭心   2015/11/19

    左右碰撞

    • 魂祭心   2015/11/19

      补上代码
      private void waterCount()
      {
      Console.WriteLine("输入墙面厚度");
      int M = int.Parse(Console.ReadLine());
      int waterCount = 0;
      //初始化墙面
      int[][] wall = new int[M][];
      Console.WriteLine("输入每块墙的高度");
      for (int i = 0; i < M; i++)
      {
      wall[i] = new int[int.Parse(Console.ReadLine())];
      }
      foreach (int[] arr in wall)
      {
      for (int i = 0; i < arr.Length; i++)
      {
      arr[i] = 1;
      }
      }
      //获取第二高墙面
      int sencondHeight = GetSecondHeight(wall);
      //获取可积累的水
      int x = wall.Length;
      for (int i = 0; i < wall.Length; i++)
      {
      for (int j = 0; j wall[i].Length - 1)
      {
      waterCount += IsLeft(wall, i, j);
      }
      }
      }
      Console.WriteLine("最大容留水量" + waterCount);
      }
      private int GetSecondHeight(int[][] wall)
      {
      List heights = new List();
      for (int i = 0; i < wall.Length; i++)
      {
      heights.Add(wall[i].Length);
      }
      heights.Sort();
      return heights.ToArray()[heights.Count - 1];
      }
      private int IsLeft(int[][] wall, int i, int j)
      {
      if (i == 0 || i == (wall.Length - 1)) return 0;
      bool lFlag = false;
      bool rFlag = false;
      for (int index = 0; index < wall.Length; index++)
      {
      bool temp=(index < j && j < wall[index].Length && wall[index][j] == 1) ? lFlag = true : rFlag = true;
      }
      return (rFlag && lFlag) ? 1 : 0;
      }
      左右碰撞,两边都撞上的才能存在,毕竟高塔不能空中楼阁,事实上并不需要极大值,需要的是次大值。

      • 魂祭心   2015/11/19

        修正错误,三目运算符改成
        if ( j < wall[index].Length)
        {
        if (index < i) //左边
        {
        lFlag = true;
        }
        else //右边
        {
        rFlag = true;
        }
        }
        前边赋值1的那段代码是冗余的。

  • 魂祭心   2015/11/19

    左右碰撞啦

  • 羽商宫   2016/01/11

    var testCase=Console.ReadLine();
    var array = testCase.Split('.').Select(p=>Convert.ToInt32(p)).ToList();
    int pL = 0;
    int pR = array.Count - 1;
    int maxLeft = array[pL];
    int maxRight = array[pR];
    int volume = 0;
    while (pL < pR)
    {
    if (maxLeft = maxLeft)
    {
    maxLeft = array[pL];
    }
    else
    {
    volume = volume + maxLeft - array[pL];
    }
    }
    else
    {
    pR = pR - 1;
    if (array[pR] >= maxRight)
    {
    maxRight = array[pR];
    }
    else
    {
    volume = volume + maxRight - array[pR];
    }
    }
    }
    Console.WriteLine(volume);
    Console.Read();

跳到底部
返回顶部