## Directi Interview Question for SDE1s

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

Seems like maths, does it not?

ab2c3 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

Comment hidden because of low score. Click to expand.
0

Jim, would be nice if you could put some psuedocode/code. The first explanation and the second one is a bit confusing.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

have a look and please report if u find anything incorrect :
yougeeks.blogspot.in/2014/08/directi-interview-question-given.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

have a look :
yougeeks.blogspot.in/2014/08/directi-interview-question-given.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````# 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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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]);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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() {
string s="ab2c5";
int k=3;
char r=res(s,k);
cout<<r<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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;
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

A simple approach to the problem python3

``````s=input()
i=0
x=s
while(i<len(x)):
if x[i]<='9' and x[i]>='0':
y=x[:i]*int(x[i])
x=y+x[i+1:]
i+=1

print(x)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.