## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

While I normally stay away from recursion usage in interview questions, here's a case where it greatly simplifies life.

in python:

``````def swap_rec(node):
if not node or not node.next:
return node
tmp = node.next
node.next = swap_rec(tmp.next)
tmp.next = node
return tmp``````

To make it work, you hand it the head node of the linked list. It will do the reversals in pairs as specified, and handles cases such as an odd-length list.

The reason I say recursion saves us time here is because tracking the pointers in a loop can become a pain. In either case, the solution is O(n) runtime

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

really nice recursive solution!

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

You must decide if you want to go for recursive function or iterative one. People tell me recursive is pretty but it uses stack memory and hence may bot be desirable some times. Here is my take

``````typedef struct node_s
{
int	data; /* You can select your type of data or no data also works */
node_t	*next;
} node_t;

/* Helper function to swap alternate nodes */
static node_t *
{
node_t *alternate = NULL;
node_t *temp = NULL;

/*
*/

/* Now swap */

return (alternate);
}``````

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

``````// A->B->C->D->E->F
// B->A->D->C->F->E

{
Node *pPrev = NULL, *pTemp = NULL, *pNext = NULL;
while (pCurrent) {

// un-even number of elements case
if (pCurrent->pNext == NULL) {
pPrev->pNext = pCurrent;
break;
}
// swap the current and the next
pNext = swap(&pCurrent);
if (pPrev) {
pPrev->pNext = pCurrent;
}
else {
}
pPrev = pCurrent->pNext;
// Set the pointer for the last element
if (pNext == NULL) { pCurrent->pNext->pNext = NULL; }
// Move ptr to the next element
pCurrent = pNext;
}
}

Node *swap(Node **pCurrent)
{
if ((!pCurrent) || (!(*pCurrent))) { return(NULL); }

Node *pTemp = (*pCurrent)->pNext;
Node *pRet = NULL;
if (pTemp) { pRet  = pTemp->pNext; }

pTemp->pNext = *pCurrent;
*pCurrent = pTemp;
return(pRet);``````

}

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

your code will fail for 1->NULL scenario.

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

``````// 1->2->3->4->5->6->7
// 2->1->4->3->6->5->7
Node* alternateReverse(Node* root){
if (!root || !root->next){
return root;
}

Node* prev = NULL;
Node* current = root;
while (current && current->next)
{
Node* temp = current;
Node* next = current->next;
Node* nextnext = current->next->next;

if (prev){
prev->next = next;
}

prev = current;
next->next = current;
current = nextnext;
}

if (prev){
prev->next = current;
}

}``````

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

``````class LinkForLinkedListSwapItemInPair {
public char data;

this.data = data;
}

public void display() {
System.out.print(data + " ==> ");
}
}

first = null;
}

public boolean isEmpty() {
if(first == null) {
return true;
}
return false;
}

public void insertFirst(char data) {
newElm.next = first;
first = newElm;
}

public void deleteFirst() {
if(isEmpty()) {
System.out.println("List is empty");
return;
}

first = temp.next;
temp.next = null;
}

public void display() {
while(current != null) {
current.display();
current = current.next;
}
System.out.println("\n");
}

return first;
}
}

class SwapItemInPair {
public SwapItemInPair() {
}

public void insert(char data) {
list.insertFirst(data);
}

public void delete() {
list.deleteFirst();
}

public void display() {
list.display();
}

public boolean isEmpty() {
return list.isEmpty();
}

public void swapItemInPair() {
if(isEmpty()) {
System.out.println("List is Empty");
return;
}

if(list.getFirst().next == null) {
System.out.println("Single Item and cannot swap anymore.");
return;
}

char temp;
while(fItem.next.next != null && sItem.next.next != null) {
temp = fItem.data;
fItem.data = sItem.data;
sItem.data = temp;
fItem = fItem.next.next;
sItem = sItem.next.next;
}
temp = fItem.data;
fItem.data = sItem.data;
sItem.data = temp;
}
}

public static void main(String[] args) {
SwapItemInPair mSwap = new SwapItemInPair();
mSwap.insert('E');
mSwap.insert('D');
mSwap.insert('C');
mSwap.insert('B');
mSwap.insert('A');
mSwap.display();
mSwap.swapItemInPair();
mSwap.display();

}
}``````

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

#include <gtest/gtest.h>
#include <gmock/gmock.h>

using namespace testing;
using namespace std;

struct Node
{
int mData;
Node* mNext;
Node ( int data ) :
mData ( data ),
mNext ( NULL )
{
}
};

