Global Scholar Interview Question Software Engineer / Developers


Country: India
Interview Type: Phone Interview


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

struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if(next != NULL)
{ head->next = reverse(next, k); }
return prev;
}

- Ali_BABA on February 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This requires O(n/k) space because of the non-tail recursion, so it isn't optimal.

- psykotic on February 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ali Baba, how do you get a pointer to the head of the new list ?

- Jas on January 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

algopadawan(dot)blogspot(dot)com/2012/05/k-reverse-linked-list(dot)html

- vivekraju.m on May 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

typedef struct Node{
	int data;
	struct Node *next;
}Node, *PNode;

PNode Reverse_K(PNode head, int k)
{
	int count;
	PNode pcur, pnext, ppre;
	PNode pfirst1 = NULL, pfirst2 = NULL;
	PNode phead;
	pnext = head;
	int bfirst = 0;
	int nextcount = 0;  //use this variable to multiples of 2
	while (pnext!=NULL)
	{
		ppre = NULL;
		pcur = NULL;
		if (nextcount%2 == 0)
		{
			pfirst1 = pnext;
		}
		else
			pfirst2 = pnext;
		count = 0;
		while(count<k&&pnext!=NULL){    //k-Node's reverse
			pcur = pnext;
			pnext = pcur->next;
			pcur->next = ppre;
			ppre = pcur;
			count++;
		}
		nextcount++;
		if(bfirst==0)   //mark the first head and return phead
		{
			phead = pcur;
			bfirst = 1;
		}
		if (nextcount%2==0 && pfirst1!=NULL)  
		{
			pfirst1->next = pcur;
		}
		else if (pfirst2!=NULL)
		{
			pfirst2->next = pcur;
		}
	}
	return phead;
}

int main()
{
	PNode head, temp;
	head = (PNode)malloc(sizeof(Node));
	head->data = 0;
	head->next = NULL;
	for (int i=10; i>0; --i)
	{
		temp = (PNode)malloc(sizeof(Node));
		temp->data = i;
		temp->next = head->next;
		head->next = temp;
	}

	head = Reverse_K(head, 3);
	return 0;

}

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

The inner loop is the same algorithm as plain old in-place reversal. The only difference is that you have to maintain a few pointers across the inner loop to hook up the k-segments.

node *reverse(node *x, int k)
{
    node *r = NULL, *p = NULL, *h = NULL;
    while (x) {
        node *nh = x;
        for (int i = 0; i < k && x; i++) {
            node *n = x->next;
            x->next = p;
            p = x;
            x = n;
        }
        if (h) h->next = p;
        else r = p;
        h = nh;
    }
    if (h) h->next = NULL;
    return r;
}

- psykotic on February 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question does not say that you can't use another data structure. Therefore i think the best answer is to push the k - elements on the stack, then pop and relink them recursively.

- baltazar on February 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//split returns element count <= splitCount
int split(node*& head, node& subHead, int splitCount);

//will change input list
void reverse(node*& head);

void append(node* list, node* node);


void reverseK(node*& globalHead, int count)
{
	node* subHead = NULL;
	node* newList = NULL;
	
	while(split(globalHead,subHead,count))
	{
		//got a sublist
		reverse(subHead);
		if(newList == null)
			newList = subHead;
		else
			append(newList,subHead);
	}
}

- Abhinav on March 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def reverseK(head, k):
    if head == None:
        return head

    data = reverse(head, k)

    newHead = data[0]
    newTail = data[1]
    nextHead = data[2]

    while nextHead:
        data = reverse(nextHead, k)
        newTail.setNext(data[0])
        newTail = data[1]
        nextHead = data[2]

    return newHead

# helper function
def reverse(head, k):
    originalHead = head
    prevHead = None
    for i in range(k):
        if head == None:
            break
        tmp = head.getNext()
        head.setNext(prevHead)
        prevHead = head
        head = tmp

    return (prevHead, originalHead, head)

using it by calling

head = reverseK(a, 3)

- wyefei88 on May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

obviously, this site doesn't have a good python parser

- wyefei88 on May 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey bharajwad.... how much time is usually given for there questions by the interviewer??

- naveen kumar on June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For this question, 10 minutes would be a reasonable time to answer.

- bharajwad on February 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverseList(Node *h,int K)
{
	Node *cur,*next,*prev;
	int count=0;
	prev=NULL;
	cur=h->next;
	Node *temp,*tempHead=h;
	while(cur!=NULL)
	{
		count=1;
		temp=cur;
		while(cur->next!=NULL&&count++<K)
		{
			printf("point 1\n");
			next=cur->next;
			cur->next=prev;
			prev=cur;
			cur=next;
		}
		next=cur->next;
		cur->next=prev;
		tempHead->next=cur;
		tempHead=temp;	
		cur=next;
		prev=NULL;
	}
}

