Zillow phone interview

Zillow

Given  a sorted array of integers. Find the median of the items

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

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

reashold = 5
return median = 7

1. class Solution:
   
2. 
   
3.     def find_median(self, array, threashold):
   
4.         lst = [x for x in array if x >= threashold]
   
5.         length = len(lst)
   
6.         if length == 0:
   
7.             return 0
   
8.         elif length % 2 == 0:
   
9.             m1 = length / 2
   
10.             m2 = length / 2 - 1
    
11.             return (lst[m1] + lst[m2]) / 2
    
12.         else:
    
13.             m = length / 2
    
14.             return lst[m]
    

复制代码

Running Time: O(n).

1. class Solution:
   
2. 
   
3.     def find_median(self, array, threashold):
   
4.         first_idx = self._find_first_idx(array, threashold)
   
5.         lst = array[first_idx:]
   
6.         length = len(lst)
   
7.         if length == 0:
   
8.             return 0
   
9.         elif length % 2 == 0:
   
10.             m1 = length / 2
    
11.             m2 = length / 2 - 1
    
12.             return (lst[m1] + lst[m2]) / 2
    
13.         else:
    
14.             m = length / 2
    
15.             return lst[m]
    
16. 
    
17.     def _find_first_idx(self, array, threashold):
    
18.         l = 0
    
19.         r = len(array) - 1
    
20.         while l <= r:
    
21.             m = (l + r) / 2
    
22.             mid = array[m]
    
23.             mid_pre = array[m - 1] if m - 1 >= 0 else None
    
24.             if mid == threashold and \
    
25.                     (mid_pre is None or mid_pre < threashold):
    
26.                 return m
    
27.             elif mid == threashold and mid_pre == threashold:
    
28.                 r = m - 1
    
29.             elif mid > threashold:
    
30.                 r = m - 1
    
31.             elif mid < threashold:
    
32.                 l = m + 1
    
33.         return l
    

复制代码

Running Time: O(log n)

1. import unittest
   
2. from solution import Solution
   
3. from solution import Solution as Solution2
   
4. 
   
5. 
   
6. class Test(unittest.TestCase):
   
7. 
   
8.     def test1(self):
   
9.         s = Solution()
   
10.         array = [1,2,3,4,5,6,7,8,9]
    
11.         threashold = 5
    
12.         res = s.find_median(array, threashold)
    
13.         self.assertEqual(res, 7)
    
14.         s2 = Solution2()
    
15.         res = s.find_median(array, threashold)
    
16.         self.assertEqual(res, 7)
    
17. 
    
18.     def test2(self):
    
19.         s = Solution()
    
20.         array = [1,2,3,4,5,6,7,8,9]
    
21.         threashold = 9
    
22.         res = s.find_median(array, threashold)
    
23.         self.assertEqual(res, 9)
    
24.         s2 = Solution2()
    
25.         res = s.find_median(array, threashold)
    
26.         self.assertEqual(res, 9)
    
27. 
    
28.     def test3(self):
    
29.         s = Solution()
    
30.         array = [1,2,3,4,5,6,7,8,9]
    
31.         threashold = 0
    
32.         res = s.find_median(array, threashold)
    
33.         self.assertEqual(res, 5)
    
34.         s2 = Solution2()
    
35.         res = s.find_median(array, threashold)
    
36.         self.assertEqual(res, 5)
    
37. 
    
38.     def test4(self):
    
39.         s = Solution()
    
40.         array = [1,2,3,4,5,6,7,8,9]
    
41.         threashold = 2
    
42.         res = s.find_median(array, threashold)
    
43.         self.assertEqual(res, 5)
    
44.         s2 = Solution2()
    
45.         res = s.find_median(array, threashold)
    
46.         self.assertEqual(res, 5)
    
47. 
    
48.     def test5(self):
    
49.         s = Solution()
    
50.         array = [1,2,3,4,5,6,7,8,9]
    
51.         threashold = 10
    
52.         res = s.find_median(array, threashold)
    
53.         self.assertEqual(res, 0)
    
54.         s2 = Solution2()
    
55.         res = s.find_median(array, threashold)
    
56.         self.assertEqual(res, 0)
    
57. if __name__ == '__main__':
    
58.     unittest.main(verbosity=2)
    

复制代码

请问是假设threshold在array中吗？就是说会不会有下面这种情况：
array = [1, 2, 3, 4, 6, 7, 8, 9]
threashold = 5

RichardCen 发表于 2015-11-8 12:56
请问是假设threshold在array中吗？就是说会不会有下面这种情况：
array = [1, 2, 3, 4, 6, 7, 8, 9]
thre ...

无所谓啊 大于也符合啊

我刚面的，也是这个题目