important questions Flashcards
number to words
dict={0:”“,1:”one”,2:”two”,3:”three”,4:”four”,5:”five”,6:”six”,7:”seven”,8:”eight”,9:”nine”,10:”ten”,11:”eleven”,12:”twelve”,13:”thirteen”,14:”fourteen”,15:”fifteen”,16:”sixteen”,17:”seventeen”,18:”eighteen”,19:”nineteen”
,20:”twenty”,30:”thirty”,40:”Fourty”,50:”fifty”,60:”sixty”,70:”seventy”,80:”eighty”,90:”ninety”,100:”hundred”,1000:”thousand”}
end=False
while not end:
x=int(input(“enter number: “))
final=""
if 0<=x<=19:
if x==0:
final+='zero'
final += dict[x]
elif len(str(x))==2:
tens=x//10
ones=x%10
final=dict[tens*10]+dict[ones]
elif len(str(x))==3:
hundreds=x//100
if 11<=x%100<=19:
tens=x%100
ones=0
else:
tens=((x%100)//10)*10
ones=(x%100)%10
final=dict[hundreds]+dict[100]+dict[tens]+dict[ones]
elif len(str(x))==4:
thousands=x//1000
hundreds=(x%1000)//100
if 11<=(x%1000)%100<=19 or 11<=(x%1000)<=19:
tens=((x%1000)%100)
ones=0
else:
tens=(((x%1000)%100)//10)*10
ones=((x%1000)%100)%10
hundred=hundreds*100
hund=""
if hundred!=0:
hund+=dict[hundreds]
hund+=dict[100]
final=dict[thousands]+dict[1000]+hund+dict[tens]+dict[ones]
print(final)
merge two sorted array into a single sorted array
Initialize two pointers i and j to 0, where i and j point to the first elements of nums1 and nums2 respectively.
Create an empty list merged.
While i is less than m and j is less than n, do the following:
If nums1[i] is less than or equal to nums2[j], append nums1[i] to merged and increment i by 1.
Otherwise, append nums2[j] to merged and increment j by 1.
If there are remaining elements in nums1, append them to merged using a loop that starts at index i.
If there are remaining elements in nums2, append them to merged using a loop that starts at index j.
Return merged.
find the contiguous subarray with the largest sum
Initialize two variables: max_sum and curr_sum to the first element of the array.
Loop through the array from the second element to the end.
For each element, add it to curr_sum.
If curr_sum becomes negative, set it to 0.
If curr_sum is greater than max_sum, set max_sum to curr_sum.
Return max_sum
write a code to create a m*n zero matrix
matrix=[ [0] * n for i in range(m) ]
find the longest subsequence given two strings
ALGORITHM
Create a two-dimensional array with dimensions (m+1) by (n+1), where m and n are the lengths of the input strings.
Initialize the first row and first column of the array to 0.
For each character i in the first input string (s1), and for each character j in the second input string (s2), compare s1[i] with s2[j].
If s1[i] is equal to s2[j], set the value in the (i+1, j+1) position of the array to the value in the (i, j) position of the array plus 1.
If s1[i] is not equal to s2[j], set the value in the (i+1, j+1) position of the array to the maximum of the values in the (i+1, j) and (i, j+1) positions of the array.
The length of the longest common subsequence is the value in the (m+1, n+1) position of the array.
To obtain the subsequence itself, start at the (m,n) position of the array and repeatedly move to the adjacent position with the higher value, until you reach the (0,0) position.
CODE IMPLEMENTATION
def longest_common_subsequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
if s1[i] == s2[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
lcs_length = dp[m][n]
lcs = ""
i, j = m, n
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
lcs = s1[i - 1] + lcs
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
print(longest_common_subsequence(s1 = “ABCDGH”, s2 = “AEDFHR”))
MATRIX
”” A E D F H R
“” 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1
B 0 1 1 1 1 1 1
C 0 1 1 1 1 1 1
D 0 1 1 2 2 2 2
G 0 1 1 2 2 2 2
H 0 1 1 2 2 3 3
implement a binary search algorithm to find x
ALGORITHM
The function takes two arguments - arr (the sorted array) and x (the element to be searched for).
It initializes two pointers left and right to the start and end indices of the array.
It then enters a while loop that runs as long as left is less than or equal to right.
Inside the loop, the function computes the midpoint index mid of the array using integer division.
If the element at the midpoint index arr[mid] is equal to x, the function returns the index mid (as the element is found).
If the element at the midpoint index arr[mid] is less than x, the function sets left to mid + 1 (to search the right half of the array).
If the element at the midpoint index arr[mid] is greater than x, the function sets right to mid - 1 (to search the left half of the array).
If the loop completes without finding the element x, the function returns -1 (to indicate that the element was not found).
CODE IMPLEMENTATION
def binary_search(arr, x):
“””
Searches for the element x in the sorted array arr using binary search algorithm.
Returns the index of x in the array if found, else returns -1.
“””
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
Add two numbers without using ‘+’ operator
ALGORITHM
Initialize two variables sum and carry to 0.
While b is not 0, do the following:
Assign the result of a XOR b to sum.
Assign the result of (a AND b) «_space;1 to carry.
Assign the value of sum to a.
Assign the value of carry to b.
Return the value of a, which is the sum of the two input integers.
CODE IMPLEMENTATION
def sum_without_plus(a, b):
while b != 0:
# Compute sum without carry
sum = a ^ b
# Compute carry
carry = (a & b) << 1
# Update a and b
a = sum
b = carry
return a
what are different ways to find the transpose of a matrix
METHOD 1
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
transpose[j][i] = matrix[i][j]
print(transpose)
METHOD 2
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(transpose)
Both method follow the same concept
CODE IMPLEMENTATION
def rotate_matrix(matrix):
rows = len(matrix)
cols = len(matrix[0])
rotated = [[0 for j in range(rows)] for i in range(cols)]
for i in range(rows):
for j in range(cols):
rotated[j][rows-i-1] = matrix[i][j]
return rotated
find the nth largest element from an array without sorting the array
import random
def quickselect(nums, k):
“””
Returns the k-th largest element in an unordered list nums.
“””
if len(nums) == 1:
return nums[0]
# Choose a pivot randomly
pivot = random.choice(nums)
# Partition the list into 2 sublists
nums1 = [x for x in nums if x > pivot]
nums2 = [x for x in nums if x < pivot]
# If k is within the first partition, recursively call quickselect on the first partition
if k <= len(nums1):
return quickselect(nums1, k)
# If k is within the second partition, recursively call quickselect on the second partition
elif k > len(nums) - len(nums2):
return quickselect(nums2, k - (len(nums) - len(nums2)))
else:
return pivot
print(quickselect([1,2,3,4,3,56,32,12,343],4))
another simpler algorithm in c
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int findNthLargest(int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
int max_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[max_index]) {
max_index = j;
}
}
swap(&arr[i], &arr[max_index]);
}
return arr[k-1]; }
write a function to reverse the order of words in it. give me the python code
def reverse_words(string):
# Split the string into words
words = string.split()
# Reverse the order of the words words = words[::-1] # Join the words back into a string reversed_string = " ".join(words) return reversed_string
write a python code to reverse a number
num = int(input(“Enter the Number:”))
temp = num
reverse = 0
while num > 0:
remainder = num % 10
reverse = (reverse * 10) + remainder
num = num // 10
print(temp,reverse)
implement linear search in python
def Linear_search(list,key):
list1=[]
flag=False
for i in range(len(list)):
if list[i]==key:
flag=True
list1.append(i)
if flag==True:
for i in list1:
print(list[i],”element is found at index : “,i)
else:
print(“element is not found”)
remove duplicate elements from a list inline
list=[1,1,2,2,3,3]
for i in range(1,len(list)):
if list[i]==list[i-1]:
list[i]=””
count=list.count(“”)
for i in range(count):
list.remove(“”)
print(list)
code to print the longest common prefix from a set of strings
list=[“race”, “racecar”, “racist”]
prefix=list[0]
while prefix!=””:
count=0
for i in range(len(list)):
if prefix in list[i]:
count+=1
else:
prefix=prefix[:-1]
if count==len(list):
break
print(prefix)
Implement a function to reverse a string in-place.
list=[1,2,3,4,5,6,7,8,9]
times=0
if len(list)%2==0:
times=len(list)//2
else:
times=(len(list)-1)//2
for i in range(times):
list[i],list[len(list)-i-1]=list[len(list)-i-1],list[i]
print(list)
