Directi Interview Question SDE1s
Country: India
Interview Type: Phone Interview
This can be done using a top-down recursive approach.
Just iterate over the string.
Keep track of the length of expanded string.
If expanded string's length >= k then reduce the problem into a subproblem X with smaller k.
Solve subproblem X.
e.g.
s = ab2c3
k = 10
a -> total_len = 1
ab -> total_len = 2
ab2 -> total_len = 4
ab2c -> total_len = 5
ab2c3 -> total_len = 15
=> total_len > k, kth character will be in string "ababcababcababc"
=> "ababc" is repeating, so we can reduce the problem to s = "ababc" and k = k % 5 where 5
is length of s = "ababc".
If modulus operation returns 0 e.g. in this case 10 % 5 == 0, then we have to pass length of s i.e. 5 to subproblem. This is due to 0 based index of string.
Note:
In code we have to take care of using long long for total_len.
We don't need to create new substring in recursive call.
In each subproblem, k will reduce along with total_len according to modulo operation. So problem will get solved in few recursive calls.
char findKthChar( string &s, int k )
{
int sl = s.length();
int i = 0;
long long total_len = 0;
while (i < sl) {
if (isalpha(s[i])) {
// got alphabet
total_len++;
if (total_len == k) {
return s[i];
}
i++;
} else {
// got number (parse complete number)
int n = 0;
while (i < sl && !isalpha(s[i])) {
n = n*10 + (s[i]-'0');
i++;
}
long long next_total_len = total_len*n;
if (k <= next_total_len) {
int pos = k % total_len;
if (!pos) {
pos = total_len;
}
return findKthChar(s, pos);
} else {
total_len = next_total_len;
}
}
}
// invalid k
return -1;
}
string uncompress(string const& str)
{
ostringstream oss;
for (size_t i = 0; i < str.size(); ) {
if (isalpha(str[i]))
oss << str[i++];
else if (isdigit(str[i])) {
char *end(nullptr);
errno = 0;
unsigned long repeat = strtoul(&str[i], &end, 10);
if (!errno && repeat > 0 && repeat < ULONG_MAX) {
if (*end)
while (str[i] != end[0])
i++;
else
i++;
ostringstream oss1;
for (size_t k = 0; k < repeat; k++)
oss1 << oss.str();
oss.str("");
oss << oss1.str();
} else
i++;
}
}
return oss.str();
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int is_num(char c)
{
if(c>='0' && c<='9')
return (c-'0');
return -1;
}
int get_int(char arr[],int i,int j)
{
int x,y=0;
char ii[10];
if(i==j)
return (arr[i]-'0');
else
{
for(x=i;x<=j;x++){
ii[y]=arr[x];
y++;}
}
int n=atoi(ii);
return n;
}
char get_kth(char arr[],char res[],int k)
{
int i=0,j,b=0;
int cl=0,pl;
while(i<strlen(arr))
{
// k=0;
pl=cl;
if(is_num(arr[i])==-1)
{
res[b++]=arr[i];
++i;
++cl;
}
else
{
int x,y;
j=i;
while(is_num(arr[j+1])!=-1)
{
j++;
}
int n=get_int(arr,i,j);
cl=cl*n;
for(x=0;x<n-1;x++)
{
for(y=0;y<pl;y++)
{
res[b++]=res[y];
}
}
i=j+1;
}
}
return res[k-1];
}
int main()
{
char arr[1536];
long long int k;
char res[1536];
while(scanf("%s %d",arr,&k)>0)
printf("%c",get_kth(arr,res,k));
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int is_num(char c)
{
if(c>='0' && c<='9')
return (c-'0');
return -1;
}
int get_int(char arr[],int i,int j)
{
int x,y=0;
char ii[10];
if(i==j)
return (arr[i]-'0');
else
{
for(x=i;x<=j;x++){
ii[y]=arr[x];
y++;}
}
int n=atoi(ii);
return n;
}
char get_kth(char arr[],char res[],int k)
{
int i=0,j,b=0;
int cl=0,pl;
while(i<strlen(arr))
{
// k=0;
pl=cl;
if(is_num(arr[i])==-1)
{
res[b++]=arr[i];
++i;
++cl;
}
else
{
int x,y;
j=i;
while(is_num(arr[j+1])!=-1)
{
j++;
}
int n=get_int(arr,i,j);
cl=cl*n;
for(x=0;x<n-1;x++)
{
for(y=0;y<pl;y++)
{
res[b++]=res[y];
}
}
i=j+1;
}
}
return res[k-1];
}
int main()
{
char arr[1536];
long long int k;
char res[1536];
while(scanf("%s %d",arr,&k)>0)
printf("%c",get_kth(arr,res,k));
return 0;
}
# your code goes here
u=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;
def printKth(s,k):
l=0
n=''
i=0
while i<len(s):
if isalpha(s[i]):
l+=1;
if(l==k):
return s[i];
i+=1;
continue;
while i<len(s) and not isalpha(s[i]):
n+=s[i];
i+=1;
nl=int(n)*l;
n=''
if(k<=nl):
k=nl%k;
if k==0:
k=l;
return printKth(s,k)
else:
l=nl
print printKth(u,k)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
char s1[] = "ab9c9de5";
int check = 20;
int a = strlen(s1);
int arr[50];
int i;
arr[0] =1;
for(i=1;i<a;i++)
{
int b = s1[i];
b= b-48;
//printf("b= %d ",b);
if(b>10)
{
arr[i] = arr[i-1]+1;
}
else
{
arr[i]= b*arr[i-1];
}
}
for(i=1;i<a;i++) printf("%d ",arr[i]);
i = 0;
while(check)
{
//printf("i=%d check = %d ",i,check);
if(check==arr[i]) check=0;
if(check>arr[i]&& check<arr[i+1])
{
check = check%arr[i];
}
else
{
if(check>arr[i] &&check!=0) i++;
if(check<arr[i] && check!=0)i--;
}
printf("\n check = %d I= %d",check,i);
}
printf("\n i= %d\n",i);
int flag=0;
while(flag==0)
{
if(s1[i]<65) i--;
else
{printf("output: %c",s1[i]);
flag=1;
}
//printf("%output: %c",s1[i]);
}
}
#include <iostream>
#include<vector>
using namespace std;
int getnum(char A){
return (A-'0');
}
char res(string s,int k){
int i=0;
int j=0;
vector<char>string;
vector<char>ans;
while(i<s.size()){
if(!isdigit(s[i])){
string.push_back(s[i]);
// cout<<string[j]<<endl;
//cout<<string[j+1]<<endl;
//cout<<"\n";
}
else{
int n=getnum(s[i]);
// cout<<n<<endl;
while(n!=0){
ans.insert(ans.end(), string.begin(), string.end());
n--;
}
string.clear();
}
i++;
}
return ans[k-1];
}
int main() {
// your code goes here
string s="ab2c5";
int k=3;
char r=res(s,k);
cout<<r<<endl;
return 0;
}
import java.util.*;
class Compress
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
String str = sc.next(),newStr="";
int k = sc.nextInt();
int i,j,asc;
char c;
for(i=0;i<str.length();i++)
{
c = str.charAt(i);
asc = (int)(c);
//System.out.println(asc);
if(asc >= 48 && asc <=57)
{
asc = asc - 48;
newStr = expand(newStr,asc);
}
else
{
newStr += str.charAt(i);
//System.out.println(newStr);
}
}
System.out.println(newStr.charAt(k-1));
}
public static String expand(String str,int asc)
{
int i;
String newS = "";
for(i=0;i<asc;i++)
newS += str;
return newS;
}
}
import java.util.*;
class Compress
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
String str = sc.next(),newStr="";
int k = sc.nextInt();
int i,j,asc;
char c;
for(i=0;i<str.length();i++)
{
c = str.charAt(i);
asc = (int)(c);
//System.out.println(asc);
if(asc >= 48 && asc <=57)
{
asc = asc - 48;
newStr = expand(newStr,asc);
}
else
{
newStr += str.charAt(i);
//System.out.println(newStr);
}
}
System.out.println(newStr.charAt(k-1));
}
public static String expand(String str,int asc)
{
int i;
String newS = "";
for(i=0;i<asc;i++)
newS += str;
return newS;
}
}
// findCharAt("ab2c3", 10)
public char findCharAt(final String compressedString, final int k) {
final char[] chars = compressedString.toCharArray();
StringBuilder sb = new StringBuilder();
for (final char currentChar : chars) {
if (Character.isDigit(currentChar)) {
sb = decompress(sb, Character.getNumericValue(currentChar));
}
else {
sb.append(currentChar);
}
if (sb.length() >= k) {
return sb.charAt(k - 1);
}
}
return '\0';
}
private StringBuilder decompress(final StringBuilder sb, final int count) {
final StringBuilder temp = new StringBuilder();
for (int i = 0; i < count; i++) {
temp.append(sb);
}
return temp;
}
package string;
public class Compress {
public static void main(String[] args) {
System.out.println(compress("sh1u2shabc3"));
}
static String compress(String inp) {
String op = "";
int pos = 0;
boolean first = true;
for(int i=0;i<inp.length();i++) {
if((int)inp.charAt(i)>=48 && (int)inp.charAt(i)<=57) {
int a = (int)inp.charAt(i);
String st = op + inp.substring(pos,i);
String str="";
for(int j=0;j<a-48;j++) {
str += st;
}
pos = i+1;
op = str;
}
}
return op;
}
}
Seems like maths, does it not?
- Jim August 28, 2014ab2c3 10
((2*2)+1)*3 > 10
So it is somewhere in the (2*2)+1 chunk. 10%5 = 0 (or 5) = 5
Ignoring the info in the 4 chunk, we take the 5th. So the answer is c.
A more complex example:
ab10c9de5 53
((2*10) + 1) *9 > 53
Consider [(2*10) + 1] chunk. It will be the 53 % 21 = 11th
(2*10) > 11
Conside the [2] chunk. It will be the 11%2 = 1st character
= a