Microsoft Interview Question for Software Developers


Team: Bing
Interview Type: Written Test




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

find kth - 1 element make it point to null, last element in linked List point to head. update head to be kth elememt

- Gear March 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

find new list's end (k -1) and rearrange elements to list's head

template<typename T>
        struct Node
        {
            T value;
            Node *next;

            Node(const T &val)
                : value(val)
                , next(nullptr)
            {}
        };

        template<typename T>
        class List
        {
        public:
            List()
                : m_head(nullptr)
                , m_len(0)
            {}

            ~List()
            {
                Node<T> *iter = m_head;
                while (iter)
                {
                    Node<T> *next = iter->next;
                    delete iter;
                    iter = next;
                }
            }

            void Insert(const T value)
            {
                if (!m_head)
                {
                    m_head = new Node<T>(value);
                    m_len++;
                }
                else
                {
                    Node<T> *iter = m_head->next;
                    Node<T> *prev = m_head;

                    while (iter)
                    {
                        prev = iter;
                        iter = iter->next;
                    }

                    prev->next = new Node<T>(value);
                    m_len++;
                }
            }

            void RotateOn(size_t k)
            {
                size_t mod_k = k % m_len;

                if (m_head && mod_k > 0)
                {
                    // localize new end of a list
                    Node<T> *iter_kth = m_head;
                    for (size_t i = 0; i < mod_k - 1; i++){
                        iter_kth = iter_kth->next;
                    }

                    // get current end-node
                    Node<T> *iter = iter_kth->next;
                    Node<T> *end = iter_kth;
                    while (iter)
                    {
                        end = iter;
                        iter = iter->next;
                    }

                    // rearrange list nodes
                    Node<T> *new_head = iter_kth->next;
                    iter_kth->next = nullptr;

                    end->next = m_head;
                    m_head = new_head;
                }
            }

        private:
            Node<T> *m_head;
            size_t m_len;
        };

- yura.gunko March 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// assuming LinkedList has a head Node member
void LinkedList::rotate(int k) {
Node* cur = head; Node* prev = null;
for (int i = 1; i < k && cur->next; ++i) {
prev = cur;
cur = cur->next;
}

if (prev && i == k) {
prev->next = 0;
Node* oldHead = head;
head = cur;
while (cur->next)
cur = cur->next;
cur-next = oldHead;
}
}

- malcolm.carvalho March 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = Node(None)

    def InsertNode(self,data):
        newnode = Node(data)
        if self.head.next == None:
            self.head.next = newnode
        else:
            currnode = self.head.next
            while currnode.next:
                currnode = currnode.next
            currnode.next = newnode

    def Print(self):
        if self.head.next == None:
            print "No Data available"
            return
        currnode = self.head.next
        while (currnode):
            print currnode.data
            currnode = currnode.next
            
    def RotateonKthElement(self,k):
        if k ==1 :
            print "First element can not be rotated"
            return
        if self.head.next == None:
            print "No Data available"
            return
        currnode = self.head.next
        i=1
        while currnode.next:
            if i+1 == k:
                nextnode = currnode.next
                currnode.next = None
                currnode = nextnode
                rotatenode = currnode
            if currnode.next:
                currnode =currnode.next
            i += 1
        lastnode = currnode
        nexttoheadnode = self.head.next
        self.head.next = rotatenode
        lastnode.next = nexttoheadnode

ll = LinkedList()
ll.InsertNode(1)
ll.InsertNode(2)
ll.InsertNode(3)
ll.InsertNode(4)
ll.InsertNode(5)
ll.RotateonKthElement(4)
ll.Print() #prints 4 5 1 2 3

- ankitpatel2100 March 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Go to the k-1th element,save the next as head.
Point the next of k-th element to null.
Take the last k elements of the list and point the end of it to the original head
In Scala you can do it by drop and take

def rotateList(list : List[Int], k : Int) : List[Int] = list.drop(k)++list.take(k)

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

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

#include<iostream>

using namespace std;

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

void printlist(struct node* head)
{
while(head!=NULL)
{
cout<<head->data;
head=head->next;
}
}
void rotateList(struct node* head, int k)
{
int count=0;
struct node* temp=head;
struct node* current=temp;
struct node* prev=NULL;
while(count!=k)
{
prev=temp;
temp=temp->next;
current=temp;
count++;
}
while(temp->next!=NULL)
temp=temp->next;
temp->next=head;
prev->next=NULL;
cout<<"======================"<<endl;
printlist(current);
}

int main()
{
struct node* head=NULL;
struct node* n= (struct node*)malloc(sizeof(struct node));
struct node* n2=(struct node*)malloc(sizeof(struct node));
struct node* n1= (struct node*)malloc(sizeof(struct node));
struct node* n3= (struct node*)malloc(sizeof(struct node));
struct node* n4=(struct node*)malloc(sizeof(struct node));
struct node* n5=(struct node*)malloc(sizeof(struct node));
n->data=1;
n->next=n1;
n1->data=2;
n1->next=n2;

n2->data=3;
n2->next=n3;
n3->data=4;
n3->next=n4;
n4->data=5;
n4->next=n5;
n5->data=6;
n5->next=NULL;
printlist(n);
cout<<"======================"<<endl;
rotateList(n,3);
cout<<"======================"<<endl;
return 0;
}

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

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

#include<iostream>

