Akhilesh Pandey
BAN USERA regular guy.
What? How?
Rabin-Karp works in expected linear time. Refer to a standard text.
Rolling hash calculation for window (i+1 to j+1) can be calculated from the hash for window (i to j) in constant time. Use of a proper base for polynomial hashing will greatly reduce false positives.
Polynomial hashing, rolling hash (kinda like Rabin-Karp string matching algorithm) should do the trick for (i).
- Akhilesh Pandey May 31, 2015Here's a working C++ code.
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
set<string> dictionary;
void populate_dictionary();
bool search_dictionary(string s);
void possible_concatenations(string s);
int main()
{
string s="bedbathandbeyond";
populate_dictionary();
possible_concatenations(s);
return 0;
}
void populate_dictionary()
{
dictionary.insert("bed");
dictionary.insert("bat");
dictionary.insert("bath");
dictionary.insert("and");
dictionary.insert("hand");
dictionary.insert("beyond");
}
bool search_dictionary(string s)
{
set<string>::iterator itr;
for(itr=dictionary.begin(); itr!=dictionary.end(); itr++)
{
if(*itr==s)
return true;
}
return false;
}
void possible_concatenations(string s)
{
static vector<string> v;
if(s=="")
{
for(int i=0; i<v.size(); i++)
cout<<v[i]<<" ";
cout<<endl;
return;
}
string sub;
for(int i=1; i<=s.size(); i++)
{
sub=s.substr(0, i);
//cout<<sub<<endl;
if(search_dictionary(sub))
{
v.push_back(sub);
possible_concatenations(s.substr(i));
v.pop_back();
}
}
}
Suppose that an array(Arr) has 'N' elements {a, b, c, d, e, ....}.
Array indexing starts at 1.
Define S=a+b+c+d+e+.....
We will have
PMEAN1 = a + 2b + 3c + 4d + 5e + .....
PMEAN2 = b + 2c + 3d + 4e + .....+Na
..
..
PMEAN(k)=PMEAN(k-1) - S + N*Arr[k-1]
Looks like a variant of the coin change problem.
Here's a DP solution -:
#define INF 99999
int table[100000];
void init()
{
int i;
for(i=0; i<100000; i++)
{
table[i]=-1;
}
}
int minsquares(long long int n)
{
if(n<0)
return INF;
if(n==0)
return 0;
if(table[n]!=-1)
{
return table[n];
}
int ans=INF;
for(int i=1; i*i<=n; i++)
{
ans=min(ans, minsquares(n-i*i));
}
table[n]=ans+1;
return table[n];
}
xi and xj contain the values needed to be added to i and j to get to adjacent cells.
- Akhilesh Pandey January 25, 2015Don't understand the question. An example would help.
- Akhilesh Pandey December 07, 2013Your palindrome number generator generates 101(next palindrome) after 9.
It should be 11 instead.
Hi,
How about instead of checking all the numbers starting from 1(decimal) to an upper limit, we generate the first 10000 (say) decimal palindromic numbers. Then convert them to octal and check if the octal representation is palindromic or not.
Below is the working C++ code to print the numbers that are palindromic in both decimal and octal representations.
Function descriptions
i) next_palindrome - This function takes a palindrome number as argument and returns the next larger palindrome. Initially started with 0 as seed.
Ex - next_palindrome(99)=101
next_palindrome(999)=1001
next_palindrome(12321)=12421
This function uses a folding technique to find out the next larger palindrome.
ii) itoa - integer to string
iii) reverse - reverse a string
iv) dec_oct - convert from decimal to octal
v) is_palindrome - to check if a string is a palindrome
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int next_palindrome(int palindrome);
void itoa(int p, char s[]);
void reverse(char s[]);
void dec_oct(int dec, char oct[]);
bool is_palindrome(char s[]);
int main()
{
int start=0;
char oct[20];
cout<<setw(10)<<"Decimal"<<setw(10)<<"Octal"<<endl;
for(int i=0; i<10000; i++)
{
dec_oct(start, oct);
if(is_palindrome(oct))
cout<<setw(10)<<start<<" "<<setw(10)<<oct<<endl;
start=next_palindrome(start);
}
return 0;
}
int next_palindrome(int pal)
{
char s[15];
char t[15];
char temp[15];
char help[15];
int nt;
itoa(pal, s);
if(strlen(s)%2)
{
memcpy(t, s, strlen(s)/2 + 1);
t[strlen(s)/2 + 1]='\0';
nt=atoi(t);
itoa(nt+1, temp);
if(strlen(temp) != strlen(t))
{
temp[strlen(t)]='\0';
memcpy(help, temp, strlen(temp)+1);
reverse(help);
strcat(temp, help);
return atoi(temp);
}
else
{
memcpy(help, temp, strlen(temp)-1);
help[strlen(temp)-1]='\0';
reverse(help);
strcat(temp, help);
return atoi(temp);
}
}
else
{
memcpy(t, s, strlen(s)/2);
t[strlen(s)/2]='\0';
nt=atoi(t);
itoa(nt+1, temp);
if(strlen(temp) != strlen(t))
{
memcpy(help, temp, strlen(temp)-1);
help[strlen(temp)-1]='\0';
reverse(help);
strcat(temp, help);
return atoi(temp);
}
else
{
memcpy(help, temp, strlen(temp)+1);
reverse(help);
strcat(temp, help);
return atoi(temp);
}
}
}
void dec_oct(int dec, char oct[])
{
int i=0;
if(dec==0)
{
oct[0]='0';
oct[1]='\0';
return;
}
while(dec>0)
{
oct[i]=dec%8+'0';
dec=dec/8;
i++;
}
oct[i]='\0';
reverse(oct);
}
bool is_palindrome(char s[])
{
char temp[20];
strcpy(temp, s);
reverse(temp);
if(strcmp(temp, s)==0)
return true;
return false;
}
void itoa(int p, char s[])
{
int i=0;
while(p>0)
{
s[i]=p%10 + '0';
p=p/10;
i++;
}
s[i]='\0';
reverse(s);
}
void reverse(char s[])
{
int i;
int len=strlen(s);
char temp;
for(i=0; i<len/2; i++)
{
temp=s[i];
s[i]=s[len-i-1];
s[len-i-1]=temp;
}
}
Output ( first 15 lines)
Decimal Octal
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
9 11
121 171
292 444
333 515
373 565
414 636
For input sequence {1, 1, 1, 1, 5} your code gives the output as {1}.
- Akhilesh Pandey November 01, 2013Can you please elaborate, and if possible, post the code....
- Akhilesh Pandey October 28, 2013@Darida
Nice....Thumbs Up
Interviewer expected the longest sub-array or just any sub-array?
For finding the longest sub-array whose sum of elements is divisible by 7, we can follow a Breadth First Search approach.
For any array we can have either of two states -:
i) The sum of elements is divisible by 7. So, we just return the array
ii) The sum of elements is not divisible by 7. So we remove either the first or the last element and begin from top.
(1, 2, 3, 4, 5)
(Sum=15, not divisible by 7)
/ \
(1, 2, 3, 4) (2, 3, 4, 5)
(sum=10, not divisible by 7) (Sum=14, divisible, return array)
Below is the working C++ code
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<int> fun(vector<int> &a);
bool divisible_by_7(vector<int> &v);
int main()
{
vector<int> a;
vector<int> result;
int n;
int temp;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>temp;
a.push_back(temp);
}
result=fun(a);
for(int i=0; i<result.size(); i++)
cout<<result[i]<<" ";
cout<<endl;
return 0;
}
vector<int> fun(vector<int> &a)
{
queue<vector<int> > q;
vector<int> temp;
if(a.size() == 0)
return temp;
q.push(a);
while(!q.empty())
{
temp.clear();
temp=q.front();
if(divisible_by_7(temp))
return temp;
if(temp.size() != 0)
{
temp.erase(temp.begin());
q.push(temp);
temp=q.front();
temp.erase(temp.end() - 1);
q.push(temp);
}
q.pop();
}
return temp;
}
bool divisible_by_7(vector<int> &v)
{
int sum=0;
for(int i=0; i<v.size(); i++)
{
sum=sum+v[i];
}
if(sum%7 == 0)
return true;
return false;
}
The same problem was posed in a programming competition at my work place. Here is the working solution I submitted.
#include<stdio.h>
#include<string.h>
#define LEFT 0
#define RIGHT 1
#define TOTAL 2
#define WEIGHT_OF_BALANCE 10
int tobeadded[50][2];
int actual_weights_kept[50][2];
int scales_dependency_left[50][50];
int scales_dependency_right[50][50];
int balance(int balance_number);
int countspaces(char *p)
{
int count=0, i;
int len=strlen(p);
for(i=0;i<len; i++)
{
if(p[i]==' ')
{
count++;
p[i]='\0';
}
}
return count;
}
void reset()
{
int i, j, k;
for(i=0; i<;50;i++)
{
for(j=0;j<;50; j++)
{
scales_dependency_left[i][j]=0;
scales_dependency_right[i][j]=0;
}
for(k=0;k<;2;k++)
{
tobeadded[i][j]=0;
actual_weights_kept[i][j]=0;
}
}
}
int main(int argc, char *argv[])
{
char str[250];
int i, j, leftcount, rightcount, n;
int ns;
char *p;
FILE *fp=fopen(argv[1], "r");
FILE *of=fopen(argv[2], "w");
while(memcmp(fgets(str, 250, fp), "E", 1)!=0)
{
reset();
n=atoi(str);
for(i=0;i<;2*n;i++)
{
fgets(str, 250, fp);
ns=countspaces(str);
if(i%2==0)
{
actual_weights_kept[i/2][LEFT]=atoi(str);
scales_dependency_left[i/2][0]=ns;
p=str + strlen(str)+1;
for(j=1; j<=ns; j++)
{
scales_dependency_left[i/2][j]=atoi(p);
p=p + strlen(p)+1;
}
}
else
{
actual_weights_kept[i/2][RIGHT]=atoi(str);
scales_dependency_right[i/2][0]=ns;
p=str+strlen(str)+1;
for(j=1;j<=ns; j++)
{
scales_dependency_right[i/2][j]=atoi(p);
p=p+strlen(p)+1;
}
}
}
for(i=0;i<n;i++)
balance(i);
for(i=0;i<n;i++)
fprintf(of, "%d %d %d\n", i, tobeadded[i][0], tobeadded[i][1]);
}
fclose(fp);
fclose(of);
return 0;
}
int balance(int balance_number)
{
int i, j;
int lweight=actual_weights_kept[balance_number][LEFT], rweight=actual_weights_kept[balance_number][RIGHT];
for(i=1; i<=scales_dependency_left[balance_number][0]; i++)
{
lweight=lweight+balance(scales_dependency_left[balance_number][i]);
}
for(j=1; j<=scales_dependency_right[balance_number][0]; j++)
{
rweight=rweight+balance(scales_dependency_right[balance_number][j]);
}
if(lweight>rweight)
{
tobeadded[balance_number][LEFT]=0;
tobeadded[balance_number][RIGHT]=lweight-rweight;
rweight=lweight;
}
else
{
tobeadded[balance_number][LEFT]=rweight-lweight;
tobeadded[balance_number][RIGHT]=0;
lweight=rweight;
}
return lweight+rweight+WEIGHT_OF_BALANCE;
}
The same question was posed as a problem in a coding competition organized at my workplace. Here is the working solution I submitted
#include<stdio.h>
#include<string.h>
#define LEFT 0
#define RIGHT 1
#define TOTAL 2
#define WEIGHT_OF_BALANCE 10
int tobeadded[50][2];
int actual_weights_kept[50][2];
int scales_dependency_left[50][50];
int scales_dependency_right[50][50];
int balance(int balance_number);
int countspaces(char *p)
{
int count=0, i;
int len=strlen(p);
for(i=0;i<len; i++)
{
if(p[i]==' ')
{
count++;
p[i]='\0';
}
}
return count;
}
void reset()
{
int i, j, k;
for(i=0; i<50;i++)
{
for(j=0;j<50; j++)
{
scales_dependency_left[i][j]=0;
scales_dependency_right[i][j]=0;
}
for(k=0;k<2;k++)
{
tobeadded[i][j]=0;
actual_weights_kept[i][j]=0;
}
}
}
int main(int argc, char *argv[])
{
char str[250];
int i, j, leftcount, rightcount, n;
int ns;
char *p;
FILE *fp=fopen(argv[1], "r");
FILE *of=fopen(argv[2], "w");
while(memcmp(fgets(str, 250, fp), "E", 1)!=0)
{
reset();
n=atoi(str);
for(i=0;i<2*n;i++)
{
fgets(str, 250, fp);
ns=countspaces(str);
if(i%2==0)
{
actual_weights_kept[i/2][LEFT]=atoi(str);
scales_dependency_left[i/2][0]=ns;
p=str + strlen(str)+1;
for(j=1; j<=ns; j++)
{
scales_dependency_left[i/2][j]=atoi(p);
p=p + strlen(p)+1;
}
}
else
{
actual_weights_kept[i/2][RIGHT]=atoi(str);
scales_dependency_right[i/2][0]=ns;
p=str+strlen(str)+1;
for(j=1;j<=ns; j++)
{
scales_dependency_right[i/2][j]=atoi(p);
p=p+strlen(p)+1;
}
}
}
for(i=0;i<n;i++)
balance(i);
for(i=0;i<n;i++)
fprintf(of, "%d: %d %d\n", i, tobeadded[i][0], tobeadded[i][1]);
}
fclose(fp);
fclose(of);
return 0;
}
int balance(int balance_number)
{
int i, j;
int lweight=actual_weights_kept[balance_number][LEFT], rweight=actual_weights_kept[balance_number][RIGHT];
for(i=1; i<=scales_dependency_left[balance_number][0]; i++)
{
lweight=lweight+balance(scales_dependency_left[balance_number][i]);
}
for(j=1; j<=scales_dependency_right[balance_number][0]; j++)
{
rweight=rweight+balance(scales_dependency_right[balance_number][j]);
}
if(lweight>rweight)
{
tobeadded[balance_number][LEFT]=0;
tobeadded[balance_number][RIGHT]=lweight-rweight;
rweight=lweight;
}
else
{
tobeadded[balance_number][LEFT]=rweight-lweight;
tobeadded[balance_number][RIGHT]=0;
lweight=rweight;
}
return lweight+rweight+WEIGHT_OF_BALANCE;
}
Input test case file name and output file name to be passed as command line arguments.
End of Input indicated by 'E' in the input file.
So the above input will look like
4
0 1
0 2
0
0 3
3
0
0
0
E
The idea is simple - Recursive Backtracking
C++ program to print all valid combinations of 'n' pair of braces
#include<iostream>
#include<string>
using namespace std;
void print_parentheses(int n);
void print(int left, int right, int n, string s);
int main()
{
int n;
cout<<"Enter n: ";
cin>>n;
print_parentheses(n);
}
void print_parentheses(int n)
{
string s="";
print(0, 0, n, s);
}
void print(int left, int right, int n, string s)
{
if(left>n || right>n || right>left)
return;
if(left==right && left+right==2*n)
{
cout<<s<<endl;
return;
}
print(left+1, right, n, s+"(");
print(left, right+1, n, s+")");
}
C++ program to generate valid words for any length
#include<iostream>
#include<string>
using namespace std;
void print(string s, int i, int n, int len);
char alphabets[]={'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u','v', 'w', 'x', 'y', 'z'};
int main()
{
string s;
int n;
cin>>n;
print(s, 0, n, 0);
return 0;
}
void print(string s, int i, int n, int len)
{
if(len==n)
{
cout<<s<<endl;
return;
}
for(int j=i; j<26; j++)
{
print(s+alphabets[j], j, n, len+1);
}
}
void find_finger(int n)
{
bool dir;
int t;
string val[]={"Thumb", "Index", "Middle", "Ring", "Little"};
if(n<6)
{
cout<<val[n-1];
cout<<endl;
return;
}
n=n-6;
t=n/4;
if(t%2==0)
{
dir=true;
}
t=n%4;
if(dir==true)
{
cout<<val[4-t-1];
}
else
{
cout<<val[t+1];
}
cout<<endl;
}
Maintain another stack minStack to keep track of the min elements.
We need to be careful for duplicates.
Here is a complete program -:
#include<iostream>
#include<stack>
using namespace std;
stack<int> a;
stack<int> minStack;
void insert(int x);
int remove();
void display();
int minimum();
int main()
{
int ch;
int x;
do
{
cout<<"Main Menu\n1 Push\n2 Pop\n3 Find Minimum\n4 Display\n5 Exit\nEnter your choice: ";
cin>>ch;
switch(ch)
{
case 1: cout<<"Enter element to be pushed: ";
cin>>x;
insert(x);
break;
case 2:cout<<"Element popped: "<<remove()<<endl;
break;
case 3:cout<<"Minimum element in the stack: "<<minimum()<<endl;
break;
case 4: display();
break;
case 5: exit(0);
break;
default: cout<<"No such option!!!"<<endl;
break;
}
}while(ch!=5);
return 0;
}
void insert(int x)
{
a.push(x);
if(minStack.empty() || x<=minStack.top())
{
minStack.push(x);
}
}
void insert(int x)
{
a.push(x);
if(minStack.empty() || x<=minStack.top())
{
minStack.push(x);
}
}
int remove()
{
if(a.empty())
{
cout<<"Stack underflow!!!";
return -9999;
}
int temp=a.top();
a.pop();
if(temp==minStack.top())
{
minStack.pop();
}
return temp;
}
void display()
{
stack<int> temp=a;
while(!temp.empty())
{
cout<<temp.top()<<" ";
temp.pop();
}
cout<<endl;
}
int minimum()
{
if(minStack.empty())
{
cout<<"Stack underflow!!!"<<endl;
return -9999;
}
else
{
return minStack.top();
}
}
Divide and Conquer.
- Akhilesh Pandey October 27, 2015Follow an approach similar to finding number of inversions using a modification of merge sort (nlogn).