Coding Test
In the coding test The three main techniques to solve programming problems are Divide and Conquer, Recursion, and Dynamic Programming. Divide and Conquer involves breaking down a problem into smaller sub-problems, solving each sub-problem independently, and then combining the solutions to solve the original problem. Examples include Merge Sort and Binary Search. Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem, such as calculating the factorial of a number or solving the Tower of Hanoi problem. Dynamic Programming solves problems by breaking it down into simpler, smaller subproblems and storing the results of each subproblem to avoid duplicate work, as seen in the Fibonacci series and the 0/1 Knapsack problem. These techniques often involve trade-offs in terms of computation time and memory usage.
Simple Questions
In order to get a feeling of the expected difficulty, below are some examples of questions. It is expected that someone will be able to solve them very fast and without mistakes.
Question: Write a function in Python to check if a number is prime or not.
def is_prime(n):
if n <= 1:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
Question: Write a function to reverse a string.
Python
C
#include <stdio.h>
#include <string.h>
void reverse_string(char* str) {
int len, i;
char temp;
len = strlen(str);
for (i = 0; i < len/2; i++) {
temp = str[i];
str[i] = str[len-i-1];
str[len-i-1] = temp;
}
}
Question: Write a function in Java to find the factorial of a number.
Question: Write a function to check if a string is a palindrome.
A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization.
For examples the word "racecar" is a palindrome. It reads the same way forward and backward. If you start reading from the first letter 'r' to the last 'r', it spells 'racecar'. Similarly, if you start reading from the last letter 'r' to the first 'r', it also spells 'racecar'. Therefore, 'racecar' is a palindrome.
Python
C++
#include <bits/stdc++.h>
using namespace std;
bool is_palindrome(string str) {
int start = 0;
int end = str.size() - 1;
while (start < end) {
if (str[start] != str[end])
return false;
start++;
end--;
}
return true;
}
int main() {
string str = "madam";
cout << (is_palindrome(str) ? "Yes" : "No");
return 0;
}
- Question: Write a function to find the sum of all elements in an array.
These are just some of the types of problems put in front during the screening part of the coding interview process.
Advanced
Depending on the organization a challenge problem can become more involved in terms of Efficiency of the requested solution, both in reducing computation time and memory usage. Usually, these are associated only with efficiently coding and applying software engineering techniques of well known algorithms. Below are some examples to understand the expected difficulty of this level.
There are three most important techniques that can be used to solve any problem. These are Divide and Conquer, Recursion, and Dynamic Programming. Let's got at them one by one and present some examples.
Divide and Conquer
Start by breaking down a problem into smaller sub-problems, solving each sub-problem independently, and then combining the solutions to solve the original problem.
Example: Merge Sort
Merge Sort is a classic example of divide and conquer. It divides the array into two halves, sorts them separately, and then merges them.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
The time complexity of Merge Sort is O(n log n) in all cases. However, it requires O(n) extra space for the temporary arrays L and R. Which means that for an input size array with n elements and time taken t, the time to merge an array of e.g. double the size (i.e. 2n) will be 2t, and so on.
Example: Binary Search
Binary Search is another example of divide and conquer. It halves the search space at every step until the target is found.
def binary_search(arr, l, r, x):
if r >= l:
mid = l + (r - l) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, l, mid-1, x)
else:
return binary_search(arr, mid + 1, r, x)
else:
return -1
Recursion
Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem.
Example: Factorial of a number
The factorial of a number can be calculated using recursion as n! = n*(n-1)!, where 0! = 1.
The time complexity is O(n) because for every number a function call is needed. The memory required depends on the language implementations of function call returns and the optimization for recursion. In programming languages like C++, the memory required can be constant.
Below is a tail recursive implementation of the factorial function in C++:
#include<iostream>
using namespace std;
int factorial_helper(int n, int result = 1) {
if (n == 0 || n == 1)
return result;
else
return factorial_helper(n - 1, n * result);
}
int factorial(int n) {
return factorial_helper(n);
}
int main() {
int num;
cout << "Enter a positive integer: ";
cin >> num;
cout << "Factorial of " << num << " = " << factorial(num);
return 0;
}
In this code, factorialHelper is a helper function that does the actual tail recursion. It takes an additional argument result which accumulates the result of the factorial calculation. The factorial function is a wrapper function that calls factorialHelper with the initial result of 1.
Example: Tower of Hanoi
The Tower of Hanoi is a classic problem that can be solved using recursion.
def tower_of_hanoi(n , source, destination, auxiliary):
if n==1:
print("Move disk 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print("Move disk",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)
Dynamic Programming
Dynamic Programming solves problems by breaking it down into simpler, smaller subproblems and storing the results of each subproblem to avoid duplicate work. It is efficiently implemented by holding a structure in memory (typically a two dimensional array) that stores all the previous sub-problems solutions before computing the next.
Example: Fibonacci Series
The Fibonacci series is a classic example where Dynamic Programming can be used. Here, we store the Fibonacci numbers calculated so far.
def fibonacci(n):
fib = [0, 1] + [0]*(n-1)
for i in range(2, n+1):
fib[i] = fib[i-1] + fib[i-2]
return fib[n]
Example: 0/1 Knapsack Problem
The 0/1 Knapsack problem is a classic problem that can be solved using Dynamic Programming. Here, we build a table K[][] in bottom-up manner.
def knapsack(W, wt, val, n):
K = [[0 for w in range(W+1)] for i in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]