Microsoft Interview Question
Software Engineer in TestsCountry: India
Interview Type: In-Person
This is a nice answer from a theoretical complexity and robustness standpoint, but it's wildly inefficient. For every character you're reading, you're incurring memory overhead and runtime overhead. If you think about what malloc()'s doing under the hood, it's a pretty expensive operation.
Rather than allocating memory for a single input, use something like
struct node{
char a[100];
struct node* next;
};
This would help in removing the malloc overhead for every input.
Yeah, guys you are right. Thanks for the tips on how to improve the code. :) I wrote it some nights ago, but didn't register on the site back then. Below are some of my points:
struct node{
char a[100];
struct node* next;
};
The code above doesn't really solve the malloc() overhead, but I can use this idea and create an static array and use it to replace the whole linked list I have created.
I didn't benchmark malloc()'s performance so I don't know for sure if malloc() is *wildly* inefficient. Of course, it's slower than the contiguous space allocation of an array, but even so it's better than a solution in Java/C# and more robust than an array of static size. ;-)
Keep on pushing all characters to a stack When user presses Enter key, just start popping the characters out of stack and display.
The interviewer wont let me use a stack. The expectation was to come up with linked list of character arrays.
Even with the stack the solution should pop the last read character if the user presses <backspace>
Tell me one thing Mr Expressions.
If the standard input is coming in, how can we dynamically allocate memory as the input is coming in ?
I'm guessing the interviewer was wanting to handle an arbitrarily large sequence of characters, and you can't preallocate infinite memory, and you also don't want to incur excessive reallocs() not overly granular mallocs(). What I'd do here is allocate 100 bytes of memory at a time, and connect those chunks with a linked list, where you insert each new chunk at the front. You basically have a stack of stacks, where the outer stack is a linked list and then inner stacks are array based. To produce the string in reverse, pop the arrays off the linked list in forward order (er, forward through the linked list, which is backward in terms of insertion order), and iterate the arrays backward.
P.S. The solution I described is way over-engineered for most practical uses cases. Instead of building your own paging scheme, it's usually wise just to call realloc() in optimistic increments. Nine times out of ten, realloc() won't have to move memory around, and even when it does, it's fast and amortized over the long run. For some OS'es, the memory model is probably some kind of virtualized paging scheme, so if you followed my initial advice, you'd be building a paging system on top of a paging system, which is just dumb.
--------------------------------------written in C-----------------------------------------------
#include<stdio.h>
#include<conio.h>
int main()
{
char a[100],b[100];
printf("enter the string:");
gets(a);
strrev(a);
printf("%s",a);
}
I believe this question is about recursion:
void read() {
char c;
scanf("%c", &c);
if (c == '\n')
return;
read();
printf("%c", c);
}
int main() {
read();
}
#include<iostream>
using namespace std;
int main(){
char c[100];
int d;
cout<<"Enter the string";
for(int i=0;i<100;i++){
cin>>c[i];
d=i;
if(c[i]=='/n')
break;
}
for(int d;d>=0;d--;)
cout<<c[d];
}
I am not sure if I am getting the ques right. I have assumed that you keep on reading till an enter key is pressed and then you print the reverse string. If you want to store the reversed string and then print, maintain two pointers, one at beginning and the other at last and keep swapping. If I am wrong, please explain the ques properly.
}
- Eddie March 21, 2013