推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4027|回复: 22
收起左侧

Yelp onsite 已跪

[复制链接] |试试Instant~ |关注本帖
rwei 发表于 2015-1-31 07:46:42 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 本科 全职@Yelp - 校园招聘会 - Onsite |Fail

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

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

x
1) Generate 一個掃雷遊戲的 board
[size=12.8000001907349px]
-google 1point3acres
                               
登录/注册后可看大图








[size=12.8000001907349px]用一個 2D array 來表示 board,給出 board 的長(L)寬(W) 和地雷數量(M),隨機地把 M 個地雷放在 L*W 個格子裏面,並在沒有地雷的格子中標記格子周圍地雷的數量。要求:絕對的 Random,並且避免發生 collision(generate 出同樣的 random number after processing)
. Waral 鍗氬鏈夋洿澶氭枃绔,
[size=12.8000001907349px]def generateBoard(L, W, M):
[size=12.8000001907349px]    """ return a 2D array representing the game board """

[size=12.8000001907349px]2) Implement Conway's Game of Life

[size=12.8000001907349px]
. 鍥磋鎴戜滑@1point 3 acres
                               
登录/注册后可看大图



鏉ユ簮涓浜.涓夊垎鍦拌鍧. [size=12.8000001907349px]給你一個 2D board,裏面包含 game 的 initial state;黑點代表 alive,白色代表 dead。每一個 iteration 都 follow 以下的 rule 來 update board,每個格子的改變都 independent of others' changes,即,你需要支持一個 step function,每次 step() 被 call 了以後遊戲都會走到下一個 state,並且在眾人開來所有的格子都在一瞬間同時被 update 完。成功 implement 的話,不斷地 call step() 黑色点組成的圖形就會在 2D board 中遊走。Minimize memory usage and running time. more info on 1point3acres.com

[size=12.8000001907349px]Rules:
[size=12.8000001907349px]
  • Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any live cell with more than three live neighbours dies, as if by overcrowding.
  • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
. 1point 3acres 璁哄潧

[size=12.8000001907349px]class GameOfLife:

[size=12.8000001907349px]    def __init__(self, board_width):
[size=12.8000001907349px]        """ Your code here """

[size=12.8000001907349px]    def set_alive(self, row, column):
[size=12.8000001907349px]        """ Your code here """
.鐣欏璁哄潧-涓浜-涓夊垎鍦

[size=12.8000001907349px]    def set_dead(self, row, column):.鐣欏璁哄潧-涓浜-涓夊垎鍦
        """ Your code here """


[size=12.8000001907349px]    def step(self):
[size=12.8000001907349px]        """ Your code here """

[size=12.8000001907349px]   # more stuffs if you want to add

[size=12.8000001907349px]3) Regular Expression Matching

[size=12.8000001907349px]def Match(string, pattern):
[size=12.8000001907349px]    """
[size=12.8000001907349px]        '*' star matches zero or more preceding characters
[size=12.8000001907349px]        '.' each dot matches exactly one character, any
[size=12.8000001907349px]        '^' prefix match, meaning that input string must start with exactly the same string following '^', e.g., '^abc' will match 'abcdefg', but 'cdefg' doesn't
[size=12.8000001907349px]        '$' suffix match, meaning that input string must end with exactly the same string following '$', e.g., '$abc' will match 'cdefgabc', but 'abcdefg' doesn't. visit 1point3acres.com for more.
[size=12.8000001907349px]        without any special character: return True if pattern is in string (contains, not exactly same), and False otherwise
[size=12.8000001907349px]    """. From 1point 3acres bbs
[size=12.8000001907349px]    # Your code here. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

[size=12.8000001907349px]4) Square root

[size=12.8000001907349px]Implement a function to compute square root of input number, assuming that input number will never be negative; six digits of decimals is precise enough
[size=12.8000001907349px]You may only use the following operations: '+', '-', '*', '/', no built-in sqrt function calls or pow function calls, minimize running time and watch out edge cases.. visit 1point3acres.com for more.

[size=12.8000001907349px]def squareRoot(number):
[size=12.8000001907349px]    """ Returns a float, which is the square root of number """

[size=12.8000001907349px]5) Object Oriented Design

[size=12.8000001907349px]If Yelp is about to launch a new web service that allows users to keep track of what they purchased(every single detail of each item) and generate spending reports that summarize their shopping habbits, by asking users to take pictures of their receipts and OCR them to database entires, how would you design data structure to efficiently store and process data? (Don't worry about OCR part, assuming that it will turn into an instance of the object you design)

[size=12.8000001907349px]6) Resume related short questions:

[size=12.8000001907349px]Explain what MapReduce is, then design a program that finds ten words with highest frequency (The words are stored as separate files on hard drives of different machines)

[size=12.8000001907349px]What is socket? If you have N machines communicating to each other, how many sockets do you have to create in total? In case of a broadcasting service, what would you do to ensure that a file sending out from one machine gets to every other ones as quickly as possible?

