Really Health 電面 game of life

剛剛面完這家店面，韓國小哥蠻有耐心的。
在網路上找不到這家公司的題目、也不確定是否有題庫。
就在此分享題目給大家做參考

使用的平台是 codinghire ,  界面挺難用的。幾乎等於純文字編輯(code highlight 至少for python是完全沒有)

# 被問到的題目是 Ga

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

是 O(1)
如果我理解有錯的話歡迎指正，謝謝

(需要大米，給點大米是對樓主發文的一點鼓勵，也不會消耗您分數!)

1. # /*
   
2. # Conway’s Game of Life
   
3. 
   
4. # Rules
   
5. # The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
   
6. 
   
7. # 1) Any live cell with fewer than two live neighbors dies, as if caused by under-population.
   
8. # 2) Any live cell with two or three live neighbors lives on to the next generation.
   
9. # 3) Any live cell with more than three live neighbors dies, as if by overcrowding.
   
10. # 4) Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
    
11. 
    
12. 
    
13. # Example:
    
14. # -------
    
15. # ______________
    
16. # |X = Dead Cell |
    
17. # |O = Alive Cell|
    
18. # --------------
    
19. 
    
20. # 1 2 3 1 2 3 1 2 3
    
21. # _____ _____ _____
    
22. # A |O O O| A |O O O| A |X O X|
    
23. # B |X O X| => B |X X X| => B |X X X| => ...
    
24. # C |O O O| C |O O O| C |X O X|
    
25. # ----- ----- -----
    
26. 
    
27. # Exercise: In any language you like, please implement a version of this game. You can assume any data structure and method of calling your app that you want.
    
28. # */
    
29. 
    
30. DEAD = 0
    
31. LIVE = 1
    
32. DEAD_TO_DEAD = 2
    
33. DEAD_TO_LIVE = 3
    
34. LIVE_TO_DEAD = 4
    
35. LIVE_TO_LIVE = 5
    
36. 
    
37. def update_current_cell_to_transient(i, j, board):
    
38. live_cnt = 0
    
39. for next_i in {i-1,i,i+1}:
    
40. for next_j in {j-1,j,j+1}:
    
41. # skip current cell:
    
42. if next_i==i and next_j==j:
    
43. continue
    
44. # check the position is on the board.
    
45. if 0<= next_i < len(board) and 0<= next_j< len(board[0]) and board[next_i][next_j] in {LIVE, LIVE_TO_DEAD, LIVE_TO_LIVE}:
    
46. live_cnt+=1
    
47.    
    
48. # update to transient state
    
49. if board[i][j] == LIVE:
    
50. if live_cnt < 2:
    
51. board[i][j] = LIVE_TO_DEAD
    
52. elif live_cnt in {2,3}:
    
53. board[i][j] = LIVE_TO_LIVE
    
54. else:
    
55. board[i][j] = LIVE_TO_DEAD
    
56. elif board[i][j] == DEAD:
    
57. if live_cnt ==3 :
    
58. board[i][j] = DEAD_TO_LIVE
    
59. else:
    
60. board[i][j] = DEAD_TO_DEAD
    
61.             
    
62. def update_transient_to_final_status(i, j, board):
    
63. if board[i][j] in {DEAD_TO_LIVE, LIVE_TO_LIVE}:
    
64. board[i][j] = LIVE
    
65. else:
    
66. board[i][j] = DEAD
    
67.             
    
68. 
    
69. # board: 2D array
    
70. # 0: DEAD
    
71. # 1: LIVE
    
72. def game_of_live(board):
    
73. # // validate input
    
74. if not board:
    
75. return []
    
76.         
    
77. # check each cell on this baord and update the current state to transient state ( because i don't want to loss info)
    
78.    
    
79. for i in range(len(board)):
    
80. for j in range(len(board)):
    
81. update_current_cell_to_transient(i,j, board)
    
82.             
    
83. # update transient status to final status
    
84. for i in range(len(board)):
    
85. for j in range(len(board)):
    
86. update_transient_to_final_status(i,j, board)
    
87.             
    
88.    
    
89. # update the transient state to next state.
    
90. # print(board)
    
91. return board
    
92.    
    
93. 
    
94. # 1 2 3 1 2 3 1 2 3
    
95. # _____ _____ _____
    
96. # A |O O O| A |O O O| A |X O X|
    
97. # B |X O X| => B |X X X| => B |X X X| => ...
    
98. # C |O O O| C |O O O| C |X O X|
    
99. # ----- ----- -----
    
100. 
     
101. import unittest
     
102. class MyTestCase(unittest.TestCase):
     
103. def test_something(self):
     
104. input = [
     
105. [1,1,1],
     
106. [0,1,0],
     
107. [1,1,1]
     
108. ]
     
109. expect = [
     
110. [1,1,1],
     
111. [0,0,0],
     
112. [1,1,1]
     
113. ]
     
114. self.assertEqual(expect, game_of_live(input))
     
115. 
     
116. input = [
     
117. [1,1,1],
     
118. [0,1,0],
     
119. [1,1,1]
     
120. ]
     
121. 
     
122. game_of_live(game_of_live(game_of_live(input)))
     
123. 
     
124. # round 1
     
125. [[1, 1, 1],
     
126. [0, 0, 0],
     
127. [1, 1, 1]
     
128. ]
     
129. 
     
130. # round 2
     
131. [[0, 1, 0],
     
132. [0, 0, 0],
     
133. [0, 1, 0]
     
134. ]
     
135. # round 3
     
136. [[0, 0, 0],
     
137. [0, 0, 0],
     
138. [0, 0, 0]
     
139. ]
     
140.    
     

复制代码