Intel Interview Question
Software Engineer / DevelopersCountry: United States
#include<iostream>
void main()
{
std::string s1="abcdef";
int pos=3;
s1.append(s1.substr(0, pos));
s1=s1.substr(pos, s1.length());
std::cout<< s1.c_str();
}
Sorry i forgot to increment variable 'i' in the loop.
The correct code is:
char * shiftString(char* str, int shiftBy)
{
char *buff = malloc((sizeof(char) * shiftBy) + 1);
int i = 0;
strncpy(buff,str,shiftBy);
buff[shiftBy] = '\0';
while(str[i + shiftBy] != '\0')
str[i++] = str[i + shiftBy];
strcat(str,buf);
return str;
}
Hey Ashutosh....your program has a small hitch....when you do the str[i++]=str[i+shiftBy] and concatenate, the array str has two instances of the same string upto the shiftBy index.
For ex:
if input is abcdef and shifBy is 3
then at the end of the while loop str has defdef and then when you concatenate, it returns abcdefdef....
I would recommend the following correction
char * shiftString(char* str, int shiftBy)
{
char *buff = malloc((sizeof(char) * shiftBy) + 1);
int i = 0;
strncpy(buff,str,shiftBy);
buff[shiftBy] = '\0';
while(str[i+shiftBy]!='\0')
{
str[i]=str[i+shiftBy];
str[i+shiftBy]='\0';
i++;
}
strcat(str,buf);
return str;
}
Apart from this your program works fine...thanks...
# include <iostream.h>
# include <conio.h>
# include <string.h>
# include <malloc.h>
int main()
{
char str[10],str2[10];
int pos;
char *s,*t;
t=str2;
cin>>str;
cin>>pos;
s=str;
if(pos>strlen(str))
cout<<"pos reater than length of string";
else
{
while(pos!=0)
{
*t=*s;
s++;
t++;
pos--;
}
*t='\0';
cout<<strcat(s,str2);
}
getch();
}
void shift(char str[], int i) {
if (i <= 0) return; // no op
int len = strlen(str);
if (i >= len) return; // no op
char* tmp = new char[i];
strncpy(tmp, str, i);
str[0] = 'c';
for (int j = i; j < len; ++j) str[j - i] = str[j];
strncpy(str + len - i, tmp, i);
delete[] tmp;
cout << str << endl;
}
How about this? I think this will be done in time O(n)
ShiftArray(char *arr, int index) {
for(int i = index; arr[i] != '\0'; i++) {
Swap(arr[i-index],arr[i]);
}
}
int mod(int a,int b)
{
if(a<0)
{
a=-a;
return b-(a%b);
}
else
return a%b;
}
string shiftBACK(string text,int index)
{
int i,sz=text.size();
string retv(text.begin(),text.end() );
for(i=0;i<text.size();i++)
retv[mod( (i-index),sz )]=text[i] ;
return retv;
}
string shiftFRONT(string text,int index)
{
int i,sz=text.size();
string retv(sz,'0');
for(i=0;i<text.size();i++)
retv[(i+index)%sz ]=text[i];
return retv;
}
char *stringFlip(char *str, int ind){
int i = 0;
if (strlen(str) < ind -1 )
return str;
char *revstr = (char *)malloc(sizeof(char)*(strlen(str)+1));
while ( *(str+i+ind) != '\0' ){
*(revstr+i) = *(str+i+ind);
i++;
}
int j = 0;
while ( j < ind){
*(revstr+i+j) = *(str+j);
j++;
}
*(revstr+i+j) = '\0';
return revstr;
}
I have not seen the code written by others, but I am assuming that most of the solutions are O(n). You can actually do it O(log n) time by using splay trees.
Encode the string which is a dynamic sequence as a splay tree. Building this splay tree will take O(n) time. But you can answer any query of the form shift(k) in O(log n) time once you build this splay tree. Splay trees are very special in the sense that they can o splits and joins. In fact, for the above problem we require only 1 split at position n-k and 1 join at position 1. Both splits and joins take only O(log n) amortized time. So if you do a sequence of k operations, it will run in only O(k log n) in the worst case.
For further details on splay trees, please refer wikipedia or "Introduction to Algorithms" by Cormen et al.
#include<stdio.h>
int main ()
{
char str[10] = "ankit";
int t;
char* buf;
int i=0;
printf("enter the string \n");
scanf("%s",str);
printf("enter num \n");
scanf("%d",&t);
buf = (char*)malloc(sizeof(char)*t);
strncpy(buf,str,t);
buf[t]='\0';
while(str[i+t]!='\0')
{
str[i]=str[i+t];
i++;
}
str[i]='\0';
strcat(str,buf);
printf("%s",str);
getch();
}
#include<iostream>
using namespace std;
string shiftString(string str,int n)
{
char s[str.length()];
int l=str.length();
int i=0;
s[l]='\0';
for(i=n;i<l;i++){
s[i-n]=str[i];
}
for(int j=0;j<n;j++){
s[i-n]=str[j];
i++;
}
return s;
}
int main()
{
string str="abcdef";
cout<<shiftString(str,3);
return 0;
}
1.start from index 0
- fullthrottle July 20, 20092.swap the character @ index 0 with its neighbour(1).
3.continue this till the first character reaches the end of the string.
repeat the above steps for N (N is the number of characters tht needed to be moved)
example:
if bcde is the string with N=2; desired output is debc
steps are as follows,
N=1
bcde
cbde
cdbe
cdeb
N=2
cdeb
dceb
decb
debc