## iLabs Interview Question for Tech Leads

Country: India
Interview Type: In-Person

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

When you say reverse, does it mean reversing the data ? Or do you mean reverse the order of traversal ?

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

reversing the order of traversal.

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

Revesre k nodes alternatively ......
when sw is 1 ..it will revesrse and it wont otherwise..

struct node * revAlternate(struct node *t,int k,int sw){
struct node *nxt,*prev=NULL;

struct node *curr=t;
int count=0;
while(curr!=NULL && count <k){
nxt=curr->next;
if(sw)
curr->next=prev;
prev=curr;
curr=nxt;
count++;
}

if(sw){

if(nxt != NULL){
t->next=revAlternate(nxt,k,!sw);
}
}else{

if(nxt!=NULL){
prev->next=revAlternate(nxt,k,!sw);
}

}

if(sw){
return prev;
}else{
return t;
}

}

int main(){

printf("\n");
return 0;
}

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

As per my understanding I'm providing the below example for others to try out

Input:

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20

and k = 5

Output:

1->2->3->4->5->10->9->8->7->6->15->14->13->12->11->20->19->18->17->16

Note: Take care of corner cases like n%k != 0 (n - number of nodes in LL) when you work out.

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

Or is the problem like, you have to skip first k nodes, then reverse the next k nodes, then skip the next k nodes, then reverse the next k nodes and so on until the end?

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

it might be...

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

Hi Guyzzz That'a A wonderful explanation for reverse a Linked List. but i am stuck with something else.. below is the function for reversion a list from a point till end... but it is looping infinite ...

can someone help me...

**now when i am printing the head it goes Infinite loop. It goes till the reversed part and then again the same List starts..**

current O/P 1->2->3->4->5->10->9->8->7->6->10->9->8->7.........

Desired O/P 1->2->3->4->5->10->9->8->7->6->null

``````public void reverseAfterK(int k){
for(int i=1;i<k;i++) {
if(current == null)
return;
current = current.next;
}
current.next = newNode.next;
}

while(peek!=null){
peek.next = rev;
rev = peek;
peek = temp;
}
return rev;
}``````

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

``````public void reverseList(int k){
List temp = start;
int i = 1;
while(i<k){
temp = temp.next;
i++;
}

List p =temp.next;
List q = null;
List r;

while(p != null){
r = q;
q = p;
p = p.next;
q.next = r;
}

temp.next = q;
}``````

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

This program doesn't take into account that size of temp can be less than k, in which case your first while loop breaks as null.next doesn't exis

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

``````#include <stdio.h>
#include <malloc.h>

typedef struct ll
{
int i;
struct ll *next;
}ll;

{
struct ll *cur_node;
for (cur_node = pHead; cur_node; cur_node = cur_node->next)
printf ("->%d",cur_node->i);
printf ("->NULL\n");
}

{
struct ll *pCur_node;
struct ll *pPrev_node;
int i;

for (i=1; i <= count; i++)
{
pCur_node = malloc (sizeof(struct ll));
pCur_node->i = i;
pCur_node->next = NULL;
pPrev_node->next = pCur_node;
pPrev_node = pCur_node;
}
}

struct ll* reverse_ll(struct ll *pStart, int count)
{
int i;
struct ll *pCur_node = pStart;
struct ll *pPrev_node = NULL;
struct ll *pNext_node = pStart->next;

for (i= 1; i < count && pNext_node; i++)
{
pPrev_node = pCur_node;
pCur_node = pNext_node;
pNext_node = pNext_node->next;
pCur_node->next = pPrev_node;
}
pStart->next = pNext_node;
return pCur_node;
}

{
int i;
struct ll **pArrayll;

pArrayll = malloc(sizeof(struct ll*) * count);

for (i= 1; i < count && pCur_node; i++)
{
pCur_node = pCur_node->next;
}

while (pCur_node && pCur_node->next)
{
pCur_node->next = reverse_ll(pCur_node->next, count);

for (i= 1; i <= count && pCur_node; i++)
{
pCur_node = pCur_node->next;
}
}

}

int main()
{
int k;
printf("Enter the k value:");
scanf("%d",&k);

}

