一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2566|回复: 24
收起左侧

新鲜G电面

[复制链接] |试试Instant~ |关注本帖
lajidahe 发表于 2016-8-10 07:33:05 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
额。。。让设计一个4-way traffic system,例子如下:
假设一个十字路口有4条路
             |0
             |
  1-------     ----------2. more info on 1point3acres.com
             |
             |

             3.1point3acres缃
.1point3acres缃
让你实现两个api
void add(int carId, int roadId)
int remove()

举个例子 (有先后顺序的):
1. add(101, 1)
2. add(102, 1) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3. add(103, 2)
4. add(104, 3)

然后call remove:
remove() => 返回101
remove() => 返回103 (因为103这时候在road 2 的头部,即使102比103来的早,也要排在103后面)
remove() => 返回104 (同上理,但是因为104 比103晚,所以要在103的后面)
remove() => 返回102
以前没见过,所以想了很久 其实仔细想想不是很难.......

评分

1

查看全部评分

本帖被以下淘专辑推荐:

lvvvvv 发表于 2016-8-10 09:47:49 | 显示全部楼层
stop sign 啊
-google 1point3acres
补充内容 (2016-8-10 09:56):
4 个 queue,  然后把 front 放到一个 size 只有 4 的 main queue 里, 只能放 front, pop 一个 ,it+1, 再放回main queue 队尾
回复 支持 3 反对 0

使用道具 举报

leetcodeyu 发表于 2016-8-15 13:32:01 | 显示全部楼层
Xochitl 发表于 2016-8-12 14:20-google 1point3acres
试着分析一下这道题~有问题还请指出~
. 鍥磋鎴戜滑@1point 3 acres
感觉像一个zigzag的改版, 而决定这个queue输出顺序的是每个路口第 ...

非常好的解法,我觉得set可以省略,在加入roadId时,判读roadId是否在queue中,可以直接检查array[roadId].isEmpty(),如果不是empty那么queue中肯定有roadId,不需要去set中查找,其他func都没有用到set
回复 支持 1 反对 0

使用道具 举报

kinggarden2001 发表于 2016-8-10 07:44:18 | 显示全部楼层
没仔细想,感觉像个排序的题。
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-8-10 08:22:43 | 显示全部楼层
应该搞4个queue然后轮询着poll()就可以了
回复 支持 反对

使用道具 举报

foreverzad 发表于 2016-8-11 08:58:36 | 显示全部楼层
写了一个,大家看看有啥问题。
  class Traffic
