CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

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.
1
of 1 vote

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.
0
of 0 votes

O(0) extra space:

class ListNode(object):
    def __init__(self, v):
        self._v = v
        self._next = None


def reorder(l):
    h = l
    next = l._next

    if not next or not next._next:
        return l

    while next._next and next._next._next:
        next = next._next

    h2 = h._next
    h._next = next._next
    next._next = None

    l2 = reorder(h2)
    h._next._next = l2

    return h        

if __name__ == '__main__':
    l = ListNode('A')
    l._next = ListNode('B')
    l._next._next = ListNode('c')
    l._next._next._next = ListNode('D')
    l._next._next._next._next = ListNode('E')
    #l._next._next._next._next._next = ListNode('F') #case 2
    r = reorder(l)
    while r:
        print(r._v)
        r = r._next

- yuhechen2018 March 05, 2020 | 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 2 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

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
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class ManageList{
    public static void main(String[] args){
        Node head = new Node('A');
        Node cur = head;
        cur.next = new Node('B');
        cur = cur.next;
        cur.next = new Node('C');
        cur = cur.next;
        cur.next = new Node('D');
        cur = cur.next;
        cur.next = new Node('E');

        Node mid = getMid(head);
        Node newHead = reverse(mid);
        Node total = combine(head, newHead);

        while(total != null){
            System.out.println(total.val);
            total = total.next;
        }
    }

    public static Node combine(Node a, Node b){
        Node dummy = new Node('*');
        Node curr = dummy;
        while(a != null || b != null){
            if(a != null && b != null){
                curr.next = a;
                a = a.next;
                curr = curr.next;
                curr.next = b;
                b = b.next;
                curr = curr.next;
            }else if(a != null){
                curr.next = a;
                a = a.next;
                curr = curr.next;
            }else if(b != null){
                curr.next = b;
                b = b.next;
                curr = curr.next;
            }
        }
        return dummy.next;
    }



    public static Node getMid(Node node){
        Node fast = node;
        Node slow = node;
        Node prev = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        prev.next = null;
        return slow;
    }

    public static Node reverse(Node node){
        Node prev = null;
        Node curr = node;
        Node next = node.next;
        while(next != null){
            curr.next = prev;
            Node temp = next.next;
            next.next = curr;
            prev = curr;
            curr = next;
            next = temp;
        }
        return curr;
    }
}

class Node{
    Node next;
    char val;
    Node(char val){
        this.val = val;
        next = null;
    }
}

- xzhan211@binghamton.edu July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//LinkedList : 
// Input: A > B > C > D > E
// Output: A > E > B > D > C


// A, [B,C,D,E] => [E,C,D,B]
// E, [C,D,B] => [B,D,C]
// B, [D,C] => [D,C]

class Node {
  constructor(data) {
    this.data = data
    this.next = null
    this.previous = null
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  
  add(data) {
    let node = new Node(data)
    
    if (!this.head) {
      this.head = node
    }
    
    if (this.tail) {
      this.tail.next = node
      node.previous = this.tail
    } 
    
    this.tail = node
    
    this.length++
  }
  
  get(index) {
    if (!this.head) 
      return null
      
    if (index <= 0)
      return this.head
      
    if (index >= this.length-1)
      return this.tail
    
    let current = this.head
    for (let i = 1; i <= index; i++) {
      if (!current.next)
        return null
        
      current = current.next
    }
    
    return current
  }
  
  remove(index) {
    let len = this.length
    
    if(index == 0) {
      let current = this.head
      current.next.previous = null
      this.head = current.next
      this.length--
      
      if(this.tail == current)
        this.tail = current.next

      current.next = null
      return current
    }
    
    if (index >= len-1) {
      let current = this.tail
      current.previous.next = null
      this.tail = current.previous
      this.length--
      
      if(this.head == current)
        this.head = current.previous
        
      current.previous = null
      return current
    }
    
    let current = this.get(index)
    current.previous.next = current.next
    current.next.previous = current.previous
    this.length--
    
    current.next = null
    current.previous = null
    
    return current
  }
  
  switch(from, to) {
    if (from == to)
      return
    
    let fromNode = this.get(from)
    let toNode = this.get(to)
    
    let data = fromNode.data
    fromNode.data = toNode.data
    toNode.data = data
  } 
  
  print() {
    let data = []
    for(let current = this.head; current != null; current = current.next) {
      data.push(current.data)
    }
    
    console.log(data)
  }
}

const list = new LinkedList()
list.add('A')
list.add('B')
list.add('C')
list.add('D')
list.add('E')

for (let i = 1; i < list.length-2; i++) {
  list.switch(i, list.length)
  list.print()
}

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

ListNode* oddEvenList(ListNode* head) {
        if (!head)
            return head;
        
        int i=0;
        ListNode* oddlist = nullptr;
        ListNode* evenlist = nullptr;
        ListNode* cur = head;
        ListNode* oddhead = nullptr;
        while (cur) {
            if (i%2 == 1) {
                if (!oddlist)
                    oddhead = cur;
                else
                    oddlist->next = cur;
                oddlist = cur;
            } else {
                if (evenlist)
                    evenlist->next = cur;
                evenlist = cur;
            }
            cur = cur->next;
            i++;
        }
        evenlist->next = oddhead;
        if (oddlist)
            oddlist->next = nullptr;
        return head;
    }

- RMP October 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import scala.annotation.tailrec

object Test extends App {

