Microsoft Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

In C, this is a pseudo code. O(n) runtime, O(1) memory. This question would be much simpler if there is a dummy head in the linked list. Asking this question would definitely impress the interviewer.
Otherwise, with the restriction on extra node creation, you will need extra 50% energy and 50% increased complexity to deal with the first node.

public node* pair_r(node* head) throw (String); //function to reverse a pair.throw String if reach end of the list.
public node* main(node* root) { //main function to reverse a linked list
    if (root.next == null) return root; //do nothing if length is 1.
    root = pair_r(root); //manually reverse first pair since lack of dummy head.
    node* cur = root.next; //set current pointer to the second node.
    while (!end) { //loop till the end of linked list
        try {cur.next = pair_r(cur.next);}//reverse
        catch (String s) {break;}//end of list, odd node
        if (cur.next == null) break; //end of list, even node
    }
    return root;
}

public node* pair_r(node* head) throw (String) {
    //linked list like: 1->2->3
    if (head.next == null) throw "end of linked list";
    node* temp = head.next; //set temp to 2nd_node
    if (temp.next != null) head.next = temp.next; //set 1st_node.next=3rd_node
    else head.next = null; //set 1st_node.next=null if hit the end of linked list
    temp.next = head; //set 2nd_node.next=1st_node
    return temp; //return pointer to 2nd_node to connect previous node.
    // linked list sorted to: 2->1->3
}

- Ares.Luo.T September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

without creating new nodeļ¼Ÿ

- sophia September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah I feel like with the first node, it's unclear whether we should just be modifying the values of the nodes as opposed to manipulating pointers. Maybe an easier version would be to change the list from "a->b->c->d->e" to "a->c->b->e->d" instead.

- Sunny December 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<iostream>

using namespace std;

typedef struct node_targ{
	char data;
	struct node_targ *next;
}Node;

Node *change(Node *root)
{
	Node *temp;
	temp = root->next->next;
	root->next->next= root;
	root = root->next;
	root->next->next = temp->next;
	temp->next = root->next->next->next;
	root->next->next->next=temp;
	return root;	
	
} 
main()
{		
	Node n5 = {'e',NULL};
	Node n4 = {'d',&n5};
	Node n3 = {'c',&n4};
	Node n2 = {'b',&n3};
	Node n1 = {'a',&n2};
	
	Node *root;
	root = &n1;
	cout<<"\n------------------before--------------------\n";
	while(root){
		cout<<root->data;
		if(root->next != NULL) cout<<"->";
		root = root->next;
	}
	cout<<"\n------------------after---------------------\n";
	
	root = change(&n1);
	while(root){
		cout<<root->data;
		if(root->next != NULL) cout<<"->";
		root = root->next;
	}
	cout<<"\n";
}

- j.a.b. September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

void reversepair(node * head){
if(!head || !head->next)
     return;
node* temp;
temp = head->next;
head->next = temp->next;
temp->next = head;
reversepair(head->next);
}

- Anonymous September 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this might create dangling pointers. For instance, after swapping the first 2 nodes ("a" and "b"), the original head pointer now points at "a", but it won't be able to access the "b" in front anymore. Similarly, after the first recursive call, we have swapped "c" and "d", but now the no one is pointing at "d".

I didn't actually test the code, so sorry if my logic turns out incorrect.

- Sunny December 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is a working code which I wrote for a general value 'k' indicating every k nodes to be reversed.
eg 1->2->3->4->5->6->7->8->9->10->11 [k=3]
answer must be [3->2->1->6->5->4->9->8->7->11->10]

For this problem put k = 2;

