Microsoft Interview Question for Software Engineer in Tests


Country: India
Interview Type: In-Person




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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct node_t {
   int c;
   struct node_t *next;
};

struct node_t *create_node(char c) {
    struct node_t* node = (struct node_t*) malloc(sizeof(struct node_t));
    node->c = c;
    node->next = NULL;
    return node;
}

void print(struct node_t *head) {
   struct node_t *p = head;
   while (p != NULL) {
     printf("%c", p->c);
     p = p->next;
   }
   printf("\n");
}

int main() {
   int x;
   struct node_t *head = NULL;   
   struct node_t *node;
   while ( (x = getchar()) != 10 ) {
     node = create_node(x);
     node->next = head;
     head = node;
   }
   print(head);   
 
   return 0;

}

- Eddie March 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- showell30@yahoo.com March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Expressions March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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. ;-)

- edward.ribeiro March 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Still it does not print characters in reverse order, dude !

- Anonymous July 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<stdio.h>
int main(){
char c;
scanf("%c",&c);
if(c!=10)
main();
printf("%c",c);
}

- Ms March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep on pushing all characters to a stack When user presses Enter key, just start popping the characters out of stack and display.

- Deepak March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

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>

- Expressions March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

So you mean your interviewer basically wanted you to implemented a vector ?

- Emotions March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- anon March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- showell30@yahoo.com March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- showell30@yahoo.com March 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int _tmain(int argc, _TCHAR* argv[])
{
std::string str;
std::getline(std::cin, str);

const unsigned int length = str.length();

for (unsigned int i = length; i > 0; --i)
{
std::cout << str[i - 1];
}

return 0;
}

- Anonymous March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sri March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If length of input > 100 characters.

- Expressions March 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use recursion.while taking the input call the funtion recursively and once input is done print the value.recursion can be easily used to solve the problem. :)

- go4gold March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
int main(){
char c;
scanf("%c",&c);
if(c!=10)
main();
printf("%c",c);
}

- Ms March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can't we use a stack? push every char to the stack, and pop them out upon enter.

- iloveseahawks March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- DarkPassenger March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Now this is a brilliant solution.Interview does not let u use a stack..you use the function call stack.Kudos.

- dummy coder September 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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.

- alex March 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the input is >100 characters.

- Expressions March 19, 2013 | Flag


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