Directi Interview Question
InternsCountry: United States
Interview Type: Phone Interview
a3b2c2 = (aaab)2c2 = (aabaabc)2 = aabaabcaabaabc looks not correct.
if a3b2c2 = (aaab)2c2 = (aaabaaabc)2 = aaabaaabcaaabaaabc then
char find(String s, int k){
int len=0;
int i;
String result = "";
for(i=1; i<s.length(); i++){
String l = getInt(i,s);
len = Integer.parseInt(l);
String seg = result + s.charAt(i-1);
result = "";
for(int j=0; j<len; j++)result += seg;
if(k < len) break;
i += l.length();
}
return result.charAt(k-1);
}
String getInt(int start, String s){
String i="";
while(start<s.length() && s.charAt(start)>='0'&&s.charAt(start)<='9'){
i += s.charAt(start);
start++;
}
return i;
}
I dont think there is a need to expand the string in the first place. Given string is a3b2c2. Suppose k is 5. We can subtract the numbers one after other from k, and when k becomes <=0, the character to the left is the letter.
So k=5. 5-3 (First number in the string) = 2;
2-2 (next number in the string) 0. Therefore, the character is 'b'. If k is still positive and we reach the end of the string, we return Null.
it works for a input like a300b200c123
#include<stdio.h>
int main()
{
char *s,ch;
int k,i;
printf("please enter a string");
gets(s);
printf("Enter k");
scanf("%d",&k);
while(k>0)
{
if((int)*s>=48 && (int)*s<=57)
{
while((int)(*s)<58)
{
i=i*10+ (int)*s-48;
s++;
}
k=k-i;
}
else
ch=*s;
s++;
}
printf("%c",ch);
return 0;
}
Simple O(n) solution with traversal of string.
Keep track of number of characters found so far, if it exceeds or equals k then print the corresponding previously saved character.
- Cerberuz September 20, 2012