Five programming problems every Software Engineer should be able to solve

etienne_marais said:
I take it that entails something more than just a recursive function ?
Click to expand...

Yup. A recursive function requires iteration and is at best O(log n) (and that's a fairly advanced recursive Fininacci function). You can represent the sequence as the repetitive application of a simple 2x2 matrix. To avoid actually doing the iteration, you can compute the Singular Value Decomposition of the matrix, put the singular values to the Nth power (I.e. you've computed the matrix power) and put (0 1) in as an input vector, and bingo you've got the Nth and N-1th Fibonacci number without doing any iteration or recursion.
 
cguy said:
Yup. A recursive function requires iteration and is at best O(log n) (and that's a fairly advanced recursive Fininacci function). You can represent the sequence as the repetitive application of a simple 2x2 matrix. To avoid actually doing the iteration, you can compute the Singular Value Decomposition of the matrix, put the singular values to the Nth power (I.e. you've computed the matrix power) and put (0 1) in as an input vector, and bingo you've got the Nth and N-1th Fibonacci number without doing any iteration or recursion.
Click to expand...

:WTF: :D
 
I tried to do the solutions as generically as possible, but if you copy and paste these into Python they'll work.

Problem 1:
Code: 
numbers = [1,2,3,4,5,6,7,8,9]

def for_count(lst):
    total = 0
    for i in xrange(0, len(lst)):
        total = total + lst[i]
    return total

def while_count(lst):
    total = 0
    i = 0
    while i < len(lst):
        total = total + lst[i]
        i = i + 1
    return total

