Facebook Interview Question


Country: United States
Interview Type: Phone Interview




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

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 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


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