peteris.rocks

Algorithm programming tips and tricks

Competitive programming basic tips and tricks in Python

Last updated on

Here is a small collection of basic tips and tricks that are useful for competitive programing and coding interviews. Code is written in the Python programming language.

Motivation for this post

I can solve the FizzBuzz problem easily because I know loops and how to determine if a number is divisible by another number. I know this because I just know, just like I know that O2 stands for oxygen. I must have learned this a long time ago.

I took part in programming competitions when I was in middle school and when I didn't know how to solve a problem after trying for a long time I looked up a solution. This way I learned about the modulo operator and how to determine the number of digits of an integer. I never figured it out on my own, I learned about it.

It explains why so many programmers can't solve the FizzBuzz problem in 1 minute. They have never competed in algorithm programming competitions and never had the use for determining the remainder of numbers. Sure, they must have learned this in college but there are so many things I've learned in computer science classes and forgotten.

If you've never taken part in competitive programming competitions and never learned about the basic tricks, this post is for you.

Whether a number is divisible by another number

If you want to know if 10 is divisible by 2, you can use the modulo operator to find out the remainder when you divide 10 by 2. If it's 0, the number is divisible by that number.

def is_divisible(n, k):
  return n % k == 0

>>> print is_divisible(10, 2)
True
>>> print is_divisible(10, 5)
True
>>> print is_divisible(10, 10)
True
>>> print is_divisible(10, 1)
True
>>> print is_divisible(10, 7)
False

This is how you can solve the FizzBuzz problem.

Whether a number is odd or even

An odd or strange number is a number that is not a multiple of 2. An even number is the opposite.

To determine if a number is odd or even, we divide it by two and check the remainder. If the remainder is 0, then it's an even number, otherwise it's an odd number.

def is_even(n):
  return n % 2 == 0

def is_odd(n):
  return n % 2 != 0

>>> print is_even(10), is_odd(10)
True False
>>> print is_even(11), is_odd(11)
False True

Digits in a number

Get the last digit of a number

If you need to get the last digit of a number without using string manipulation, you can use the modulo operator to get the remainder when you divide the number by 10.

def last_digit(n):
  return n % 10

>>> print last_digit(123)
3
>>> print last_digit(456)
6
>>> print last_digit(1)
1
>>> print last_digit(10)
0

How to get the digits of an integer

If you need to extract the digits from the number 456 without using string manipulation, you can divide it by 10 until it becomes 0. Use the modulo operator to get the last digit.

def digits(n):
  while n:
    yield n % 10
    n /= 10

>>> print list(digits(123))
[3, 2, 1]

Sum of all digits of a number

Like before, you can get the last digit of a number by using the modulo operator n % 10 and then remove the last digit by diving the number by 10.

def sum(n):
  s = 0
  while n:
    s += n % 10
    n /= 10
  return s

>>> print sum(123)
6

Number of digits in a number

Instead of calculating the sum or returning all digits, count the number of times you'd return them.

def length(n):
  # if n == 0: return 1
  s = 0
  while n:
    s += 1
    n /= 10
  return s

>>> print length(123)
3
>>> print length(1)
1
>>> print length(0)
0 # modify the function if 0 is not the correct answer in your case

Reverse digits in a number

You know how to get all digits of a number. How can you create a number with the digits reversed?

We've previously seen how to get the digits in the reverse order. Now we need to combine them.

If you have 3, 2 and 1 you can create the number 321 by multiplying 3 by 100, 2 by 10 and 1 by 1 and summing them all up:

3*100 + 2*10 + 1*1 = 300 + 20 + 1 = 321

As you can see, if you know that the number of digits is 3 then you start with 10*10 = 100 and divide 100 by 10.

def length(n):
  s = 0
  while n:
    s += 1
    n /= 10
  return s

def reverse(n):
  sum = 0
  k = 10 ** (length(n) - 1)
  while n:
    sum += k * (n % 10)
    n /= 10
    k /= 10
  return sum

>>> print reverse(123)
321

Quickly divide or multiply by 2

Numbers are stored in memory as bits.

0  0000
1  0001
2  0010
3  0011
4  0100

If you shift all bits to the left, you are multiplying a number by 2:

1 0001
2 0010
4 0100

Similarly if you shift bits to the right, you will be dividing them by 2:

4 0100
2 0010
1 0001

In most programming languages you can do this with the bitwise operators.

>>> print 4 << 1   # shift bits to the left one time
8
>>> print 4 << 2   # shift bits to the left two times
16
>>> print 4 << 3   # shift bits to the left three times
32
>>> print 64 >> 1  # shift bits to the right one time
32

You can also do this with all numbers, not just those of power 2.

>>> print 3 << 1
6
>>> print 3 << 2
12
>>> print 12 >> 1
6

Swap two numbers

Here is how to swap two integers without using a temporary variable.