-google 1point3acres  {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  public:
      Traffic(){
          m_WL.resize(4);
          m_Road2Go = -1;
      }
      void add(int carId, int roadId)
      {
          if(m_Road2Go == -1)
          {
              m_Road2Go = roadId;
          }
          m_WL[roadId].push(carId);
      }
      int remove()
      {
          if(m_Road2Go == -1). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
          {
              return -1;
          }
          int car2go = m_WL[m_Road2Go].front();
          m_WL[m_Road2Go].pop();
          int nextroad = (m_Road2Go +1)%4;
          while(nextroad!=m_Road2Go && m_WL[nextroad].empty())
          {
              nextroad = (nextroad+1)%4;
          }
          if(nextroad==m_Road2Go)
          {
              m_Road2Go = -1;
          }else
          {
              m_Road2Go = nextroad;-google 1point3acres
          }
          return car2go;
      }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  private:
      int m_Road2Go; // current index of queue to pop
      vector<queue<int>> m_WL; // waiting list 4 queue
  };
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-8-11 09:31:04 | 显示全部楼层
foreverzad 发表于 2016-8-11 08:58
写了一个,大家看看有啥问题。
  class Traffic
  {

不对, 走了一辆车之后, 你是轮询下一个路口, 没有体现出来的先后。. from: 1point3acres.com/bbs
比如路口 0 来了第一辆车a, 2 来了 b, 1 来了 c, a 走了之后你会先 check 路口 1
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-11 09:48:57 | 显示全部楼层
同楼上 四个que 轮流popleft
回复 支持 反对

使用道具 举报

foreverzad 发表于 2016-8-11 12:09:09 | 显示全部楼层
lvvvvv 发表于 2016-8-11 09:31
不对, 走了一辆车之后, 你是轮询下一个路口, 没有体现出来的先后。
比如路口 0 来了第一辆车a, 2 来 ...
. from: 1point3acres.com/bbs
hmm, 同意。多谢指正
回复 支持 反对

使用道具 举报

foreverzad 发表于 2016-8-11 13:02:47 | 显示全部楼层
lvvvvv 发表于 2016-8-11 09:31
不对, 走了一辆车之后, 你是轮询下一个路口, 没有体现出来的先后。
比如路口 0 来了第一辆车a, 2 来 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
照你思路重写了,麻烦看下。

class Traffic
{
public:
    Traffic(){
        m_WL.resize(4);. 1point3acres.com/bbs
    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    void add(int carId, int roadId)
    {. 1point 3acres 璁哄潧
        if(m_WL[roadId].empty())
        {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            m_mainq.push(carId);
        }
        m_WL[roadId].push(carId);
    }
    int remove()
    {
        if(m_mainq.empty())
        {
            return -1;
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        
        int car = m_mainq.front();
        m_mainq.pop();-google 1point3acres
        for(int i=0; i<4; i++)
        {
            if(!m_WL.empty() && m_WL.front()==car)
            {
                m_WL.pop();
                if(!m_WL.empty())
                {
                    m_mainq.push(m_WL.front());
                }
            }. 1point3acres.com/bbs
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        return car;
    }
private:
    queue<int> m_mainq;       // main queue
    vector<queue<int>> m_WL; // waiting list 4 queue
};
回复 支持 反对

使用道具 举报

Dirty小熊猫 发表于 2016-8-11 16:40:22 | 显示全部楼层
foreverzad 发表于 2016-8-11 13:02
照你思路重写了,麻烦看下。

class Traffic

感觉并不需要main queue。。。只要一个int count_car存还没走的车就行了~~然后用一个index来指4个queue的号就行了~~
回复 支持 反对

使用道具 举报

readman 发表于 2016-8-11 20:28:05 | 显示全部楼层
two queue, one int index, queue1 store cars, queue2 is temp, index store the previous remove direction.
. Waral 鍗氬鏈夋洿澶氭枃绔,
when remove, queue1 do poll() and store in queue2, until find the next car which has different direction

补充内容 (2016-8-11 20:36):. more info on 1point3acres.com
哦错了....
回复 支持 反对

使用道具 举报

HuaZhe 发表于 2016-8-12 10:11:27 | 显示全部楼层
想问一下如果是按照 1  2  1 3  1这个顺序来的车那么应该如何remove?  是 1  2  3  1 1 还是 1  2 1  3  1
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-8-12 11:03:21 | 显示全部楼层
HuaZhe 发表于 2016-8-12 10:11
想问一下如果是按照 1  2  1 3  1这个顺序来的车那么应该如何remove?  是 1  2  3  1 1 还是 1  2 1  3  1

按照stop sign的规则是1 2 3 1 1,如果是12131就一个queue就解决啦,不会那么简单的
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-8-12 14:20:29 | 显示全部楼层
试着分析一下这道题~有问题还请指出~
. visit 1point3acres.com for more.
感觉像一个zigzag的改版, 而决定这个queue输出顺序的是每个路口第一辆车 成为当前分叉口的第一辆车 的次序. more info on 1point3acres.com
听上去有点儿绕口,举个小例子~&#127792;
一个set来存目前几个路口有车,
一个queue来存目前每个路口第一辆车进来的顺序
一个array来存目前每个路口车等候的顺序,一个list[queue]结构
这样如果我的程序调用顺序如下
                       SET                        QUEUE                         ARRAY
add(A,1)           (1)                      [1]                            [[] , [A] , [] , [] ]       #set中没有1时加入1,queue最后加入1,array[1]中加入carID . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
add(B,1)           (1)                      [1]                            [[], [A,B],[] , [] ]       #set中有1时,直接在array[1]中加入carID即可. 1point3acres.com/bbs
add(C,1)           (1)                      [1]                            [[], [A,B,C],[] , [] ]. 鍥磋鎴戜滑@1point 3 acres
add(D,2)           (1,2)                   [1,2]                         [[], [A,B,C],[D] , [] ]   #set中没有2时加入2,queue最后加入2,array[2]中加入carID
add(E,3)           (1,2,3)                [1,2,3]                       [[], [A,B,C],[D] ,[E]]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
remove()          (1,2,3)                [2,3,1]                       [[], [B,C], [D] , [E]]     
# QUEUE中pop出第一个roadId,去array[roadID]pop出来第一辆车ID==A,输出第一辆车ID,判断此时array[roadID]不为空,表示此路口还有车,下一辆车进入路口成为第一辆车是目前有车的路口里面随后一位,所以把roadID再放进QUEUE里面去,set不用变
remove()          (1,3)                   [3,1]                          [ [], [B,C], [], [E] ]
# QUEUE中pop出第一个roadId,去array[roadID]pop出来第一辆车ID==D,输出第一辆车ID,判断此时array[roadID]为空,表示此路口没有车了,把roadID从set中删除,也不用再把roadId放进queue里进行排序了
add(F,1)           (1,3)                   [3,1]                          [[] , [B,C,F], [] , []]
add(G,0)          (1,3,0)                [3,1,0]                        [[G], [B,C,F], [], []]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

多一个set的原因是如果extend到n个路口,每个function的复杂度还是O(1). more info on 1point3acres.com
希望能够看完我这一大段回复的朋友,如果发现了错误或者可以优化的地方指出交流一下
我粗略写了一下代码没测~测完发~

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

amszhou 发表于 2016-8-13 11:38:02 | 显示全部楼层
很好奇add和remove 是交叉进行还是所有add后再remove?
回复 支持 反对

使用道具 举报

laogudongfu 发表于 2016-8-15 10:43:32 | 显示全部楼层
  1. </blockquote><blockquote>
复制代码
回复 支持 反对

使用道具 举报

laogudongfu 发表于 2016-8-15 10:45:05 | 显示全部楼层
  1. package com.indeed;

  2. import java.util.ArrayList;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.Queue;

  6. /**
  7. * @author binghong
  8. */

  9. public class Traffic {
  10.     private final Queue<Queue<Integer>> crossing = new LinkedList<>();
  11.     private final List<Queue<Integer>> roads;

  12.     Traffic(final int n){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  13.         roads = new ArrayList<>();
  14.         for (int i = 0; i < n; ++i){. 1point3acres.com/bbs
  15.             roads.add(new LinkedList<Integer>());
  16.         }
  17.     }

  18.     public void add(final int carId, final int roadId){
  19.         final Queue<Integer> road = roads.get(roadId);

  20.         if (road.isEmpty()){. from: 1point3acres.com/bbs
  21.             crossing.offer(road);.1point3acres缃
  22.         }
  23.         road.offer(carId);
  24.     }. From 1point 3acres bbs

  25.     public int remove(){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.         final int carId;
  27. . 1point 3acres 璁哄潧
  28.         if (crossing.isEmpty()) {
  29.             return -1;
  30.         }
  31. . visit 1point3acres.com for more.
  32.         final Queue<Integer> nextRoad = crossing.poll();
  33.         carId = nextRoad.poll();
  34.         if (!nextRoad.isEmpty()) {
  35.             crossing.offer(nextRoad);. visit 1point3acres.com for more.
  36.         }
  37.         return carId;
  38.     }. 1point 3acres 璁哄潧
  39. }
复制代码
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-8-16 12:48:32 | 显示全部楼层
leetcodeyu 发表于 2016-8-15 13:32
非常好的解法,我觉得set可以省略,在加入roadId时,判读roadId是否在queue中,可以直接检查array[roadId].is ...

嗯,是的可以忽略~谢谢指出~
回复 支持 反对

使用道具 举报

Josh 发表于 2016-8-17 06:46:13 | 显示全部楼层
求问楼主如果进车顺序是1,2,3,3,2,1的顺序,那么出来的顺序是1,2,3,3,2,1还是1,2,3,1,2,3?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-20 12:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表