Node* createLinkedList ( int number )
{
if ( number == 0 )
{
return NULL;
}

Node* head = new Node ( 1 );
for ( int i = 1; i < number; ++i )
{
head->mNext = new Node ( i + 1 );
}

}

void printList ( Node* head )
{
while ( head != NULL )
{
cout << head->mData << " --> ";
}
cout << "TAIL" << "\n";
}

Node* swapPair ( Node* head )
{
Node* nextNode = NULL;
Node* backupTail = NULL;

if ( currentNode == NULL )
{
}

while ( currentNode != NULL )
{
nextNode = currentNode->mNext;

if ( backupTail != NULL )
backupTail->mNext = currentNode;

currentNode->mNext = prevNode;
prevNode->mNext = nextNode;
backupTail = prevNode;

if ( nextNode != NULL )
{
currentNode = nextNode->mNext;
prevNode = nextNode;
}
else
{
currentNode = NULL;
}
}

return result;
}

/**
*/
{

Node* result = swapPair ( head );
printList ( result );
}

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

#include <gtest/gtest.h>
#include <gmock/gmock.h>

using namespace testing;
using namespace std;

struct Node
{
int mData;
Node* mNext;
Node ( int data ) :
mData ( data ),
mNext ( NULL )
{
}
};

Node* createLinkedList ( int number )
{
if ( number == 0 )
{
return NULL;
}

Node* head = new Node ( 1 );
for ( int i = 1; i < number; ++i )
{
head->mNext = new Node ( i + 1 );
}

}

void printList ( Node* head )
{
while ( head != NULL )
{
cout << head->mData << " --> ";
}
cout << "TAIL" << "\n";
}

Node* swapPair ( Node* head )
{
Node* nextNode = NULL;
Node* backupTail = NULL;

if ( currentNode == NULL )
{
}

while ( currentNode != NULL )
{
nextNode = currentNode->mNext;

if ( backupTail != NULL )
backupTail->mNext = currentNode;

currentNode->mNext = prevNode;
prevNode->mNext = nextNode;
backupTail = prevNode;

if ( nextNode != NULL )
{
currentNode = nextNode->mNext;
prevNode = nextNode;
}
else
{
currentNode = NULL;
}
}

return result;
}

/**
*/
{

Node* result = swapPair ( head );
printList ( result );
}

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

Can we use just add/remove api from the list?

``````static void swapInPairs(LinkedList list){
int N = list.size();
int last = N - (N%2) - 1;
for (int i = 1; i <= last; i = i + 2){
}
}``````

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

Can we use just simple add/remove API?

``````static void swapInPairs(LinkedList list){
int N = list.size();
int last = N - (N%2) - 1;
for (int i = 1; i <= last; i = i + 2){
}
}``````

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

Written quickly before running to work, I realise there are checks I need to add. WIll add soon.

``````public class LLPairSwapFB {

public static void main(String[] args) {
LLNode p1, p2, p3, px, head;

LLNode n1 = new LLNode('A');
LLNode n2 = new LLNode('B');
LLNode n3 = new LLNode('C');
LLNode n4 = new LLNode('D');

n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);

p1 = n1;
p2 = p1.getNext();
p3 = p1.getNext().getNext();
px=null;

while(true){
p2.setNext(p1);
p1.setNext(p3);
if(px!=null)
px.setNext(p2);
else
px = p1;

if(p3!=null){
p1 = p3;
p2 = p3.getNext();
p3 = p3.getNext().getNext();
}
if(p1.getNext() == null){
break;
}
}
}
System.out.print("null");
}

}``````

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

Cleaned up to accept elements from command line, handle the case where there are 0 and 1 elements; and odd and even numbers of elements. The class LLNode is a simple java class with a data and a next field.

``````public class LLPairSwapFB {

public static void main(String[] args) {
LLNode p1, p2, p3, px, head;

if(args[0].length() == 0){
System.out.println("Provide atleast one element");
return;
}
LLNode n = null;
n = new LLNode(args[0].charAt(0));
for(int i = 1; i < args[0].length(); i++){
n.setNext(new LLNode(args[0].charAt(i)));
n = n.getNext();
}
n.setNext(null);

else{ //if the list has only one element, then that is the head and no processing is needed
return;
}

p2 = p1.getNext();
p3 = p1.getNext().getNext();
px=null;

while(true){
p2.setNext(p1);
p1.setNext(p3);
if(px!=null)
px.setNext(p2);
px = p1;

if(p3!=null){
p1 = p3;
if(p3.getNext()==null)
break;
p2 = p3.getNext();
p3 = p3.getNext().getNext();
}
if(p1.getNext() == null){
break;
}
}
}
}

}``````

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

