美国卖车经历分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 5686|回复: 24
收起左侧

新鲜G电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
lajidahe 发表于 2016-8-10 07:33:05 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
额。。。让设计一个4-way traffic system,例子如下:
假设一个十字路口有4条路.1point3acres网
             |0
             |
  1-------     ----------2-google 1point3acres
             |
             | 来源一亩.三分地论坛.

             3-google 1point3acres

让你实现两个api
void add(int carId, int roadId)
int remove().本文原创自1point3acres论坛

举个例子 (有先后顺序的):
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大米 +40 收起 理由
candy_shmily + 40

查看全部评分


上一篇:FB不回复我的time availability邮件
下一篇:Google Onsite面经

本帖被以下淘专辑推荐:

我的人缘0
lvvvvv 发表于 2016-8-10 09:47:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stop sign 啊
来源一亩.三分地论坛.
补充内容 (2016-8-10 09:56):
4 个 queue,  然后把 front 放到一个 size 只有 4 的 main queue 里, 只能放 front, pop 一个 ,it+1, 再放回main queue 队尾
回复 支持 3 反对 0

使用道具 举报

我的人缘0
leetcodeyu 发表于 2016-8-15 13:32:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Xochitl 发表于 2016-8-12 14:20
试着分析一下这道题~有问题还请指出~

感觉像一个zigzag的改版, 而决定这个queue输出顺序的是每个路口第 ...

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

使用道具 举报

我的人缘0
kinggarden2001 发表于 2016-8-10 07:44:18 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
没仔细想,感觉像个排序的题。
回复 支持 反对

使用道具 举报

我的人缘0
muybienw 发表于 2016-8-10 08:22:43 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
应该搞4个queue然后轮询着poll()就可以了
回复 支持 反对

使用道具 举报

我的人缘0
foreverzad 发表于 2016-8-11 08:58:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
写了一个,大家看看有啥问题。
  class Traffic
  {. 牛人云集,一亩三分地
  public: 来源一亩.三分地论坛.
      Traffic(){
          m_WL.resize(4);
          m_Road2Go = -1;
      }
      void add(int carId, int roadId)
      {
          if(m_Road2Go == -1). 一亩-三分-地,独家发布
          {
              m_Road2Go = roadId;
          }
. more info on 1point3acres          m_WL[roadId].push(carId);
      }
      int remove()
      {. from: 1point3acres
          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
          {. more info on 1point3acres
              m_Road2Go = nextroad;
          }
          return car2go;
      }
  private:
      int m_Road2Go; // current index of queue to pop. From 1point 3acres bbs
      vector<queue<int>> m_WL; // waiting list 4 queue
  };
回复 支持 反对

使用道具 举报

