Remove duplicates from the sorted array
**Problem **
Remove duplicates from the sorted array
Example
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5]
Method 1- using 3 pointers
//using 3 pointers fixDuplicatesInSortedArray(Integer\[\] a): start = 0 end = 0 destination = 0 while(start < a.length): while(end < a.length && a\[end\] == a\[start\]): end++ end-- //copy the distinct element a\[destination\] = a\[start\] destination++ start = end + 1 end = start //null out the rest while destination < a.
[Read More]
print all word combinations from phone number
Print all words combinations from phone number.
ex: 111-1111 -> AAA-AAAA, AAA-AAAB … CCC-CCCC
char charkeyMap(int digit, int position)
ex:
charkeyMap(1, 0) = ‘A’
charkeyMap(1, 1) = ‘B’
charkeyMap(1, 2) = ‘C’
`
void printCombinations(int[] in):
char[] out = new char[in.length]
//first combination ex: 111-1111 -> AAA-AAAA
for(int i = in.length -1; i >= 0; i–):
out[i] = charkeyMap(in[i], 0)
int i
while (true):
out.print()
i = in.length - 1;
[Read More]
String matching
The naive brute force approach:
It is very simple to code but there are little things to look for (as least I have to) with respect to optimization. The outer loop runs for text, the inner loop runs for pattern with one more condition - **i+ len(pattern) <= len(text)**.
int bruteForce (text, pattern) for (i =0; i < len(text); i++):
for (j = 0; j < len(pattern) && **i+ len(pattern) <= len(text)**; j++): //instead of i+j < len(text) if text[i+j] !
[Read More]
Threaded binary tree
Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used.
[Read More]
Find the median in a continous stream of numbers
Problem
Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
OR
You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time)
**OR **
[Read More]
Quick sort
Hoore cisca discovered it in 1961.
Why quicksort?
Definitely a greatest hit algorithm Prevalent in practice O(n log n) time “on average” minimal extra memory needed (which gives it leverage over merge sort) The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Quicksort helps us solving this problem.
What is quick sort?
[Read More]
Binary search on Array - Recursive and iterative
There are two basic searching algorithms used. One is the simplest technique and is discussed here.
Here we will discuss the binary search method.
The other search method is the binary search method. The binary search technique is a very fast and a more efficient technique when compared to the linear search method, and gets us the result in O(log n) where n is number of elements. The only requirement for this method is that the input array of elements must be in the sorted order.
[Read More]
Given a list of n numbers from 1 to n-1, with one of the numbers repeated. Devise a method to determine which number is repeated
The sum of the numbers 1 to n-1 is (n)(n-1)/2. Add the numbers on the list, and subtract (n)(n-1)/2. The result is the number that has been repeated.
Efficient code for extracting unique elements from a sorted list of array
int main()
{
int a\[10\]={1, 2, 4, 4, 7, 8, 9, 14, 14, 20};
int i;
for (i = 0;i<9;i++)
{
if (a\[i\] != a\[i+1\])
printf("%d\\n",a\[i\]);
}
return 0;
}