Problems from Programming Praxis: INSERT LINK
Posted on May 13, 2014
Solutions written by ggventurini on May 14 2014
One of the sites that I watch from time to time is Career Cup, which publishes coding questions that have been asked in actual job interviews. These questions came through this morning:
- Consider a sorted singly-linked list having the following nodes: 10 -> 30 -> 50 -> 70 -> NULL. You are given a pointer to node 50 and a new node having the value 40. Can you insert node 40 correctly in the list maintaining the ascending order?
# my linked list class
class llist:
def __init__(self, value, next_elem):
self.value = value
self.next_elem = next_elem
old = None
values = [10, 30, 50, 70, None]
values.reverse()
for i in values:
old = llist(i, old)
if i == 50:
a = old
print "We start with the element: %s" % str(a.value)
# solution
new_elem = llist(50, a.next_elem)
a.value = 40
a.next_elem = new_elem
print "Solved, list after the insertion:"
while True:
print old.value,
old = old.next_elem
if old == None:
break
We start with the element: 50 Solved, list after the insertion: 10 30 40 50 70 None
- Given a linked list 5 -> 4 -> 3 -> 2 -> 1 produce a linked list 4 -> 2 -> 0 -> 2 -> 1 by subtracting the last node of the list from the first, the next-to-last node from the second, and so on, stopping at the midpoint of the list.
old = None
values = [5, 4, 3, 2, 1]
values.reverse()
for i in values:
old = llist(i, old)
# this is the head of the list
head = old
print "We start from head: %s" % str(head.value)
print "List before:",
i = head
while True:
print i.value,
i = i.next_elem
if i == None:
break
print ""
print "Solving..."
# Not pretty, but I suppose we know the list length.
list_len = 5
j = head
steps = range(list_len - 1, -1, -2)
for _ in range(int(list_len/2 + list_len % 2)):
i = j
for _ in range(steps.pop(0)):
i = i.next_elem
j.value -= i.value
j = j.next_elem
print "List after:",
i = head
while True:
print i.value,
i = i.next_elem
if i == None:
break
We start from head: 5 List before: 5 4 3 2 1 Solving... List after: 4 2 0 2 1
- Write a program to output the number of consecutive trailing zeros in the factorial of a number. For example, if the number is 5, then 5! = 120, and there is one trailing zero.
def zeros_in_factorial(i):
"""Returns the number of trailing zeros in the factorial of an int i"""
zeros = [0, 0]
ind = {2:0, 5:1}
while i > 1:
div = [0, 0]
for j in ind.keys():
while int(i/(j**div[ind[j]])) % j == 0 and 2*i > j**div[ind[j]]:
div[ind[j]] += 1
i = i - 1
zeros = [x+y for x, y in zip(div, zeros)]
return min(zeros)
for i in range(2, 20):
print math.factorial(i), zeros_in_factorial(i)
2 0 6 0 24 0 120 1 720 1 5040 1 40320 1 362880 1 3628800 2 39916800 2 479001600 2 6227020800 2 87178291200 2 1307674368000 3 20922789888000 3 355687428096000 3 6402373705728000 3 121645100408832000 3