我的人缘0
lvvvvv 发表于 2016-8-11 09:31:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
foreverzad 发表于 2016-8-11 08:58. 围观我们@1point 3 acres
写了一个,大家看看有啥问题。
  class Traffic
  {

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

使用道具 举报

我的人缘0
pushazhiniao 发表于 2016-8-11 09:48:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同楼上 四个que 轮流popleft
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
foreverzad 发表于 2016-8-11 12:09:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lvvvvv 发表于 2016-8-11 09:31
不对, 走了一辆车之后, 你是轮询下一个路口, 没有体现出来的先后。. 牛人云集,一亩三分地
比如路口 0 来了第一辆车a, 2 来 ...

hmm, 同意。多谢指正
回复 支持 反对

使用道具 举报

我的人缘0
foreverzad 发表于 2016-8-11 13:02:47 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
lvvvvv 发表于 2016-8-11 09:31
不对, 走了一辆车之后, 你是轮询下一个路口, 没有体现出来的先后。
比如路口 0 来了第一辆车a, 2 来 ...

照你思路重写了,麻烦看下。

class Traffic
. Waral 博客有更多文章,{. 1point3acres
public:.1point3acres网
    Traffic(){
        m_WL.resize(4);
    }
    void add(int carId, int roadId)
    {
        if(m_WL[roadId].empty())
        {
            m_mainq.push(carId);
        }. 留学申请论坛-一亩三分地
        m_WL[roadId].push(carId);
    }
    int remove().本文原创自1point3acres论坛
    {. more info on 1point3acres
        if(m_mainq.empty())
        {
            return -1;
        }
. 一亩-三分-地,独家发布        
        int car = m_mainq.front();
        m_mainq.pop();
        for(int i=0; i<4; i++).1point3acres网
        {
            if(!m_WL.empty() && m_WL.front()==car)
            {
                m_WL.pop();
                if(!m_WL.empty())
                {
                    m_mainq.push(m_WL.front());
                }
            }.留学论坛-一亩-三分地
        }
        return car;. more info on 1point3acres
    }
private:
    queue<int> m_mainq;       // main queue
    vector<queue<int>> m_WL; // waiting list 4 queue
};
回复 支持 反对

使用道具 举报

我的人缘0
Dirty小熊猫 发表于 2016-8-11 16:40:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
foreverzad 发表于 2016-8-11 13:02
照你思路重写了,麻烦看下。. 牛人云集,一亩三分地

class Traffic

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

使用道具 举报

我的人缘0
readman 发表于 2016-8-11 20:28:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
two queue, one int index, queue1 store cars, queue2 is temp, index store the previous remove direction.

when remove, queue1 do poll() and store in queue2, until find the next car which has different direction

补充内容 (2016-8-11 20:36):
哦错了....
回复 支持 反对

使用道具 举报

我的人缘0
HuaZhe 发表于 2016-8-12 10:11:27 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
想问一下如果是按照 1  2  1 3  1这个顺序来的车那么应该如何remove?  是 1  2  3  1 1 还是 1  2 1  3  1
回复 支持 反对

使用道具 举报

我的人缘0
Xochitl 发表于 2016-8-12 11:03:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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就解决啦,不会那么简单的
回复 支持 反对

使用道具 举报

我的人缘0
Xochitl 发表于 2016-8-12 14:20:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
试着分析一下这道题~有问题还请指出~

感觉像一个zigzag的改版, 而决定这个queue输出顺序的是每个路口第一辆车 成为当前分叉口的第一辆车 的次序. more info on 1point3acres
听上去有点儿绕口,举个小例子~&#127792;-google 1point3acres
一个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即可
add(C,1)           (1)                      [1]                            [[], [A,B,C],[] , [] ]
add(D,2)           (1,2)                   [1,2]                         [[], [A,B,C],[D] , [] ]   #set中没有2时加入2,queue最后加入2,array[2]中加入carID. 围观我们@1point 3 acres
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)
希望能够看完我这一大段回复的朋友,如果发现了错误或者可以优化的地方指出交流一下
我粗略写了一下代码没测~测完发~. 围观我们@1point 3 acres


回复 支持 反对

使用道具 举报

我的人缘0
amszhou 发表于 2016-8-13 11:38:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
很好奇add和remove 是交叉进行还是所有add后再remove?
回复 支持 反对

使用道具 举报

我的人缘0
laogudongfu 发表于 2016-8-15 10:43:32 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
  1. </blockquote><blockquote>
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
laogudongfu 发表于 2016-8-15 10:45:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
  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<>();. visit 1point3acres for more.
  11.     private final List<Queue<Integer>> roads;. 一亩-三分-地,独家发布

  12.     Traffic(final int n){
  13.         roads = new ArrayList<>();. 留学申请论坛-一亩三分地
  14.         for (int i = 0; i < n; ++i){
  15.             roads.add(new LinkedList<Integer>());. Waral 博客有更多文章,
  16.         }
  17.     }
  18. . 一亩-三分-地,独家发布
  19.     public void add(final int carId, final int roadId){. visit 1point3acres for more.
  20.         final Queue<Integer> road = roads.get(roadId);. 围观我们@1point 3 acres

  21.         if (road.isEmpty()){
  22.             crossing.offer(road);
  23.         }.留学论坛-一亩-三分地
  24.         road.offer(carId);
  25.     }

  26.     public int remove(){
  27.         final int carId;

  28.         if (crossing.isEmpty()) {
  29.             return -1;
  30.         }

  31.         final Queue<Integer> nextRoad = crossing.poll();. 围观我们@1point 3 acres
  32.         carId = nextRoad.poll();. From 1point 3acres bbs
  33.         if (!nextRoad.isEmpty()) {
  34.             crossing.offer(nextRoad);
  35.         }
  36.         return carId;.1point3acres网
  37.     }
  38. }
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
Xochitl 发表于 2016-8-16 12:48:32 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
leetcodeyu 发表于 2016-8-15 13:32
非常好的解法,我觉得set可以省略,在加入roadId时,判读roadId是否在queue中,可以直接检查array[roadId].is ...

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

使用道具 举报

我的人缘0
Josh 发表于 2016-8-17 06:46:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求问楼主如果进车顺序是1,2,3,3,2,1的顺序,那么出来的顺序是1,2,3,3,2,1还是1,2,3,1,2,3?
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-21 01:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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