Welcome, guest | Sign In | My Account | Store | Cart

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
 1
 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