Another solution based on split/merge linked list

``````public static Node swapInPairs(Node head) {
}

while (t1 != null && t2 != null) {
t1.next = t2.next;
t2.next = t2.next != null ? t2.next.next : null;
t1 = t1.next;
t2 = t2.next;
}

while (c1 != null || c2 != null) {
if (c1 != null) {
t.next = c1;
t = t.next;
c1 = c1.next;
}
if (c2 != null) {
t.next = c2;
t = t.next;
c2 = c2.next;
}
}

}
}``````

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

Algorithm:
1. Split the list into odd_list and even_list.
2. Merge the even_list and odd_list picking one element from each.

Example:
1->2->3->4->5->6
After 1.
odd_list : 1->3->5
even_list : 2->4->6

After 2:
2->1->4->3->6->5

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

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

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

void insert(char x){
struct node* tmp = (struct node*)malloc(sizeof(struct node));

tmp->data=x;

}

void print(){

while(tmp!=NULL){
printf("%c ",tmp->data);
tmp= tmp->next;
}

}

void myfun(){

struct node* pre;
struct node* nex;

nex= cur->next;
cur->next= nex->next;

pre= cur;
cur=cur->next;

if(cur!=NULL){

while(cur->next!=NULL){

nex= cur->next;
cur->next= nex->next;
nex->next= pre->next;
pre->next=nex;

pre= cur;
cur=cur->next;
}
}

}

}

main(){

//insert('f');
insert('e');
insert('d');
insert('c');
insert('b');
insert('a');

print();
printf("\n");
myfun();
print();
}

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

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

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

void insert(char x){
struct node* tmp = (struct node*)malloc(sizeof(struct node));

tmp->data=x;

}

void print(){

while(tmp!=NULL){
printf("%c ",tmp->data);
tmp= tmp->next;
}

}

void myfun(){

struct node* pre;
struct node* nex;

nex= cur->next;
cur->next= nex->next;

pre= cur;
cur=cur->next;

if(cur!=NULL){

while(cur->next!=NULL){

nex= cur->next;
cur->next= nex->next;
nex->next= pre->next;
pre->next=nex;

pre= cur;
cur=cur->next;
}
}

}

}

main(){

//insert('f');
insert('e');
insert('d');
insert('c');
insert('b');
insert('a');

print();
printf("\n");
myfun();
print();
}

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

``````Node* swapAdjacent(Node* n) {
if (n == NULL || n->next == NULL) return n;
n->next->next = n;
Node* next = n->next;
n->next = nextNext;
return next;
}

Node* newRoot = (n!=NULL && n->next!=NULL) ? n->next : n;
Node* prev = NULL;
while (n != NULL && n->next != NULL) {
Node* nxt = n->next->next;
n->next->next = n;
if (prev != NULL) prev->next = n->next;
n->next = nxt;
prev = n;
n = nxt;
}
return newRoot;
}``````

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

``````struct Node
{
int i;
Node *Next;

Node(int j) :i(j), Next(NULL) {}
};

{
{
return (NULL);
}

{
}

return (Temp);
}``````

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

``````public class EvenOddLinkedList {

Node last;

Node node = new Node(data);

} else {
last.next = node;
}
last = node;

return this;

}

static class Node {

int data;
Node next;

public Node(int data) {
this.data = data;
}

@Override
public String toString() {

return data + "";
}

}

public void print() {

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

public void swap() {
return;

while (runner != null) {
c.next.next = c;
c.next = runner.next == null ? runner : runner.next;
c = runner;

if (runner.next != null)
runner = runner.next.next;
else
runner = null;

}
if (c.next != null) {
c.next.next = c;
c.next = null;
}
last = c;

}

public static void main(String[] args) {

System.out.println("======");
}
}``````

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

``````public void ReversePairs(Node list)
{
if(list == null)
{
return;
}

Node first = list;
Node second = list.next;
Node previous = null;

while(first != null && second != null)
{
// swap pointers
first.next = second.next;
second.next = first;

// if previous exists, then assign to the second node since it's before first now
if(previous != null)
{
previous.next = second;
}

// set previous to what is now the second node
// that way if we need to process more, we can point to the new firsts
previous = first;

// move to the next pair. If first is null, then there's nothing else to do
// if first's next is null, we still assign but while loop won't be true, so it will break
first = first.next;
if(first == null)
{
break;
}

second = first.next;
}
}``````

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

