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

- Jim August 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 04, 2014 | Flag
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;
}

- Cerberuz August 31, 2014 | Flag Reply
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

- Rahul Sharma August 30, 2014 | Flag Reply
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

- Rahul Sharma August 30, 2014 | Flag Reply
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();
}

- Teh Kok How August 31, 2014 | Flag Reply
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;
}

- nj123 September 28, 2014 | Flag Reply
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;
}

- nj123 September 28, 2014 | Flag Reply
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)

- harshit.knit October 29, 2014 | Flag Reply
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]);
}
}

- Anonymous December 01, 2014 | Flag Reply
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() {
	// your code goes here
	string s="ab2c5";
	int k=3;
	char r=res(s,k);
	cout<<r<<endl;
	return 0;
}

- Psyacoder June 23, 2015 | Flag Reply
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;
	}
}

- Shubhendu Kumar September 08, 2015 | Flag Reply
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;
	}
}

- shubhendukumar4332 September 08, 2015 | Flag Reply
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;
	}
	
	
	
}

- shukad333 August 29, 2014 | Flag Reply
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)

- Ankit Rathore September 27, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More