Microsoft Interview Question for Software Engineer / Developers


Team: STB
Country: India
Interview Type: In-Person




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

{{
node *reverse(node *root, node *newHead)
{
if(node->next == NULL) return newHead;

node *cur = reverse(root->next, newHead);
cur->next = root;
return root;
}}
newHead is reversed list.

- trekster July 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice algo bro..
nd efficient and logical too

- shreyans August 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Everything seems fine but there is no end condition to make the old head point to null when the LL is reversed. meaning 1->2->3->NULL
what this algo does it 3->2->1 ... (Missing ->NULL)

- Navam September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

mynode* fun(mynode* root)
{
  if(root->next!=NULL)
  {
     fun(root->next);
    root->next->next=root;
    return root;
  }
 else
  head=node;
}

mynode is a struct type.

- Abhishek July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is very ambiguous. What is head and what is node?

- Spock July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems like head is global variable and node should be root??

- Vannu July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can find solution to this problem in this amazing video lecture
reverse a link list using recursion
youtube.com/watch?v=CXjQUdAwRSg

reverse linked list using iteration
youtube.com/watch?v=FRab13yyYms

- Anonymous July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

void toreverse1 (node *head ,node *head2 )
{

if(head2->next!=NULL)
toreverse1(head2,head2->next);

head2->next=head;
head->next=NULL;
}
node * toreverse (node *head )
{
node * q=head;
if(head==NULL)
return head;
while(q->next!=NULL)
{
q=q->next;
}
if(q==head)
return head;
toreverse1(head,head->next);
return q;

}

- ashish July 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well there are actually n number of ways to reverse a linked list. One way is to simply a make an empty linked list and while traveling through the nodes of the current linked list use a push function (which is used for pushing elements in stack) to push the elements in the result linked list. Here is the code.

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

struct node {
       int data;
       struct node *next;
};

void push(struct node **headref, int num) {
     struct node * newnode = malloc(sizeof(struct node));
     newnode->data = num;
     newnode->next = *headref;
     *headref = newnode;
}

void reverse(struct node **headref) {
     struct node *current = *headref;
     struct node *result = NULL;
     while(current != NULL) {
                   push(&result, current->data);
                   current = current->next;
     }
     *headref = result;
}

int main() {
    struct node *head = NULL;
    push(&head,1);
    struct node *tail;
    tail = head;
    int i;
    for(i = 2; i <= 5; i++) {              //Here we are making a linked list {1,2,3,4,5} with head pointing to 1.
          push(&(tail->next),i);
          tail = tail->next;
    }
    reverse(&head);
    while(head != NULL) {                 //After calling reverse the output will be printed as {5,4,3,2,1}.
               printf("%d ", head->data);
               head = head->next;
    }
system("pause");
return 0;
}

- Spock July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another approach is to use recursion. Well to use recursion to solve this problem is a bit tricky.
Here is the code.

void reverse(struct node **headref) {
struct node *first = *headref;
struct node *rest;
if(first == NULL) {
return;
}
rest = first->next;
if(rest == NULL) {
return;
}
reverse(&rest);
first->next->next = first;
first->next = NULL;
*headref = rest;
}

- Spock July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how to code this problem in c#?

- hello July 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static LinkedList<string> ReverseLinkedList1(LinkedList<string> list)
{
LinkedList<string> newList = new LinkedList<string>();
LinkedListNode<string> first = list.First;
while(first!=null)
{
newList.AddFirst(first.Value);
first = first.Next;
}
return newList;
}

- Anonymous July 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if (m_head == null || m_head.Next == null)
                return;
            
            
            SingleLinkedListNode p1, p2, p3;

            p1 = m_head;
            p2 = m_head.Next;
            p3 = m_head.Next.Next;

            m_head.Next = null;

            while (p3 != null)
            {
                p2.Next = p1;

                p1 = p2;
                p2 = p3;
                p3 = p3.Next;
            }

            p2.Next = p1;
            m_head = p2;

- Anonymous July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if (m_head == null || m_head.Next == null)
return;

SingleLinkedListNode p1, p2, p3;

p1 = m_head;
p2 = m_head.Next;
p3 = m_head.Next.Next;

m_head.Next = null;

while (p3 != null)
{
p2.Next = p1;

p1 = p2;
p2 = p3;
p3 = p3.Next;
}

p2.Next = p1;
m_head = p2;

- Anonymous July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

recursive way

NodeType* reverse(NodeType* head)
{
    if(root == NULL || head->next == NULL) return root;
    NodeType* newHead = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

- wangxuyang September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reverse(){
		if(head == null){
			return;
		}
		Node ptr = head;
		Node prev = null;
		while(ptr != null){
			Node tmp = ptr.next;
			ptr.next = prev;
			prev = ptr;
			ptr = tmp;
		}
		head = prev;
	}

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

Language: C++
Implementation:Iterative
Linked List Node: <int value, Node * next>

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

#include <cstdlib>


struct Node { 

	Node * next; 
	int value;
}; 


void test (Node * root);
void reverse(Node * root);
int main (int argc, char ** argv) { 
	//new linked list 
	Node * root = new Node;
	root->next = NULL;
	Node * current = new Node;
	Node * node; 

	//step 1: 
	//set the root of the lis
	current->value = 0; 
	current->next = NULL;
	//set the beginning of the list
	root->next = current;

        //step 2: fill the array
	for (int i=1; i<5; i++) { 
		node = new Node;
		node->value = i; 
		node->next = NULL; 
		current->next = node; 
		current = current->next;
	}
	//display as test 
	test(root); 
	//reverse linked list
        //Step 3: Reverse the list
	reverse (root);
	test(root);
}

//Function template @ 
//geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/
void reverse (Node * root ) { 
	Node * current;  //node that we need to update 
	Node * next;      //node that 'current' points to before reverting
	Node * previous; //node that 'current' needs to point to after reverting 
	//get first element
	current = root->next;
	//make sure this first element is set up to point to NULL (by making 'previous' = NULL) since it will be the last item of the array
	previous = NULL;
	while (current !=NULL) { 
		next = current->next;
		current->next = previous;
		previous = current; 
		current = next;
	}

	//make sure the root is pointing to the last element
	//and not 'current' because at this point current = NULL
	root->next = previous;
}
void test (Node * root) { 
	Node * node;
	node = root->next;
	while (node !=NULL) { 
		printf ("%u \n", node->value);
		node = node ->next;
	}
}

- nathaliekaligirwa October 14, 2014 | 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