Output
bash-4.2\$ ./ll_reverse
Enter the k value:7
bash-4.2\$ ./ll_reverse
Enter the k value:1
bash-4.2\$ ./ll_reverse
Enter the k value:2
bash-4.2\$ ./ll_reverse
Enter the k value:3
bash-4.2\$ ./ll_reverse
Enter the k value:4
bash-4.2\$ ./ll_reverse
Enter the k value:5
bash-4.2\$ ./ll_reverse
Enter the k value:6
bash-4.2\$ ./ll_reverse
Enter the k value:7
bash-4.2\$ ./ll_reverse
Enter the k value:8
bash-4.2\$ ./ll_reverse
Enter the k value:9
bash-4.2\$ ./ll_reverse
Enter the k value:10
bash-4.2\$ ./ll_reverse
Enter the k value:11
bash-4.2\$ ./ll_reverse
Enter the k value:15
bash-4.2\$ ./ll_reverse
Enter the k value:19
bash-4.2\$ ./ll_reverse
Enter the k value:20
bash-4.2\$ ./ll_reverse
Enter the k value:18
bash-4.2\$``````

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

/* Checks all corner cases, does a best case skip/reversal */

void skip_k_rev_k(struct node *head, int k)
{
struct node *prev, *save, *save_skipped_last, *save_rev_first;

/* Skip k and return if we reach end */
for(int i = 0; i < k; i++) {
return;
}

return;

/* Save first element in the subset list being reversed */

/* Reverse entire subset list */
for(int i = 0; i < k; i++) {
/* Break for cases where we run out list since we still need to fixup */
break;
}

/* Retrieve last element of the initial skipped list */
save_skipped_last = save_rev_first->next;

/* Point it to the last element of the skipped list */
save_skipped_last->next = prev;

/* Point last element of the now reversed list to the next element of the list it reversed */
}

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

``````void skip_k_rev_k(struct node *head, int k)
{
struct node *prev, *save, *save_skipped_last, *save_rev_first;

/* Skip k and return if we reach end */
for(int i = 0; i < k; i++) {
return;
}

return;

/* Save first element in the subset list being reversed */

/* Reverse entire subset list */
for(int i = 0; i < k; i++) {
/* Break for cases where we run out list since we still need to fixup */
break;
}

/* Retrieve last element of the initial skipped list */
save_skipped_last = save_rev_first->next;

/* Point it to the last element of the skipped list */
save_skipped_last->next = prev;

/* Point last element of the now reversed list to the next element of the list it reversed */
}``````

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

