Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
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 *
swap_alternate_nodes(node_t head*)
{
node_t *alternate = NULL;
node_t *temp = NULL;
/*
* Check if the head or head->next is null
* If so return head
*/
if (head == NULL || head->next == NULL)
return (head);
alternate = head->next;
temp = swap_alternate_nodes(head->next->next);
/* Now swap */
head->next = temp;
alternate->next = head;
return (alternate);
}
// A->B->C->D->E->F
// B->A->D->C->F->E
void SwapPairs(Node **pHead)
{
Node *pPrev = NULL, *pTemp = NULL, *pNext = NULL;
Node *pCurrent = *pHead;
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 {
// Update the head
*pHead = pCurrent;
}
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);
}
// 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;
Node* head = current->next;
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;
}
return head;
}
class LinkForLinkedListSwapItemInPair {
public char data;
public LinkForLinkedListSwapItemInPair next;
public LinkForLinkedListSwapItemInPair(char data) {
this.data = data;
}
public void display() {
System.out.print(data + " ==> ");
}
}
class LinkedList {
private LinkForLinkedListSwapItemInPair first;
public LinkedList() {
first = null;
}
public boolean isEmpty() {
if(first == null) {
return true;
}
return false;
}
public void insertFirst(char data) {
LinkForLinkedListSwapItemInPair newElm = new LinkForLinkedListSwapItemInPair(data);
newElm.next = first;
first = newElm;
}
public void deleteFirst() {
if(isEmpty()) {
System.out.println("List is empty");
return;
}
LinkForLinkedListSwapItemInPair temp = first;
first = temp.next;
temp.next = null;
}
public void display() {
LinkForLinkedListSwapItemInPair current = first;
while(current != null) {
current.display();
current = current.next;
}
System.out.println("\n");
}
public LinkForLinkedListSwapItemInPair getFirst() {
return first;
}
}
class SwapItemInPair {
private LinkedList list;
public SwapItemInPair() {
list = new LinkedList();
}
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;
}
LinkForLinkedListSwapItemInPair fItem = list.getFirst();
LinkForLinkedListSwapItemInPair sItem = list.getFirst().next;
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 class LinkedListSwapItemInPair {
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();
}
}
#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 );
Node* saveHead = head;
for ( int i = 1; i < number; ++i )
{
head->mNext = new Node ( i + 1 );
head = head->mNext;
}
return saveHead;
}
void printList ( Node* head )
{
cout << "HEAD --> ";
while ( head != NULL )
{
cout << head->mData << " --> ";
head = head->mNext;
}
cout << "TAIL" << "\n";
}
Node* swapPair ( Node* head )
{
Node* prevNode = head;
Node* nextNode = NULL;
Node* currentNode = head->mNext;
Node* backupTail = NULL;
Node* result = head->mNext;
if ( currentNode == NULL )
{
return head;
}
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;
}
/**
* Test swaping linked list.
*/
TEST(LinkedListTest, 123456789)
{
Node* head = createLinkedList ( 9 );
printList ( head );
Node* result = swapPair ( head );
printList ( result );
}
#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 );
Node* saveHead = head;
for ( int i = 1; i < number; ++i )
{
head->mNext = new Node ( i + 1 );
head = head->mNext;
}
return saveHead;
}
void printList ( Node* head )
{
cout << "HEAD --> ";
while ( head != NULL )
{
cout << head->mData << " --> ";
head = head->mNext;
}
cout << "TAIL" << "\n";
}
Node* swapPair ( Node* head )
{
Node* prevNode = head;
Node* nextNode = NULL;
Node* currentNode = head->mNext;
Node* backupTail = NULL;
Node* result = head->mNext;
if ( currentNode == NULL )
{
return head;
}
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;
}
/**
* Test swaping linked list.
*/
TEST(LinkedListTest, 123456789)
{
Node* head = createLinkedList ( 9 );
printList ( head );
Node* result = swapPair ( head );
printList ( result );
}
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);
head = n2; //new head always n2?
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;
}
}
while(head!=null){
System.out.print(head.getData() + "->");
head = head.getNext();
}
System.out.print("null");
}
}
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));
head = n;
for(int i = 1; i < args[0].length(); i++){
n.setNext(new LLNode(args[0].charAt(i)));
n = n.getNext();
}
n.setNext(null);
p1 = head;
if(head.getNext() != null)
head = head.getNext();
else{ //if the list has only one element, then that is the head and no processing is needed
System.out.println(head.getData());
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;
}
}
while(head.getNext()!=null){
System.out.print(head.getData() + "->");
head = head.getNext();
}
System.out.println(head.getData());
}
}
Another solution based on split/merge linked list
public static Node swapInPairs(Node head) {
if (head == null || head.next == null) {
return head;
}
Node head2 = head.next;
Node t1 = head;
Node t2 = head2;
while (t1 != null && t2 != null) {
t1.next = t2.next;
t2.next = t2.next != null ? t2.next.next : null;
t1 = t1.next;
t2 = t2.next;
}
Node t = head2;
Node c1 = head;
Node c2 = head2.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;
}
}
return head2;
}
}
#include<stdio.h>
#include<stdlib.h>
struct node{
char data;
struct node* next;
};
struct node* head;
void insert(char x){
struct node* tmp = (struct node*)malloc(sizeof(struct node));
tmp->data=x;
tmp->next=head;
head= tmp;
}
void print(){
struct node* tmp = head;
while(tmp!=NULL){
printf("%c ",tmp->data);
tmp= tmp->next;
}
}
void myfun(){
struct node* pre;
struct node* cur= head;
struct node* nex;
if(head !=NULL || cur->next!=NULL){
nex= cur->next;
cur->next= nex->next;
nex->next= head;
head=nex;
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();
}
#include<stdio.h>
#include<stdlib.h>
struct node{
char data;
struct node* next;
};
struct node* head;
void insert(char x){
struct node* tmp = (struct node*)malloc(sizeof(struct node));
tmp->data=x;
tmp->next=head;
head= tmp;
}
void print(){
struct node* tmp = head;
while(tmp!=NULL){
printf("%c ",tmp->data);
tmp= tmp->next;
}
}
void myfun(){
struct node* pre;
struct node* cur= head;
struct node* nex;
if(head !=NULL || cur->next!=NULL){
nex= cur->next;
cur->next= nex->next;
nex->next= head;
head=nex;
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();
}
Node* swapAdjacent(Node* n) {
if (n == NULL || n->next == NULL) return n;
Node* nextNext = swapAdjacent(n->next->next);
n->next->next = n;
Node* next = n->next;
n->next = nextNext;
return next;
}
Node* swapAdjacentIter(Node* n) {
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;
}
struct Node
{
int i;
Node *Next;
Node(int j) :i(j), Next(NULL) {}
};
Node *SwapListInPairs(Node* Head)
{
if (Head == NULL)
{
return (NULL);
}
if (Head->Next == NULL)
{
return (Head);
}
Node *Res = SwapListInPairs(Head->Next->Next);
Node *Temp = Head->Next;
Head->Next->Next = Head;
Head->Next = Res;
return (Temp);
}
public class EvenOddLinkedList {
Node head;
Node last;
public EvenOddLinkedList add(int data) {
Node node = new Node(data);
if (head == null) {
head = node;
} 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() {
Node current = head;
while (current != null) {
System.out.println(current.data + " ");
current = current.next;
}
}
public void swap() {
if (head == null || head.next == null)
return;
Node c = head;
Node runner = head.next.next;
head = head.next;
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) {
EvenOddLinkedList evenOddLinkedList = new EvenOddLinkedList().add(1).add(2).add(3).add(4).add(5).add(6);
evenOddLinkedList.print();
System.out.println("======");
evenOddLinkedList.swap();
evenOddLinkedList.print();
}
}
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;
}
}
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;
}
// 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;
Node* head = current->next;
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;
}
return head;
}
struct Node *
reverse_pair(struct Node *head) {
if (head == NULL) {
return NULL;
}
if (head->next == NULL) {
return head;
}
struct Node *temp = NULL;
struct Node *ptr1 = head;
struct Node *ptr2 = ptr1->next;
temp = ptr2->next;
ptr2->next = ptr1;
ptr1->next = reverse_pair(temp);
return ptr2;
}
Iterative solution. ReversePairs is inside LinkedList class, so head is class level variable.
public void ReversePairs()
{
if(head == null || head.next == null)
return;
Node curr = head, prev=null;
head = curr.next;
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;
}
}
<?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;
}
<?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;
}
Fairly simple problem can be solved with double pointers in c
typedef struct Node {
int data;
struct Node *next;
} Node;
void SwapPairs(Node **pHead) {
Node *temp;
<*-- Input Area 1: 5 rows --*>
while (*pHead && (*pHead)->next) { // Base: 7, Surcharge: 5
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
}
}
Fairly simple problem, double ptrs needed
typedef struct Node {
int data;
struct Node *next;
} Node;
void SwapPairs(Node **pHead) {
Node *temp;
<*-- Input Area 1: 5 rows --*>
while (*pHead && (*pHead)->next) { // Base: 7, Surcharge: 5
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
}
}
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;
}
}
public void rearrange() {
Node pointer1 = head;
Node pointer2 = head.next;
Node temp;
pointer1.next = pointer2.next;
pointer2.next = pointer1;
head = pointer2;
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();
}
swaps pairs one at a time and returns new Head of List.
public static NodeLinked switchPairs(NodeLinked head) {
NodeLinked t1, t2, h2 = null;
t1 = head;
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;
}
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 tmpTo 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.
- Javeed April 22, 2015The 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