Facebook Interview Question


Country: United States
Interview Type: Phone Interview




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

Not sure if this can be done in-memory, I have however used stack iteratively with Deque implementation. Here is the code :

public Node swapApp(Node node) {
    Deque<Node> stack = new ArrayDeque<>();
    while (node != null) {
          stack.addFirst(node);
          node = node.next;
    }
    Node head = new Node('Z');
    Node dummy = head;
    boolean isAlternate = true;
    while (!stack.isEmpty()) {
        Node n1 = null;
        if (isAlternate) {
            n1 = stack.pollLast();
            head.next = n1;
        } else {
            n1 = stack.pollFirst();
           head.next = n1;
        }
        n1.next = null;
        isAlternate = !isAlternate;
        head = head.next;
    }

    return dummy.next;
  }

- getPDat February 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It should be in memory . No extra space is allowed .

- Anonymous February 05, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like this stack approach, the stack is only keeping references to the nodes; so one could argue that it's not strictly O(n) on memory...

- 0x February 28, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you are using it already, why don't we use arraylist and simply solve the problem there by storing pointers and then reorder the list? :-)

- NoOne April 12, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Leetcode 143. Reorder List

- Anonymous February 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you give more specification about the question?

- Anonymous February 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

step 0: A->B->C->D->E
step 1: A->B->C<-D<-E
step 2: A->E, B->C<-D
step 3: A->E->B->D, C
step 4: A->E->B->D->C

- Anonymous February 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
  if (!head || !head.next) return head
  
  // 1. find the middle node O(n)
  let slow = head
  let fast = head.next
  
  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
  }
  
  // 2. reverse from middle
  let newHead = null
  let curr = slow.next
  slow.next = null
  
  while (curr) {
    const next = curr.next
    curr.next = newHead
    newHead = curr
    curr = next
  }

  // 3. merge mid and head
  let currHead = head
  let currMid = newHead
  
  while (currHead && currMid) {
    const headNext = currHead.next
    const midNext = currMid.next
    
    currHead.next = currMid
    currMid.next = headNext
    
    currHead = headNext
    currMid = midNext
  }
  
  return head
};

- mildog8 February 05, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void ReorderLinkedList(LinkedList<char> list)
        {
            if (!list.Any())
            {
                throw new ArgumentNullException(nameof(list));
            }

            var length = list.Count - 1;

            for (int i = 0; i <= length / 2; i++)
            {
                if (i % 2 != 0)
                {
                    continue;
                }

                var first = list.ElementAt(i);
                var nodeFirst = list.Find(first);
                var last = list.ElementAt(length);
                list.AddAfter(nodeFirst, last);
                list.RemoveLast();
            }

            foreach (var element in list)
            {
                Console.Write(string.Concat(element, " "));
            }
        }

- Anonymous February 06, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use the same recursion as checking palindrome of linked list. play around with pointers when rewinding and you will be able to solve it.

- point February 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reorderList(ListNode head) {
        
        Stack<ListNode> stack = new Stack<ListNode>();
        int size = 0;
        ListNode current = head;
        
        while(current!=null){
            stack.push(current);
            current = current.next;
            size++;
        }
        int counter = 0;
        current = head;
        while(current!=null&&counter<size/2){
            ListNode next = current.next;            
            ListNode popped = stack.pop();
            popped.next = next;
            current.next = popped;
            current = popped.next;
            counter++;
        }  
        current.next = null;        
    }

- Anonymous February 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;

public void reorderList(ListNode head) {
if(head==null) return;
left=head;

myList(head);
}
public void myList(ListNode root)
{
if(root==null) return;
myList(root.next);
if(left.next==null) return;
ListNode t=left.next;
if(left.next==root)
{
root.next=null; return;
}
if(t.next== root) t.next=null;

left.next=root;
root.next=t;
left=t;

}
}

- Dhruvil Kotak March 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;
public void reorderList(ListNode head) {
if(head==null) return;
left=head;

myList(head);
}
public void myList(ListNode root)
{
if(root==null) return;
myList(root.next);
if(left.next==null) return;
ListNode t=left.next;
if(left.next==root)
{
root.next=null; return;
}
if(t.next== root) t.next=null;
left.next=root;
root.next=t;
left=t;
}
}

- Dhruvil Kotak March 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;

public void reorderList(ListNode head) {
if(head==null) return;
left=head;

myList(head);
}
public void myList(ListNode root)
{
if(root==null) return;
myList(root.next);
if(left.next==null) return;
ListNode t=left.next;
if(left.next==root)
{
root.next=null; return;
}
if(t.next== root) t.next=null;

left.next=root;
root.next=t;
left=t;

}
}

- Dhruvil Kotak March 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution {
ListNode left=null;

public void reorderList(ListNode head) {
if(head==null) return;
left=head;

myList(head);
}
public void myList(ListNode root)
{
if(root==null) return;
myList(root.next);
if(left.next==null) return;
ListNode t=left.next;
if(left.next==root)
{
root.next=null; return;
}
if(t.next== root) {
t.next=null;
}
left.next=root;
root.next=t;
left=t;

}
}

- Dhruvil Kotak March 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inplace through recusion

class Solution {
        public void reorderList(ListNode head) {
            reorder(head, head);
        }

        private ListNode reorder(ListNode slow, ListNode fast) {
            if (fast == null) {
                return slow;
            }
            if (fast.next == null) {
                ListNode toRet = slow.next;
                slow.next = null;
                return toRet;
            }
            ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;
            if (reNext.next == reNext) {
                reNext.next = null;
            }
            slow.next = reNext;
            return toRet;
        }
    }Solution {
        public void reorderList(ListNode head) {
            reorder(head, head);
        }

        private ListNode reorder(ListNode slow, ListNode fast) {
            if (fast == null) {
                return slow;
            }
            if (fast.next == null) {
                ListNode toRet = slow.next;
                slow.next = null;
                return toRet;
            }
            ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;
            if (reNext.next == reNext) {
                reNext.next = null;
            }
            slow.next = reNext;
            return toRet;
        }
    }

- vikrant omar March 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In place through recursion :
1. Handle even and odd length lists (check comments)
2. reach middle point through slow and fast pointers, which should both be initialized from head. (reorder(head, head)).
3. Basic idea is that once middle is reached than return the next element which your parent should point towards now.

For e.,g. 1->2->3->4->5->6->7->
ans : 1->7->2->6->3->5->4->
when 4 is reached (which you would know if the fast pointer reaches 7)
it should return 5 so that 3 makes 5 as its next element. but before that, 5 should point to what 3 was pointing towards. and even before that, cache 5's next to be returned for this call of recursion.

ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;

slow.next = reNext;
            return toRet;

now once the stack unfurls at 4, 4 would return its next which is 5, which would return 6, which would return 7 and so on :
some special cases needs to be handled for even and odd lengths, if they are not clear enough do let me know.


Over all code :

class Solution {
        public void reorderList(ListNode head) {
            reorder(head, head);
        }

        private ListNode reorder(ListNode slow, ListNode fast) {
            if (fast == null) {
                return slow;
            }
            if (fast.next == null) {
                ListNode toRet = slow.next;
                slow.next = null;
                return toRet;
            }
            ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;
            if (reNext.next == reNext) {
                reNext.next = null;
            }
            slow.next = reNext;
            return toRet;
        }
    }

- vikrant omar March 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In place through recursion :
1. Handle even and odd length lists (check comments)
2. reach middle point through slow and fast pointers, which should both be initialized from head. (reorder(head, head)).
3. Basic idea is that once middle is reached than return the next element which your parent should point towards now.

For e.,g. 1->2->3->4->5->6->7->
ans : 1->7->2->6->3->5->4->
when 4 is reached (which you would know if the fast pointer reaches 7)
it should return 5 so that 3 makes 5 as its next element. but before that, 5 should point to what 3 was pointing towards. and even before that, cache 5's next to be returned for this call of recursion.

ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;

slow.next = reNext;
            return toRet;

now once the stack unfurls at 4, 4 would return its next which is 5, which would return 6, which would return 7 and so on :
some special cases needs to be handled for even and odd lengths, if they are not clear enough do let me know.


Over all code :

class Solution {
        public void reorderList(ListNode head) {
            reorder(head, head);
        }

        private ListNode reorder(ListNode slow, ListNode fast) {
            if (fast == null) {
                return slow;
            }
            if (fast.next == null) {
                ListNode toRet = slow.next;
                slow.next = null;
                return toRet;
            }
            ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;
            if (reNext.next == reNext) {
                reNext.next = null;
            }
            slow.next = reNext;
            return toRet;
        }
    }

- Vikrant Bin Omar Jain March 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In place through recursion :
1. Handle even and odd length lists (check comments)
2. reach middle point through slow and fast pointers, which should both be initialized from head. (reorder(head, head)).
3. Basic idea is that once middle is reached than return the next element which your parent should point towards now.

For e.,g. 1->2->3->4->5->6->7->
ans : 1->7->2->6->3->5->4->
when 4 is reached (which you would know if the fast pointer reaches 7)
it should return 5 so that 3 makes 5 as its next element. but before that, 5 should point to what 3 was pointing towards. and even before that, cache 5's next to be returned for this call of recursion.

ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;

slow.next = reNext;
            return toRet;

now once the stack unfurls at 4, 4 would return its next which is 5, which would return 6, which would return 7 and so on :
some special cases needs to be handled for even and odd lengths, if they are not clear enough do let me know.


Over all code :

class Solution {
        public void reorderList(ListNode head) {
            reorder(head, head);
        }

