useful code Flashcards
Sort an array of 0s, 1s and 2s
in general if you know the number in the array just count them and then print them in order. Think about the Counting Sort
What is jump search?
Just instead of doing binary search you jump linearly from 0 to m to 2m ….. when you get somethign higher than x you stop and you do linear search between nm and (n+1)m.
Time complexity is O(√ n) between linear and binary search.
Like in the EGG from skyscraper problem.
Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps,
So in a system where jumping back is costly, we use Jump Search.
How do you check if 2 elemetns of the array have products equal to p.
O(n^2) of course do the naive thing of tring all the products.
O(nlogn): you can sort and then go to the array O(n) and search for prod/arr[i] in the rest of the array. This give you O(nlogn)
As usual hash are amazingly good. buit a hash in O(n) than look for p-1 p/2-2 etch if you find both you are done.
def find_prod(A,prod):
freq = [0]*(prod+1)
for a in A:
if a freq[a] = 1
i=1
j=prod
while i # print(i,j)
if freq[i] and freq[j]:
print(i,j)
return True
i+=1
if j%i !=0:
continue
else:
j = prod//i
return False
Sort a nearly sorted (or K sorted) array
Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.
We can use Insertion Sort to sort the elements efficiently. Following is the C code for standard Insertion Sort.
The inner loop will run at most k times. To move every element to its correct place, at most k elements need to be moved. So overall complexity will be O(nk)
We can sort such arrays more efficiently with the help of Heap data structure. Following is the detailed process that uses Heap.
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See this GFact)
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.
Removing an element and adding a new element to min heap will take Logk time. So overall complexity will be O(k) + O((n-k)*logK)
Find subarray with given sum.
Again brute force is O(n^2). The key is to understand that once your sum exceeds the value you are looking for you just have to remove elements starting from the beginning till you get to exactly or below the value you are looking for. def subArraySum(arr, n, sum): for i in range(n): curr_sum = arr[i] j = i+1 while j <= n: if curr_sum == sum: print (“Sum found between”) print(“indexes %d and %d”%( i, j-1)) return 1 if curr_sum > sum or j == n: break curr_sum = curr_sum + arr[j] j += 1 print (“No subarray found”) return 0
How to identify is a problem is a dynamic programming one?
Typically, all the problems that require to maximize or minimize certain quantity or counting problems that say to count the arrangements under certain condition or certain probability problems can be solved by using Dynamic Programming.
How can you check if 2 number are missing from a sequence?
In this case, xor or the sum trick might not be that convenience. If you can leave with the O(n) space you can build a hash table.
if you use the sum you get the sum of the 2 numbers. You can get the average. one is going to be smaller than that one higher. You can repeat the sum trick for 1-avg avg-n to find out the 2 numbers.
With xor, it is the same you get x^y where xy are missing.
now if you have a bit 1 in that, it means that either x or y do not have that. Select all the elements with 1 there and do a xor.
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
O(n) and space efficient We create a Dequeue, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window. Thanks to Aashish for suggesting this method.
Find the recursion for the cutting rod problem
Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n.Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)
length | 1 2 3 4 5 6 7 8 ——————————————– price | 1 5 8 9 10 17 17 20
We can get the best price by making a cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.
Let cutRod(n) be the required (best possible price) value for a rod of length n. cutRod(n) can be written as following.
cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}
Returns the best obtainable price for a rod of length n and
price[] as prices of different pieces
def cutRod(price, n):
val = [0 for x in range(n+1)]
val[0] = 0
Build the table val[] in bottom up manner and return
the last entry from the table
for i in range(1, n+1):
max_val = INT_MIN
for j in range(i):
max_val = max(max_val, price[j] + val[i-j-1])
val[i] = max_val
return val[n]
Which sorting algorithms in its typical implementation gives the best performance when applied on an array which is sorted or almost sorted
Insertion sort takes linear time when input array is sorted or almost sorted (maximum 1 or 2 elements are misplaced). All other sorting algorithms mentioned above will take more than linear time in their typical implementation.
Given two unsorted arrays A of size N and B of size M of distinct elements, the task is to find all pairs from both arrays whose sum is equal to X.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains 3 lines . The first line contains 3 space separated integers N, M, X. Then in the next two lines are space separated values of the array A and B respectively.
Input
s =9
A = 1 2 4 5 7
B = 5 6 3 4 8
Output
1 8, 4 5, 5 4
If you have space hashing would work
def find_pairs(A,B,s):
freq = [0]*200
for i in range(0,len(B)):
freq[s-B[i]] = 1
for i in range(0,len(A)):
if freq[A[i]] == 1 :
print(A[i],s-A[i])
return 0
What is the output of the following program :
print 0.1 + 0.2 == 0.3
Neither of 0.1, 0.2 and 0.3 can be represented accurately in binary. The round off errors from 0.1 and 0.2 accumulate and hence there is a difference of 5.5511e-17 between (0.1 + 0.2) and 0.3.
Find if a string is a permutatin of a palindrom!
They key here is to see that to be a palindrome you need to have an even frequency for each character but one in odd strings (that can be the central). Then just implement this with an hash!
Decode the string
An encoded string (s) is given, the task is to decode it.
The pattern in which the strings were encoded were as follows
original string: abbbababbbababbbab
encoded string : “3[a3[b]1[ab]]”.
The idea is to use two stacks, one for integers and another for characters.
Now, traverse the string,
Whenever we encounter any number, push it into the integer stack and in case of an alphabet (a to z) or open bracket (‘[‘), push it onto the character stack.
Whenever any close bracket (‘]’) is encounter pop the character from the character stack until open bracket (‘[‘) is not found in the character stack. Also, pop the top element from the integer stack, say n. Now make a string repeating the popped character n number of time. Now, push all character of the string in the stack.
def decode_str(s):
string = list(s)
stack_chr = []
stack_int = []
for i in string:
if i.isdigit():
stack_int.append(int(i))
elif i != “]”:
stack_chr.append(i)
elif i == “]”:
_n = stack_int.pop()
_chr = stack_chr.pop()
_str = []
while _chr != “[”:
_str.append(_chr)
_chr = stack_chr.pop()
stack_chr.append(““.join(_str) * _n)
else:
return 0
return ““.join(stack_chr)
Interpolation search?
It is a binary search where you do not look in the middle.
you choose where to look by comparing x with the highest and smallest elements in the array.
pos = lo + [(x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
You need to do this in place.
Note that if you end up using an additional array, you will only receive partial score.
Example:
If the array is
1 2 3 4 5 6 7 8 9
Then the rotated array becomes:
7 4 1 8 5 2 9 6 3
Below are some important observations.
First row of source –> First column of destination, elements filled in opposite order
Second row of source –> Second column of destination, elements filled in opposite order
so … on
Last row of source –> Last column of destination, elements filled in opposite order.
An N x N matrix will have floor(N/2) square cycles. For example, a 4 X 4 matrix will have 2 cycles. The first cycle is formed by its 1st row, last column, last row and 1st column. The second cycle is formed by 2nd row, second-last column, second-last row and 2nd column.
The idea is for each square cycle, we swap the elements involved with the corresponding cell in the matrix in anti-clockwise direction i.e. from top to left, left to bottom, bottom to right and from right to top one at a time. We use nothing but a temporary variable to achieve this.
An Inplace function to rotate
N x N matrix by 90 degrees in
anti-clockwise direction
def rotateMatrix(mat):
Consider all squares one by one
for x in range(0, int(N/2)):
Consider elements in group
of 4 in current square
for y in range(x, N-x-1):
store current cell in temp variable
temp = mat[x][y]
move values from right to top
mat[x][y] = mat[y][N-1-x]
move values from bottom to right
mat[y][N-1-x] = mat[N-1-x][N-1-y]
move values from left to bottom
mat[N-1-x][N-1-y] = mat[N-1-y][x]
assign temp to left
mat[N-1-y][x] = temp
Find the first unique element of a string!
You go through the string, build a hash table with the frequency, then you go trough the string again and you stop when freq[char] ==1
This is an O(n)
Search an element in a sorted rotated array.
Like this?
5 6 7 8 9 10 1 2 3
Also what is a condition to be able to do this in log(n)?
low + (high - low)/2;
You need to have no repeated elements. Otherwise, you can not do this in O(logn):
Otherwise, you can obtain the pivot, using a binary search slightly modified in logN. Once you have the pivot you can do a bnary search in one of the 2 arrays in the usual way.
In the same way you can get the minimum value
def findPivot(arr, low, high):
base cases
if high < low:
return -1
if high == low:
return low
mid = int((low + high)/2)
if mid < high and arr[mid] > arr[mid + 1]:
return mid
if mid > low and arr[mid] < arr[mid - 1]:
return (mid-1)
if arr[low] >= arr[mid]:
return findPivot(arr, low, mid-1)
return findPivot(arr, mid + 1, high)
Recursion for friends pairing problem
Given n friends, each one can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways in which friends can remain single or can be paired up.
f(n) = ways n people can remain single or pair up.
For n-th person there are two choices:
1) n-th person remains single, we recur for f(n - 1)
2) n-th person pairs up with any of the remaining n - 1 persons.We get (n - 1) * f(n - 2)
Therefore we can recursively write f(n) as: f(n) = f(n - 1) + (n - 1) * f(n - 2)
Find the recursion for the tiling problem
Given a “2 x n” board and tiles of size “2 x 1”, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.
Let “count(n)” be the count of ways to place tiles on a “2 x n” grid, we have following two ways to place first tile.
1) If we place first tile vertically, the problem reduces to “count(n-1)”
2) If we place first tile horizontally, we have to place second tile also horizontally. So the problem reduces to “count(n-2)”
Therefore, count(n) can be written as below.
count(n) = n if n = 1 or n = 2 count(n) = count(n-1) + count(n-2)
This is basically a fibonacci series and it can be solved in the same way