[size=12.8000001907349px]What are processes and threads? What are the differences? How could different processes communicate with each other?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

[size=12.8000001907349px]What is deadlock? How to prevent deadlock?
. 1point 3acres 璁哄潧
[size=12.8000001907349px]Tell me what happens when you enter a URL on your web browser and hit enter. Explain the process of getting a web page back, as detailed as you can.
. 鍥磋鎴戜滑@1point 3 acres
[size=12.8000001907349px]What are TCP and UDP? What are the differences between them? If TCP is better than UDP, why would people still use UDP? In what situation would you ever want to use UDP, and why?

[size=12.8000001907349px]What's the difference between 'range' and 'xrange' in Python?
. 1point 3acres 璁哄潧
[size=12.8000001907349px]Explain the differences between C++ and Python. Particularly, explain the different memory management scheme in each, and describe how you would implement a garbage collection procedure for Python..鏈枃鍘熷垱鑷1point3acres璁哄潧

[size=12.8000001907349px]... 其他的我記不清了。。。


. From 1point 3acres bbs
补充内容 (2015-1-31 07:53):
Sorry for the "[size=12.8000001907349px]", I didn't see any of them before I posted, but it came out of nowhere after I hit the submit button...

评分

5

查看全部评分

本帖被以下淘专辑推荐:

  • · Yelp|主题: 11, 订阅: 4
fsc111 发表于 2015-1-31 07:49:23 | 显示全部楼层
lz投的什么职位,为啥一直让实现GUI
回复 支持 反对

使用道具 举报

 楼主| rwei 发表于 2015-1-31 07:52:17 | 显示全部楼层
This one:

http://www.yelp.com/careers?jvi=oDOmWfwt,Job 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 1point 3acres 璁哄潧
I added the image to demonstrate what they wanted me to do, but all that they asked was to fill in the function body, of which the interfaces have been defined and provided.
回复 支持 反对

使用道具 举报

Primer 发表于 2015-1-31 08:18:16 来自手机 | 显示全部楼层
lz多久出结果的?
回复 支持 反对

使用道具 举报

 楼主| rwei 发表于 2015-1-31 08:59:52 | 显示全部楼层
Primer 发表于 2015-1-31 08:18
lz多久出结果的?

1 week from onsite interview
回复 支持 反对

使用道具 举报

broccoli 发表于 2015-1-31 09:06:44 | 显示全部楼层
感谢lz分享!
回复 支持 反对

使用道具 举报

还来得及吗 发表于 2015-2-2 00:08:36 | 显示全部楼层
LZ面试一定要用python吗。。。可不可以用Java
回复 支持 反对

使用道具 举报

 楼主| rwei 发表于 2015-2-2 00:48:10 来自手机 | 显示全部楼层
Yelp 是一家以 Python 為主的公司,onsite 的四輪當中有兩輪被要求一定要用 Python,剩下兩輪隨便什麼語言。
回复 支持 反对

使用道具 举报

arthur1233 发表于 2015-2-17 05:16:00 | 显示全部楼层
感觉题都不简单啊,楼主拿到没有
回复 支持 反对

使用道具 举报

ryuichist 发表于 2015-3-9 10:51:12 | 显示全部楼层
感觉好难的样子啊,这是什么职位,front end吗
回复 支持 反对

使用道具 举报

池大侠 发表于 2015-3-14 02:26:46 | 显示全部楼层
get a bruce force to solve the first problem how to you do it without bruce force?
  1. import random
  2. def miner(L,W,M):
  3.         if M>L*W:
  4.                 return None
  5.         board=[['.' for i in range(W)] for j in range(L)]
  6.         rowm=random.sample(range(L),M) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7.         colm=random.sample(range(W),M)
  8.         for row in rowm:
  9.                 for col in colm:
  10.                         board[row][col]='m'
  11.         def check(x,y):
  12.                 return x>=0 and x<L and y>=0 and y<W and board[x][y]=='m'
  13.         def bruce(x,y):
  14.                 rownbr=[0,-1,-1,-1,0,1,1,1]
  15.                 colnbr=[-1,-1,0,1,1,1,0,-1]
  16.                 count=0
  17.                 for k in range(len(rownbr)):
  18.                         if check(x+rownbr[k],y+colnbr[k]):
  19.                                 count+=1
  20.                 if board[x][y]!='m':
  21.                         board[x][y]=count
  22.         for row in range(L):
  23.                 for col in range(W):.1point3acres缃
  24.                         bruce(row,col). visit 1point3acres.com for more.
  25.         return board



  26. print miner(12,14,2)
复制代码
回复 支持 反对

使用道具 举报

bb4ever 发表于 2015-3-14 02:30:21 | 显示全部楼层
怎么会这么难。。。
回复 支持 反对

