using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text.RegularExpressions;
namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
//This part assumes that all the elements in the array lie in the range (min,min + arraylength -1).
int[] arr1 = { 1, 2, 3, 4, 4, 5, 2, 1, 1, 1 };
int count = 1;
int min = arr1.Min();
int max = arr1.Max();
for (int i = 0; i < arr1.GetLength(0); i++)
{
arr1[Math.Abs(arr1[i])] *= -1;
}
for (int i = 0; i < arr1.GetLength(0); i++)
{
Console.Write(arr1[i] + " ");
}
Console.WriteLine();
for (int i = min; i <= max; i++) { if (arr1[i] > 0)
{
Console.Write(i + " ");
}
}
Console.WriteLine();
//This part sorts the array and finds the frequency map and counts the frequency of each element.
int[] arr2 = { 1, 2, 3, 4, 4, 5, 2, 1, 1, 1 };
Array.Sort(arr2);
for (int i = 0; i < arr2.GetLength(0) - 1; i++)
{
count = 1;
while (arr2[i + 1] == arr2[i])
{
i++;
count++;
}
if (count % 2 == 0)
{
Console.WriteLine(arr2[i] + " " + count);
}
}
}
}
}
A blog on programming and software design interview problems and solutions. Also there are some application development related stuff.
Pages
Monday, July 23, 2012
Given an array of positive integers, print out all the numbers which are repeated an even number of times without using additional storage
Sunday, July 22, 2012
Printing the max length substring with max repetition count
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text.RegularExpressions;
namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
string str = Console.ReadLine();
int[] maxcount = new int[str.Length + 1];
string[] maxstring = new string[str.Length + 1];
for (int i = 0; i < str.Length; i++)//Starting point of the substring to be searched.
{
for (int length = 1; length <= str.Length - i; length++)//Length of the substring to be searched.
{
int count = 0;
string substr1 = str.Substring(i, length);
for (int j = 0; j <= str.Length - length; j++)//Starting point in the string from where the search starts.
{
string substr2 = str.Substring(j, length);
if (substr1 == substr2)
{
count++;
}
}
if (maxcount[length] < count)
{
maxcount[length] = count;
maxstring[length] = substr1;
}
}
}
int maxcnt = 0;
string maxstr="";
for (int i = 1; i <= str.Length; i++)
{
if (maxcnt <= maxcount[i])
{
maxcnt = maxcount[i];
maxstr = maxstring[i];
}
}
Console.WriteLine(maxstr + " has the max length: " + maxcnt);
}
}
}
abcabcabcabc
abc has the max length: 4
Press any key to continue . . .
C Program to write the permutations of the characters of a string using Recursion
#include<stdio.h>
#include<string.h>
int main()
{
void permute(char[],char[],int[],int,int);
char A[100];
scanf("%s",A);
char B[100]="";
int length=strlen(A);
int level=0;
int used[100]={0};
permute(A,B,used,length,level);
return 0;
}
void permute(char* A,char* B,int* used,int length,int level)
{
if(level==length)
{
B[level]='';
printf("%s\n",B);
return;
}
else
{
for(int i=0;i<length;i++)
{
if(used[i]==1)
{
continue;
}
used[i]=1;
B[level]=A[i];
permute(A,B,used,length,level+1);
used[i]=0;
B[level]='';
}
return;
}
}
Saturday, July 21, 2012
Alternating Letters
An alternation in a string is defined to be two distinct characters (letters, digits, or punctuation) that alternate at least three times as the word is read from left to right. The word “boo” has no alternations, but “booboo” has “bobo” as an alternation of length 4. Upper and lower case characters are considered to be different, and so, “aragorn” contains the 4-element alternation “arar”, but “Aragorn” only has the 3-element alternation “rar”. Digits and punctuation may be used, so “a2b-c2d-” has the alternation “2-2-”. The objective of this problem is to write a program to find the length of the longest alternation in a word.
Examples:
Examples:
Input | Output | Explanation |
exasperated | Length = 5 | eaeae |
counterintuitive | Length = 6 | tititi |
insignificant | Length = 6 | ininin |
Aragorn | Length = 3 | rar |
a2b-c2d- | Length = 4 | 2-2- |
cat | Length = 0 | No subsequence having length > 3 |
ca | Length = 0 | No subsequence having length > 3 |
#include<stdio.h>
#include<string.h>
int main()
{
int A[256]={0},max=0,B[256]={0};
char s[1000];
scanf("%s",s);
for(int i=0;i<strlen(s);i++)
{
A[s[i]]++;
if(s[i]>max)
{
max=s[i];
}
}
int k=0;
for(int i=0;i<=max;i++)
{
if(A[i]!=0)
{
B[k]=i;
k++;
}
}
int maxcount=0;
for(int i=0;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
int count=0;
int order=0;
char curr='';
for(int c=0;c<strlen(s);c++)
{
if(s[c]==B[i])
{
if(order==0)
{
count++;
order=1;
curr=B[i];
}
else if(curr==B[j])
{
count++;
curr=B[i];
}
}
else if(s[c]==B[j])
{
if(order==0)
{
count++;
order=1;
curr=B[j];
}
else if(curr==B[i])
{
count++;
curr=B[j];
}
}
}
if(maxcount<count)
{
maxcount=count;
}
}
}
if(maxcount>=3)
{
printf("%d\n",maxcount);
}
else
{
printf("0\n");
}
return 0;
}
Tuesday, July 17, 2012
Simple Minded Hashing
All of you know a bit or two about hashing. It involves mapping an element into a numerical value using some mathematical function. In this problem we will consider a very ‘simple minded hashing’. It involves assigning numerical value to the alphabets and summing these values of the characters.
For example, the string “acm” is mapped to 1 + 3 + 13 = 17. Unfortunately, this method does not give one-to-one mapping. The string “adl” also maps to 17 (1 + 4 + 12). This is called collision.
In this problem you will have to find the number of strings of length L, which maps to an integer S, using the above hash function. You have to consider strings that have only lowercase letters in strictly ascending order.
Suppose L = 3 and S = 10, there are 4 such strings.
agb also produces 10 but the letters are not strictly in ascending order.
bh also produces 10 but it has 2 letters.
Input
There will be several cases. Each case consists of 2 integers L and S. (0 < L, S < 10000). Input is terminated with 2 zeros.
Output
For each case, output Case #: where # is replaced by case number. Then output the result. Follow the sample for exact format. The result will fit in 32 bit signed integers.
For example, the string “acm” is mapped to 1 + 3 + 13 = 17. Unfortunately, this method does not give one-to-one mapping. The string “adl” also maps to 17 (1 + 4 + 12). This is called collision.
In this problem you will have to find the number of strings of length L, which maps to an integer S, using the above hash function. You have to consider strings that have only lowercase letters in strictly ascending order.
Suppose L = 3 and S = 10, there are 4 such strings.
- abg
- acf
- ade
- bce
agb also produces 10 but the letters are not strictly in ascending order.
bh also produces 10 but it has 2 letters.
Input
There will be several cases. Each case consists of 2 integers L and S. (0 < L, S < 10000). Input is terminated with 2 zeros.
Output
For each case, output Case #: where # is replaced by case number. Then output the result. Follow the sample for exact format. The result will fit in 32 bit signed integers.
Sample Input | Output for Sample Input |
3 10 2 3 0 0 | Case 1: 4 Case 2: 1 |
#include<stdio.h>
int main()
{
int fun(int,int,int,int,int,int,int[]);
int t,inp,num,A[10000]={0};
scanf("%d %d",&inp,&num);
if(inp==0 && num==0)
{
return 0;
}
else
{
printf("Count= %d\n",fun(1,inp,0,0,num,0,A));
}
return 0;
}
int fun(int level,int inp,int sum,int curr,int num,int count,int A[10000])
{
if(level==inp)
{
if(num-sum<=26 && num-sum>curr)
{
for(int i=0;i<level-1;i++)
{
printf("%d ",A[i]);
}
printf("%d\n",num-sum);
count+=1;
return count;
}
else
{
return count;
}
}
else
{
for(int i=curr+1;i<=(num/(inp-1));i++)
{
sum+=i;
A[level-1]=i;
count=fun(level+1,inp,sum,i,num,count,A);
sum-=i;
}
return count;
}
}
Saturday, July 7, 2012
Determinant Calculator
C-program to calculate the determinant of a square matrix of any dimensions up to [100x100]
#include<stdio.h>
int main()
{
int determinant(int A[][100],int n,int i,int s);
int A[100][100],i,n,B[100];
printf("Enter the number of rows or columns: \n");
scanf("%d",&n);
printf("Enter the square matrix: \n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&A[i][j]);
}
}
printf("The determinant is: \n");
int s=0;
s=determinant(A,n,i,s);
printf("%d\n",s);
fflush(stdin);
getchar();
return 0;
}
int determinant(int A[][100],int n,int i,int s)
{
int B[100][100];
int a=s;
if(n==2)
{
return A[0][0]*A[1][1] - A[0][1]*A[1][0];
}
else
{
//int s=0;
for(int j=0;j<n;j++)
{
int x=0;
for(int p=1;p<n;p++)
{
int y=0;
for(int q=0;q<n;q++)
{
if(q!=j)
{
B[x][y]=A[p][q];
y++;
}
}
x++;
}
if(j%2==0)
{
s+=A[0][j]*determinant(B,n-1,j,a);
}
else
{
s-=A[0][j]*determinant(B,n-1,j,a);
}
}
return s;
}
}
Output:
Enter the number of rows or columns: 4
Enter the square matrix:
1 13 4 6
23 21 18 5
4 2 7 9
1 10 15 12
The determinant is:
20353
Subscribe to:
Posts (Atom)