- sarath on July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node
{
public:
int i_obj;
Node *next;
};
class sknode
{
public:
Node *ptr;
sknode *next;
}*skStart;

void push(Node *ptr)
{
sknode *p = new sknode;
p->ptr = ptr;
p->next = NULL;
if(skStart == NULL)
{
skStart = p;
}
else
{
p->next = skStart;
skStart = p;
}
}
Node *pop()
{
Node *ptr = NULL;
if(skStart != NULL)
{
sknode *temp = skStart;
skStart = skStart->next;

ptr = temp->ptr;
delete temp;
}
return ptr;
}
==========================================
void List::reverseKelemts(int k)
{
Node *ptr = start;
Node *newPtr = NULL;
start = NULL;
int K = k;
int counter = 0;
while(ptr != NULL)
{
counter++;
while(K >= 1)
{
counter++;
if(ptr == NULL)
break;
push(ptr);
ptr = ptr->next;
K--;
}
while(K < 3)
{
counter++;
if(start == NULL)
{
start = pop();
newPtr = start;
}
else
{

newPtr->next = pop();
newPtr = newPtr->next;
newPtr -> next = NULL;
}
K++;
}
}
cout<<"Number of iterations: "<< counter <<endl;
}

- Anonymous on August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/** 
- check if we can form 1st k elements reversed list
	- if yes, update the newhead and newtail of that list
	- if no, update the head with newhead and return
- check if we can form next k elemets reversed list
   - if yes, append this list to the one formed above and update newtail alone
   - if no, (means we are able to make reversed list with less than k elements)
		appened this list and update the head with newhead and return head
*/
Node* ReverseKelements(Node * head, int k)
{
	/** If list is NULL return */
	if(temp == NULL)
		return temp;

	int flag = 0; /** Helps in identifying new head */
	while(1)
	{
		/** reverse the first k elements
			and from the new list */
		Node *last = NULL;
		Node *temp = head;
		Node *temp2, *new_head, *new_tail;
		for(int i = 1 ; (i < k)&& (temp != NULL) ; i++)
		{
			temp2 = temp->next;
			temp->next = last;
			last = temp;
			temp = temp2;
		}

		/** list end reached before k elements*/
		if(temp == NULL)
		{
			if(flag == 0)
			{
				/** Total no: of elements in list is less than k */
				head = last;
				return head;
			}
			else
			{
				new_tail->next = last;
				head = new_head;
				return head;
			}
		}

		/** successfully reversed k elements*/
		if(flag == 0)
		{
			/** first reversed list
				store the new head*/
			new_head = last;
			new_tail = head;
			flag = 1;
		}
		else
		{
			/** second time onwards*/
			new_tail->next = last;
			new_tail = head;
		}

		/** update the iterators*/
		head = temp;
		last = NULL;
	}

}

- Vignesh on August 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
/* Subroutine to Reverse a Linked List */
void Reverse(struct node** headRef)
{
	if(*headRef == NULL || (*headRef)->next == NULL)
		return;
	else 
	{
		struct node* p = NULL;
		struct node* q = *headRef;
		struct node* r;
		while(q != NULL)
		{
			r = q->next;
			q->next = p;
			p = q;
			q = r;			
		}
		*headRef = p;
	}
}

/* Function to Reverse every K nodes in the given linked list */
void ReverseEveryKNodes(struct node** headRef, int k)
{
	int pos = 0;
	struct node* NodePtrInOriginalList = *headRef;
	struct node* NodeAfterKthNode = NULL;
	struct node* NodeBeforeKthNode = NULL;
	bool FirstTime = true;
	while(NodePtrInOriginalList != NULL)
	{
		struct node* NodePtrInSubList = NodePtrInOriginalList;
		pos = 0;
		for(pos = 0; pos < k - 1; pos++)
		{
			if(NodePtrInOriginalList == NULL)
				break;
			else
				NodePtrInOriginalList = NodePtrInOriginalList->next;
		}
		if(NodePtrInOriginalList == NULL)
			break;
		NodeAfterKthNode = NodePtrInOriginalList->next;
		NodePtrInOriginalList->next = NULL;
		Reverse(&NodePtrInSubList);
		if (FirstTime)
		{
			*headRef = NodePtrInSubList;
			FirstTime = false;
		}
		else
		{
			NodeBeforeKthNode->next = NodePtrInSubList;
		}
		while(NodePtrInSubList->next != NULL)
		{
			NodePtrInSubList = NodePtrInSubList->next;
		}		
		NodeBeforeKthNode = NodePtrInSubList;
		NodePtrInSubList->next = NodeAfterKthNode;
		NodePtrInOriginalList = NodePtrInSubList->next;
	}
}

}

- randomlyideas on December 14, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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