void ReverseK(Node** headRef, int k)
{
    Node *ptr = *headRef;
    Node *next_ptr = ptr->next;
    Node *prev_ptr = NULL;
    Node *subarray_head = *headRef;
    Node *prevsubarray_tail = NULL;
    int count = k;
    bool isHeadReset = false;
    
    while (subarray_head)
    {
        while (count-- && ptr)
        {
            next_ptr = ptr->next;
            ptr->next = prev_ptr;
            prev_ptr = ptr;
            ptr = next_ptr;
        }
        
        if (!isHeadReset)
        {
            *headRef = prev_ptr;
            isHeadReset = true;            
        }
        else
        { 
            prevsubarray_tail->next = prev_ptr; 
        }
            
        prevsubarray_tail = subarray_head;
        subarray_head = ptr;
        prev_ptr = NULL;    
        count = k;
    } 
}

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

yup.. this time microsoft seems to be in an easy mood... bt they are asking some irrelevant question... like how to chek if a tree is binary.. a post is on careercup,refering this irrelevant question,people are commenting its nonsense question made by poster himself.. bt believe me it is a microsoft question..

- rockstar September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Non Recursive version with actual swapping of links(not swapping the value)

struct list* PairReverse(struct list *head)
{
struct list* curr = head;

while (curr != NULL)
{
if (curr ->link != NULL)
{
next = curr->link;
curr->link = next->link;
next->link = curr;
curr = curr->link;
}
}

if (head->link) //If there are atleast 2 elements in list than 2nd one becomes new head
return (head->link);
else
return (head); //if there is only 1 element in list.
}

- nOoB September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you have a bug.

curr->link = next->link;

- Anonymous December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Working code..

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

Link* reversePairWise(Link* lnk)
{
	if(lnk == NULL ) return lnk;
	if(lnk->next == NULL ) return lnk;

	Link* t1 = lnk->next;
	lnk->next = lnk->next->next;
	t1->next = lnk;
	Link* prev = t1->next;
	lnk = t1->next->next;
	while(lnk != NULL && lnk->next != NULL )
	{
		Link* temp1 = lnk->next;
		lnk->next = lnk->next->next;
		temp1->next = lnk;
		prev->next = temp1;
		prev = prev->next->next;
		lnk = lnk->next;
	}
	return t1;
}

- Prashant R Kumar September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is right , rest all codes are wrong ..they are using extra node ..

- Ashish Bhat September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

my c# version does not use an extra node so please be specific before you assume the "rest" are all wrong.

- yhax September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't Link technically a node? it's just not called a node, but it has the same structure as a node...

- Anon November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

y u all are creating extra node(p, q, temp etc...)???? it is mention in the question

without creating new node.

- don September 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes I think they are, I was very confused also

- Anonymous October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's because they (including me) are assuming that the method can't return anything. In that case, if the method signature is something like "void flip(Node head)", I don't think you can flip the nodes with the head pointer referencing the new head of the list. Like if head is "a", then you can flip the "a" and "b" etc, but head will still point at "a", leaving "b" inaccessible.

Then I realized we can always make the method return the new head of the list instead...

- Sunny December 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

y u all are creating extra node(p, q, temp etc...)???? it is mention in the question

without creating new node.

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

It looks like to me the value are of Binary Search Tree Traversal where b is the root node.
a->b->c->d->e (is actually the In-Order Traversal where b is the root)
and b->a->d->c->e (is the Pre-Order Traversal where b is the root)...

Try putting it in a BST where b is the root...(just look at the letters as ascii value to perform binary insertion and comparison logic...)

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

Node pairWiseReverse(Node root) {

if (root == null || root.next == null)
return root;

Node back = root;
Node front = root.next;
Node forward = root.next.next;

front.next = back;
back.next = pairWiseReverse(forward);
return front;

}

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

Node pairWiseReverse(Node root) {

	if (root == null || root.next == null)
		return root;

	Node back = root;
	Node front = root.next;
	Node forward = root.next.next;

	front.next = back;
	back.next = pairWiseReverse(forward);
	return front;

}

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

swap the value in odd nodes

private void reverseLinkedList(){
int count=0;
LinkListNode temp=head;
while (temp.link!=null){
if(count%2==0){
int x=temp.value;
temp.value=temp.link.value;
temp.link.value=x;

}
temp=temp.link;
count++;
}


}

- Anonymous September 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome solution ...

