## Global Scholar Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 9 vote

struct node *reverse (struct node *head, int k)
{
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;
}

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

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

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

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

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

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;

{
int count;
PNode pcur, pnext, ppre;
PNode pfirst1 = NULL, pfirst2 = NULL;
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++;
{
bfirst = 1;
}
if (nextcount%2==0 && pfirst1!=NULL)
{
pfirst1->next = pcur;
}
else if (pfirst2!=NULL)
{
pfirst2->next = pcur;
}
}
}

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

return 0;``````

}

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

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

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.

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

``````//split returns element count <= splitCount

//will change input list

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

{
node* newList = NULL;

{
//got a sublist
if(newList == null)
else
}
}``````

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

``````def reverseK(head, k):

newTail = data

newTail.setNext(data)
newTail = data

# helper function
for i in range(k):
break

using it by calling

``head = reverseK(a, 3)``

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

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

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??

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

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

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;
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;
cur=next;
prev=NULL;
}
}``````

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

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
- 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)
*/
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;
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 */
}
else
{
new_tail->next = last;
}
}

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

/** update the iterators*/
last = NULL;
}``````

}

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

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

/* Function to Reverse every K nodes in the given linked list */
void ReverseEveryKNodes(struct node** headRef, int k)
{
int pos = 0;
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)
{
FirstTime = false;
}
else
{
NodeBeforeKthNode->next = NodePtrInSubList;
}
while(NodePtrInSubList->next != NULL)
{
NodePtrInSubList = NodePtrInSubList->next;
}
NodeBeforeKthNode = NodePtrInSubList;
NodePtrInSubList->next = NodeAfterKthNode;
NodePtrInOriginalList = NodePtrInSubList->next;
}
}``````

}

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.

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