Citrix System Inc Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
this should be done with O(n+m) time and O(26) space, which is a const, therefore O(1) space
int a[26]={0};
// first scan "llld" and change a['l'-'a']=3;
//a['d'-'a']=1;
// then scan target string accoring to a[26] with a increment counter.
// return counter
I assume that repeated characters in the source string counts only one time
You can count references on both sides and then multiple each character in the source string by the number of references in the target string. The code would be something like this (a mix of Python and C++ code):
len(targetString) = n
len(sourceString) = m
references = array[256] with 0 in each position -> O(256) ~ O(1)
for char in targetString: -> O(n)
references[char]++ -> O(1)
result = 0
for char in sourceString: -> O(m)
result += references[char]
references[char] = 0 // to avoid duplicate
return result
The result is O(n + m)
Solution for this problem using recursion:-
int getCharCount(String source, String target)
{
if(source.length() == 0)
return 0;
boolean flag = false;
int i;
for(i = 0; i < target.length(); i++)
{
if(target.charAt(i) == source.charAt(0))
{
flag = true;
break;
}
}
if(flag)
return 1 + getCharCount(source.substring(1), target.substring(0, i) +
target.substring(i + 1));
else
return getCharCount(source.substring(1), target);
}
A Java sample code
public static int getCharCount(String target, String source)
{
int count = 0;
Set<Character> visitedChars = new HashSet<Character>();
for(char c:source.toCharArray())
{
if(!visitedChars.contains(c))
{
String trimmedString= target.replaceAll(""+c, "");
count+= target.length() - trimmedString.length();
visitedChars.add(c);
}
}
return count;
}
not optimal but why not use a set to maintain distinct source chars and count each element of set appear in target string?
public static int getcount(String src, String tar){
if (src.length()==0 ||tar.length()==0)
return 0;
char[] src_array = src.toCharArray();
char[] tar_array = tar.toCharArray();
int count=0;
Set<Character> src_set = new HashSet<Character>();
for (char ele: src_array)
src_set.add(ele);
for (char ele: tar_array){
if (src_set.contains(ele)){
count++;
}
}
return count;
}
#include <stdio.h>
#include <string.h>
int no_of_char_occurences_found(char* str1, char* str2)
{
int occurence_found = 0;
static int total = 0;
int i=0;
for (i=0;i<=strlen(str1);i++)
{
int j=strlen(str2)-1;
for(j=strlen(str2)-1;j>=0;j--)
{
if((str2[j] == str1[i]))
{
occurence_found = 1;
total++;
break;
}
}
}
return total;
}
int main()
{
char str1[] = "Hello World";
char str2[] = "llld";
int res = no_of_char_occurences_found(str1, str2);
printf("No. of Occurences Found: %d\n",res);
return 0;
}
#include <stdio.h>
#include <string.h>
int no_of_char_occurences_found(char* str1, char* str2)
{
int occurence_found = 0;
static int total = 0;
int i=0;
for (i=0;i<=strlen(str1);i++)
{
int j=strlen(str2)-1;
for(j=strlen(str2)-1;j>=0;j--)
{
if((str2[j] == str1[i]))
{
occurence_found = 1;
total++;
break;
}
}
}
return total;
}
int main()
{
char str1[] = "Hello World";
char str2[] = "llld";
int res = no_of_char_occurences_found(str1, str2);
printf("No. of Occurences Found: %d\n",res);
return 0;
}
#include<stdio.h>
#include<string.h>
int countr(char *t, char *s) {
int count = 0,length,i;
length = strlen(t) - 1;
while(*s != '\0') {
for(i = 0; i<=length;i++) {
if(t[i] == *s) {
count++;
break;
}
}
s++;
}
return count;
}
int main()
{
int count;
char s[] ="hello world";
char t[] ="llld";
count = countr(t,s);
printf("%d\n", count);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
if (argc != 3) {
printf("Usage: %s <string to look in> <chars to look for>\n", argv[0]);
exit(1);
}
int sourceVals[128] = {0};
int occurences = 0;
int i = 0;
for (i = 0; i < strlen(argv[1]); i++) {
sourceVals[argv[1][i]]++;
}
for (i = 0; i < strlen(argv[2]); i++) {
if (sourceVals[argv[2][i]] >=0 ) {
occurences += sourceVals[argv[2][i]];
sourceVals[argv[2][i]] = -1;
}
}
printf("Occurences: %d\n", occurences);
return 0;
}
int main()
{
char str1[] = "Hellooo World";
char str2[] = "lldo";
int i,j, match[10]={0};
for(i=0; i < strlen(str2);i++)
{
for(j=0; j < strlen(str1);j++)
{
if(str2[i]==str1[j])
match[i]++;
}
}
printf("\n Match array is");
for(i=0; i < strlen(str2);i++)
{
printf("\n %c occurred %d times",str2[i],match[i]);
}
return 0;
}
public static int getTotalNumberOfOccurences(String target, String source)
{
int[] targetCharacterCount = new int[256];
for(int i=0;i<target.length();i++)
{
targetCharacterCount[target.charAt(i)]++;
}
int totalCount = 0;
boolean[] sourceCharacter = new boolean[256];
for(int i=0;i<source.length();i++)
{
if(!sourceCharacter[source.charAt(i)])
{
totalCount = totalCount+targetCharacterCount[source.charAt(i)];
sourceCharacter[source.charAt(i)] = true;
}
}
return totalCount;
}
static int getNumFoundSrc(String src, String dest) {
int total = 0;
int srcCharArry[][] = new int[2][127];
// calculate the occurance of each characters in source
char[] srcCharArray = src.toCharArray();
char[] destCharArray = dest.toCharArray();
for (int sCount = 0; sCount < srcCharArray.length; sCount++) {
srcCharArry[0][(int) srcCharArray[sCount]] = srcCharArry[0][(int) srcCharArray[sCount]] + 1;
}
for (int dCount = 0; dCount < destCharArray.length; dCount++) {
if (srcCharArry[1][(int) destCharArray[dCount]] != 1) {
total = total + srcCharArry[0][(int) destCharArray[dCount]];
srcCharArry[1][(int) destCharArray[dCount]] = 1;
}
}
return total;
}
I don't see any restriction on the usage of specific approach.. so here is the best approach.
Have a hash table of size 26 or 52 assuming i will contain only alphabet..
hash['H']=1;
hash['a']=1;
hash['l']=1;..
this will be done in o(n)
then do in o(m) for destination and increment the number when the hash contains the value only..
- ethioer November 15, 2013