def recurse_count(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        i = len(lst) - 1
        subtotal = lst[i] + lst[i - 1]
        lst.pop() #into the void with you
        lst[-1] = subtotal
        return recurse_count(lst)

print for_count(numbers)
print while_count(numbers)
print recurse_count(numbers)

Problem 2:
Code: 
#This function supports asymmetric list combination too
def asymmetric_comb(lst1, lst2):
    newlst = []
    j = max(len(lst1), len(lst2))
    for i in xrange(0,j):
        if i < len(lst1):
            newlst.append(str(lst1[i]))
        if i < len(lst2):
            newlst.append(str(lst2[i]))
    return newlst

print asymmetric_comb(["a","b","c","d","e"], [1,2,3])
print asymmetric_comb(["a","b","c","d"], [1,2,3,4,5])

Problem 3:
Code: 
import math

gr = (1 + math.sqrt(5)) / 2
def fibonacci(n):
    return (math.pow(gr, n) - math.pow(1 - gr, n)) / math.sqrt(5)

total = 0
for i in xrange(0, 100):
    total = total + fibonacci(i)

print total

Problem 4 (this one was quite fun, and yes, it uses a bubblesort...):
Code: 
import math

numbers = [50,2,1,9,10,100,52]

def arrange(lst):
    for i in xrange(0, len(lst)):
        for j in xrange(0, len(lst)):
            if i != j:
                comparison = compare(lst[i], lst[j])
                if lst[i] == comparison[0]:
                    temp = lst[j]
                    lst[j] = lst[i]
                    lst[i] = temp
    return lst

def compare(num1, num2):
    pow10_1 = math.floor(math.log10(num1))
    pow10_2 = math.floor(math.log10(num2))

    temp1 = num1
    temp2 = num2

    if pow10_1 > pow10_2:
        temp2 = (temp2 / math.pow(10, pow10_2)) * math.pow(10, pow10_1)
    elif pow10_2 > pow10_1:
        temp1 = (temp1 / math.pow(10, pow10_1)) * math.pow(10, pow10_2)

    print "Starting", num1, num2
    print "Comparing", temp1, temp2

    if temp1 > temp2:
        return [num1, num2]
    elif temp2 > temp1:
        return [num2, num1]
    else:
        if num1 < num2:
            return [num1, num2]
        else:
            return [num2, num1]

print arrange(numbers)

Problem 5:

Yet to tackle this one. However, since the root is always 1, a tree structure branching from (n) into (n + 1) with three operators (+,-,c) where "c" is "combine" should be one solution to the problem. Is there a more efficient way? In the end this has 3^9 possible solutions, but it should be possible to eliminate some along the way.

Code: 
					1
		/			|			\
		+2			-2			c2
	/	|	\	/	|	\	/	|	\
	+3	-3	c3	+3      -3	 c3	+3	-3	c3
	...................................
 
Last edited:
Bar0n said:
I tried to do the solutions as generically as possible, but if you copy and paste these into Python they'll work.
Problem 5:

Yet to tackle this one. However, since the root is always 1, a tree structure branching from (n) into (n + 1) with three operators (+,-,c) where "c" is "combine" should be one solution to the problem. Is there a more efficient way? In the end this has 3^9 possible solutions, but it should be possible to eliminate some along the way.

Code: 
					1
		/			|			\
		+2			-2			c2
	/	|	\	/	|	\	/	|	\
	+3	-3	c3	+3      -3	 c3	+3	-3	c3
	...................................
Click to expand...

When I saw that you were using python, I had a very cunning idea specific to python (well actually anything that supports string-as-code execution):

Answer to 5:

Code: 
op = ('+', '-', '')
for a in range(0,3):
  for b in range(0,3):
    for c in range(0,3):
      for d in range(0,3):
        for e in range(0,3):
          for f in range(0,3):
            for g in range(0,3):
              for h in range(0,3):
                lhs = '1'+op[a]+'2'+op[b]+'3'+op[c]+\
                      '4'+op[d]+'5'+op[e]+'6'+op[f]+\
                      '7'+op[g]+'8'+op[h]+'9'
                res = eval( lhs )
                if ( res == 100 ):
                  print lhs+'=100'

Not the most elegant solution, but it took all of 3 minutes to code. :D

It does all 3^8 combinations (number of ops, not coefficients), and it also uses python to evaluate the string (which is actuall pretty fast - takes less about 1 secs to run), whereas most solutions (I would guess), essentially try to parse the string manually.
 
cguy said:
When I saw that you were using python, I had a very cunning idea specific to python (well actually anything that supports string-as-code execution):

Answer to 5:

Code: 
op = ('+', '-', '')
for a in range(0,3):
  for b in range(0,3):
    for c in range(0,3):
      for d in range(0,3):
        for e in range(0,3):
          for f in range(0,3):
            for g in range(0,3):
              for h in range(0,3):
                lhs = '1'+op[a]+'2'+op[b]+'3'+op[c]+\
                      '4'+op[d]+'5'+op[e]+'6'+op[f]+\
                      '7'+op[g]+'8'+op[h]+'9'
                res = eval( lhs )
                if ( res == 100 ):
                  print lhs+'=100'

Not the most elegant solution, but it took all of 3 minutes to code. :D

It does all 3^8 combinations (number of ops, not coefficients), and it also uses python to evaluate the string (which is actuall pretty fast - takes less about 1 secs to run), whereas most solutions (I would guess), essentially try to parse the string manually.
Click to expand...

Yes, that's a fairly quick and easy solution in Python. Would be a bit more effort in another language, I think.

Overall, I found problem 4 the most interesting.
 
cguy said:
When I saw that you were using python, I had a very cunning idea specific to python (well actually anything that supports string-as-code execution):

Answer to 5:

Code: 
op = ('+', '-', '')
for a in range(0,3):
  for b in range(0,3):
    for c in range(0,3):
      for d in range(0,3):
        for e in range(0,3):
          for f in range(0,3):
            for g in range(0,3):
              for h in range(0,3):
                lhs = '1'+op[a]+'2'+op[b]+'3'+op[c]+\
                      '4'+op[d]+'5'+op[e]+'6'+op[f]+\
                      '7'+op[g]+'8'+op[h]+'9'
                res = eval( lhs )
                if ( res == 100 ):
                  print lhs+'=100'

Not the most elegant solution, but it took all of 3 minutes to code. :D

It does all 3^8 combinations (number of ops, not coefficients), and it also uses python to evaluate the string (which is actuall pretty fast - takes less about 1 secs to run), whereas most solutions (I would guess), essentially try to parse the string manually.
Click to expand...

This trick should also work in java-script.
A solution that doesn't brute force it could be a bit more interesting.
 
etienne_marais said:
:WTF: :D
Click to expand...

:)

FYI, if you look at Bar0n's solution, he uses an explicit Fibonacci formula to compute the Nth number in the sequence. The magical numbers and operations (sqrt(5), (1+sqrt(5))/2 and powers) he's using will pop out exactly from the process I outlined above.
 
