## Facebook Interview Question for Software Engineer Interns

Country: UK
Interview Type: Phone Interview

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

Assuming the list is singly circular linked list.

1- List is empty: a New node will be the head node
2- List is not empty: the location will be found and a new node will be inserted in O(n)

``````Node* sortedInsert(Node* head , int val)
{
Node* prev = NULL;
Node* ins = new Node(val);

if(!head){ // if it is empty
}

}

if(prev){
prev->next = ins;
}else{
}
}``````

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

Assuming the list is singly circular linked list, Hence
Node can be inserted
- at beginning of the list O(1), Swap the data from new node and head and correct the next pointer reference
- In middle of the list - O(n), Traverse to the node
- at the end - O(n) ,
- List is empty and New node will be inserted As first node of the list O(1)

If LIst is doubly circular linked list
Node can be inserted
- at beginning of the list O(1),
- In middle of the list - O(n), Traverse to the node,
- at the end - O(1) , Check if new node has greater value then last node , then insert it at beginning and make second node as head, and new node as last pointer
- List is empty and New node will be inserted As first node of the list O(1)

Feel free to correct me.....

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

``````Node* sortedInsert(Node* head , int val)
{
Node* prev = NULL;
Node* ins = new Node(val);

if(!head){ // if it is empty
}

}

if(prev){
prev->next = ins;
}else{
}
}``````

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

``````static class Node{
int data;
Node next;

Node(int d){
data = d;
}
}

public static Node insert(Node n, int d){
if(n == null)
return new Node(d);
Node p = n;
if(p.data > d ){
while(p.data < p.next.data){
p = p.next;
}
Node l = p.next;
Node t = new Node(d);
p.next = t;
t.next = l;
p = p.next;
return p;
}else{
Node c = p;
while(p.data < p.next.data && p.data < d){
c = p;
p = p.next;
}
if(d < p.data){
Node t = new Node(d);
c.next = t;
t.next = p;
}else{
Node t = new Node(d);
Node l = p.next;
p.next = t;
t.next = l;
}
return n;
}
}``````

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

``````Node *Insert(Node *head, int val)
{
Node *n = new Node(val);
n->next_ = n;
} else {
}
for (n = head; n->next_ != head && n->val_ > n->next_->val_; n = n->next_) {
swap(n->val_, n->next_->val_);
}
}``````

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

``````while (true){
if(cur.data < elem){
if(cur.next.data > elem                //found mid point between the nodes appropriate
|| cur.next.data < cur.data) //end of sorted numbers, and given elem is the max.
{
insert;
return;
}
else{
cur = cur.next;
}
}
else{
cur = cur.next;
}
}``````

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.

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