c*******r
发帖数: 610 | 1 刚面的。 第一轮店面。
面试官是白人geek来自安卓组，以前是earth组的。 貌似不知道该怎么开始面试。
1. high-level questions
进程与线程的区别
当只有单核时，用多线程有什么优缺点
什么是好的软件设计开发pattern或者行为
谈谈你见过的最好的设计是什么
接下来就是设计题的实现：
class EventCounter{
public:
//registers a single event
void Increment() ;
int getLastSecondCount();
int getLastDayCount();
};
题目要求是假设有一个webserver，这个EventCounter 类被这个webserver调用以得到
网站返回错误信息event的计数。
要求实现这三个函数。
貌似是以前老题吧，我自己没有认真考虑过，答得一般估计挂啦，完全不是算法的路子
，这种开放式题目实在是自己的弱项，有什么好办法可以提高？ thx
|
w****r
发帖数: 15252 | |
d********t
发帖数: 9628 | 3 你ID是我以前英国manager都last name
【在 w****r 的大作中提到】
: 这么难，我老没戏去google了
|
w****r
发帖数: 15252 | |
d********i
发帖数: 582 | 5 你ID是我以前加拿大manager的first name
【在 d********t 的大作中提到】
: 你ID是我以前英国manager都last name
|
l*****4
发帖数: 267 | 6 bless！！
请问楼主是new grad吗？
面的哪里？
谢谢！ |
l********b
发帖数: 64 | |
j**********3
发帖数: 3211 | |
c*******r
发帖数: 610 | 9 谢谢：）
我不是newgrad， 有差不多两年工作经验。 面的g mountain view，没有指定组
【在 l*****4 的大作中提到】
: bless！！
: 请问楼主是new grad吗？
: 面的哪里？
: 谢谢！
|
c*******r
发帖数: 610 | 10 我没有任何特殊背景啊，给我感觉面试官应该是比较喜欢设计，从一开始的交流就问了
几个关于什么是好的什么是坏的软件设计的问题。我虽然工作差不多两年，接触到的设
计实在是太少，可能我自己太懒了吧，没有在工作之余多学习点design的东西。
【在 j**********3 的大作中提到】
: 第一个题怎么这么恶心？lz你有特殊背景么？
|
|
|
z****e
发帖数: 54598 | 11 线程在单核时候可能会被blocked
多线程在这个时候会自动绕开被blocked的线程，导致整体process不会停滞
好的设计pattern就是你不需要去阅读代码就能明白对方在做什么
如果需要阅读代码，那么会有一个先入为主的idea，指导你对方在做什么
这样可以大量节省时间，提升你阅读代码的速度
最好的设计，这个就是纯粹聊天题，看你知识深度和广度，随便聊
【在 c*******r 的大作中提到】
: 刚面的。 第一轮店面。
: 面试官是白人geek来自安卓组，以前是earth组的。 貌似不知道该怎么开始面试。
: 1. high-level questions
: 进程与线程的区别
: 当只有单核时，用多线程有什么优缺点
: 什么是好的软件设计开发pattern或者行为
: 谈谈你见过的最好的设计是什么
: 接下来就是设计题的实现：
: class EventCounter{
: public:
|
z****e
发帖数: 54598 | 12 最后一题是多线程的并发处理题
还是跟topk一样，建heap，priorityqueue
这题涉及到多线程并发，priorityblockingqueue
http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/P
【在 c*******r 的大作中提到】
: 刚面的。 第一轮店面。
: 面试官是白人geek来自安卓组，以前是earth组的。 貌似不知道该怎么开始面试。
: 1. high-level questions
: 进程与线程的区别
: 当只有单核时，用多线程有什么优缺点
: 什么是好的软件设计开发pattern或者行为
: 谈谈你见过的最好的设计是什么
: 接下来就是设计题的实现：
: class EventCounter{
: public:
|
z****e
发帖数: 54598 | 13 EventCounter这题可能不需要建heap
heap有点overkill了，用concurrenthashmap这种应该效果更好 |
c*******r
发帖数: 610 | 14 怎么把blocking queue用到这个问题上呢？ webserver是怎么调用这几个函数呢？ 如
果现在的时候不是一天的结尾，怎么得到过去一天的count呢？ 如果服务器不是每秒钟
更新错误信息event的计数，怎么得到过去一秒钟的counter呢？应该存储什么数据呢？
用什么数据结构存储，以及计算该如何做呢？ 如果是多线程该怎么处理呢？ 我觉得这
些问题我都没有办法相处非常好的答案，尽管是open ended，能否指教指教？多谢
【在 z****e 的大作中提到】
: 最后一题是多线程的并发处理题
: 还是跟topk一样，建heap，priorityqueue
: 这题涉及到多线程并发，priorityblockingqueue
: http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/P
|
z****e
发帖数: 54598 | 15 基本上是多线程为主的技术问题，不是算法
但是多线程还是常见的问题 |
z****e
发帖数: 54598 | 16 如果用了synchronized的class的话，这题就不用synchronized关键字了
这题想办法处理好多线程的并发冲突就好了
最简单的就是synchronized关键字，但是这个效率偏低
用concurrenthashmap就快很多了，再启一个线程，对每过去一秒的计数可以做
persistence
随便找个db存一下就好了，内存db都可以，java可以用javadb或者redis都可以
android就用android自己的sqllite，然后倒数第二个函数就纯粹是去db里面query了
倒数第一个函数就是instant data的查询，这个可能要用到atomicinteger这种原子操
作的类
如果你自己额外建一个计数器的话，但是这样做还是会blocked，最好是操作hashmap
然后再异步去那个atomicinteger里面做加加减减
都是多线程的那些思路，这些题其实并不侧重设计
只是多线程这些多多少少会涉及一点设计罢了
这种题好处在于，对方通过问这种题可以把底摸个透
【在 c*******r 的大作中提到】
: 怎么把blocking queue用到这个问题上呢？ webserver是怎么调用这几个函数呢？ 如
: 果现在的时候不是一天的结尾，怎么得到过去一天的count呢？ 如果服务器不是每秒钟
: 更新错误信息event的计数，怎么得到过去一秒钟的counter呢？应该存储什么数据呢？
: 用什么数据结构存储，以及计算该如何做呢？ 如果是多线程该怎么处理呢？ 我觉得这
: 些问题我都没有办法相处非常好的答案，尽管是open ended，能否指教指教？多谢
|
c*******r
发帖数: 610 | 17 学习了，你说的这些java的东西我没有什么经验，我主要是写c++的，java只知道点皮
毛。 正在通过学习开源软件提高java水平中。。。。
他是安卓组的， 所以我想你说的应该是他想要的吧
【在 z****e 的大作中提到】
: 如果用了synchronized的class的话，这题就不用synchronized关键字了
: 这题想办法处理好多线程的并发冲突就好了
: 最简单的就是synchronized关键字，但是这个效率偏低
: 用concurrenthashmap就快很多了，再启一个线程，对每过去一秒的计数可以做
: persistence
: 随便找个db存一下就好了，内存db都可以，java可以用javadb或者redis都可以
: android就用android自己的sqllite，然后倒数第二个函数就纯粹是去db里面query了
: 倒数第一个函数就是instant data的查询，这个可能要用到atomicinteger这种原子操
: 作的类
: 如果你自己额外建一个计数器的话，但是这样做还是会blocked，最好是操作hashmap
|
z****e
发帖数: 54598 | 18 c++也是一样的，只不过区别在于要自己动手实现一些类
我对java比较熟，所以例子里面多数用的是java的类库和api
用go或者scala这些都可以，不过我对这些语言的api和语法不熟
面试时候还是不冒险了，主要是多线程的编程
多看看多线程的编程，遇到这种就不会束手无策了
【在 c*******r 的大作中提到】
: 学习了，你说的这些java的东西我没有什么经验，我主要是写c++的，java只知道点皮
: 毛。 正在通过学习开源软件提高java水平中。。。。
: 他是安卓组的， 所以我想你说的应该是他想要的吧
|
c*******r
发帖数: 610 | 19 你说的对，谢谢，这方面确实欠缺，需要恶补。
【在 z****e 的大作中提到】
: c++也是一样的，只不过区别在于要自己动手实现一些类
: 我对java比较熟，所以例子里面多数用的是java的类库和api
: 用go或者scala这些都可以，不过我对这些语言的api和语法不熟
: 面试时候还是不冒险了，主要是多线程的编程
: 多看看多线程的编程，遇到这种就不会束手无策了
|
j**********3
发帖数: 3211 | |
|
|
w********s
发帖数: 1570 | 21 多线程的2个好处:
1, UI响应快
2，有些blocking的处理，比如网络传输，用多线程可以加快。
参考C++ Concurrency in Action: Practical Multithreading
http://www.amazon.com/C-Concurrency-Action-Practical-Multithrea
【在 z****e 的大作中提到】
: 线程在单核时候可能会被blocked
: 多线程在这个时候会自动绕开被blocked的线程，导致整体process不会停滞
: 好的设计pattern就是你不需要去阅读代码就能明白对方在做什么
: 如果需要阅读代码，那么会有一个先入为主的idea，指导你对方在做什么
: 这样可以大量节省时间，提升你阅读代码的速度
: 最好的设计，这个就是纯粹聊天题，看你知识深度和广度，随便聊
|
z****e
发帖数: 54598 | 22 所谓ui响应快跟第二点几乎是一致的
一般都有一个ui线程，保证这个不要被blocked反应就快了
死背书很无聊的说
【在 w********s 的大作中提到】
: 多线程的2个好处:
: 1, UI响应快
: 2，有些blocking的处理，比如网络传输，用多线程可以加快。
: 参考C++ Concurrency in Action: Practical Multithreading
: http://www.amazon.com/C-Concurrency-Action-Practical-Multithrea
|
c*******r
发帖数: 610 | 23 因为多线程经验特别有限，所以我一个字都没提。
可能他假设我应该精通这方面吧。
【在 j**********3 的大作中提到】
: 你简历写了些什么吧？感觉一般不会这么问
|
g**e
发帖数: 6127 | 24 应该说用spark/storm，立马onsite
【在 z****e 的大作中提到】
: EventCounter这题可能不需要建heap
: heap有点overkill了，用concurrenthashmap这种应该效果更好
|
s**x
发帖数: 7506 | 25 第二题就是 一个 circular array 吧？ one array with 86400 counters, extra
counter for day counts. you probably do not even need a lock as numbers can
be atomically incremented.
zhaoce 大牛光知道胡侃。 |
a*****n
发帖数: 158 | |
v***n
发帖数: 562 | |
f********x
发帖数: 2086 | 28
can
我也是这么想的....毕竟一个G的店面整体上还是往coding上靠吧
考knowledge的都是小公司
【在 s**x 的大作中提到】
: 第二题就是 一个 circular array 吧？ one array with 86400 counters, extra
: counter for day counts. you probably do not even need a lock as numbers can
: be atomically incremented.
: zhaoce 大牛光知道胡侃。
|
z*****m
发帖数: 119 | 29 那个计数器函数都没有参数，直接一个atomicinteger搞定吧 |
g*******d
发帖数: 495 | 30 The interviewer wants to know about your CS knowledge, rather than ability
to write interview question code. Knowledge has to be accumulated by time
but interview question could be rushed out. |
|
|
j**********3
发帖数: 3211 | 31 我认识的被考了这个问题的，都是自己写了什么。如果没写被问到，听说直接说不会就
可以了。。。
【在 c*******r 的大作中提到】
: 因为多线程经验特别有限，所以我一个字都没提。
: 可能他假设我应该精通这方面吧。
|
z****e
发帖数: 54598 | 32 concurrenthashmap底层就是一个array，所有的hashmap底层实现都是一个array
所有的hashcode算法都可以做成consistent hashing，也就是circular array
用concurrenthashmap的好处就在于，如果发生了冲突，这个轮子可以自动帮忙调节
而不需要自己去从底层实现，效率快很多，而且automic increment这个很容易写错
需要知道哪些是原子操作，哪些不是，一般简单的i+1这种就不是原子操作
synchronized关键字是要避免使用的，会是好事，但是不太容易维护，太容易错
在多线程并发的时候，很容易出错，这题是去年常考的题目的变种，更简单了一点
一开始题目并没有说要多线程
can
【在 s**x 的大作中提到】
: 第二题就是 一个 circular array 吧？ one array with 86400 counters, extra
: counter for day counts. you probably do not even need a lock as numbers can
: be atomically incremented.
: zhaoce 大牛光知道胡侃。
|
z****e
发帖数: 54598 | 33 这题在去年的面经里面出现的频率是非常高的，堪比今年的topk问题
你看gate在说storm，去年就是因为这题，所以很多人跑去看storm了
我说复杂了，但是基本原理是一样的，轮子可以不用，但是用与不用
都不改变这题实现的本质，用了轮子不过是锦上添花而已
你还是需要明白这题是怎么实现的
【在 c*******r 的大作中提到】
: 因为多线程经验特别有限，所以我一个字都没提。
: 可能他假设我应该精通这方面吧。
|
z****e
发帖数: 54598 | 34 可以，如果thread多而且访问频繁的话，会blocked
server side一般多cpu多core是常事，最好不要假设是单线程
【在 z*****m 的大作中提到】
: 那个计数器函数都没有参数，直接一个atomicinteger搞定吧
|
o***g
发帖数: 2784 | 35 赵老师，这题我挺sdlx一把
他说的很有道理，您在仔细想想？
lastsecond应该是过去了的一秒，同理lastDay应该是，今天11号，是要昨天10号的结果
所以这里根本就没有同步一说。对当前秒和天，都是+操作，不原子也没关系。退一步
讲即便是要当前秒和当前天的数据，不同步也没关系，结果差点儿无所谓吧
【在 z****e 的大作中提到】
: concurrenthashmap底层就是一个array，所有的hashmap底层实现都是一个array
: 所有的hashcode算法都可以做成consistent hashing，也就是circular array
: 用concurrenthashmap的好处就在于，如果发生了冲突，这个轮子可以自动帮忙调节
: 而不需要自己去从底层实现，效率快很多，而且automic increment这个很容易写错
: 需要知道哪些是原子操作，哪些不是，一般简单的i+1这种就不是原子操作
: synchronized关键字是要避免使用的，会是好事，但是不太容易维护，太容易错
: 在多线程并发的时候，很容易出错，这题是去年常考的题目的变种，更简单了一点
: 一开始题目并没有说要多线程
:
: can
|
z****e
发帖数: 54598 | 36 但是我说的是多个线程写的同步冲突问题
并不是只有一个读和一个写两个线程的冲突
两个线程比较容易搞，因为取i操作是原子操作，赋值i也是原子操作
可以额外弄一个int temp来保存当前值，然后赋值i，然后读线程来取i这样
这样可以避开同步的问题，但是如果是多个线程同时写，就有可能冲突
这里面涉及的问题可能会很复杂，一般这个时候就绕开了
避免使用synchronized关键字，可读性太差
不用的话，完全凭借对原子操作的了解的话，需要对jvm的机制很了解才行
这个我没有把握，所以还是老老实实用concurrent类
这样既不用知道jvm机制，也不用担心synchronized关键字
我没有说他说的是错的，设计题可以有多个答案
这题其实难点在于多个机器同时调用这个类的时候，可能会引发的冲突
不过原题也没有说有多个机器会同时调用这个类
就说了一个，android上一般对付两个线程冲突
主要是输入和ui线程，这两个冲突控制了的话，剩下就好办了
server side不太一样，一般server side会出现多个cpu多个core然后起一堆线程
每个线程接收一个request这种，tomcat什么都是如此，不过也可以写成单线程的
但是blocked的东西需要自己去处理，就麻烦了
结果
【在 o***g 的大作中提到】
: 赵老师，这题我挺sdlx一把
: 他说的很有道理，您在仔细想想？
: lastsecond应该是过去了的一秒，同理lastDay应该是，今天11号，是要昨天10号的结果
: 所以这里根本就没有同步一说。对当前秒和天，都是+操作，不原子也没关系。退一步
: 讲即便是要当前秒和当前天的数据，不同步也没关系，结果差点儿无所谓吧
|
m*****k
发帖数: 731 | 37 这题就是writer间的同步问题，都不用考虑reader, getlastSecCount()读的都是历史
数据啦。
Java 5 java.util.concurrent.atomic provides wrapper classes for int and long
that can be used to achieve this atomically without usage of
Synchronization
AtomicInteger 典型use case. |
v***o
发帖数: 287 | 38 class EventCounter{
public:
//registers a single event
void Increment() ;
int getLastSecondCount();
int getLastDayCount();
};
只用一个 global counter， 一个timer thread 每秒钟check 一下，current counter
- previous counter, update lastSecondCout 另一个day timer thread 每天check
一下， 然后update lastDayCount, 同时，reset global counter.
这样连ring array 也省了。
【在 c*******r 的大作中提到】
: 刚面的。 第一轮店面。
: 面试官是白人geek来自安卓组，以前是earth组的。 貌似不知道该怎么开始面试。
: 1. high-level questions
: 进程与线程的区别
: 当只有单核时，用多线程有什么优缺点
: 什么是好的软件设计开发pattern或者行为
: 谈谈你见过的最好的设计是什么
: 接下来就是设计题的实现：
: class EventCounter{
: public:
|