below is the code, i tried and it works. but you need to need tweak the code,
1. if the input list is not unique(if not unique, removeAll won't work in the below logic)
2. total size of inputList is not a multiple of inputCount.
..............
//Preparing input list upto 20;
int inputCount = 5;

for (int i = 0; i < 20; i++) {
}

System.out.println("inputList: " + inputList);

for (int j = 0; j < inputList.size(); j++) {

int skipcount = inputCount;
if (j < skipcount) {
continue;
}

int subListStartInd = j;
int subListEndInd = j+inputCount;
System.out.println("sublisting");
List<Integer> subListL = inputTemp.subList(subListStartInd, subListEndInd);

System.out.println("removing sublist");
inputList.removeAll(subListL);

System.out.println("reversing sublist");
Collections.reverse(subListL);

System.out.println("inserting sublist");
j = subListEndInd-1;
}
System.out.println("outputList: " + inputList);
.............

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

``````public static void reversePartial(LinkedList<Integer> list, int n){
List<Integer> l = new ArrayList<Integer>();
for(int i = 0; i < n; i++){
int num = list.poll();
}

Collections.reverse(list);
for(int i = l.size() - 1; i >= 0; i--){
}
}``````

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

Solution in Java ....

``````public Node reverseNodes(Node head){

Node start = null;

Node next;

while(current != null){
for (int i = 0; i < 2; i++){
if(end == null)
break;
end = end.next;
}

start = end;

if(end != null){
end = end.next;
Node prev = null;

for (int i = 0; i< 3; i++){
if(end == null)
break;
next = end.next;
end.next = prev;
prev = end;
end = next;
}

if(prev != null)
start.next = prev;

for(int i = 0; i < 3; i++){
start = start.next;
}
if(start != null)
start.next = end;
}
current = end;
}

}``````

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

Simple solution with Stack, taking into account all the conditions:

``````public boolean skipAndReverse(MyNode<T> current, int k)
{
if(k<2 || current == null){
return false;
}

for(int y = 0; y<k;y++)
{
current = current.next;
if(current == null){
return false;
}
}

Stack<T> s = new Stack<>();
MyNode<T> temp = current;

while( current !=null)
{
for(int x = 0; x < k; x++)
{
s.push(temp.data);
temp = temp.next;

if(temp== null){
break;
}
}

temp = current;

while(!s.isEmpty())
{
T val = s.pop();
temp.data = val;
temp = temp.next;
}

current = temp;
}

return true;``````

}

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

``````public Node ReverseFromKthNode(Node head, int k)
{
{
}
int i = 0;
while(i<k)
{
curr = curr.Next;
i++;
if (curr==null)
{
return null;
}
}
Node next;
Node prev = null;
while (curr!=null)
{
next = curr.Next;
curr.Next = prev;
prev = curr;
curr = next;
}
return prev;
}``````

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

Oops. Got the question wrong. Need to reverse only k elements, not the entire linked list after k elements

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

``````node *reverse(node *head){
int i=1;
node *prev, *h, *n, *t, *q;
prev =NULL;
while(i<5){

h=h->next;
i++;
}
t =h->next;
q=t;
while(t!=NULL)
{
i=0;
q= t;
while(i<5){
n = t->next;
t->next = prev;
prev = t;
t = n;
i++;
}
h->next = prev;
h=q;
prev = NULL;
}

}``````

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

node* reverseRecursively(node** list) {
if (!*list) return;

//SET THE LIST WITH FIRST AND REST INSTANCES
node* first = *list;
node* rest = first->next;

if (!rest) return;

reverseRecursively(&rest);

//F->N->N = F makes the next node point to itself to reverse its direction
//AND THEN F->N is made to point NULL
first->next->next = first;
first->next = NULL;

*list = rest;
return *list;
}

//SKIP K ELEMENTS IN THE LIST AND THEN
//RECURSIVELY REVERSE THE REMAINING LINKED LISTS
node* reverseKNodes(node** list, int k) {
if (!*list) return;

while (k >= 0) {
*list = (*list)->next;
k--;
}

(*list)->next = reverseRecursively(&(*list)->next);
}

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

``````public static void deletelast(Node x)
{
Node one=x;
Node two=x;
int count=0;
if(one.next==null)
{
one=null;
}
else
{
while(one.next!=null)
{
one=one.next;
if(count==1)
two=two.next;
else if(count<1)
count++;
}

two.next=null;
}
}

{
if(one.next==null)
{
if(newfirst!=null)
{
y.next=one;
one.next=null;
y=one;

}
else
{
y=newfirst=one;

}
deletelast(one);
return newfirst;
}
Node temp=one;
while(temp.next!=null)
{
temp=temp.next;
}
if(newfirst==null)
{
temp.next=null;
y=newfirst=temp;
}
else
{
y.next=temp;
temp.next=null;
y=temp;

}
deletelast(one);
return newfirst;
}

public static Node partialrev(int i,Node x)
{
Node one=x;
int z=1;
Node onelag=x;
int count=0;
while(z<i)
{
one=one.next;
if(count>0)
onelag=onelag.next;
z++;
count++;
}
Node two=one.next;
onelag.next.next=null;
one.next=rev;
return x;

}``````

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

``````import java.util.Stack;

public class SkipReverseKNodes {

System.out.println("Enter a value greater than 1 and less than "+head.getSize());
return;
}
for(int i=0;i<k-1;i++){
runner=runner.next;
current=current.next;
}
runner=current.next;
while(runner!=null){
Stack<Integer> s=new Stack<Integer>();
for(int i=0;i<k;i++){
s.push(runner.data);
runner=runner.next;
if(runner==null) break;
}
while(!s.isEmpty()){
current.next.data=s.pop();
current=current.next;
}
}
}

public static void main(String[] args) {

SkipReverseKNodes s=new SkipReverseKNodes();

while(n!=null){
System.out.print(n.data+" ");
n=n.next;
}

System.out.println();
while(n!=null){
System.out.print(n.data+" ");
n=n.next;
}
}
}``````

Comment hidden because of low score. Click to expand.

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.