吴小波二面

热乎乎电面，题目是

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

日常求大米


补充内容 (2018-11-15 08:51):
update：已挂。。我也不知道为什么。。用count sort写的，也跑过了test case。。。

刷题网站气无? 这题还不在黑车tag下面哎

clezhong 发表于 2018-11-11 05:39
刷题网站气无? 这题还不在黑车tag下面哎

是的是的，我也才看到这道题，不过我用桶排序做的，感觉很玄了，哎/。。。。。

想问楼主有结果了吗？ 我也上周五刚面完，不知道现在uber的处理速度怎么样。。。

应该一周会有feedback，可以发邮件问hr

还没有结果呢emmm

可能面试官想让楼主用三指针做？？不开额外空间，O(n)time

面试官也许期待Dutch national flag problem： https://en.wikipedia.org/wiki/Dutch_national_flag_problem

面试官也许期待这个算法： Dutch national flag problem https://en.wikipedia.org/wiki/Dutch_national_flag_problem

A sample:
public void sortColors(int[] a) {
    if (a == null || a.length == 0) return;
    int n = a.length;
    int head = 0;
    while (head < n && a[head] == 0) ++head;
    int tail = n - 1;
    while (head < tail && a[tail] == 2) --tail;

    int i = head;
    while (i <= tail) {
      if (a[i] == 0) {
        swap(a, head++, i++);
      } else if (a[i] == 1) {
        ++i;
      } else { // a[i] == 2
        swap(a, i, tail--);
      }
    }
  }

  private void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }