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


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