- Dibyendu March 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

great ....

- Dibyendu March 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Complexity - O(N), Space - O(1)

In this question, we need head node of the list.

Step 1: Create a Char pointer.

Step 2: Traverse the list , using head node, and char pointer point info part of the node.

Step 3: Update head=head->next; and swap the value pointed by char pointer and current node value i.e hold by head.

Step 4: Again update char pointer and point to next head node, repeat the above process

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

static ListNode SwapPairs(ListNode head)
{
if (head == null) return null;
if (head.Next == null) return head;

ListNode ret = head.Next;


while (head != null)
{
ListNode np = head.Next.Next;

head.Next.Next = head;

if (np == null || np.Next == null)
{
head.Next = np;
head = null;
}
else
{

head.Next = np.Next;
head = np;
}
}

return ret;
}

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

static ListNode SwapPairs(ListNode head)
{
if (head == null) return null;
if (head.Next == null) return head;

ListNode ret = head.Next;


while (head != null)
{
ListNode np = head.Next.Next;

head.Next.Next = head;

if (np == null || np.Next == null)
{
head.Next = np;
head = null;
}
else
{

head.Next = np.Next;
head = np;
}
}

return ret;
}

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

1. Have two pointers.
2. One pointing to the first element and the other one to the second element.
3. Swap elements that the first and second pointer are pointing to.
4. Repeat step 3 by moving both the pointers two places until anyone pointer points to null.

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

I am confused isn't it really simple just...

a->next = b->next;
b->next = a

Of course this is not general and only works for the questions stated above.

- Anonymous October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry I thought only swapping first two.
I wish I could delete that post.

- Anonymous October 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a way to do it using a counter. Assuming we are provided a Head pointer. It preserves the Head pointer.

public static void awkwardSwap(TreeNode head) {
int count=0;
TreeNode curr = head.next;
TreeNode prev = head;
while(curr!=null) {
   if(count==0) head=curr;
   if(count>=1) prev.next = prev.next.next;
   prev.next = curr.next;
   curr.next - prev;
   curr = prev.next.next;
   prev = prev.next;
   count++;
   }
}

- AnkitB October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

This seems to be pair wise reverse of linked list..
This method will reverse the linked list depending on the given value n.
for n=2 // pair wise reverse.
--------------------------------------------

struct linkedlist* reverse(struct linkedlist *head, int n)  {
	struct linkedlist *temp,*prev,*curr;
	temp = prev = head;
	int count =n;

	while(temp->next  && count>1)
	{
		curr = temp->next;
		temp->next = curr->next;
		curr->next = prev;
		prev = curr;
		count--;
	}
	if(temp->next)
		temp->next = reverse(temp->next, n);
return prev;
}

- Aalok September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

struct node
{
char data;
struct node* link;
};

struct node * modification(struct node * start ) // start is pointer to start of linked list
{
struct node *p , *q;
char temp;

if(!start || !start-> link)
return;

p = start;
q = start->link;

while (q)
{
temp = p->data;
p->data = q->data;
q->data = temp;
p = q->link;
q = p->link;
}
return start;
}

- mAn1Ac September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if(!start || !start-> link)
return;

Will not even compile..

- Prashant R Kumar September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Lots of flaw it will not swap first two nodes..

- Prashant R Kumar September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

don't comment without verifying !!! i ran this code using GCC compiler and its working fine !!

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

Then its time for you to get a new compiler..
Are you mad of something...Do you think you are the smatest one around...

p->value = q->value;
q->value = temp;
p = q->link;

What is value in your struct..
Your struct defnition is..

struct node
{
char data;
struct node* link;
};

- Prashant R Kumar September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

and who do u think u r .. u are in a public forum so act accordingly !!
GCC is a well renowned compiler !! people everywhere use it !!
and best code is not one with complex statements and lots of symbols with big names !! best code is with best logic !! main question is of logic .. anyone can convert it in some language ..
and if u r such a genius so y don't u give ur code .. y r u going around and just blurting non sense all over the place .. people come here to learn something and morons like u are spoiling that !!!