Code: 
op = ('+', '-', '')
for a in range(0,3):
  for b in range(0,3):
    for c in range(0,3):
      for d in range(0,3):
        for e in range(0,3):
          for f in range(0,3):
            for g in range(0,3):
              for h in range(0,3):
                lhs = '1'+op[a]+'2'+op[b]+'3'+op[c]+\
                      '4'+op[d]+'5'+op[e]+'6'+op[f]+\
                      '7'+op[g]+'8'+op[h]+'9==100'
                if eval( lhs ):
                  print lhs

A minor refinement - no need to do any of the evaluation outside of the eval.
 
And a quick recursive version, based on the same principle:

Code: 
def f( n, eq ):
  if n==10:
    if eval(eq)==100:
      print eq + '==100'
    return
  f( n+1, eq+'+'+str(n) )
  f( n+1, eq+'-'+str(n) )
  f( n+1, eq+str(n) )  
f(2, '1')
 
cguy said:
:)

FYI, if you look at Bar0n's solution, he uses an explicit Fibonacci formula to compute the Nth number in the sequence. The magical numbers and operations (sqrt(5), (1+sqrt(5))/2 and powers) he's using will pop out exactly from the process I outlined above.
Click to expand...

Cool.

I checked my 'Linear Algebra: An Applied First Course", while it covers singular matrices and conjugates, I don't see singular value decomposition. Which year at university will this typically be taught ? ( I had linear algebra up to first semester, second year level, I may just have forgotten this ?)
 
Last edited:
etienne_marais said:
Cool.

I checked my 'Linear Algebra: An Applied First Course", while it covers singular matrices and conjugates, I don't see singular value decomposition. Which year at university will this typically be taught ?
Click to expand...

It's usually in the more advanced linear algebra courses - I think I touched on it in my 2nd year. It is similar to the eigendecomposition of a matrix, except with SVD's, the matrix doesn't have to be square, and the singular values of a real matrix are always real, whereas eigenalues can be complex. It does this by relaxing the constraint that the pre-and-post multiplied matrices be inverses of one another.

http://en.wikipedia.org/wiki/Singular_value_decomposition
 
cguy said:
It's usually in the more advanced linear algebra courses - I think I touched on it in my 2nd year. It is similar to the eigendecomposition of a matrix, except with SVD's, the matrix doesn't have to be square, and the singular values of a real matrix are always real, whereas eigenalues can be complex. It does this by relaxing the constraint that the pre-and-post multiplied matrices be inverses of one another.

http://en.wikipedia.org/wiki/Singular_value_decomposition
Click to expand...

I love mathematics far more than programming itself, pity I did not exactly excel in it though. In fact, I'm more motivated now to pick up the books to refresh some linear algebra than doing any programming whatsoever. Out of curiosity, does your job entail mathematics beyond the usual ?
 
etienne_marais said:
I love mathematics far more than programming itself, pity I did not exactly excel in it though. In fact, I'm more motivated now to pick up the books to refresh some linear algebra than doing any programming whatsoever. Out of curiosity, does your job entail mathematics beyond the usual ?
Click to expand...

Yup. A lot of advanced maths and stats. Almost everyone I work closely with right now has a PhD in stats, engineering, maths or physics.
 
My solution to number 4:
Code: 
def large( nums ):
  return ''.join(sorted([str(n)for n in nums],cmp=lambda x,y:int(y+x)-int(x+y)))
 
First 3 too easy to even bother doing. 4 and 5 slightly more complex but I'd end up just generating all permutations and evaluating/sorting the results which is almost the same solution. It would work but wouldn't be elegant.

Also, now I see why cguy can spend $12000 on living expenses. I'm useless at math...
 
The
rorz0r said:
First 3 too easy to even bother doing. 4 and 5 slightly more complex but I'd end up just generating all permutations and evaluating/sorting the results which is almost the same solution. It would work but wouldn't be elegant.

Also, now I see why cguy can spend $12000 on living expenses. I'm useless at math...
Click to expand...

The quick goes away, but the dirty remains.
 
Last edited:
True dat. Many a "temporary solution" has been running for years. At least in my previous job I had the mandate to go fix old/crap code. Now I don't touch a damn thing until all necessary formalities has been followed. No one will ever accept a quote and pay for something to be done again, same functionality, but better.
 
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X