        private ListNode reorder(ListNode slow, ListNode fast) {
            if (fast == null) {
                return slow;
            }
            if (fast.next == null) {
                ListNode toRet = slow.next;
                slow.next = null;
                return toRet;
            }
            ListNode reNext = reorder(slow.next, fast.next.next);
            ListNode toRet = reNext.next;
            reNext.next = slow.next;
            if (reNext.next == reNext) {
                reNext.next = null;
            }
            slow.next = reNext;
            return toRet;
        }
    }

- Vikrant Bin Omar Jane March 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void reorderList()
{
FBNode current = head, c2 = head;
FBNode next = null, prev = null;
while (current.next != null)
{
next = current.next;
while (c2.next != null)
{
prev = c2;
c2 = c2.next;
}
prev.next = null;
current.next = c2;
c2.next = next;
c2 = next;
current = next;
}
}

- Test April 12, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is recursive python implementation

class Node:
    def __init__(self,val):
        self.val = val
        self.next = None

    def __repr__(self):
        head = self
        string = ""
        while(head):
            string += str(head.val) + ','
            head = head.next
        return string


class Llist:
    def __init__(self):
        self.head = None
        self.tail = None
    def insert(self, val):
        node = Node(val)
        if not self.head:
            self.tail = self.head = node
        else:
            self.tail.next = node
            self.tail = node
        return True


    def __repr__(self):
        head = self.head
        string = ""
        while(head):
            string += str(head.val) + ','
            head = head.next
        return string

def modify_list(head):
    global global_head, flag, return_head
    if not head:
        return head
    print("called", head.val)

    temp = modify_list(head.next)

    if not flag:
        return return_head
    if not temp:
        return_head = global_head
    if head!=global_head:
        temp_global = global_head
        if temp:
            temp.next = global_head
            head.next = None

        global_head = global_head.next
        temp_global.next = head
    else:
        temp.next = head
        head.next = None
        #print(global_head)
        flag=False
    #print(head.val, global_head, return_head)
    if head==global_head:
        flag=False
    return head






llist1 = Llist()
llist1.insert('A')
llist1.insert('B')
llist1.insert('C')
llist1.insert('D')
llist1.insert('E')
llist1.insert('F')
print(llist1)
global_head= llist1.head
flag = True
return_head = None
print(modify_list(llist1.head))

- Anonymous June 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
def __init__(self,val):
self.val = val
self.next = None

def __repr__(self):
head = self
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string


class Llist:
def __init__(self):
self.head = None
self.tail = None
def insert(self, val):
node = Node(val)
if not self.head:
self.tail = self.head = node
else:
self.tail.next = node
self.tail = node
return True


def __repr__(self):
head = self.head
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string

def modify_list(head):
global global_head, flag, return_head
if not head:
return head
print("called", head.val)

temp = modify_list(head.next)

if not flag:
return return_head
if not temp:
return_head = global_head
if head!=global_head:
temp_global = global_head
if temp:
temp.next = global_head
head.next = None

global_head = global_head.next
temp_global.next = head
else:
temp.next = head
head.next = None
#print(global_head)
flag=False
#print(head.val, global_head, return_head)
if head==global_head:
flag=False
return head






llist1 = Llist()
llist1.insert('A')
llist1.insert('B')
llist1.insert('C')
llist1.insert('D')
llist1.insert('E')
llist1.insert('F')
print(llist1)
global_head= llist1.head
flag = True
return_head = None
print(modify_list(llist1.head))

- Anonymous June 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static Node screw(Node in) {
		Node reversed = reverse(in);
		Node screwedNode = new Node();
		Node screwedCurr = screwedNode;
		Node currIn = in;
		Node currRev = reversed;
		int length = length(in);
		for (int i=0; i<length; i++) {
			if (i%2==0) {
				screwedCurr.value = currIn.value;
				currIn = currIn.next;
			} else {
				screwedCurr.value = currRev.value;
				currRev = currRev.next;
			}
			if (i<length-1) {
				screwedCurr.next = new Node();
				screwedCurr = screwedCurr.next;
			}
		}
		return screwedNode;
	}

	static int length(Node in) {
		int counter = 1;
		while((in = in.next) != null) counter++;
		return counter;
	}

	static Node reverse(Node in) {
		Node reverse = clone(in);
		Node curr = reverse;
		Node prev = curr;
		Node next;
		while (true) {
			next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
			if (curr == null) break;
		}
		reverse.next = null;
		return prev;
	}

	private static Node clone(Node in) {
		Node clone = new Node();
		Node cloneCurr = clone;
		cloneCurr.value = in.value;
		while((in = in.next) != null) {
			cloneCurr.next = new Node();
			cloneCurr = cloneCurr.next;
			cloneCurr.value = in.value;
		}
		return clone;
	}

- omikheev June 27, 2019 | Flag Reply


Add a Comment
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.

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