100 QUESTIONS AND ANSWERS OF PYTHON
:-Python basic [exercises with solution]
Question #1: Find the length of the list and simply swap the first
# Python3 program to swap first
# and last element of a list
# Swap function
def swapList(newList):
size = len(newList)
# Swapping
temp = newList[0]
newList[0] = newList[size - 1]
newList[size - 1] = temp
return newList
# Driver code
newList = [12, 35, 9, 56, 24]
print(swapList(newList))
[24, 35, 9, 56, 12]
Question #2: Swap the first and last element is using tuple variable. Store the first and last element as a pair in a tuple variable, say get, and unpack those elements with first and last element in that list. Now, the First and last values in that list are swapped.
# Python3 program to swap first
# and last element of a list
# Swap function
def swapList(list):
# Storing the first and last element
# as a pair in a tuple variable get
get = list[-1], list[0]
# unpacking those elements
list[0], list[-1] = get
return list
# Driver code
newList = [12, 35, 9, 56, 24]
print(swapList(newList))
[24, 35, 9, 56, 12]
Question #3: The last element of the list can be referred as list[-1]. Therefore, we can simply swap list[0] with list[-1].
# Python3 program to swap first
# and last element of a list
# Swap function
def swapList(newList):
newList[0], newList[-1] = newList[-1], newList[0]
return newList
# Driver code
newList = [12, 35, 9, 56, 24]
print(swapList(newList))
[24, 35, 9, 56, 12]
Question #4: Using * operand.
This operand proposes a change to iterable unpacking syntax, allowing to specify a “catch-all” name which will be assigned a list of all items not assigned to a “regular” name.
# Python3 program to illustrate
# the usage of * operand
list = [1, 2, 3, 4]
a, *b, c = list
print(a)
print(b)
print(c)
1
[2, 3]
4
Approach #5: Swap the first and last elements is to use the inbuilt function list.pop(). Pop the first element and store it in a variable. Similarly, pop the last element and store it in another variable. Now insert the two popped element at each other’s original position.
# Python3 program to swap first
# and last element of a list
# Swap function
def swapList(list):
first = list.pop(0)
last = list.pop(-1)
list.insert(0, last)
list.append(first)
return list
# Driver code
newList = [12, 35, 9, 56, 24]
print(swapList(newList))
[24, 35, 9, 56, 12]
Question #6: Using slicing
In this approach, we first check if the list has at least 2 elements.
If the list has at least 2 elements, we swap the first and last elements using slicing by assigning the value of the last element to the first element and the value of the first element to the last element.
We then slice the list from the second element to the second-to-last element and concatenate it with a list containing the first element and the last element in their new positions.
def swap_first_last_3(lst):
# Check if list has at least 2 elements
if len(lst) >= 2:
# Swap the first and last elements using slicing
lst = lst[-1:] + lst[1:-1] + lst[:1]
return lst
# Initializing the input
inp=[12, 35, 9, 56, 24]
# Printing the original input
print("The original input is:",inp)
result=swap_first_last_3(inp)
# Printing the result
print("The output after swap first and last is:",result)
The original input is: [12, 35, 9, 56, 24]
The output after swap first and last is: [24, 35, 9, 56, 12]
Question #7: Write a Python program to check if a number is positive, negative, or zero.
num = float(input("Enter a number: "))
if num > 0:
print("Positive number")
elif num == 0:
print("Zero")
else:
print("Negative number")
Enter a number: 5
Positive number
Question #8: Write a Python program to find the maximum of two numbers.
num1 = float(input("Enter first number: "))
num2 = float(input("Enter second number: "))
if num1 > num2:
print("Maximum:", num1)
else:
print("Maximum:", num2)
Enter first number: 7
Enter second number: 4
Maximum: 7.0
Question #9: Write a Python program to find the factorial of a number.
num = int(input("Enter a number: "))
factorial = 1
for i in range(1, num + 1):
factorial *= i
print("Factorial:", factorial)
Enter a number: 5
Factorial: 120
Question #10: Write a Python program to check if a number is prime.
num = int(input("Enter a number: "))
if num > 1:
for i in range(2, num):
if (num % i) == 0:
print(num, "is not a prime number")
break
else:
print(num, "is a prime number")
else:
print(num, "is not a prime number")
Enter a number: 7
7 is a prime number
Question #11: Write a Python program to check if a number is palindrome.
num = int(input("Enter a number: "))
temp = num
reverse = 0
while num > 0:
digit = num % 10
reverse = reverse * 10 + digit
num //= 10
if temp == reverse:
print("Palindrome")
else:
print("Not Palindrome")
Enter a number: 121
Palindrome
Question #12: Write a Python program to find the sum of natural numbers up to'n'.
n = int(input("Enter a number: "))
sum = 0
for i in range(1, n + 1):
sum += i
print("Sum of natural numbers up to", n, "is", sum)
Enter a number: 5
Sum of natural numbers up to 5 is 15
Question#13: Write a Python program to print Fibonacci series up to 'n' terms.
n = int(input("Enter the number of terms: "))
n1, n2 = 0, 1
count = 0
if n <= 0:
print("Please enter a positive integer")
elif n == 1:
print("Fibonacci sequence upto", n, ":")
print(n1)
else:
print("Fibonacci sequence:")
while count < n:
print(n1)
nth = n1 + n2
n1 = n2
n2 = nth
count += 1
Enter the number of terms: 7
Fibonacci sequence:
0
1
1
2
3
5
8
Question #14: Write a Python program to find the LCM of two numbers.
def gcd(x, y):
while(y):
x, y = y, x % y
return x
def lcm(x, y):
return (x * y) // gcd(x, y)
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print("LCM of", num1, "and", num2, "is", lcm(num1, num2))
Enter first number: 12
Enter second number: 15
LCM of 12 and 15 is 60
Question #15: Write a Python program to check if a string is a palindrome.
string = input("Enter a string: ")
if string == string[::-1]:
print("Palindrome")
else:
print("Not Palindrome")
Enter a string: radar
Palindrome
Question #16: Write a Python program to count the number of vowels in a string.
string = input("Enter a string: ").lower()
vowels = 'aeiou'
count = 0
for char in string:
if char in vowels:
count += 1
print("Number of vowels:", count)
Enter a string: Hello World
Number of vowels: 3
Question #17: Write a Python program to reverse a string.
string = input("Enter a string: ")
print("Reversed string:", string[::-1])
Enter a string: Python
Reversed string: nohtyP
Question #18: Write a Python program to check if a string is an anagram of another string.
str1 = input("Enter first string: ").lower()
str2 = input("Enter second string: ").lower()
if sorted(str1) == sorted(str2):
print("Anagrams")
else:
print("Not Anagrams")
Enter first string: listen
Enter second string: silent
Anagrams
Question #19: Write a Python program to count the frequency of each character in a string.
string = input("Enter a string: ")
frequency = {}
for char in string:
if char in frequency:
frequency[char] += 1
else:
frequency[char] = 1
print("Character frequencies:", frequency)
Enter a string: hello
Character frequencies: {'h': 1, 'e': 1, 'l': 2, 'o': 1}
Question #20: Write a Python program to find the sum of elements in a list.
lst = [int(x) for x in input("Enter elements of list separated by space: ").split()]
print("Sum of elements:", sum(lst))
Enter elements of list separated by space: 1 2 3 4 5
Sum of elements: 15
Question #21: Write a Python program to find the largest element in a list.
lst = [int(x) for x in input("Enter elements of list separated by space: ").split()]
print("Largest element:", max(lst))
Enter elements of list separated by space: 4 7 2 9 1
Largest element: 9
Question #22: Write a Python program to remove duplicates from a list.
lst = [int(x) for x in input("Enter elements of list separated by space: ").split()]
unique_lst = list(set(lst))
print("List after removing duplicates:", unique_lst)
Enter elements of list separated by space: 1 2 2 3 3 4
List after removing duplicates: [1, 2, 3, 4]
Question #23: Write a Python program to find the second largest element in a list.
lst = [int(x) for x in input("Enter elements of list separated by space: ").split()]
unique_lst = list(set(lst))
unique_lst.sort()
print("Second largest element:", unique_lst[-2])
Enter elements of list separated by space: 5 8 3 1 9
Second largest element: 8
Question #24: Write a Python program to find the frequency of each element in a list.
lst = [int(x) for x in input("Enter elements of list separated by space: ").split()]
frequency = {}
for elem in lst:
if elem in frequency:
frequency[elem] += 1
else:
frequency[elem] = 1
print("Element frequencies:", frequency)
Enter elements of list separated by space: 1 2 1 3 4 2 1
Element frequencies: {1: 3, 2: 2, 3: 1, 4: 1}
Question #25: Write a Python program to find the intersection of two lists.
list1 = [1, 2, 3, 4, 5]
list2 = [4, 5, 6, 7, 8]
intersection = list(set(list1) & set(list2))
print("Intersection of lists:", intersection)
Intersection of lists: [4, 5]
Question #26: Write a Python program to find the union of two lists.
list1 = [1, 2, 3, 4, 5]
list2 = [4, 5, 6, 7, 8]
union = list(set(list1) | set(list2))
print("Union of lists:", union)
Union of lists: [1, 2, 3, 4, 5, 6, 7, 8]
Question #27: Write a Python program to check if a list is sorted in ascending order.
def is_sorted(lst):
return all(lst[i] <= lst[i + 1] for i in range(len(lst) - 1))
lst = [1, 2, 3, 4, 5]
print("Sorted:", is_sorted(lst))
Sorted: True
Question #28: Write a Python program to merge two sorted lists into a single sorted list.
def merge_sorted_lists(list1, list2):
merged_list = []
i = j = 0
while i < len(list1) and j < len(list2):
if list1[i] < list2[j]:
merged_list.append(list1[i])
i += 1
else:
merged_list.append(list2[j])
j += 1
merged_list.extend(list1[i:])
merged_list.extend(list2[j:])
return merged_list
list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]
print("Merged sorted list:", merge_sorted_lists(list1, list2))
Merged sorted list: [1, 2, 3, 4, 5, 6, 7, 8]
Question #29: Write a Python program to find the sum of all elements in a 2D array.
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
total_sum = sum(sum(row) for row in matrix)
print("Sum of elements in 2D array:", total_sum)
Sum of elements in 2D array: 45
Question #30: Write a Python program to transpose a matrix.
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose = [[matrix[j][i] for j in range(len(matrix))] for i in range(len(matrix[0]))]
print("Transposed matrix:", transpose)
Transposed matrix: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
Question #31: Write a Python program to check if a matrix is symmetric.
def is_symmetric(matrix):
return all(matrix[i][j] == matrix[j][i] for i in range(len(matrix)) for j in range(len(matrix[0])))
matrix = [[1, 2, 3], [2, 4, 5], [3, 5, 6]]
print("Symmetric:", is_symmetric(matrix))
Symmetric: False
Question #32: Write a Python program to find the maximum occurring character in a string.
string = input("Enter a string: ")
frequency = {}
for char in string:
frequency[char] = frequency.get(char, 0) + 1
max_char = max(frequency, key=frequency.get)
print("Maximum occurring character:", max_char)
Enter a string: hello
Maximum occurring character: l
Question #33: Write a Python program to find all duplicate characters in a string.
string = input("Enter a string: ")
duplicates = set(char for char in string if string.count(char) > 1)
print("Duplicate characters:", duplicates)
Enter a string: hello
Duplicate characters: {'l'}
Question #34: Write a Python program to remove all duplicates from a string.
string = input("Enter a string: ")
unique_string = ''.join(set(string))
print("String after removing duplicates:", unique_string)
Enter a string: hello
String after removing duplicates: lohe
Question #35: Write a Python program to check if a string is a pangram.
import string
def is_pangram(sentence):
alphabet = set(string.ascii_lowercase)
return set(sentence.lower()) >= alphabet
sentence = input("Enter a sentence: ")
if is_pangram(sentence):
print("Pangram")
else:
print("Not a Pangram")
Enter a sentence: The quick brown fox jumps over the lazy dog
Pangram
Question #36: Write a Python program to count the number of words in a sentence.
sentence = input("Enter a sentence: ")
word_count = len(sentence.split())
print("Number of words:", word_count)
Enter a sentence: Hello world, how are you?
Number of words: 5
Question #37: Write a Python program to find the sum of digits of a number.
num = int(input("Enter a number: "))
digit_sum = sum(int(digit) for digit in str(abs(num)))
print("Sum of digits:", digit_sum)
Enter a number: 12345
Sum of digits: 15
Question #38: Write a Python program to reverse a number.
num = int(input("Enter a number: "))
reverse_num = int(str(abs(num))[::-1]) if num >= 0 else -int(str(abs(num))[::-1])
print("Reversed number:", reverse_num)
Enter a number: 12345
Reversed number: 54321
Question #39: Write a Python program to find the sum of the first 'n' natural numbers
n = int(input("Enter a number: "))
sum_natural = n * (n + 1) // 2
print("Sum of first", n, "natural numbers:", sum_natural)
Enter a number: 5
Sum of first 5 natural numbers: 15
Question #40: Write a Python program to check if a number is Armstrong number.
num = int(input("Enter a number: "))
order = len(str(num))
sum = 0
temp = num
while temp > 0:
digit = temp % 10
sum += digit ** order
temp //= 10
if num == sum:
print("Armstrong number")
else:
print("Not an Armstrong number")
Enter a number: 153
Armstrong number
Question #41: Write a Python program to find the factors of a number.
num = int(input("Enter a number: "))
factors = [i for i in range(1, num + 1) if num % i == 0]
print("Factors of", num, "are:", factors)
Enter a number: 12
Factors of 12 are: [1, 2, 3, 4, 6, 12]
Question #42: Write a Python program to find the ASCII value of a character.
char = input("Enter a character: ")
ascii_value = ord(char)
print("ASCII value of", char, "is:", ascii_value)
Enter a character: A
ASCII value of A is: 65
Question #43: Write a Python program to convert a decimal number to binary, octal, and hexadecimal.
decimal_num = int(input("Enter a decimal number: "))
print("Binary:", bin(decimal_num))
print("Octal:", oct(decimal_num))
print("Hexadecimal:", hex(decimal_num))
Enter a decimal number: 25
Binary: 0b11001
Octal: 0o31
Hexadecimal: 0x19
Question #44: Write a Python program to find the sum of elements of a dictionary.
my_dict = {'a': 10, 'b': 20, 'c': 30}
sum_values = sum(my_dict.values())
print("Sum of dictionary values:", sum_values)
Sum of dictionary values: 60
Question #45: Write a Python program to remove a key from a dictionary.
my_dict = {'a': 1, 'b': 2, 'c': 3}
key_to_remove = 'b'
if key_to_remove in my_dict:
del my_dict[key_to_remove]
print("Dictionary after removing key:", my_dict)
Dictionary after removing key: {'a': 1, 'c': 3}
Question #46: Write a Python program to sort a dictionary by key.
my_dict = {'b': 2, 'c': 3, 'a': 1}
sorted_dict = dict(sorted(my_dict.items()))
print("Sorted dictionary by key:", sorted_dict)
Sorted dictionary by key: {'a': 1, 'b': 2, 'c': 3}
Question #47: Write a Python program to sort a dictionary by value.
my_dict = {'b': 2, 'c': 3, 'a': 1}
sorted_dict = dict(sorted(my_dict.items(), key=lambda item: item[1]))
print("Sorted dictionary by value:", sorted_dict)
Sorted dictionary by value: {'a': 1, 'b': 2, 'c': 3}
Question #48: Write a Python program to check if two strings are anagrams, ignoring case and spaces.
def is_anagram(str1, str2):
str1 = str1.replace(" ", "").lower()
str2 = str2.replace(" ", "").lower()
return sorted(str1) == sorted(str2)
string1 = input("Enter first string: ")
string2 = input("Enter second string: ")
if is_anagram(string1, string2):
print("Anagrams")
else:
print("Not Anagrams")
Enter first string: listen
Enter second string: silent
Anagrams
Question #49: Write a Python program to find the first non-repeating character in a string.
from collections import Counter
def first_non_repeating_char(string):
count = Counter(string)
for char in string:
if count[char] == 1:
return char
return None
string = input("Enter a string: ")
first_non_repeat = first_non_repeating_char(string)
print("First non-repeating character:", first_non_repeat)
Enter a string: minimum
First non-repeating character: n
Question #50: Write a Python program to find the longest common prefix among a list of strings.
def longest_common_prefix(strings):
if not strings:
return ""
shortest = min(strings, key=len)
for i, char in enumerate(shortest):
for string in strings:
if string[i] != char:
return shortest[:i]
return shortest
list_of_strings = ["flower", "flow", "flight"]
common_prefix = longest_common_prefix(list_of_strings)
print("Longest common prefix:", common_prefix)
Longest common prefix: fl
Question #51: Write a Python program to find the longest substring without repeating characters.
def longest_substring(string):
longest = ""
current = ""
for char in string:
if char in current:
current = current[current.index(char) + 1:]
current += char
if len(current) > len(longest):
longest = current
return longest
string = input("Enter a string: ")
longest_substr = longest_substring(string)
Enter a string: abcabcbb
Longest substring without repeating characters: abc
Question #52: Write a Python program to rotate an array to the right by 'k' steps.
def rotate_array(nums, k):
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
rotate_array(nums, k)
print("Rotated array:", nums)
Rotated array: [5, 6, 7, 1, 2, 3, 4]
Question #53: Write a Python program to move all zeroes to the end of an array, while maintaining the relative order of the other elements.
def move_zeroes(nums):
non_zero_idx = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[non_zero_idx], nums[i] = nums[i], nums[non_zero_idx]
non_zero_idx += 1
nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print("Array after moving zeroes to end:", nums)
Array after moving zeroes to end: [1, 3, 12, 0, 0]
Question #54: Write a Python program to remove duplicates from a sorted array.
def remove_duplicates(nums):
if not nums:
return 0
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
nums = [1, 1, 2, 2, 3, 4, 5, 5]
new_length = remove_duplicates(nums)
print("Array after removing duplicates:", nums[:new_length])
Array after removing duplicates: [1, 2, 3, 4, 5]
Question #55: Write a Python program to find the intersection of two sorted arrays.
def find_intersection(nums1, nums2):
i = j = 0
intersection = []
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
intersection.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return intersection
nums1 = [1, 2, 2, 3, 4]
nums2 = [2, 2, 3, 5]
intersection = find_intersection(nums1, nums2)
print("Intersection of arrays:", intersection)
Intersection of arrays: [2, 2, 3]
Question #56: Write a Python program to implement bubble sort algorithm.
def bubble_sort(nums):
n = len(nums)
for i in range(n):
for j in range(0, n - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
nums = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(nums)
print("Sorted array:", nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #57: Write a Python program to implement insertion sort algorithm.
def insertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and key < nums[j]:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
nums = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(nums)
print("Sorted array:", nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #58: Write a Python program to implement merge sort algorithm.
def merge_sort(nums):
if len(nums) > 1:
mid = len(nums) // 2
left_half = nums[:mid]
right_half = nums[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
nums[k] = left_half[i]
i += 1
else:
nums[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
nums[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
nums[k] = right_half[j]
j += 1
k += 1
nums = [64, 34, 25, 12, 22, 11, 90]
merge_sort(nums)
print("Sorted array:", nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #59: Write a Python program to implement quick sort algorithm.
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
nums = [64, 34, 25, 12, 22, 11, 90]
sorted_nums = quick_sort(nums)
print("Sorted array:", sorted_nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #60: Write a Python program to find the missing number in a given integer array of 1 to n.
def find_missing_number(nums):
n = len(nums) + 1
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum
nums = [1, 2, 4, 6, 3, 7, 8]
missing_number = find_missing_number(nums)
print("Missing number:", missing_number)
Missing number: 5
Question #61: Write a Python program to find the duplicate number in a given integer array.
def find_duplicate_number(nums):
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
nums = [1, 3, 4, 2, 2]
duplicate_number = find_duplicate_number(nums)
print("Duplicate number:", duplicate_number)
Duplicate number: 2
Question #62: Write a Python program to find the peak element in an array.
def find_peak_element(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
nums = [1, 2, 1, 3, 5, 6, 4]
peak_index = find_peak_element(nums)
print("Peak element:", nums[peak_index])
Peak element: 6
Question #63: Write a Python program to implement a binary search algorithm.
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
nums = [2, 3, 4, 10, 40]
target = 10
index = binary_search(nums, target)
if index != -1:
print("Element found at index:", index)
else:
print("Element not found")
Element found at index: 3
Question #64: Write a Python program to calculate the power of a number using recursion.
def power(x, n):
if n == 0:
return 1
elif n % 2 == 0:
return power(x, n // 2) ** 2
else:
return x * power(x, n // 2) ** 2
x = 2
n = 5
result = power(x, n)
print("Result:", result)
Result: 32
Question #65: Write a Python program to reverse a linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
reversed_head = reverse_linked_list(head)
while reversed_head:
print(reversed_head.val)
reversed_head = reversed_head.next
3
2
1
Question #66: Write a Python program to check if a linked list has a cycle.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Example usage:
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next # Cycle here
print("Has cycle:", has_cycle(head))
Has cycle: True
Question #67: Write a Python program to find the starting node of the cycle in a linked list, if it exists.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
# Example usage:
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = ListNode(-4)
head.next.next.next.next = head.next # Cycle here
cycle_start = detect_cycle(head)
print("Cycle starts at node with value:", cycle_start.val)
Cycle starts at node with value: 2
Question #68: Write a Python program to merge two sorted linked lists.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(l1, l2):
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
# Example usage:
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)
merged_list = merge_two_lists(l1, l2)
while merged_list:
print(merged_list.val, end=" ")
merged_list = merged_list.next
1 1 2 3 4 4
Question #69: Write a Python program to implement a stack using linked list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def pop(self):
if self.head is None:
return None
popped = self.head.data
self.head = self.head.next
return popped
def peek(self):
return self.head.data if self.head else None
def is_empty(self):
return self.head is None
# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Peek:", stack.peek())
print("Pop:", stack.pop())
print("Peek after pop:", stack.peek())
print("Is stack empty?", stack.is_empty())-
Peek: 3
Pop: 3
Peek after pop: 2
Is stack empty? False
Question #70: Write a Python program to implement a circular queue using arrays.
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.front = self.rear = -1
def enqueue(self, item):
if (self.rear + 1) % self.capacity == self.front:
print("Queue is full")
elif self.front == -1:
self.front = self.rear = 0
self.queue[self.rear] = item
else:
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
def dequeue(self):
if self.front == -1:
print("Queue is empty")
elif self.front == self.rear:
item = self.queue[self.front]
self.front = self.rear = -1
return item
else:
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
return item
def display(self):
if self.front == -1:
print("Queue is empty")
elif self.rear >= self.front:
print("Queue:", " ".join(str(self.queue[i]) for i in range(self.front, self.rear + 1)))
else:
print("Queue:", " ".join(str(self.queue[i]) for i in range(self.front, self.capacity)))
print(" ".join(str(self.queue[i]) for i in range(0, self.rear + 1)))
# Example usage:
queue = CircularQueue(5)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)
queue.display()
print("Dequeue:", queue.dequeue())
print("Dequeue:", queue.dequeue())
queue.display()
Queue: 1 2 3 4 5
Dequeue: 1
Dequeue: 2
Queue: 3 4 5
Question #71: Write a Python program to implement a priority queue using heapq module.
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
self.index = 0
def push(self, item, priority):
heapq.heappush(self.heap, (priority, self.index, item))
self.index += 1
def pop(self):
return heapq.heappop(self.heap)[-1]
# Example usage:
pq = PriorityQueue()
pq.push("Task 1", 3)
pq.push("Task 2", 1)
pq.push("Task 3", 2)
print("Popped:", pq.pop())
print("Popped:", pq.pop())
Popped: Task 2
Popped: Task 3
Question #72: Write a Python program to find the minimum spanning tree of a graph using Kruskal's
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
x_root = self.find(parent, x)
y_root = self.find(parent, y)
if rank[x_root] < rank[y_root]:
parent[x_root] = y_root
elif rank[x_root] > rank[y_root]:
parent[y_root] = x_root
else:
parent[y_root] = x_root
rank[x_root] += 1
def kruskal(self):
result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e += 1
result.append([u, v, w])
self.union(parent, rank, x, y)
return result
# Example usage:
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print("Minimum spanning tree:", g.kruskal())
Minimum spanning tree: [[2, 3, 4], [0, 3, 5], [0, 1, 10]]
Question #73: Write a Python program to find the shortest path between two nodes in a graph using Dijkstra's algorithm.
import heapq
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v, w):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append((v, w))
def dijkstra(self, start):
distances = {node: float('inf') for node in self.graph}
distances[start] = 0
pq = [(0, start)]
while pq:
dist_u, u = heapq.heappop(pq)
if dist_u > distances[u]:
continue
for v, w in self.graph.get(u, ()):
dist_v = dist_u + w
if dist_v < distances[v]:
distances[v] = dist_v
heapq.heappush(pq, (dist_v, v))
return distances
# Example usage:
g = Graph()
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 2)
g.add_edge('B', 'C', 5)
g.add_edge('B', 'D', 10)
g.add_edge('C', 'D', 3)
start_node = 'A'
shortest_distances = g.dijkstra(start_node)
print("Shortest distances from", start_node, ":", shortest_distances)
Shortest distances from A : {'A': 0, 'B': 4, 'C': 2, 'D': 5}
Question #74: Write a Python program to find the longest increasing subsequence of a given list of integers.
def longest_increasing_subsequence(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# Example usage:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print("Length of longest increasing subsequence:", longest_increasing_subsequence(nums))
Length of longest increasing subsequence: 4
Question #75: Write a Python program to find the longest common subsequence of two given strings.
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# Example usage:
text1 = "abcde"
text2 = "ace"
print("Length of longest common subsequence:", longest_common_subsequence(text1, text2))
Length of longest common subsequence: 3
Question #76: Write a Python program to find the minimum number of coins needed to make up a given amount using a provided set of denominations.
def min_coins(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Example usage:
coins = [1, 2, 5]
amount = 11
print("Minimum number of coins needed:", min_coins(coins, amount))
Minimum number of coins needed: 3
Question #77: Write a Python program to find the length of the longest substring with at most k distinct characters.
def length_of_longest_substring(s, k):
if k == 0:
return 0
char_count = {}
max_length = start = 0
for end, char in enumerate(s):
char_count[char] = char_count.get(char, 0) + 1
while len(char_count) > k:
char_count[s[start]] -= 1
if char_count[s[start]] == 0:
del char_count[s[start]]
start += 1
max_length = max(max_length, end - start + 1)
return max_length
# Example usage:
s = "eceba"
k = 2
print("Length of longest substring with at most", k, "distinct characters:", length_of_longest_substring(s, k))
Length of longest substring with at most 2 distinct characters: 3
Question #78: Write a Python program to find the longest palindromic substring in a given string.
def longest_palindromic_substring(s):
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
longest = ""
for i in range(len(s)):
palindrome1 = expand_around_center(i, i)
palindrome2 = expand_around_center(i, i + 1)
longest = max(longest, palindrome1, palindrome2, key=len)
return longest
# Example usage:
s = "babad"
print("Longest palindromic substring:", longest_palindromic_substring(s))
Longest palindromic substring: bab
Question #79: Write a Python program to generate all possible subsets of a set.
def subsets(nums):
result = [[]]
for num in nums:
result += [curr + [num] for curr in result]
return result
# Example usage:
nums = [1, 2, 3]
print("All possible subsets:", subsets(nums))
All possible subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Question #80: Write a Python program to find all valid combinations of k numbers that sum up to n (1 ≤ k ≤ 9, 1 ≤ n ≤ 30).
def combination_sum3(k, n):
def backtrack(start, target, path):
if target == 0 and len(path) == k:
result.append(path)
return
for i in range(start, 10):
if i > target:
break
backtrack(i + 1, target - i, path + [i])
result = []
backtrack(1, n, [])
return result
# Example usage:
k = 3
n = 9
print("Valid combinations:", combination_sum3(k, n))
Valid combinations: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
Question #81: Write a Python program to implement a Trie (prefix tree) and perform insert, search, and startsWith operations.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Example usage:
trie = Trie()
trie.insert("apple")
print("Search for 'apple':", trie.search("apple"))
print("Search for 'app':", trie.search("app"))
print("Starts with 'app':", trie.starts_with("app"))
trie.insert("app")
print("Search for 'app':", trie.search("app"))
Search for 'apple': True
Search for 'app': False
Starts with 'app': True
Search for 'app': True
Question #82: Write a Python program to implement a Binary Search Tree (BST) and perform insertion, deletion, search, and traversal operations.
class TreeNode:
def __init__(self, key):
self.val = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, root, key):
if not root:
return TreeNode(key)
if key < root.val:
root.left = self._insert(root.left, key)
elif key > root.val:
root.right = self._insert(root.right, key)
return root
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, root, key):
if not root:
return root
if key < root.val:
root.left = self._delete(root.left, key)
elif key > root.val:
root.right = self._delete(root.right, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
temp = self._min_value_node(root.right)
root.val = temp.val
root.right = self._delete(root.right, temp.val)
return root
def _min_value_node(self, node):
current = node
while current.left:
current = current.left
return current
def search(self, key):
return self._search(self.root, key)
def _search(self, root, key):
if not root or root.val == key:
return root
if key < root.val:
return self._search(root.left, key)
return self._search(root.right, key)
def inorder_traversal(self):
self._inorder_traversal(self.root)
print()
def _inorder_traversal(self, root):
if root:
self._inorder_traversal(root.left)
print(root.val, end=" ")
self._inorder_traversal(root.right)
# Example usage:
bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
print("Inorder traversal:", end=" ")
bst.inorder_traversal()
bst.delete(20)
bst.delete(30)
print("Inorder traversal after deletion:", end=" ")
bst.inorder_traversal()
Inorder traversal: 20 30 40 50 60 70 80
Inorder traversal after deletion: 40 50 60 70 80
Question #83: Write a Python program to reverse a string using recursion.
def reverse_string(s):
if len(s) == 0:
return s
return reverse_string(s[1:]) + s[0]
# Example usage:
s = "hello"
print("Reversed string:", reverse_string(s))
Reversed string: olleh
Question #84: Write a Python program to implement binary search on a sorted list.
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example usage:
nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
print("Index of target element:", binary_search(nums, target))
Index of target element: 5
Question #85: Write a Python program to check if a string is a palindrome.
def is_palindrome(s):
s = ''.join(char.lower() for char in s if char.isalnum())
return s == s[::-1]
# Example usage:
s = "A man, a plan, a canal: Panama"
print("Is palindrome:", is_palindrome(s))
Is palindrome: True
Question #86: Write a Python program to implement the Sieve of Eratosthenes algorithm to find all prime numbers up to a given number.
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0], primes[1] = False, False
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
return [i for i in range(n + 1) if primes[i]]
# Example usage:
n = 30
print("Prime numbers up to", n, ":", sieve_of_eratosthenes(n))
Prime numbers up to 30 : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Question #87: Write a Python program to count the number of occurrences of a given character in a string.
def count_occurrences(s, char):
return sum(1 for c in s if c == char)
# Example usage:
s = "programming"
char = "m"
print("Occurrences of", char, "in the string:", count_occurrences(s, char))
Occurrences of m in the string: 2
Question #88: Write a Python program to implement the bubble sort algorithm.
def bubble_sort(nums):
n = len(nums)
for i in range(n - 1):
for j in range(n - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
# Example usage:
nums = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(nums)
print("Sorted array:", nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #89: Write a Python program to implement the selection sort algorithm.
def selection_sort(nums):
n = len(nums)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if nums[j] < nums[min_index]:
min_index = j
nums[i], nums[min_index] = nums[min_index], nums[i]
# Example usage:
nums = [64, 34, 25, 12, 22, 11, 90]
selection_sort(nums)
print("Sorted array:", nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #90: Write a Python program to implement the merge sort algorithm.
def merge_sort(nums):
if len(nums) > 1:
mid = len(nums) // 2
left_half = nums[:mid]
right_half = nums[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
nums[k] = left_half[i]
i += 1
else:
nums[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
nums[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
nums[k] = right_half[j]
j += 1
k += 1
# Example usage:
nums = [64, 34, 25, 12, 22, 11, 90]
merge_sort(nums)
print("Sorted array:", nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #91: Write a Python program to implement the quick sort algorithm.
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage:
nums = [64, 34, 25, 12, 22, 11, 90]
sorted_nums = quick_sort(nums)
print("Sorted array:", sorted_nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #92: Write a Python program to implement the heap sort algorithm.
def heapify(nums, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and nums[left] > nums[largest]:
largest = left
if right < n and nums[right] > nums[largest]:
largest = right
if largest != i:
nums[i], nums[largest] = nums[largest], nums[i]
heapify(nums, n, largest)
def heap_sort(nums):
n = len(nums)
for i in range(n // 2 - 1, -1, -1):
heapify(nums, n, i)
for i in range(n - 1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
heapify(nums, i, 0)
# Example usage:
nums = [64, 34, 25, 12, 22, 11, 90]
heap_sort(nums)
print("Sorted array:", nums)
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Question #93: Write a Python program to find the longest common prefix string amongst a list of strings.
def longest_common_prefix(strs):
if not strs:
return ""
min_len = min(len(s) for s in strs)
common_prefix = ""
for i in range(min_len):
char = strs[0][i]
if all(s[i] == char for s in strs):
common_prefix += char
else:
break
return common_prefix
# Example usage:
strs = ["flower", "flow", "flight"]
print("Longest common prefix:", longest_common_prefix(strs))
Longest common prefix: fl
Question #94: Write a Python program to find the longest substring without repeating characters.
def longest_substring_without_repeating(s):
max_len = start = 0
char_indices = {}
for i, char in enumerate(s):
if char in char_indices and char_indices[char] >= start:
start = char_indices[char] + 1
else:
max_len = max(max_len, i - start + 1)
char_indices[char] = i
return max_len
# Example usage:
s = "abcabcbb"
print("Length of longest substring without repeating characters:", longest_substring_without_repeating(s))
Length of longest substring without repeating characters: 3
Question #95: Write a Python program to implement a basic calculator to evaluate a simple expression string containing non-negative integers, '+', '-', '*', and '/' operators.
def calculate(s):
stack = []
num = 0
sign = '+'
for i, char in enumerate(s):
if char.isdigit():
num = num * 10 + int(char)
if (not char.isdigit() and char != ' ') or i == len(s) - 1:
if sign == '+':
stack.append(num)
elif sign == '-':
stack.append(-num)
elif sign == '*':
stack.append(stack.pop() * num)
elif sign == '/':
stack.append(int(stack.pop() / num))
sign = char
num = 0
return sum(stack)
# Example usage:
s = "3+2*2"
print("Result:", calculate(s))
Result: 7
Question #96: Write a Python program to implement a queue using stacks.
class QueueUsingStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []
def enqueue(self, x):
self.stack1.append(x)
def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def is_empty(self):
return not self.stack1 and not self.stack2
# Example usage:
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print("Dequeue:", q.dequeue())
print("Dequeue:", q.dequeue())
Dequeue: 1
Dequeue: 2
Question #97: Write a Python program to implement a stack using queues.
from collections import deque
class StackUsingQueues:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, x):
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self):
return self.queue1.popleft()
def is_empty(self):
return not self.queue1
# Example usage:
s = StackUsingQueues()
s.push(1)
s.push(2)
s.push(3)
print("Pop:", s.pop())
print("Pop:", s.pop())
Pop: 3
Pop: 2
Question #98: Write a Python program to implement an LRU (Least Recently Used) cache.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key, value):
if key in self.cache:
self.cache.pop(key)
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
# Example usage:
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print("Get 1:", cache.get(1))
cache.put(3, 3)
print("Get 2:", cache.get(2))
cache.put(4, 4)
print("Get 1:", cache.get(1))
print("Get 3:", cache.get(3))
print("Get 4:", cache.get(4))
Get 1: 1
Get 2: -1
Get 1: -1
Get 3: 3
Get 4: 4
Question #99: Write a Python program to implement a basic calculator that evaluates arithmetic expressions containing parentheses.
def calculate(s):
stack = []
num = 0
sign = 1
result = 0
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char == '+':
result += sign * num
num = 0
sign = 1
elif char == '-':
result += sign * num
num = 0
sign = -1
elif char == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ')':
result += sign * num
result *= stack.pop()
result += stack.pop()
num = 0
return result + sign * num
# Example usage:
s = "(1+(4+5+2)-3)+(6+8)"
print("Result:", calculate(s))
Result: 23
Question #100: Write a Python program to find the kth smallest element in a sorted matrix.
import heapq
def kth_smallest(matrix, k):
n = len(matrix)
min_heap = [(matrix[i][0], i, 0) for i in range(n)]
heapq.heapify(min_heap)
for _ in range(k - 1):
num, row, col = heapq.heappop(min_heap)
if col < n - 1:
heapq.heappush(min_heap, (matrix[row][col + 1], row, col + 1))
return heapq.heappop(min_heap)[0]
# Example usage:
matrix = [
[1, 5, 9],
[10, 11, 13],
[12, 13, 15]
]
k = 8
print("Kth smallest element:", kth_smallest(matrix, k))
Kth smallest element: 13
Share:
Facebook
Twitter
Pinterest
LinkedIn