``````Node* swap_pairs(Node *start)
{
Node* cur, *prev, *next, *result;
cur = start;
next = 0;
prev = 0;
result = 0;
while(cur && cur->next)
{
next = cur->next->next;
if (!result) result = cur->next;
if (prev) prev->next = cur->next;
cur->next->next = cur;
cur->next = next;
prev = cur;
cur = next;
}
if (!result) result = start;
return result;
}``````

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

``````// 1->2->3->4->5->6->7
// 2->1->4->3->6->5->7
Node* alternateReverse(Node* root){
if (!root || !root->next){
return root;
}

Node* prev = NULL;
Node* current = root;
while (current && current->next)
{
Node* temp = current;
Node* next = current->next;
Node* nextnext = current->next->next;

if (prev){
prev->next = next;
}

prev = current;
next->next = current;
current = nextnext;
}

if (prev){
prev->next = current;
}

}``````

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

``````struct Node *
return NULL;
}
}
struct Node *temp = NULL;
struct Node *ptr2 = ptr1->next;
temp = ptr2->next;
ptr2->next = ptr1;
ptr1->next = reverse_pair(temp);

return ptr2;
}``````

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

Iterative solution. ReversePairs is inside LinkedList class, so head is class level variable.

``````public void ReversePairs()
{
return;

while (curr != null && curr.next != null)
{
Node next = curr.next;
curr.next = next.next;
next.next = curr;

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

if (curr.next != null)
curr = curr.next;
prev = next.next;
}
}``````

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

``````<?php

class Node {
public \$val = null;
public \$prev = null;
public \$next = null;
public function __construct(\$val){
\$this->val = \$val;
}
public function __toString() {
\$nextVal = \$this->next ? \$this->next->val : "";
\$prevVal = \$this->prev ? \$this->prev->val : "";
return "Value {\$this->val}, Next {\$nextVal}, Prev {\$prevVal}\n";
}
}

function swapPairs(\$first, \$second) {
if (!\$first || !\$second) return;

\$secondNext = \$second->next;
\$firstPrev = \$first->prev;

\$second->next = \$first;
\$second->prev = \$firstPrev;

\$first->next = \$secondNext;
\$first->prev = \$second;

if (\$secondNext) {
\$secondNext->prev = \$first;
swapPairs(\$secondNext, \$secondNext->next);
}
if (\$firstPrev) {
\$firstPrev->next = \$second;
}
}

\$a = new Node('a');
\$b = new Node('b');
\$c = new Node('c');
\$d = new Node('d');
\$e = new Node('e');
\$f = new Node('f');

\$a->next = \$b;
\$b->next = \$c;
\$c->next = \$d;
\$d->next = \$e;
\$e->next = \$f;

\$b->prev = \$a;
\$c->prev = \$b;
\$d->prev = \$c;
\$e->prev = \$d;
\$f->prev = \$e;

swapPairs(\$a, \$b);

echo \$a, \$b, \$c, \$d, \$e, \$f;

\$node = \$b;
while (\$node) {
print "{\$node->val} ";
\$node = \$node->next;
}``````

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

``````<?php

class Node {
public \$val = null;
public \$prev = null;
public \$next = null;
public function __construct(\$val){
\$this->val = \$val;
}
public function __toString() {
\$nextVal = \$this->next ? \$this->next->val : "";
\$prevVal = \$this->prev ? \$this->prev->val : "";
return "Value {\$this->val}, Next {\$nextVal}, Prev {\$prevVal}\n";
}
}

function swapPairs(\$first, \$second) {
if (!\$first || !\$second) return;

\$secondNext = \$second->next;
\$firstPrev = \$first->prev;

\$second->next = \$first;
\$second->prev = \$firstPrev;

\$first->next = \$secondNext;
\$first->prev = \$second;

if (\$secondNext) {
\$secondNext->prev = \$first;
swapPairs(\$secondNext, \$secondNext->next);
}
if (\$firstPrev) {
\$firstPrev->next = \$second;
}
}

\$a = new Node('a');
\$b = new Node('b');
\$c = new Node('c');
\$d = new Node('d');
\$e = new Node('e');
\$f = new Node('f');

\$a->next = \$b;
\$b->next = \$c;
\$c->next = \$d;
\$d->next = \$e;
\$e->next = \$f;

