Google Interview Question
Software Engineer / DevelopersCountry: United States
Nicely done.
How about the case, when you need to insert after the last node? Will your code handle that?
In your implementation for scenario 2, when you need to replace the head node (i.e. head_ref->data >= newNode->data), you iterate through every node to reach the end. Why not just swap new_node's data with head_ref data and insert new_node after the current head_ref?
void insert(Node node, int x) {
if (node == null) {
node = new Node(x);
node.next = node;
return;
}
Node nextP = node; // To move forward
Node prevP = NULL; // To hold pointer on previous node
do {
prev = nextP;
nextP = nextP.next;
if (x <= nextP.data && x >= prevP->data){
//If value resides between two values of nextP & prevP, add here
break;
}
if ((prevP.data > nextP.data) && (x < nextP.data || x > prevP.data)) {
//If node x is largest (larger than all elements in the list)
//or smallest (smaller than all elements in the list)
break;
}
} while (nextP != node);
Node newNode = new Node(x);
newNode.next = nextP;
prevP.next = newNode;
}
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *start;
int insert(int element)
{
struct node *temp,*prev,*new;
new = malloc(sizeof(struct node));
new->data = element;
new->next = NULL;
if(!start)
{
start = new;
new->next = start;
return 0;
}
if(start->data > new->data)
{
new->next = start;
temp = start;
while(temp->next != start)
{
temp = temp->next;
}
temp->next = new;
start = new;
return 0;
}
temp = start;
prev = start;
do{
prev = temp;
temp = temp->next;
}while((temp->next!=start)&&(temp->data < new->data));
if(temp!= start && temp->data > new->data)
{
new->next = temp;
prev->next = new;
return 0;
}
else if(temp->next == start)
{
temp->next = new;
new->next = start;
return 0;
}
}
void print()
{
struct node *temp;
printf("%d ",start->data);
temp = start->next;
while(temp != start)
{
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
return;
}
main()
{
insert(200);
insert(100);
insert(250);
insert(3250);
insert(2250);
print();
}
output : 100 200 250 2250 3250
import java.util.*;
class CircularLinkedList
{
public Node root = null;
public class Node
{
Node next = null;
int item;
public Node(int data)
{
item = data;
}
}
public Node sortedInsert(Node root, int data)
{
Node current = root;
Node newItem = new Node(data);
// Case1: LinkedList is none
if( current == null) { current = newItem; current.next = current; root = current;} // self loop, since its the only item
// Case2: inserting before the head node
if( current.item > data ){ newItem.next = current; current.next = newItem; root = newItem;}
// Case 3: inbetween
if(newItem.item > current.item)
{
while(current !=null){
if(current.next != null && current.next.item > newItem.item)
{
Node temp = current.next;
current.next = newItem;
current.next.next = temp;
break;
}
if(newItem.item > current.item && current.next.item == root.item) // is the last element
{
current.next = newItem;
current.next.next = root;
break;
}
current = current.next;
}
}
return root;
}
public void display(Node n)
{
Node current = n;
while(current != null)
{
System.out.println(current.item);
current = current.next;
if( current.item == n.item) break;
}
}
public static void main(String[] args)
{
CircularLinkedList cr = new CircularLinkedList();
System.out.println("After inserting 2");
cr.root = cr.sortedInsert(cr.root, 2);
cr.display(cr.root);
System.out.println("After inserting 1");
cr.root = cr.sortedInsert(cr.root, 1);
cr.display(cr.root);
System.out.println("After inserting 4");
cr.root = cr.sortedInsert(cr.root, 4);
cr.display(cr.root);
System.out.println("After inserting 3");
cr.root = cr.sortedInsert(cr.root, 3);
cr.display(cr.root);
System.out.println("After inserting 5");
cr.root = cr.sortedInsert(cr.root, 5);
cr.display(cr.root);
}
}
I think we cannot get anything better than O(n), because in case of inserting the largest element, we will have to traverse through all the list anyway.
Correct me if I am wrong, but the answer here is trivial. This would require O(1) memory and O(n) operations.
The special case: all the items are the same, we have to insert an item larger than that. This leads us to another interesting task: finding out the length of the structure. This is still O(1) memory and O(n) operations.
void insertNode(Node* &head, Node *node) {
// empty list
if (!head) {
head = node;
node->next = node;
return;
}
// insert before head
if (node->value <= head->value) {
Node *tail = head;
while (tail->next != head) tail = tail->next;
tail->next = node;
node->next = head;
head = node;
} else {
Node* it = head;
while (it->next != head) {
if (node->value > it->next->value) {
it = it->next;
continue;
}
// insert in the middle.
node->next = it->next;
it->next = node;
return;
}
// insert tail.
node->next = head;
it->next = node;
}
}
Algo :
1. keep a pointer which always pointing the head node say *root
2. take the value x
3. check if list is empty
if true
allocate new node
insert value x
on the next field put addr of root
return
4. else
take another pointer *p where p=root->next
while p!=root
check each node value with x
if location found
allocate new node
insert node
return
else
p=p->next
void Insert(Node*& head, Node* new_node) {
if (!head) {
head = new_node->next = new_node;
return;
}
for (Node* it = head; true; it = it->next) {
if ((new_node->val >= it->val && new_node->val <= it->next->val) ||
it->next == head) {
new_node->next = it->next;
it->next = new_node;
if (new_node->val < head->val)
head = new_node;
return;
}
}
}
void insertIntoACiruclarList(lNode * head , uint32_t number) {
lNode * currentNode = head;
while (currentNode->next->data >= currentNode->data) {
if (currentNode->data <= number && currentNode->next->data >= number)
break;
currentNode = currentNode->next;
}
// insert after currentNode
lNode * keepNext = currentNode->next;
lNode * newNode = new lNode();
newNode->data = number;
newNode->next = keepNext;
currentNode->next = newNode;
cout << "insert " << number << " between " << currentNode->data << " and " << currentNode->next->next->data << endl;
}
When traversing the linked list. All you need to know is weather the new value fits between the current node you are looking at and the next upcoming node. The following code uses XOR for this check. And will work for ascending as well as descending linked list.
public Node {
int val;
Node next;
}
public void insert(Node head, int value) {
Validate.notNull(head);
Node nNode = new Node(value);
if(start.next == start) {
start.next = nNode;
nNode.next = start;
}
Node curr = start;
Node next = start.next;
while(!(curr.value < start.value) ^ (next.value < start.value)) {
curr = next;
next = curr.next;
}
nNode.next = curr.next;
curr.next = nNode;
if(isHead(next)) {
updateHead(nNode);
}
}
Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data < new_node->data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;
Output:
1 2 11 12 56 90
Time Complexity: O(n) where n is the number of nodes in the given linked list.
Case 2 of the above algorithm/code can be optimized.
- gdg March 11, 2014