Google Interview Question for Software Engineer / Developers


Country: United States




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

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;

#include<stdio.h>
#include<stdlib.h>

/* structure for a node */
struct node
{
  int data;
  struct node *next;
};

/* function to insert a new_node in a list in sorted way.
   Note that this function expects a pointer to head node
   as this can modify the head of the input linked list */
void sortedInsert(struct node** head_ref, struct node* new_node)
{
  struct node* current = *head_ref;

  // Case 1 of the above algo
  if (current == NULL)
  {
     new_node->next = new_node;
     *head_ref = new_node;
  }

  // Case 2 of the above algo
  else if (current->data >= new_node->data)
  {
    /* If value is smaller than head's value then
      we need to change next of last node */
    while(current->next != *head_ref)
        current = current->next;
    current->next = new_node;
    new_node->next = *head_ref;
    *head_ref = new_node;
  }

  // Case 3 of the above algo
  else
  {
    /* Locate the node before the point of insertion */
    while (current->next!= *head_ref && current->next->data < new_node->data)
      current = current->next;

    new_node->next = current->next;
    current->next = new_node;
  }
}

/* Function to print nodes in a given linked list */
void printList(struct node *start)
{
  struct node *temp;

  if(start != NULL)
  {
    temp = start;
    printf("\n");
    do {
      printf("%d ", temp->data);
      temp = temp->next;
    } while(temp != start);
  }
}

/* Driver program to test above functions */
int main()
{
  int arr[] = {12, 56, 2, 11, 1, 90};
  int list_size, i;

  /* start with empty linked list */
  struct node *start = NULL;
  struct node *temp;

  /* Create linked list from the array arr[].
    Created linked list will be 1->2->11->56->12 */
  for(i = 0; i< 6; i++)
  {
    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = arr[i];
    sortedInsert(&start, temp);
  }

  printList(start);
  getchar();
  return 0;
}

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.

// Case 2 of the above algo
  else if (current->data >= new_node->data)
  {
    // swap the data part of head node and new node
    swap(&(current->data), &(new_node->data));  // assuming that we have a function swap(int *, int *)

    new_node->next = (*head_ref)->next;
    (*head_ref)->next = new_node;
  }

- gdg March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nicely done.
How about the case, when you need to insert after the last node? Will your code handle that?

- puneet.sohi March 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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?

- Anonymous March 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe that the optimal approach should be logn with binary search

- jigili August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ajeet March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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

- nani.m March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- maverick March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should have used
if
statement
else if
statement

instead of if followed by if.

- springs November 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- ilya.smagin March 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Deo March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- istiyak916 March 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zprogd August 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- nik September 20, 2015 | 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