\$b->prev = \$a;
\$c->prev = \$b;
\$d->prev = \$c;
\$e->prev = \$d;
\$f->prev = \$e;

swapPairs(\$a, \$b);

echo \$a, \$b, \$c, \$d, \$e, \$f;

\$node = \$b;
while (\$node) {
print "{\$node->val} ";
\$node = \$node->next;
}``````

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

``````public void swap(Node head) {
Node prev = head, next = prev.next;

while (next != null) {
prev.next = next.next;
next.next = prev;
next = prev.next;
}
}``````

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

Sorry, corrected a mistake in the previous submission:

``````public void swap(Node head) {
Node prev = head, next = prev.next;

while (next != null) {
prev.next = next.next;
if (next.next != null) next.next = prev;
next = prev.next;
}
}``````

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

Fairly simple problem can be solved with double pointers in c

``````typedef struct Node {
int data;
struct Node *next;
} Node;

Node *temp;

<*-- Input Area 1: 5 rows --*>
temp = *pHead;                  // Base: 4, Surcharge: 0
*pHead = temp->next;            // Base: 4, Surcharge: 0
temp->next = (*pHead)->next;    // Base: 4, Surcharge: 0
(*pHead)->next = temp;          // Base: 4, Surcharge: 0
pHead = &(temp->next);          // Base: 4, Surcharge: 0
}

}``````

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

Fairly simple problem, double ptrs needed

``````typedef struct Node {
int data;
struct Node *next;
} Node;

Node *temp;

<*-- Input Area 1: 5 rows --*>
temp = *pHead;                  // Base: 4, Surcharge: 0
*pHead = temp->next;            // Base: 4, Surcharge: 0
temp->next = (*pHead)->next;    // Base: 4, Surcharge: 0
(*pHead)->next = temp;          // Base: 4, Surcharge: 0
pHead = &(temp->next);          // Base: 4, Surcharge: 0
}``````

}

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

``````struct node *reverse (struct node *head)
{
struct node* next = NULL;

if (current != NULL && current->next != NULL)
{
prev = current->next;
next = prev->next;
prev->next = current;
current->next = reverse(next);
}

return prev;
}``````

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

``````struct node *reverse (struct node *head)
{
struct node* next = NULL;

if (current != NULL && current->next != NULL)
{
prev = current->next;
next = prev->next;
prev->next = current;
current->next = reverse(next);
}

return prev;
}``````

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

``````struct node *reverse (struct node *head)
{
struct node* next = NULL;

if (current != NULL && current->next != NULL)
{
prev = current->next;
next = prev->next;
prev->next = current;
current->next = reverse(next);
}

return prev;``````

}

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

``````public class HelloWorld
{

public static Node func(Node root){
//A->B->C->D
if (root == null || root.next == null) return root;
//root = A
Node b = root.next; //b == B
root.next = func(b.next); //A->f( C )  which is A -> D -> C
b.next = root; //B->A
return b; //B
}

public static void main(String[] args)
{
Node n = new Node('a');
Node start = n;
n.next = new Node('b');
n = n.next;
n.next = new Node('c');
n = n.next;
n.next = new Node('d');
n = n.next;
n.next = new Node('e');
n = n.next;
n.next = new Node('f');
n = n.next;
n.next = new Node('g');
n = n.next;
n.next = new Node('h');

start = func(start);
while(start!=null){
System.out.println(start.val); //Returns b->a->d->c->f->e->h->g
start=start.next;
}
}
}

public class Node{
public Node next;
public char val;

public Node(char a){
val = a;
next = null;
}
}``````

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

``````public void rearrange() {
Node temp;

pointer1.next = pointer2.next;
pointer2.next = pointer1;

while(pointer1.next != null && pointer1.next.next != null) {

temp = pointer1;
pointer1 = temp.next;
pointer2 = pointer1.next;
pointer1.next = pointer2.next;
pointer2.next = pointer1;
temp.next = pointer2;
}

print();
}``````

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

swaps pairs one at a time and returns new Head of List.

``````public static NodeLinked switchPairs(NodeLinked head) {
NodeLinked t1, t2, h2 = null;
while(t1 != null && t1.next != null) {
t2 = t1.next;
t1.next = t2.next;
if (t1.next != null) {
t1.next.prev = t1;
}

t2.prev = t1.prev;
if (t2.prev == null){
h2 = t2;
} else {
t2.prev.next = t2;
}
t1.prev = t2;
t2.next = t1;

t1 = t1.next;
}
return h2;
}``````

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

its a singly linked list in the question

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.