Directi Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Checking and decreasing count k inplace. If k == 0 output the character. If invalid position return a space or blank.!!
#include <stdio.h>
#include <ctype.h>
#define SIZE 100
/* Index starts from 0 - kth position */
char getChar (char *str, int k) {
int i, index = 0, count = 0 ;
if ( k < 0 || strlen(str)==0)
return ' ' ;
char ch = str[0];
while ( str[index] != '\0' ) {
if ( isalpha(str[index]) ) {
if ( k <= 0 )
return ch ;
k -= count ;
ch = str[index] ;
count = 0 ;
}
else {
count = count * 10 + (str[index]-'0') ;
if ( k < count )
return ch ;
}
index ++ ;
}
if ( k == 0 || k < count )
return ch ;
return ' ' ;
}
int main () {
char str[SIZE] ;
int k ;
scanf ( "%s", str ) ;
scanf ( "%d", &k ) ;
printf ( "\nChar at position : %c", getChar(str,k) ) ;
return 0 ;
}
I got brute force way to find kth character in explored String, any type of optimization is welcome....
public static char exploreString(String str,int k){
String temp="";
int num=0,flag=0;
String tmp="",numstr="";
for(int i=0;i<str.length();){
flag=0;
tmp="";
numstr="";
while(i < str.length() && !Character.isDigit(str.charAt(i))){
tmp=tmp+str.charAt(i);
i++;
flag=1;
}
while(i < str.length() && Character.isDigit(str.charAt(i))){
numstr+=(str.charAt(i));
i++;
flag=2;
}
if(flag==2){
num=Integer.parseInt(numstr);
for(int j=0;j<num;j++){
temp+=tmp;
}
}
}
return temp.charAt(k-1);
}
C++ pseudo code to illustrate the logic,O(n)runtime, O(1)memory.
string exploreString ( string A, int k ){
int decoded=0;
int length;
int index_left=0;
int index_right=get_index_of_next_integer(A,index_left);
int number=get_next_number(A,index_left);
while(number!=null){
length=index_right-index_left;
if (k<decoded+length*number) return A[index_left+((k-decoded)modnumber)];
else passed+=length*index_num;
update index_left,index_right,number to next string&number set;
}}
import re
def exploreString( str, k ):
if k < 0 :
print( "k cannot be negative" )
return "NONE"
match = re.findall( r"([a-z])([1-9]*)", str )
print( match )
iter = 0
for pattern in match:
letter = pattern[0]
rep = pattern[1]
if rep == "" :
rep = "1"
print( letter, rep )
rep = int( rep )
if k >= iter and k < iter + rep:
return letter
else:
iter = iter + rep
return "NONE"
if __name__ == "__main__":
str = "a2b2cd2"
print( exploreString( str, 4 ) )
complexity O(k)
Code written in Java:
public class Problem1 {
public static void main(String args[]) {
int kthCharIntValue = exploreString("", 1);
if (kthCharIntValue == -1) {
System.out.println(" String A can not be empty or null");
}
else if (kthCharIntValue == -2) {
System.out.println(" k can not be negative integer");
} else if (kthCharIntValue == -3) {
System.out.println(" kth position is out of bound");
} else {
System.out.println((char) kthCharIntValue);
}
}
/**
* @param A
* @param k
* @return
*/
private static int exploreString(String A, int k) {
// A can not be empty or null
if (A == null || A == "") {
return -1;
}
// k can not be negative
if (k < 0) {
return -2;
}
// convert string to char array
char[] a = A.toCharArray();
//can be initialized with any integer value;
int kthChar=-10;
for (int i = 0; k > 0; i++) {
// return -3 if it finds kth position is out of bound
if (i >= A.length()) {
return -3;
}
else if ((a[i] >= '0' && a[i] <= '9')) {
// convert char to actual int value;
int l = new Integer(a[i] + "");
k = k - l + 1;
} else {
kthChar = a[i];
k--;
}
}
return kthChar;
}
}
Kindly let me know your thoughts for this solution.
#include<stdio.h>
#include<strings.h>
char exploreString(char str[],int k)
{
int i=0;
int current=0;
int l=strlen(str) ;
for(i=0;i<l;i++)
{
if(str[i]>47 &&str[i]<55)
{
current+=str[i]-'0' ;
if(k<=current)
return str[i-1] ;
}
}
printf("k is not in string\n") ;
}
void main()
{
char str[50],ch ;
int k;
printf("enter the string\n") ;
scanf("%s",str) ;
printf("enter the number\n") ;
scanf("%d",&k) ;
ch=exploreString(str,k) ;
printf("%c",ch) ;
}
You don't necessarily need to decode the string !!
Here is a solution with O(len(encoded-string))
the idea is to keep track of the latest string and no. of times its repeated
and the value k for the remaining string.
While coding this algorithm, I found a bug in C++! :)
#include <iostream>
#include <string>
using namespace std;
char exploreString (string A, int k) {
int len = A.length();
int i = 0;
while (i < len) {
string s;
s.push_back(A[i]);
while (A[i+1] - 48 > 9 || A[i+1] - 48 < 0) {
s.push_back(A[i+1]);
i++;
}
i++;
int n = A[i] - 48;
while (A[i+1] - 48 <= 9 && A[i+1] - 48 >=0) {
n = n*10 + (A[i+1] - 48);
i++;
}
int len = s.length();
if (k - n*len <= 0) {
if (k % len == 0) return s[len - 1];
else return s[k % len - 1];
}
else { k -= n*len; i++;}
}
return 'N';
}
int main () {
string A;
int k;
cin >> A >> k;
cout << exploreString (A, k) << endl;
}
#include<iostream>
#include<cstring>
using namespace std;
void findChar(char* str,int pos)
{
int n=strlen(str);
if(n==0)
{
cout<<"string khaali aa"<<endl;
return;
}
else if(n==2)
{
if(pos<2)
{
cout<<str[0]<<endl;
return;
}
else
{
cout<<"overflow aa jaa underflow aa"<<endl;
return;
}
}
int count=0;
for(int i=0;i<n;i+=2)
{
count+=str[i+1]-48;
if(count>=pos){
cout<<str[i]<<endl;
return;
}
}
cout<<"Index waddi aa"<<endl;
}
int main()
{
char* str="a2b2c3d3e4";
findChar(str,0);
findChar(str,3);
findChar(str,2);
findChar(str,12);
findChar(str,18);
return 0;
}
A recursive solution is provided ,however can be easily converted to iterative as well.
#define SIZE 5
int exp_string(char * str,int k)
{
//a recursive implementation
if(*str == '\0') //reached end but couldn't find character
return -1;
//locate the digit
int count = 0; //no. of characters
while(*str > '9') //this is a character
{
str++;
count++;
}
//now count holds the no. of characters
char buffer[SIZE];
int index = 0;
while(*str >= '0' && *str <= '9')
{
buffer[index++] = *str;
str++;
}
//now str points to another character
buffer[index] = '\0';
int count_2 = atoi(buffer);
//now no. of characters of this window
int char_count = (count * count_2);
if(char_count < k)
return exp_string(str,k-char_count);
else //this window contains the character
{
//k is the no. of required character in this window
int ind = k % count;
if(ind == 0)
ind = count;
return *(str-index-count+ind-1);
}
}
s=(raw_input())
k=int(raw_input())
def isalpha(c):
if ('A'<=c and c<='Z') or ('a'<=c and c<='z'):
return True;
else:
return False;
out=''
c=''
n=''
i=0
while i<=len(s):
if(k<=0):
out= c
break;
if isalpha(s[i]):
if len(n)>0:
k-=int(n)
n=''
else:
k-=1
c=s[i]
else:
n+=s[i]
i+=1;
if out=='':
print "None"
else:
print out
use regular expression
def find_kth_in_encoded_str(str, k):
assert k > 0 and len(str) > 0
l = 0 #the length of decoded string
# use regular expression to
# find a match which contains a string followed by a num
for mo in re.finditer(r"(?P<s>[a-z]+)(?P<c>[0-9]+)", str, flags = re.I):
s = mo.group('s') # the string
c_str = mo.group('c') # the repeation number
if not c_str or c_str[0] == '0':
raise ValueError("repeation number <{0}> is incorrect.", c_str)
c = int(c_str)
# the total length of the decoded matched string.
t = len(s) * c
l += t
# if k falls in this range, find the kth char
if t >= k:
i = k % len(s) - 1
return s[i]
else:
k -= t
raise Exception("k is larger than the length of the decoded string {0}".format(l))
I think this C Code will work. If any issue , please post your views.
#include<stdio.h>
#include<malloc.h>
char explore_string(char *str, int dis)
{
char *p= malloc(sizeof(char));
char *temp = str;
int i=0,count=0,j=0,k=0;
char ch;
char *save = malloc(sizeof(char));
while(*temp != '\0')
{
if(isdigit(*temp))
{
count = *temp - '0';
while(--count)
{
k=0;
while(k<= j-1)
{
*(p+i) = *(save+k);
k++;
i++;
}
}
j=0;
}
else
{
*(save+j) = *temp;
j++;
*(p+i) = *temp;
i++;
}
temp++;
}
*(p+i) = '\0';
printf("Changed string is \n %s\n",p);
ch = *(p+dis);
free(p);
free(save);
return ch;
}
int main(void)
{
char *str = "a2b2cd2";
char ch;
ch = explore_string(str,6);
printf("Required character = %c\n",ch);
return 0;
}
Ankit, we have changed string of 8 characters ("aabbcdcd" )..then for 9th position , it will not print anyhting. we can just print characters from 0 to 7 range in this string . For big string you also need to change the string in main function.Please do that way.
#include<cstdio>
#include<cstring>
char explorestring(char *a, int k)
{
int count,i,j,len = strlen(a);
char curr_char;
for(i=0;i<len && k > 0;i++)
{
if(a[i]>96)
{
curr_char = a[i];
k--;
}
else if(a[i] < 58)
{
count = a[i] - 48;
for(j=i+1;a[j] < 58 && j<len;j++)
{
count = count *10;
count = count + a[j] -48;
}
k = k - count + 1 ;
i=j-1;
}
}
return curr_char;
}
int main()
{
char a[100];
scanf("%s",a);
int k;
scanf("%d",&k);
printf("%c",explorestring(a,k));
}
i hope this works. Pls give me some testcases it might not work for if u think.
Java Implementation:
- kangkanB September 17, 2012public class Directi { /** * @param args */ public static void main(String[] args) { String givenString = "a2b3c2df5"; int k = 9; System.out.println("The character: " + ExploreString(givenString, k)); } public static char ExploreString(String A, int k){ String str = ""; int i=0, j=0; while(i<A.length()){ if(Character.isDigit(A.charAt(i))){ Character c = new Character(A.charAt(i)); int l = Integer.parseInt(c.toString()); //System.out.println(l); String temp = A.substring(j, i); for(int in = 0; in<l; in++){ str = str.concat(temp); } j = i+1; i++; } else{ i++; } } //System.out.println(str); return str.charAt(k-1); } }