  val input: List[Symbol] = List('A, 'B, 'C, 'D, 'E)

  def reverse[T](in: List[T]): List[T] = {

    @tailrec
    def reverseUtil(l: List[T], result: List[T]): List[T] = l match {
      case Nil => result
      case h :: t => reverseUtil(t, h :: result)
    }

    reverseUtil(in, Nil)
  }

  println(s"Input = $input")

  println(buildList(input))


  //overall complexity O(n)
  def buildList[T](list: List[T]): List[T] = {
    val reversed = reverse(list)// O(n)

    println(s"reversed = $reversed")
    val isEven = list.length % 2 == 0
    val iterations = list.length/2

    //invariant reversed.length == list.length

    //O(n) where n = length/2
    def genListUtil(index: Int, l: List[T], r: List[T]): List[T] = if(index > iterations) Nil else (l, r) match {
      case (Nil, Nil) => Nil
      case (h1 :: t1, Nil)  => throw new RuntimeException(s"Invariant violated: l=$l r=$r")
      case (Nil, h1 :: t1)  => throw new RuntimeException(s"Invariant violated: l=$l r=$r")
      case (h1 :: t1, h2 :: t2) =>
        if((index == iterations) && !isEven)
          h1 :: genListUtil(index + 1, t1, t2)
        else
          h1 :: h2 :: genListUtil(index + 1, t1, t2)
    }

    genListUtil(0, list, reversed)
  }
  
}

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

import scala.annotation.tailrec

object Test extends App {

  val input: List[Symbol] = List('A, 'B, 'C, 'D, 'E)

  def reverse[T](in: List[T]): List[T] = {

    @tailrec
    def reverseUtil(l: List[T], result: List[T]): List[T] = l match {
      case Nil => result
      case h :: t => reverseUtil(t, h :: result)
    }

    reverseUtil(in, Nil)
  }

  println(s"Input = $input")

  println(buildList(input))


  //overall complexity O(n)
  def buildList[T](list: List[T]): List[T] = {
    val reversed = reverse(list)// O(n)

    println(s"reversed = $reversed")
    val isEven = list.length % 2 == 0
    val iterations = list.length/2

    //invariant reversed.length == list.length

    //O(n) where n = length/2
    def genListUtil(index: Int, l: List[T], r: List[T]): List[T] = if(index > iterations) Nil else (l, r) match {
      case (Nil, Nil) => Nil
      case (h1 :: t1, Nil)  => throw new RuntimeException(s"Invariant violated: l=$l r=$r")
      case (Nil, h1 :: t1)  => throw new RuntimeException(s"Invariant violated: l=$l r=$r")
      case (h1 :: t1, h2 :: t2) =>
        if((index == iterations) && !isEven)
          h1 :: genListUtil(index + 1, t1, t2)
        else
          h1 :: h2 :: genListUtil(index + 1, t1, t2)
    }

    genListUtil(0, list, reversed)
  }
  
}

- Patrick November 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 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


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