May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲



查看: 3718|回复: 22

Yelp onsite 已跪

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

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


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

1) Generate 一個掃雷遊戲的 board


[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]給你一個 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

  • 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.

. From 1point 3acres bbs
[size=12.8000001907349px]class GameOfLife:

[size=12.8000001907349px]    def __init__(self, board_width):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
[size=12.8000001907349px]        """ Your code here """-google 1point3acres
[size=12.8000001907349px]    def set_alive(self, row, column):.
[size=12.8000001907349px]        """ Your code here """. more info on

. visit for more.
[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
[size=12.8000001907349px]        without any special character: return True if pattern is in string (contains, not exactly same), and False otherwise. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
[size=12.8000001907349px]    """
[size=12.8000001907349px]    # Your code here. Waral 鍗氬鏈夋洿澶氭枃绔,

[size=12.8000001907349px]4) Square root.1point3acres缃

.鏈枃鍘熷垱鑷1point3acres璁哄潧[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.

[size=12.8000001907349px]def squareRoot(number):
[size=12.8000001907349px]    """ Returns a float, which is the square root of number """
. more info on
[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:-google 1point3acres

[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?-google 1point3acres
. 1point 3acres 璁哄潧
[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?

[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.

[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?

[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.

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

补充内容 (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...





  • · Yelp|主题: 11, 订阅: 4
fsc111 发表于 2015-1-31 07:49:23 | 显示全部楼层
回复 支持 反对

使用道具 举报

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

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 来自手机 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| rwei 发表于 2015-1-31 08:59:52 | 显示全部楼层
Primer 发表于 2015-1-31 08:18. more info on

1 week from onsite interview
回复 支持 反对

使用道具 举报

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

使用道具 举报

还来得及吗 发表于 2015-2-2 00:08:36 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| 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).鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.         colm=random.sample(range(W),M). visit for more.
  8.         for row in rowm:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.                 for col in colm:
  10.                         board[row][col]='m'.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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):
  24.                         bruce(row,col)
  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?

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 = []. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.     while k > 0:
  5.         index = int(random() * (n-k)). from:
  6.         result.append(indices[index])
  7.         indices[index] = indices[n-len(result)]
  8.         k -= 1
  9.     return result
  10. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11. def get2Dcoordinate(index, board_width): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.     col = index % board_width
  13.     row = index / board_width
  14.     return row, col

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

  21. def updateCount(row, col, board):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  22.     for i in xrange(row - 1, row + 2):
  23.         for j in xrange(col - 1, col + 2):
  24.             if validIndex(i, j, board) and i != row and j != col:
  25.                 print (i, j)
  26.                 board[i][j] += 1

  27. def generateBoard(L, W, M):.1point3acres缃
  28.     num_mines = L * W
  29.     if num_mines < M:
  30.         return None-google 1point3acres
  31.     mine_indices = N_choose_K(range(num_mines), num_mines, M)
  32.     board = [[0 for col in xrange(W)] for row in xrange(L)]-google 1point3acres
  33.     # place mines
  34.     row_cols = [get2Dcoordinate(index, W) for index in mine_indices]
  35.     print row_cols
  36.     for row, col in row_cols:
  37.         board[row][col] = 'm'
  38.     for row, col in row_cols:
  39.         updateCount(row, col, board)
  40.     return board
  41. -google 1point3acres
  42. board = generateBoard(10, 10, 20)
  43. for row in board:
  44.     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 ...

回复 支持 反对

使用道具 举报

贪睡之萨满 发表于 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?

        colm=random.sample(range(W),M). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

贪睡之萨满 发表于 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 下一条

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

custom counter

GMT+8, 2017-5-25 03:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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