interview.py

"""
1)

Given a 2D list of integers where each row and column is sorted in ascending
order from left to right and top to bottom...
e.g.
"""

"""
Write a method that checks for the number occurrences of an integer in the matrix.

NOTE: there is at most one occurrence of a particular integer in a row or column, but there may be more than one occurrence over all in the matrix.
"""

import bisect

listOfListOfInts = [
    [2,  3,  6,  11, 15],
    [5,  8,  9,  17, 23],
    [7,  9,  11, 18, 25],
    [10, 13, 17, 19, 31],
    [15, 18, 19, 30, 47]
]

def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i

def numberOfOccurances(i):
    occurances = 0
    for row in listOfListOfInts:
        if index(row, i) is not None:
            occurances += 1
    return occurances

#print(numberOfOccurances(15))
#print(numberOfOccurances(17))
#print(numberOfOccurances(47))
#print(numberOfOccurances(100))


"""
2)

In Python, random.randint(0,99) would return a single pseudo-random integer. 
Make two generators, which would provide a limited-length sequence of such pseudo-random integers in direct and reverse orders respectively. Length of the sequence is a parameter.

Output Example:
5 23 90 12 66 71 1
1 71 66 12 90 23 5

"""

import random
n = 100
p = 10
chunk_seeds = {} # idx -> seed

def get_chunk(index):
    if index not in chunk_seeds:
        chunk_seeds[index] = 10#random.randint(0,99)
    chunk = []
    random.seed(chunk_seeds[index])
    for i in range(p):
        chunk.append(random.randint(0,99))
    return chunk
    
def random_ints():
    for i in range(n/p):
        chunk = get_chunk(int(i/p))
        for j in range(p):
            yield chunk[j]

def reverse_random_ints():
    for i in range(n/p):
        chunk = get_chunk(int(i/p))
        for j in range(p):
            yield chunk[j]
            
f = random_ints()
#r = reverse_random_ints()

print(" ".join([str(x) for x in f]))
#print(" ".join([str(x) for x in r]))