Found this Interview question. Here is my solution to it.
Assume f(x,y,z) = a^x * b^y * c^z
The x, y and z are integers larger than or equal to zero. Find the kth number in the series this function produces.
Check out my blog Captain DeadBones Chronicles
Python, 60 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | import sys
from collections import deque
def main(argv):
if len(argv) != 5:
sys.exit('Usage: kth.py <a> <b> <c> <k> <echo>')
# get bases
a = int(sys.argv[1])
b = int(sys.argv[2])
c = int(sys.argv[3])
k = int(sys.argv[4])
echo = int(sys.argv[5])
# setup queue
q1 = deque([])
q2 = deque([])
q3 = deque([])
# init variables
q1.append(1)
val = 0
for i in range(k):
# set v to the next value in queue or to MAX_INT if queue empty
if len(q1) > 0: v1 = q1[0]
else: v1 = 2**32
if len(q2) > 0: v2 = q2[0]
else: v2 = 2**32
if len(q3) > 0: v3 = q3[0]
else: v3 = 2**32
# choose the next minimum value from the 3 queues
val = min(v1,v2,v3)
# add next values to queue
if val == v1:
q1.popleft()
q1.append(a*val)
q2.append(b*val)
elif val == v2:
q2.popleft()
q2.append(b*val)
elif val == v3:
q3.popleft()
# always add the largest
q3.append(c*val)
# if echo is True print every number
if echo: print str(i+1) + ": " + str(val)
print '\nThe kth number is: ' + str(val) + '\n'
if __name__ == "__main__":
main(sys.argv[1:])
|
Here are some example output:
python kth.py 3 5 7 20 0
The kth number is: 175
And another with the numbers:
python kth.py 3 5 7 10 1
1: 1
2: 3
3: 5
4: 7
5: 9
6: 15
7: 21
8: 25
9: 27
10: 35
The kth number is: 35