def swap(a, b):
  a = a + b
  b = a - b
  a = a - b
  return (a, b)

>>> swap(1, 2)
(2, 1)

And another way using XOR.

def swap_xor(a, b):
  a ^= b
  b ^= a
  a ^= b
  return (a, b)

>>> swap_xor(1, 2)
(2, 1)

You can read about advantages and disadvantages of using this approach in practice on Wikipedia.

In Python, you can use this syntax to swap elements, not just numbers.

def swap_python(a, b):
  a, b = b, a
  return (a, b)

>>> swap_python(1, 2)
(2, 1)
>>> swap_python('a', 'b')
('b', 'a')

Random number between x and y

If you have a random number generator that returns a number between 0 and 1, you can use the following formula to get a number in the range you need.

import random

def rand(min, max):
  n = random.uniform(0.0, 1.0)
  return int(n * (max - min) + min)

>>> print list(rand(0, 10) for _ in xrange(5))
[1, 8, 9, 8, 5]

Here is a visual explanation of how it works.

Very fast random number generator

Xorshift random number generators can be used to create sequences of pseudorandom numbers very, very quickly. They are useful when you need randomness but don't want to suffer a performance penalty.

Here is an implementation taken from Aristide on StackOverflow:

def xor128(n):
  x = 123456789
  y = 362436069
  z = 521288629
  w = 88675123
  while n:
    t = (x ^ (x << 11)) & 0xffffffff
    (x, y, z) = (y, z, w)
    w = (w ^ (w >> 19) ^ (t ^ (t >> 8))) & 0xffffffff
    yield w
    n -= 1

>>> print list(xor128(5))
[3701687786, 458299110, 2500872618, 3633119408, 516391518]

Sorting

The Wikipedia article on sorting algorithms is a great place to see an overview of existing sorting algorithms and their effectiveness.

Bubble sort

If you know nothing about sorting, the bubble sort algorithm is usually the first algorithm that is taught.

I remember when my teacher showed it to me when I was around 12. My reaction was something along the lines of "woah, this is so cool".

It is very easy to implement but not efficient in practice so it is never used. Note that this implementation is very easy to memorize but it is the most inefficient one.

def bubble_sort(list):
  for a, a_val in enumerate(list):
    for b, b_val in enumerate(list):
      if a_val < b_val:
        list[a], list[b] = list[b], list[a]
  return list

>>> print bubble_sort([1, 5, 3, 2, 4])
[1, 2, 3, 4, 5]

Remove duplicates from an array

One solution to this problem consists of two steps. First, sort the array. When an array is sorted, duplicate elements will be next to each other. Second, loop through the array and remove or ignore values that are equal to the previous values.

def unique(list):
  list.sort()
  prev = None
  for val in list:
    if prev is not None and val != prev:
      yield val
    prev = val

>>> print list(unique([4, 2, 1, 4, 1, 3, 5, 1]))
[1, 2, 3, 4, 5]

What if you can't change the order of elements in an array? You can use a set to store already seen elements.

def unique_stable(list):
  dupes = set()
  for val in list:
    if val not in dupes:
      dupes.add(val)
      yield val

>>> print list(unique_stable([4, 2, 1, 4, 1, 3, 5, 1]))
[4, 2, 1, 3, 5]

Remove several elements from an array in a single pass

Normally, when you remove an element from the middle of an array you need to shift the other elements one place to the left resulting in an O(n) time complexity where n is the number of elements in an array. This can be very inefficient if you need to remove several items.

If you are free to change the order of items in an array, you can replace the item to remove with the last element of an array and change the size of the array.

def remove(list, values_to_remove):
  new_length = len(list)
  for index, value in enumerate(list):
    if index >= new_length:
      continue
    if value in values_to_remove:
      list[index] = list[new_length - 1]
      new_length -= 1
  return list[:new_length]

>>> print remove([1, 2, 3, 4, 5, 6, 7, 8], [2, 3])
[1, 8, 7, 4, 5, 6]

TODO: spot the bug.

Whether a string is a rotation of another string

You want to know if the string rispete is a rotation of the string peteris.

If you concatenate rispete with itself and you'll get rispeterispete and you'll see that peteris is a substring.

def is_rotation(s1, s2):
  return s2 in s1+s1

>>> print is_rotation('rispete', 'peteris')
True

This solution creates a new string and so is not the most effective. But you can use this idea to develop a solution that loops over a string and when you reach the end start at the beginning again.

Majority element in a sequence

How you you determine the majority element in this sequence?

A A A C C B B C C C B C C

Here is the majority vote algorithm:

def majority_vote(sequence):
  counter = 0
  element = None
  for candidate in sequence:
    if counter == 0:
      element = candidate
      counter = 1
    else:
      if candidate == element:
        counter += 1
      else:
        counter -= 1
  return element

>>> print majority_vote('A A A C C B B C C C B C C'.split())
C

Practice this problem on leetcode.