Problem Statement
Given an integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time.
Solution
[Read more…]
Array
Find a pythagorean triplet from an array
Problem Statement:
Given an array a of n integers find all possible Pythagorean triplets from the array.
What is Pythagorean triplet?
A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. this formula is derived from Pythagoras theorem: “For every right angle triangle with side lengths a, b, and c=> a2 + b2 = c2“.
Pythagorean Triplet
Solution:
[Read more…]
3 SUM problem
Problem Statement:
Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.
Solution:
Brute force approach is of O(n^4) but we can solve it in O(n^2) by using the approach in Non duplicate pairs that sum to S.
First sort the array(Order O(nlogn)), than finding a, b, c pairs is equal to finding=> For every element a in the array, if there exists a pair with sum equal to -a. As explained in Non duplicate pairs that sum to S, we can get the pair with sum -a in O(n) and we have to repeat this exercise n times so order of complexity will be O(n^2).
Rotate an array by k elements
Given an array of n elements, write an algorithm to rotate it right by k element without using any other array. In other words rotate an array in place.
you can have temp variable to swap two elements.
Ex:-
Initial Array: A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Rotating array A right by 3 elements should result in
A = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}
Hint: There is a trick, think before doing much of the programming 🙂
See Solution: Rotate an array by k elements
So the trick is to reverse the whole array first then reverse the array from 0 to k-1 and k to n-1.
For example
Array A after reversing whole array: {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 0 to 2 elements: {8, 9, 10, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 3 to 9 elements: {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}
Code:
For example
Array A after reversing whole array: {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 0 to 2 elements: {8, 9, 10, 7, 6, 5, 4, 3, 2, 1}
Array A after reversing 3 to 9 elements: {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}
Code:
void rotateRight(int[] a, int k){
int length = a.length();//in C/C++ it will be given as input
reverse(a, 0, length -1);//reverse whole array
reverse(a, 0, k-1);//assuming 0 < k < length
reverse(1, k, n-1);
}
void reverse(int[] a, int start, int end){
while(start < end){
swap(a, start, end);
start++;
end--;
}
}
void swap(int[] a, int pos1, int pos2){
int temp = a[pos1];
a[pos1]= a[pos2];
a[pos2] = temp;
}
//Note: in interviews you might be asked to handle negative scenarios
// like array out of bound etc.
