/*
First Let's see what all approaches we can take and then we check if it fits our requirement.
1. Brute Force: Select an element from 1 to N and check it frequency of occurrence. But this will be O(n2) and not O(n) .
2. XOR : but this technique won't work as question mentions an element can be repeated multiple times. so if element repeats 2 times or 4 times each time result of xor will be 0 so we cannot get the frequency of occurrences.
3. HashMap : We can create a HashMap in O(n) key will be elements and value will be their frequency of occurrence. But since we have to do it in O(1) space we cannot take this approach.
So we cannot opt for any of the above 3 approach. We have to check for some 4th approach.
Since we have range of numbers given to us we have to think in those lines.
Array Index is from 0 to N-1 and range is from 1 to N. Can't we use the array as hash itself?
where array "Index-1" represents the key (element) and value stored at index will represent the "frequency of occurrence".
But how will we take care that an element present at any index is not overwritten as this can cause problem?
We can sort the array in that case value present at index i is I+1 itself.
What is the complexity of sorting the array?
since the range of element is given to us we can sort it in O(n).
ALGORITHM
Since array contains elements from 1 to N we cannot keep frequency in same array as it will confuse which one is frequency and which one is the element value.
To overcome this, store frequency in negative, -1 = element appear once and so on, by this we are able to distinguish between frequency of occurrence and elements.
Negative values/0 are frequency and +ve values are elements.
1. Scan array from left to right.
Pos =0 ; while pos < N
2. If current element is –ve or 0 then move forward (pos++).
3. Desiredpos = arr[pos]-1.
4. Check if arr[desiredPos] > 0
a. If yes that means no previous occurrence of current element.
Hence copy arr[pos] = arr[desiredPos] and set arr[desiredPos] =-1 i.e. first occurrence.
b. Else if it is encountered earlier also then decrement the frequency (arr[desiredPos]--) and set arr[pos] =0.
5. While displaying frequency multiply the elements with -1, as all elements in array will be either –ve or 0.
*/
#include <iostream>
using namespace std;
void getDuplicate(int arr[],int size)
{
int pos = 0;
int desiredPos = 0;
while(pos < size)
{
if(arr[pos] <= 0)
{
pos++;
continue;
}
desiredPos = arr[pos] -1;
if(arr[desiredPos] > 0)
{
arr[pos] = arr[desiredPos];
arr[desiredPos] = -1;
}
else
{
arr[desiredPos]--;
arr[pos] = 0;
pos++;
}
}
}
void display(int arr[], int size)
{
for(int i=0; i<size; i++)
cout<<"\nElement = "<<i+1<<"\tFrequency = "<<arr[i]*-1;
}
int main()
{
int arr[] = {6,4,1,4,3,2,5,2,1};
int size = sizeof(arr)/sizeof(arr[0]);
getDuplicate(arr,size);
display(arr,size);
}
Sunday 14 July 2013
You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
Print all the words in a 3x3 matrix 'c','b','k' ..... 'd','a','l' ...... 'g','t','i' . words can be found horizontally, vertically and diagonally (reverse/straight order).
/*
An alphabet can be used only in one of the word.
If any cell of matrix constitutes to any word, I have replaced the character with a '*'
*/
#include <iostream>
#include <sstream>
using namespace std;
const int DIM = 3;
const int MAXNEIGHBOURS = 8;
int displacement[8][2] = {{-1,-1},{0,-1},{1,-1},{1,0},{-1,1},{0,1},{-1,1},{-1,0}};
char matrix[DIM][DIM] = {{'c','a','t'},{'a','j','i'},{'t','n','o'}};
void displayMatrix();
bool isValid(int row, int col)
{
if(row<0 || col <0 || row >= DIM || col >= DIM)
return false;
if(matrix[row][col] == '*')
return false;
return true;
}
bool solveMatrix(int row,int col, string word)
{
if(word.compare("*") ==0)
return false;
if(dictionary.search(word))
{
cout<<"\n"<<word;
matrix[row][col] = '*';
return true;
}
for(int i=0; i<MAXNEIGHBOURS ; i++)
{
int newRow = row + displacement[i][0];
int newCol = col + displacement[i][1];
char originalCharacter = matrix[row][col];
matrix[row][col] = '*';
if(isValid(newRow,newCol))
{
if(solveMatrix(newRow,newCol,word+matrix[newRow][newCol]))
return true;
}
matrix[row][col] = originalCharacter;
}
return false;
}
string toString(char ch)
{
stringstream ss;
string s;
ss<<ch;
ss>>s;
return s;
}
int main()
{
dictionary.insert("hello");
dictionary.insert("cat");
dictionary.insert("in");
dictionary.insert("no");
dictionary.insert("at");
for(int i=0; i<DIM; i++)
for(int j=0; j<DIM; j++)
solveMatrix(i,j,toString(matrix[i][j]));
cout<<endl;
system("pause");
}
/*
I have used TRIE to store dictionary below is the implentation of it.
*/
class TRIENode
{
public:
bool word;
int prefixCount;
TRIENode *child[26];
TRIENode()
{
word = false;
prefixCount = 0;
for(int i=0; i<26; i++)
child[i] = NULL;
}
bool isWord()
{
return word;
}
};
class TRIE
{
private:
TRIENode *headNode;
public:
TRIE()
{
headNode = new TRIENode();
}
void insert(string w)
{
TRIENode *ptr = headNode;
ptr->prefixCount++;
for(int i=0; i<w.length(); i++)
{
int index = w[i] - int('a');
if(ptr->child[index] ==NULL)
{
ptr->child[index] = new TRIENode();
}
ptr->child[index]->prefixCount++;
ptr = ptr->child[index];
}
ptr->word = true;
}
bool search(string str)
{
TRIENode *ptr = headNode;
for(int i=0; i<str.length(); i++)
{
int index = str[i] - 'a';
if(ptr->child[index] == NULL)
return false;
ptr = ptr->child[index];
}
if(ptr->isWord())
return true;
return false;
}
}dictionary;
Monday 8 July 2013
Given a sorted rotated array, find an element in O(logn) time without finding the pivot element.
//============================================================================
// Name : SortedRotatedArray.cpp
// Author : Varun Sharma
// Version : 1.0
// Complexity : O(logn)
// Description : Finding Element in a sorted rotated array, without finding pivot.
//============================================================================
/*
ALGORITHM
=========
1. Initialize start = 0, end = size-1.
2. Repeat while start <= end
a. Calculate mid element => mid = (start+end)/2.
b. If arr[mid] = val then print position and return true.
c. Array is sorted from start to mid or from mid to end, check which one is the case.
d. Sorted from Mid to end: arr[mid] < arr[end].
i. If search value lies in right sorted half : val arr[mid] && val <= arr[end]
then start = mid+1
ii.Else end = mid-1
e. Else Sorted from start to mid .
i. If search value lies in left sorted half: val <arr[mid] && val>= arr[start]
then end = mid-1
ii.Else start = mid+1.
3. Return false if element not found.
*/
#include <iostream>
using namespace std;
bool search(int arr[],int size,int val) {
int start = 0;
int end = size-1;
int mid;
while(start <= end) {
mid = (start+end)/2;
//Value at mid == search value then return found.
if(arr[mid] == val) {
cout<<"nFOUND AT POSITION : "<<mid+1;
return true;
}
//If value at mid < value at end
//i.e. Array is sorted from mid to end.
if(arr[mid] < arr[end]) {
//Value lies in right sorted half of array.
if(val > arr[mid] && val <= arr[end])
start = mid+1;
else
//Value lies in left half of array.
end = mid-1;
}
//Array is sorted from start to mid.
else {
//Value lies in left sorted half of array.
if(val < arr[mid] && val >= arr[start])
end = mid-1;
//Value lies in right sorted half.
else
start = mid+1;
}
}
return false;
}
int main() {
int arr[] = {6,7,8,9,10,11,1,2,3,4,5};
int size = sizeof arr/sizeof arr[0];
if(!search(arr,size,6))
cout<<"nVALUE DOESN'T EXIST";
int arr1[] = {6,7,8,9,10,11,12,13,14,5};
int size1 = sizeof arr1/sizeof arr1[0];
if(!search(arr1,size1,5))
cout<<"nVALUE DOESN'T EXIST";
int arr2[] = {5,6,7,8,9,10,11,12,13,14};
int size2 = sizeof arr2/sizeof arr2[0];
if(!search(arr2,size2,5))
cout<<"nVALUE DOESN'T EXIST";
int arr3[] = {5,6,7,8,9,10,11,12,13,14};
int size3 = sizeof arr3/sizeof arr3[0];
if(!search(arr3,size3,18))
cout<<"nVALUE DOESN'T EXIST";
int arr4[] = {6,7,8,9,10,11,12,13,14,5};
int size4 = sizeof arr4/sizeof arr4[0];
if(!search(arr4,size4,1))
cout<<"nVALUE DOESN'T EXIST";
return 0;
}
Sunday 7 July 2013
Convert Infix expression to Post/Pre fix.
/*
* Compiler always represent expression in postfix Notation.
* Shunting yard algorithm is used for this conversion.
* It can be used to convert to Prefix also.
* Reverse Input string.
* Use shunting yard algorith.
* Reverse the output string
*/
#include <iostream>
#include <stack>
using namespace std;
string output = "";
stack<int> operatorStack;
// Attach integer value with each operand.
// Same precedence operator share same int. value.
// ( paren has least value.
int getPrecedence(char ch)
{
switch(ch)
{
case '*' : return 2;
case '+' : return 1;
case '/' : return 2;
case '-' : return 1;
case '(' : return 0;
}
}
// Get precedence of current as well as stack top element.
// If current precedence is greater or equal then return true
// else return false
bool greaterPrecedenceThanStackTop(char ch)
{
int topPrecedence = getPrecedence(operatorStack.top());
int charPrecedence = getPrecedence(ch);
if(charPrecedence >= topPrecedence)
return true;
return false;
}
bool isOperand(char ch)
{
switch(ch)
{
case '+' : return true;
case '-' : return true;
case '*' : return true;
case '/' : return true;
default : return false;
}
}
bool isParen(char ch)
{
if(ch == '(' || ch == ')')
return true;
return false;
}
// If opening paren push it to operator stack.
// Else Pop operators from operator stack to output string.
// until operning paren is popped.
void scannedParen(char ch)
{
if(ch == '(')
{
cout<<"\n\tPUSH ( TO OPERATOR STACK";
operatorStack.push(ch);
}
else
{
while(!operatorStack.empty() && operatorStack.top() != '(')
{
cout<<"\n\tPOP AND ADD TO OUTPUT "<<char(operatorStack.top());
output += operatorStack.top();
operatorStack.pop();
}
if(!operatorStack.empty())
{
cout<<"\n\tPOP (";
operatorStack.pop();
}
}
}
// If stack is empty push operator.
// If operator has same or higher precedence than stack[top] push operator.
// Else pop operators until stack is empty or stack[top] has equal or less precedence
// Than current operator.
void scannedOperator(char ch)
{
if(operatorStack.empty())
{
cout<<"\n\tPUSH TO OPERATOR STACK";
operatorStack.push(ch);
return;
}
if(greaterPrecedenceThanStackTop(ch))
{
cout<<"\n\tPUSH TO OPERATOR STACK";
operatorStack.push(ch);
}
else
{
while(!greaterPrecedenceThanStackTop(ch) && !operatorStack.empty())
{
cout<<"\n\tPOP "<<char(operatorStack.top());
output += operatorStack.top();
operatorStack.pop();
}
cout<<"\n\tPUSH "<<ch;
operatorStack.push(ch);
}
}
//Copy all operators from operatroStack to output string.
void flushStack()
{
while(!operatorStack.empty())
{
char c = operatorStack.top();
cout<<"\n\tCOPY "<<c<<" TO OUTPUT";
operatorStack.pop();
if(c == '(')
continue;
output += c;
}
}
//Separate operators, parenthesis and Operands.
//Call appropriate function accordingly.
void scanInput(string input)
{
string operand = "";
for(int i=0 ; i< input.length(); i++)
{
char ch = input[i];
cout<<"\n\nCURRENT CHAR = "<<ch;
if(isParen(ch))
{
output += operand;
operand = "";
scannedParen(ch);
}
else if(isOperand(ch))
{
output += operand;
operand = "";
scannedOperator(ch);
}
else
{
cout<<"\n\tCOPY TO OUTPUT STRING";
operand += ch;
}
}
cout<<"\n\nEND OF INPUT : FLUSH STACK";
output += operand;
flushStack();
}
int main()
{
string input = "a+(b+c*(e/f)+d)*g";
cout<<"INFIX NOTATION : "<<input;
scanInput(input);
cout<<"\n\nPOSTFIX NOTATION : "<<output<<endl;
system("pause");
}
/*
OUTPUT
-------
INFIX NOTATION : a+(b+c*(e/f)+d)*g
CURRENT CHAR = a
COPY TO OUTPUT STRING
CURRENT CHAR = +
PUSH TO OPERATOR STACK
CURRENT CHAR = (
PUSH ( TO OPERATOR STACK
CURRENT CHAR = b
COPY TO OUTPUT STRING
CURRENT CHAR = +
PUSH TO OPERATOR STACK
CURRENT CHAR = c
COPY TO OUTPUT STRING
CURRENT CHAR = *
PUSH TO OPERATOR STACK
CURRENT CHAR = (
PUSH ( TO OPERATOR STACK
CURRENT CHAR = e
COPY TO OUTPUT STRING
CURRENT CHAR = /
PUSH TO OPERATOR STACK
CURRENT CHAR = f
COPY TO OUTPUT STRING
CURRENT CHAR = )
POP AND ADD TO OUTPUT /
POP (
CURRENT CHAR = +
POP *
PUSH +
CURRENT CHAR = d
COPY TO OUTPUT STRING
CURRENT CHAR = )
POP AND ADD TO OUTPUT +
POP AND ADD TO OUTPUT +
POP (
CURRENT CHAR = *
PUSH TO OPERATOR STACK
CURRENT CHAR = g
COPY TO OUTPUT STRING
END OF INPUT : FLUSH STACK
COPY * TO OUTPUT
COPY + TO OUTPUT
POSTFIX NOTATION : abcef/*d++g*+
*/
Wednesday 3 July 2013
Given a number, return the next multiple of 64 that follows it, using bit operations and no loops. e.g input = 90, return 128.
#include <iostream>
using namespace std;
int main()
{
int n = 90;
int n1 = n>>6;
int n2 = (n1+1)<<6;
cout<<n2;
system("pause");
}
Subscribe to:
Posts (Atom)