使用道具 举报

 楼主| rwei 发表于 2015-3-14 11:34:23 | 显示全部楼层
池大侠 发表于 2015-3-14 02:26
get a bruce force to solve the first problem how to you do it without bruce force?
. visit 1point3acres.com for more.
Well, this is what I did: (kind of linear time solution without having to worry about collision)
p.s. You are not allow to call the built-in sample function. All that you have is a random generator that returns a float from 0 to 1.
  1. from random import random

  2. def N_choose_K(indices, n, k):
  3.     result = []. From 1point 3acres bbs
  4.     while k > 0:. 鍥磋鎴戜滑@1point 3 acres
  5.         index = int(random() * (n-k))
  6.         result.append(indices[index]). 1point 3acres 璁哄潧
  7.         indices[index] = indices[n-len(result)]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.         k -= 1
  9.     return result

  10. def get2Dcoordinate(index, board_width):
  11.     col = index % board_width. 1point 3acres 璁哄潧
  12.     row = index / board_width
  13.     return row, col

  14. def validIndex(row, col, board):
  15.     L = len(board)
  16.     if L == 0:
  17.         return False
  18.     W = len(board[0])
  19.     return row >= 0 and row < L and col >= 0 and col < W and board[row][col] != 'm'

  20. def updateCount(row, col, board):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  21.     for i in xrange(row - 1, row + 2):
  22.         for j in xrange(col - 1, col + 2):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.             if validIndex(i, j, board) and i != row and j != col:
  24.                 print (i, j)
  25.                 board[i][j] += 1

  26. def generateBoard(L, W, M):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.     num_mines = L * W
  28.     if num_mines < M:
  29.         return None
  30.     mine_indices = N_choose_K(range(num_mines), num_mines, M)
  31.     board = [[0 for col in xrange(W)] for row in xrange(L)]
  32.     # place mines
  33.     row_cols = [get2Dcoordinate(index, W) for index in mine_indices]
  34.     print row_cols
  35.     for row, col in row_cols:. Waral 鍗氬鏈夋洿澶氭枃绔,
  36.         board[row][col] = 'm'
  37.     for row, col in row_cols:. from: 1point3acres.com/bbs
  38.         updateCount(row, col, board)
  39.     return board. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  40. board = generateBoard(10, 10, 20)
  41. for row in board:. 1point3acres.com/bbs
  42.     print [str(e) for e in row]
复制代码

补充内容 (2015-3-14 11:40):
line 27 should be
if validIndex(i, j, board) and (i != row or j != col):
回复 支持 反对

使用道具 举报

Larrylianj 发表于 2015-3-26 00:20:08 | 显示全部楼层
Regular Expression Match 这个好难啊,要求是部分匹配就可以。是不是有类似于KMP的方法啊?
回复 支持 反对

使用道具 举报

 楼主| rwei 发表于 2015-3-26 00:24:21 来自手机 | 显示全部楼层
Larrylianj 发表于 2015-3-26 00:20. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Regular Expression Match 这个好难啊,要求是部分匹配就可以。是不是有类似于KMP的方法啊?

其實就在 leetcode 那道題的基礎上加了一個 prefix match 和 suffix match,增加兩個 if 應該就能 handle。我感覺到目前為止還沒有遇到有公司是不考 dynamic programming 的…
回复 支持 反对

使用道具 举报

Larrylianj 发表于 2015-3-28 05:53:46 | 显示全部楼层
rwei 发表于 2015-3-26 00:24
其實就在 leetcode 那道題的基礎上加了一個 prefix match 和 suffix match,增加兩個 if 應該就能 handle ...

它不是要求不能完全匹配,只能部分匹配吗,这样不就可以从中间开始匹配了吗。还是用DP做吗?
回复 支持 反对

使用道具 举报

贪睡之萨满 发表于 2015-4-23 06:18:19 | 显示全部楼层
池大侠 发表于 2015-3-14 02:26
get a bruce force to solve the first problem how to you do it without bruce force?

        rowm=random.sample(range(L),M)
        colm=random.sample(range(W),M)
如果这2段code是不是无法生成(2,1)和(2,3)这2个点,因为x的值是一样的;
如果没有上面这个问题可以是不是不会生成同一个点2次。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我不是写python的,尝试去理解这两行,不管哪种理解方式都似乎不对。
回复 支持 反对

使用道具 举报

贪睡之萨满 发表于 2015-4-23 06:19:51 | 显示全部楼层
rwei 发表于 2015-3-14 11:34
Well, this is what I did: (kind of linear time solution without having to worry about collision)
...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
为什么不check collision?感觉check collision才是难点
回复 支持 反对

使用道具 举报

 楼主| rwei 发表于 2015-4-23 08:59:03 来自手机 | 显示全部楼层
你再仔细看一下那代码,这种方法是不可能产生 collision 的。详情见 cracking the coding interview。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-23 02:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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