Remove duplicates from the sorted array

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**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]
Algorithms  kodeknight  duplicate  array  remove-duplicates  sorted-array 

print all word combinations from phone number

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

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]
Algorithms  kodeknight 

String matching

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

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]
Algorithms  kodeknight  String  optimization 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

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.

kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

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]
kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Write a C Program to reverse a stack "in place" using recursion ?

 Posted on April 10, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**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]
kodeknight  reverse  stack 

How do you know where the memory leaks when you have multiple files?

 Posted on April 10, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

One Way to detect the memory leaks is to check that while using Inheritance and Virtual Functions some where we have initialized baseclass pointer with the derived class object but when calling destructor the destructor that u have used in the baseclass is not declared as Virtual. eg: #include using namespace std; class Base1 { public: ~Base1() { cout « “~Base1()\n”; } }; class Derived1 : public Base1 { public: [Read More]
kodeknight