PradeepN
BAN USER- 6of 6 votes
AnswersGiven an array of elements, return an array of values pertaining to how many elements are greater than that element remaining in the array.
- PradeepN in United States
Brute force is obvious, but must be done faster than O(n^2)
Ex. [3,4,5,9,2,1, 3]
Return [3, 2, 1, 0, 1, 1, 0]
First element is 3 because 3<4,5,9. Second element is 2 because 4< 5,9 etc| Report Duplicate | Flag | PURGE
Google Algorithm
import Queue
import heapq
def prime_set(prime_set, n):
prime_set = list(prime_set)
print prime_set
prime_set.sort()
queue_list = []
ret_list = []
for i in prime_set:
tmp_queue = Queue.Queue()
queue_list.append(tmp_queue)
heap = []
ret_list.append(1)
for j in range(0,len(queue_list)):
queue_list[j].put(1*prime_set[j])
heapq.heappush(heap, (queue_list[j].get(),j))
while len(ret_list) < n:
v = heapq.heappop(heap)
ret_list.append(v[0])
for j in range(v[1], len(queue_list)):
val = (prime_set[j]*v[0])
queue_list[j].put(val)
heapq.heappush(heap,(queue_list[v[1]].get(), v[1]))
print ret_list
if __name__ == '__main__':
primes = {2,3,5,7, 11}
prime_set(primes, 100)
def permute_set(pref, sets, length):
if len(pref) == length:
print pref
else:
for i in sets:
se = list(pref)
se.append(i)
permute_set(se, sets, length)
def main():
sets = {2,3,4, 5}
length = 4
se= []
count = 0
permute_set(se, sets, length)
if __name__ == '__main__':
main()
Sort isn't actually necessary, I was just testing it.
- PradeepN October 31, 2015