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]
Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort
in your Pseudocode, the if condition should be if …
RM - May 3, 2014
in your Pseudocode, the if condition should be if (low < high).
Thanks Rish. I have made the change a[low] > a[high] rather than low < low. :). Thanks for correcting me.
Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort
Problem Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort.
Example Input - Binary unsorted array
A = {0,1,1,0,0,1};
Output - binary sorted array
B = {0,0,0,1,1,1}
Solution This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n).
[Read More]
Write a C Program to reverse a stack "in place" using recursion ?
**You can only use the following ADT functions on Stack: IsEmpty IsFull Push Pop Top** #include #include using namespace std;
stack S;
void func(int n){
if(S.empty())
S.push(n);
else{
int t= S.top();
S.pop();
func(n);
S.push(t);
}
}
void Rec(){
if(!S.empty()){
int t = S.top();
S.pop();
Rec();
func(t);
}
}
void printStack(){
if(!S.empty()){
int t= S.top();
S.pop();
cout«”,";
printStack();
S.push(t);
}
else{
cout«"Stack empty now”;
}
}
int main(int argc, char* argv[])
[Read More]
You are given a datatype, say X in C. The requirement is to get the size of the datatype, without declaring a variable or a pointer variable of that type, And, of course without using sizeof operator !
Sol:- #define size(type) ( (int)((type \*)0+1) - (int)((type \*)0))
What can be maximum memory that a process can have in 32-bit machine? What assigns a process this memory?
Sol:- #define size(type) ( (int)((type \*)0+1) - (int)((type \*)0))
What should be done when an exception occurs in the constructor?
Sol:- #define size(type) ( (int)((type \*)0+1) - (int)((type \*)0))