using namespace std;

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

void printlist(struct node* head)
{
	while(head!=NULL)
	{
	cout<<head->data;
	head=head->next;
	}
}
void rotateList(struct node* head, int k)
{
	int count=0;
	struct node* temp=head;
	struct node* current=temp;
	struct node* prev=NULL;
	while(count!=k)
	{
		prev=temp;
		temp=temp->next;
		current=temp;
		count++;
	}
	while(temp->next!=NULL)
		temp=temp->next;
	temp->next=head;
	prev->next=NULL;
cout<<"======================"<<endl;
	printlist(current);
}

int main()
{
struct node* head=NULL;
struct node* n= (struct node*)malloc(sizeof(struct node));
struct node* n2=(struct node*)malloc(sizeof(struct node));
struct node* n1= (struct node*)malloc(sizeof(struct node));
struct node* n3= (struct node*)malloc(sizeof(struct node));
struct node* n4=(struct node*)malloc(sizeof(struct node));
struct node* n5=(struct node*)malloc(sizeof(struct node));
n->data=1;
n->next=n1;
n1->data=2;
n1->next=n2;

n2->data=3;
n2->next=n3;
n3->data=4;
n3->next=n4;
n4->data=5;
n4->next=n5;
n5->data=6;
n5->next=NULL;
printlist(n);
cout<<endl;
rotateList(n,3);
cout<<endl;
return 0;
}

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

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

#include<iostream>

using namespace std;

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

void printlist(struct node* head)
{
	while(head!=NULL)
	{
	cout<<head->data;
	head=head->next;
	}
}
void rotateList(struct node* head, int k)
{
	int count=0;
	struct node* temp=head;
	struct node* current=temp;
	struct node* prev=NULL;
	while(count!=k)
	{
		prev=temp;
		temp=temp->next;
		current=temp;
		count++;
	}
	while(temp->next!=NULL)
		temp=temp->next;
	temp->next=head;
	prev->next=NULL;
cout<<"======================"<<endl;
	printlist(current);
}

int main()
{
struct node* head=NULL;
struct node* n= (struct node*)malloc(sizeof(struct node));
struct node* n2=(struct node*)malloc(sizeof(struct node));
struct node* n1= (struct node*)malloc(sizeof(struct node));
struct node* n3= (struct node*)malloc(sizeof(struct node));
struct node* n4=(struct node*)malloc(sizeof(struct node));
struct node* n5=(struct node*)malloc(sizeof(struct node));
n->data=1;
n->next=n1;
n1->data=2;
n1->next=n2;

n2->data=3;
n2->next=n3;
n3->data=4;
n3->next=n4;
n4->data=5;
n4->next=n5;
n5->data=6;
n5->next=NULL;
printlist(n);
cout<<"======================"<<endl;
rotateList(n,3);
cout<<"======================"<<endl;
return 0;
}

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

struct ListNode {
         int val;
         ListNode *next;
         ListNode(int x) : val(x), next(NULL) {}
     };

ListNode * reverseK(ListNode *  cur)
{
    ListNode * prev=0;
    ListNode * next=0;
    while ( cur )
    {
        next=cur->next;
        cur->next=prev;
        prev=cur;
        cur=next;
    
    }
    return prev;
}
ListNode * rotateK(ListNode *  head, int k)
{
    ListNode * l1 = head;

    ListNode * prev = 0;
    
    while(k--)
    {
        prev=head;
        head=head->next;
    }
    if ( head == 0 )
        return l1;
    
    if (prev) prev->next=0;
    
    ListNode* l2=head;
    l2=reverseK(l2);
    if ( k ) head->next=l1;
    return l2;
}

- drolmal April 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public ListNode rotateRight(ListNode head, int k) {
        if(head==null||head.next==null)
            return head;
        ListNode tempNode = new ListNode(0);
        tempNode.next = head;
        ListNode fastPtr = tempNode;
        ListNode slowPtr = tempNode;
        
        int len = 0;
        for(;fastPtr.next!=null;len++)
            fastPtr = fastPtr.next;
        
        for(int i = len - k % len; i>0;i--)
            slowPtr = slowPtr.next;
        
        fastPtr.next = tempNode.next;
        tempNode.next = slowPtr.next;
        slowPtr.next = null;
        
        return tempNode.next;
    }

- Unmesh April 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

struct list;

typedef struct list {
    int val;
    struct list *next;
} list_t;


list_t * rotate_list (list_t *head, int k)
{
    int i = 1;
    list_t *cur;
    list_t *new_head;

    if (!head)
        return NULL;

    if (k == 0)
        return NULL;

    if (k == 1)
        return head;

    cur = new_head = head;

    while (cur) {
        if (i == (k -1)) {

            /* save the new head of the list */
            new_head = cur->next;

            /* 
             * Check for error condition : there are less elements in the list
             * than k
             */
            if (!cur->next)
                return NULL;
            else {
                /* k -1 node is now the last one in the list */
                cur->next = NULL;
                cur = new_head;
            }
        }

        if (cur->next == NULL) {
            /* 
             * check for the case where there is only one element in the list 
             * Do not create a circular list in that case
             */
            if (cur != head) {
                cur->next = head;
                cur = NULL;
            }
        } else {
            i++;
            cur = cur->next;
        }
    }

    return new_head;
}

- code_dino April 20, 2017 | 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