注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
本帖最后由 大队管理员 于 2019-9-24 00:22 编辑
和一个quant聊了电面, 对方基本不会技术, 轻松忽悠, 然后email了我一道题, 原题底下:
Given a sorted array of N ints with duplicates, for example:
1,2,2,2,2,2,4,12,12,12,53
count the number of occurrences of each unique element.
1a) Solve this with an O(N) algorithm
1b) Solve this with a better-than-O(N) algorithm and analyze its time complexity.
我的solution, 求大佬们指教
import collections
import bisect
import random
import timeit
import time
arr = [1,2,2,2,2,2,4,12,12,12,53]
def randomSortedList(num):
res = []
for i in range(num):
res.append(random.randint(0, num))
res = sorted(res)
return res
# 1a) Solve this with an O(N) algorithm
# The below function will return a hashmap with each element as key, as their corresponding count as value
def search(arr):
res = collections.defaultdict(int)
for item in arr:
res[item] += 1
return res
print(search(arr))
print(binarySearch(arr))
print(search(arr2))
print(binarySearch(arr2))
"""
In terms of performance, method 1 performs better when there are more unique elements,
method 2 performs better when there are massive duplicates
"""
While it may be useful to run your code with the example array above, please also test it with a larger (ex., 100 elements) randomly generated, sorted array.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
recruiter第二天说代码非常好, 等对方回复onsite confirmation, 过了几天recruiter说, 抱歉, 对方内部有变化, 要等, 等了两周, 没信了 LOL
虽然对这个公司没兴趣,他们号称是做blockchain investment的, 但至少不行给个信啊
|