一亩三分地论坛

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

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

Yelp onsite 已跪

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

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

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

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

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


.鐣欏璁哄潧-涓浜-涓夊垎鍦



. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

[size=12.8000001907349px]用一個 2D array 來表示 board,給出 board 的長(L)寬(W) 和地雷數量(M),隨機地把 M 個地雷放在 L*W 個格子裏面,並在沒有地雷的格子中標記格子周圍地雷的數量。要求:絕對的 Random,並且避免發生 collision(generate 出同樣的 random number after processing)

[size=12.8000001907349px]def generateBoard(L, W, M):
[size=12.8000001907349px]    """ return a 2D array representing the game board """
. From 1point 3acres bbs
[size=12.8000001907349px]2) Implement Conway's Game of Life
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
[size=12.8000001907349px]

                               
登录/注册后可看大图



[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

[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.. from: 1point3acres.com/bbs


[size=12.8000001907349px]class GameOfLife:

[size=12.8000001907349px]    def __init__(self, board_width):. 1point3acres.com/bbs
[size=12.8000001907349px]        """ Your code here """

[size=12.8000001907349px]    def set_alive(self, row, column):
[size=12.8000001907349px]        """ Your code here """

. more info on 1point3acres.com
[size=12.8000001907349px]    def set_dead(self, row, column):
        """ Your code here """. Waral 鍗氬鏈夋洿澶氭枃绔,


[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]    """. more info on 1point3acres.com
[size=12.8000001907349px]    # Your code here
.1point3acres缃
[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.

[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). 鍥磋鎴戜滑@1point 3 acres

[size=12.8000001907349px]6) Resume related short questions:
. 1point3acres.com/bbs
[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)
. Waral 鍗氬鏈夋洿澶氭枃绔,
[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?

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

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多久出结果的?
.1point3acres缃
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. from: 1point3acres.com/bbs
  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:-google 1point3acres
  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]. visit 1point3acres.com for more.
  15.                 colnbr=[-1,-1,0,1,1,1,0,-1]
  16.                 count=0. From 1point 3acres bbs
  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):. 1point 3acres 璁哄潧
  24.                         bruce(row,col)
  25.         return board. From 1point 3acres bbs



  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 = []. 1point 3acres 璁哄潧
  4.     while k > 0:
  5.         index = int(random() * (n-k))
  6.         result.append(indices[index])
  7.         indices[index] = indices[n-len(result)]
  8.         k -= 1
  9.     return result

  10. def get2Dcoordinate(index, board_width):
  11.     col = index % board_width. from: 1point3acres.com/bbs
  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-google 1point3acres
  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):-google 1point3acres
  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. Waral 鍗氬鏈夋洿澶氭枃绔,
  33.     row_cols = [get2Dcoordinate(index, W) for index in mine_indices]
  34.     print row_cols
  35.     for row, col in row_cols:
  36.         board[row][col] = 'm'
  37.     for row, col in row_cols:
  38.         updateCount(row, col, board)
  39.     return board. visit 1point3acres.com for more.
  40. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  41. board = generateBoard(10, 10, 20)
  42. for row in board:
  43.     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的方法啊?
. 1point 3acres 璁哄潧
其實就在 leetcode 那道題的基礎上加了一個 prefix match 和 suffix match,增加兩個 if 應該就能 handle。我感覺到目前為止還沒有遇到有公司是不考 dynamic programming 的…
回复 支持 反对

使用道具 举报

Larrylianj 发表于 2015-3-28 05:53:46 | 显示全部楼层
rwei 发表于 2015-3-26 00:24. more info on 1point3acres.com
其實就在 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)
...
. From 1point 3acres bbs
为什么不check collision?感觉check collision才是难点
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 20:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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