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
x and yIf 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.