- mAn1Ac September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
Still, you dont get it do you.? Your struct has {{{ struct node { char data; struct node* link; }; }}} Your struct has {{{data}} as a member.. While you are acceesing it as {{{value}}}.. What effectively you are doing is, {{{ struct node { char data; struct node* link; }; struct node *p , *q; --- --- p->value; //Now where is the declaraion of value? What is value? }}} Another thing is your function declaration says it returns node* while you are returning void. How will that compile..?? So ofcourse your programme will never compile..Yet you are saying that it is compiling and and giving you right output.. That makes you a liar and that explains my outburst... Talking about me moron or something, dont bother, I know what I am, and I know what I talk about...:-)..Only bad thing about me is I am still trying to make you understand C language..cheers. - Prashant September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ohhhh !!! actually i was working on some other code and when i wrote this code so everything here got mixed up !! sorry for that .. i take all back .. u seem a pretty decent guy .. sorry for my outburst :)
also u saw my unedited code thats y ... i edited it afterwards ... thanks anyways :)

- mAn1Ac September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is a working C# code.

public static Link SwapLinks(Link head)
{
    if (head == null || head.Next == null)
        return head;
    Link LastNode = new Link();
    LastNode.Next = head;
    head = head.Next;
    while (LastNode.Next != null && LastNode.Next.Next != null)
    {
        Link trl = LastNode.Next;
        Link fwd = trl.Next;
        LastNode.Next = fwd;
        trl.Next = fwd.Next;
        fwd.Next = trl;
        LastNode = trl;
    }
    return head;
}

- MasterChief September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

One constraint was not creating extra node..and you are doing exactly that..

Link LastNode = new Link();

- Prashant R Kumar September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is my c# code, tested it and I believe it's right -

public static Node ReversePairs (Node link)
        {
            if (link == null || link.next == null) return null;
            Node nextPair = link;

            while (link != null && link.next != null)
            {
                if (nextPair == link)
                {
                    Node tmp = link.next;
                    link.next = link.next.next;
                    Node tmp2 = link;
                    link = tmp;
                    link.next = tmp2;
                    nextPair = tmp2.next;
                }
                else
                    link = nextPair;
            }
            return link;
        }

- yhax September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Only problem is it runs O(2n)..While it can be done in O(n)..

- Prashant R Kumar September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't see much difference between doing this in O(2n) and O(n) in an interview, at the end of the day, it's still O(n). Please let me know what changes you would make to get it to O(n)

- yhax September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Flawless code.... Enjoy!!

#include<iostream>
using namespace std;

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

void insert(node*& head, int data)
{
	node* t = new node;
	t->data = data;
	t->next = head;
	head = t;
}

void print(node* head)
{
	cout<<endl;
	while(head)
	{
		cout<<head->data<<" ";
		head = head->next;
	}
	cout<<endl;
}

node* revN(node* &head, int n)
{
	if(!head || n < 1)
		return head;

	node* prev = NULL, *cur = head, *next;

	while(cur && n--)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}

	head = prev;
	return next;
}

node* reverseN(node* head, int n)
{
	if(!head || n < 1)
		return head;

	node* newhead = head;
	node* newstart = revN(newhead, n);
	head->next = reverseN(newstart, n);
	return newhead;
}

int main()
{
	node* head = NULL;
	insert(head,5);
	insert(head,4);
	insert(head,3);
	insert(head,2);
	insert(head,1);

	print(head);
	head = reverseN(head,7);
	print(head);

	return 0;
}

- Avinash September 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You have to find length of the linked list..Which is ofcourse an extra computation.. While this can be solved without that..

- Prashant R Kumar September 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Prashant.. This piece of code does not find the length anywhere...I doubt if you have read the code properly?... The routine reverseN(node*,int) is a generic routine which takes 'n' as an integer parameter and reverses the linked list accordingly. So, as per the question 'n = 2' suffice...

- Avinash September 09, 2012 | 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