Basic Coding Problems You Must Be Able to Solve As a Computer Science Graduate
Check Prime Number
A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself. For example, the first six prime numbers are 2, 3, 5, 7, 11, and 13.
The number 6 is not a prime number because it has more than two positive integer divisors. In fact, the divisors of 6 are 1, 2, 3, and 6.
To determine if a number is prime, you can check if it has any positive integer divisors other than 1 and itself. If it does, then it is not a prime number.
Problem: Write a function that determines if a given integer is a prime number.
1def is_prime(n):
2 if n <= 1:
3 return False
4
5 for i in range(2, n):
6 if n % i == 0:
7 return False
8 return True
You can then use this above function to find all the prime numbers within a given range by using a loop:
1def find_primes(n):
2 primes = []
3 for i in range(2, n+1):
4 if is_prime(i):
5 primes.append(i)
6 return primes
7
8print(find_primes(10)) # Output: [2, 3, 5, 7]
The time complexity of the is_prime() function is O(n), since the time it takes to execute the function is directly proportional to the value of the input n. This is because the function uses a for loop that iterates over all the values from 2 to n (not including n) and checks if n is divisible by each value.
The space complexity of the is_prime() function is O(1), since the function only uses a constant amount of memory regardless of the size of the input. This is because the function only uses a few variables (n and i) and does not create any new data structures.
Optimization
One optimization is to check if n is even before entering the loop. If n is even, we can immediately return False because even numbers are not prime (except for 2). This optimization reduces the time complexity from O(n) to O(1) for even input numbers.
1def is_prime(n):
2 if n <= 1:
3 return False
4
5 if n % 2 == 0:
6 return n == 2
7
8 for i in range(3, n, 2):
9 if n % i == 0:
10 return False
11
12 return True
Check Palindrome Number
A palindrome number is a number that remains the same when its digits are reversed. For example, 121, 11, and 55555 are palindrome numbers because they are the same when their digits are reversed. On the other hand, 123, 456, and 789 are not palindrome numbers because they are not the same when their digits are reversed.
Method 1
To check if a number is a palindrome in Python, you can convert the number to a string and compare the string with its reverse.
1def is_palindrome(n: int):
2 n = str(n)
3 return n == n[::-1]
4
5print(is_palindrome(121)) # Output: True
6print(is_palindrome(123)) # Output: False
Method 2
You can check if a number is a palindrome by comparing the digits of the number from left to right and right to left using two pointers.
1def is_palindrome(n: int):
2 n = str(n)
3 left = 0
4 right = len(n) - 1
5
6 while left < right:
7 if n[left] != n[right]:
8 return False
9
10 # increment the left pointer
11 left += 1
12 # decrease the right pointer
13 right -= 1
14
15 return True
16
17print(is_palindrome(121)) # Output: True
18print(is_palindrome(123)) # Output: False
Method 3
Without converting the number to string.
1#without converting to string
2def is_palindrome2(x: int):
3 # any negative number is not a palindrome
4 if x < 0:
5 return False
6
7 reverse = 0
8 original = x
9 while x > 0:
10 # Adding the last digit of x to the reverse variable.
11 reverse = reverse * 10 + x % 10
12 # The same as `x = x // 10`
13 x = x // 10
14
15 return reverse == original
The time complexity of the is_palindrome2() function is O(n), where n is the number of digits in the number x. This is because the function uses a while loop that iterates over the digits of x and performs a constant amount of work on each iteration.
The space complexity of the is_palindrome2() function is O(1), since the function only uses a constant amount of memory regardless of the size of the input. This is because the function only uses a few variables (x, reverse, and original) and does not create any new data structures.
Merge Sort
Merge sort is a divide and conquer sorting algorithm that works by recursively dividing a list into smaller sublists, sorting each sublist, and then merging the sublists back together.
1def merge_sort(arr):
2 if len(arr) <= 1:
3 return arr
4
5 # Divide the list into two halves
6 mid = len(arr) // 2
7 left = arr[:mid]
8 right = arr[mid:]
9
10 # Recursively sort the two halves
11 left = merge_sort(left)
12 right = merge_sort(right)
13
14 # Merge the sorted halves
15 return merge(left, right)
16
17def merge(left, right):
18 result = []
19 while left and right:
20 if left[0] < right[0]:
21 result.append(left.pop(0))
22 else:
23 result.append(right.pop(0))
24 result.extend(left)
25 result.extend(right)
26 return result
27
28# Test the merge_sort function
29arr = [5, 3, 2, 1, 4]
30print(merge_sort(arr)) # Output: [1, 2, 3, 4, 5]
The time complexity of merge sort is O(n log n), where n is the number of elements in the list being sorted. This is because the algorithm works by recursively dividing the list into smaller sublists and then merging the sublists back together, which takes O(n log n) time in the worst case.
The space complexity of merge sort is O(n), since the algorithm uses additional space to store the sublists and the merged list.
In the context of merge sort, the logarithmic term "log n" refers to the number of times the list is divided in half during the sorting process.
In each step of the merge sort algorithm, the list is divided into two equal-sized sublists. The process is repeated recursively on each sublist until the sublists are of size 1 (i.e., they are sorted). The number of times the list is divided in half is equal to the number of recursive calls needed to sort the list, which is logarithmic in the size of the list.
For example, consider a list with 8 elements. To sort this list using merge sort, the list would be divided into two sublists of size 4, and then each sublist would be divided into two sublists of size 2. This process would be repeated until each sublist has only one element, resulting in a total of 3 recursive calls (since 2^3 = 8). In this case, log function will have a base 2, as the we are splitting each list into 2 in every recursive calls.
Binary Search
Binary search is an efficient search algorithm that works by repeatedly dividing a sorted list in half and comparing the search key to the middle element of the list. If the search key is equal to the middle element, the search is successful and the index of the element is returned. If the search key is less than the middle element, the search continues in the left half of the list. If the search key is greater than the middle element, the search continues in the right half of the list.
Binary search only works if they given list is already sorted.
1def fn_binary_search(arr, target):
2 left = 0
3 right = len(arr) - 1
4 while left <= right:
5 mid = (left + right) // 2
6 if target == arr[mid]:
7 # means we found the target, and return the index of the target
8 return mid
9 # if the target is in the right half of the array
10 elif target > arr[mid]:
11 left = mid + 1
12 # if the target is in the left half of the array
13 else:
14 right = mid - 1
15 # if the target is not in the array
16 return -1
Time complexity: O(log n)
Generate Fibonacci Series
To generate the Fibonacci series from 1 to n, you can use a loop to iterate over the range of numbers from 1 to n and use a recursive function to compute each element in the series.
1# find the n-th fibonacci number
2def fibonacci(n):
3 if n == 0:
4 return 0
5 elif n == 1:
6 return 1
7 else:
8 return fibonacci(n-1) + fibonacci(n-2)
9
10
11# generate the series that contains all numbers upto n
12def generate_fibonacci_series(n):
13 series = []
14 for i in range(1, n+1):
15 series.append(fibonacci(i))
16 return series
17
18# Test the generate_fibonacci_series function
19n = 10
20print(generate_fibonacci_series(n)) # Output: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
The time complexity of the above code is O(n^2), since the fibonacci() function takes O(2^n) time to compute each element in the series. The space complexity is O(n), since the generate_fibonacci_series() function uses a list to store the series and the fibonacci() function uses additional space to store the recursive calls.
Note that this implementation of the Fibonacci series has a relatively high time complexity due to the use of a recursive function to compute each element in the series. A more efficient implementation of the Fibonacci series would use an iterative approach and have a lower time complexity.
1def generate_fibonacci_series(n):
2 series = [0, 1]
3 for i in range(2, n+1):
4 series.append(series[i-1] + series[i-2])
5 return series
6
7# Test the generate_fibonacci_series function
8n = 10
9print(generate_fibonacci_series(n)) # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
In this implementation, the generate_fibonacci_series() function uses a for loop to iterate over the range of numbers from 2 to n and computes each element in the series using the previous two elements. This approach has a time complexity of O(n) and a space complexity of O(n), making it a more efficient way to generate the Fibonacci series.
How to reverse a string using Python without built-in functions
One way to reverse a string in Python without using any built-in functions is to use a for loop to iterate over the characters in the string in reverse order and append them to a new string.
1def reverse_string(string):
2 reversed_string = ""
3 for i in range(len(string) - 1, -1, -1):
4 reversed_string += string[i]
5 return reversed_string
6
7# Test the function
8print(reverse_string("hello")) # Output: "olleh"
9print(reverse_string("world")) # Output: "dlrow"
Remove duplicate numbers from a list
Using built-in function
1def remove_duplicates(numbers):
2 return list(set(numbers))
3
4# Test the function
5print(remove_duplicates([1, 2, 3, 3, 4, 4, 5, 5])) # Output: [1, 2, 3, 4, 5]
Without built-in functions
1def remove_duplicates(numbers):
2 unique_numbers = []
3 for number in numbers:
4 if number not in unique_numbers:
5 unique_numbers.append(number)
6 return unique_numbers
7
8# Test the function
9print(remove_duplicates([1, 2, 3, 3, 4, 4, 5, 5])) # Output: [1, 2, 3, 4, 5]
The time complexity of the remove_duplicates function is O(n), where n is the length of the input list. This is because the function requires one pass through the list to remove the duplicates.
The space complexity of the function is also O(n), because it creates a new list called unique_numbers to store the unique elements from the input list. The size of this list grows as the function adds more unique elements to it, so it requires O(n) space in the worst case.
Remove duplicate characters from a string
Using built-in function
1def remove_duplicates(string):
2 return "".join(set(string))
3
4# Test the function
5print(remove_duplicates("hello")) # Output: "helo"
6print(remove_duplicates("world")) # Output: "wrdl"
Without using built-in function
1def remove_duplicates(string):
2 unique_characters = ""
3 for character in string:
4 if character not in unique_characters:
5 unique_characters += character
6 return unique_characters
7
8# Test the function
9print(remove_duplicates("hello")) # Output: "helo"
10print(remove_duplicates("world")) # Output: "wrdl"
Count the occurrence of a given character in a string
using built-in function
1def count_occurrences(string, char):
2 return string.count(char)
3
4# Test the function
5print(count_occurrences("hello", "l")) # Output: 2
6print(count_occurrences("world", "w")) # Output: 1
Without using built-in function
1def count_occurrences(string, char):
2 count = 0
3 for c in string:
4 if c == char:
5 count += 1
6 return count
7
8# Test the function
9print(count_occurrences("hello", "l")) # Output: 2
10print(count_occurrences("world", "w")) # Output: 1
Check if two strings are anagrams
An anagram is a word or phrase formed by rearranging the letters of another word or phrase. For example, "listen" and "silent" are anagrams because they both contain the same letters, just arranged differently.
Here are a few more examples of anagrams:
- "friend" and "finder"
- "elbow" and "below"
- "school" and "coolsh"
Using built-in sorted function
1def is_anagram(string1, string2):
2 return sorted(string1) == sorted(string2)
3
4# Test the function
5print(is_anagram("hello", "olleh")) # Output: True
6print(is_anagram("world", "worlld")) # Output: False
Without built-in function
1def is_anagram(string1, string2):
2 char_count1 = {}
3 char_count2 = {}
4 for c in string1:
5 if c in char_count1:
6 char_count1[c] += 1
7 else:
8 char_count1[c] = 1
9 for c in string2:
10 if c in char_count2:
11 char_count2[c] += 1
12 else:
13 char_count2[c] = 1
14 return char_count1 == char_count2
15
16# Test the function
17print(is_anagram("hello", "olleh")) # Output: True
18print(is_anagram("world", "worlld")) # Output: False
Calculate the number of vowels and consonants in a string
1def count_vowels_consonants(string):
2 vowels = 0
3 consonants = 0
4 for c in string:
5 if c.lower() in "aeiou":
6 vowels += 1
7 elif c.isalpha():
8 consonants += 1
9 return vowels, consonants
10
11# Test the function
12print(count_vowels_consonants("hello")) # Output: (2, 3)
13print(count_vowels_consonants("world")) # Output: (1, 4)
Find the second highest number in an integer array
Using built-in function
1def find_second_highest(arr):
2 max_number = float("-inf")
3 second_highest = float("-inf")
4
5 i = j = 0
6
7 while i < len(arr):
8 if arr[i] > max_number:
9 max_number = arr[i]
10 i = i +1
11
12 while j < len(arr):
13 if arr[j] > second_highest and arr[j] != max_number:
14 second_highest = arr[j]
15 j = j + 1
16
17 return second_highest
18
19
20
21# test the function
22array = [1, 2, 3, 4, 5]
23print(find_second_highest(array)) # should print 4
The time complexity of the find_second_highest function is O(n), because the function performs two sequential scans of the input array, arr. In both scans, the function examines each element in the array once, so the time complexity is linear with respect to the size of the array.
The space complexity of the function is also O(1), because the function only uses a constant amount of additional space regardless of the size of the input array. The function uses two variables (max_number and second_highest) to store the maximum and second highest values, but these variables do not change in size based on the size of the input array.
Find the largest and smallest number from an array of integers
1# list of integers
2numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
3
4# initialize variables
5largest = smallest = numbers[0]
6
7# iterate over the rest of the list
8for num in numbers[1:]:
9 if num > largest:
10 largest = num
11 if num < smallest:
12 smallest = num
13
14# print the results
15print("The largest number is:", largest)
16print("The smallest number is:", smallest)
Author: Sadman Kabir Soumik