Microsoft Interview Question Jr. Software Engineers
Country: United States
Interview Type: In-Person
template <typename Type>
void insert(Node<Type>* headPtr, Type value) {
Node<Type>* prevPtr = headPtr;
while (headPtr != nullptr && headPtr->value < value) {
prevPtr = headPtr;
headPtr = headPtr.next;
}
Node<Type>* newNode = new Node<Type>(value);
prevPtr.next = newNode;
newNode.next = headPtr;
}
insert(node n){
if(first == null ) first = n;
else{
node current = first;
node previous = null;
while(current!= null && current.value<=n.value){
previous = current
current = current.next;
}
node.next = current;
if(previous!=null) previous.next=node
}
}
void sortedInsert(node *&head, node *newnode)
{
node *temp = head;
if(head == NULL || head->data >= newnode->data)
{
newnode->next = head;
head = newnode;
}
else
{
while(head->next != NULL && head->next->data < newnode->data)
{
head = head->next;
}
newnode->next = head->next;
head->next = newnode;
}
}
void sortedInsert(node *&head, node *newnode)
{
node *temp = head;
if(head == NULL || head->data >= newnode->data)
{
newnode->next = head;
head = newnode;
}
else
{
while(head->next != NULL && head->next->data < newnode->data)
{
head = head->next;
}
newnode->next = head->next;
head->next = newnode;
}
}
///
// List.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
struct node
{
node* pNext;
int data;
node (int nData) {data = nData;}
};
class List
{
node* pHead;
public:
List () {pHead = NULL;}
void print ();
node* lookUp (int nData);
void sortInsert (int Data);
void insertAfter (node* pNode, int nData);
};
void List::insertAfter (node* pNodePrev, int nData)
{
node* pNodeNew = new node (nData);
pNodeNew->pNext = pNodePrev->pNext;
pNodePrev->pNext = pNodeNew;
}
node* List::lookUp (int nData)
{
node* pItr = pHead;
node* pPrev = NULL;
while (pItr != NULL )
{
if (nData > pItr->data)
{
return pPrev;
}
pPrev = pItr->pNext;
if (pPrev)
pItr = pPrev->pNext;
else
return pItr;
}
return NULL;
}
void List::sortInsert (int nData)
{
node* pInsertAfter = lookUp (nData);
if (!pInsertAfter)
{
node* pNode = new node (nData);
pNode->pNext = pHead;
pHead = pNode;
return;
}
else
insertAfter (pInsertAfter, nData);
return;
}
void List::print ()
{
node* pItr = pHead;
while (pItr != NULL)
{
cout << pItr->data << " ";
pItr = pItr->pNext;
}
cout << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {1, 5, 23, 9, 32, 6};
List* l = new List;
for (int i = 0; i < sizeof(arr)/sizeof (int); i++)
l->sortInsert (arr[i]);
l->print ();
return 0;
}
\\\
// List.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
struct node
{
node* pNext;
int data;
node (int nData) {data = nData;}
};
class List
{
node* pHead;
public:
List () {pHead = NULL;}
void print ();
node* lookUp (int nData);
void sortInsert (int Data);
void insertAfter (node* pNode, int nData);
};
void List::insertAfter (node* pNodePrev, int nData)
{
node* pNodeNew = new node (nData);
pNodeNew->pNext = pNodePrev->pNext;
pNodePrev->pNext = pNodeNew;
}
node* List::lookUp (int nData)
{
node* pItr = pHead;
node* pPrev = NULL;
while (pItr != NULL )
{
if (nData > pItr->data)
{
return pPrev;
}
pPrev = pItr->pNext;
if (pPrev)
pItr = pPrev->pNext;
else
return pItr;
}
return NULL;
}
void List::sortInsert (int nData)
{
node* pInsertAfter = lookUp (nData);
if (!pInsertAfter)
{
node* pNode = new node (nData);
pNode->pNext = pHead;
pHead = pNode;
return;
}
else
insertAfter (pInsertAfter, nData);
return;
}
void List::print ()
{
node* pItr = pHead;
while (pItr != NULL)
{
cout << pItr->data << " ";
pItr = pItr->pNext;
}
cout << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {1, 5, 23, 9, 32, 6};
List* l = new List;
for (int i = 0; i < sizeof(arr)/sizeof (int); i++)
l->sortInsert (arr[i]);
l->print ();
return 0;
}
void insert(node **head, node *n){
{ node *iter=*head;
if (**head==NULL)
{ *head = n;
return;
}
while(iter->next!==NULL && iter->next->iter<n->i)
iter=iter->next;
n->next=iter->next;
iter->next=n;
return;
}
#include<iostream.h>
#include<string.h>
struct list_node
{
int data;
struct list_node *next;
};
void insert_list(struct list_node **start)
{
int idata;
struct list_node *temp;
cout << " Enter data to be inserted : " << endl;
cin >> idata;
temp=(*start);
if(*start == NULL)
{
(*start)=new list_node;
(*start)->data=idata;
(*start)->next=NULL;
}
else
{
while(temp != NULL )
{
if(temp->data > idata)
{
struct list_node *temp2=new struct list_node;
temp2->data=idata;
temp2->next=temp;
(*start)=temp2;
break;
}
else if(temp->next == NULL)
{
temp->next = new list_node;
temp->next->data=idata;
temp->next->next=NULL;
break;
}
else if(temp->data < idata && temp->next->data > idata)
{
struct list_node *temp2=new struct list_node;
temp2->next=temp->next;
temp2->data=idata;
temp->next=temp2;
break;
}
else
{
temp=temp->next;
}
}
}
}
void display(struct list_node *start)
{
struct list_node *temp;
temp=start;
while(temp!=NULL)
{
cout << temp->data << " -> " ;
temp=temp->next;
}
cout << endl;
}
int main()
{
struct list_node *start=NULL;
int i;
while(1)
{
cout << " You wanna insert new element? Press 1 else anyother key " << endl;
cin >> i;
if(i!=1)
break;
insert_list(&start);
display(start);
}
return 0;
}
struct Node* insert(struct Node* head,int x)
{
if(!head)return head;
struct Node* temp=(struct Node*)malloc(sizeof(struct Node*));
temp->val=x;
temp->next=NULL;
if(x<head->val)
{temp->next=head;
head=temp;}
struct Node* search=head;
while(search->next){
if(search->val<=x && x<=search->next->val)
{temp->next=search->next;
search->next=temp;
break;
}
}
if(!search->next)search->next=temp;
return head;
}
Implemented in C
#include<stdio.h>
#include<stdlib.h>
typedef struct listNode {
int item;
struct listNode * next;
} node;
node ** pHead;
node * createNode(int item) {
node * temp = (node *) malloc(sizeof(node));
temp->item = item;
temp->next = NULL;
return temp;
}
void insertNodeSorted(node * Head, int item) {
if (Head == NULL) {
(*pHead) = createNode(item);
}
else {
while (Head->next != NULL && Head->next->item < item)
Head = Head->next;
node * temp = Head->next;
Head->next = createNode(item);
Head->next->next = temp;
}
}
void displayNode(node * Head) {
while (Head != NULL) {
printf("%d ", Head->item);
Head = Head->next;
}
printf("\n");
}
int main() {
node * Head = NULL;
pHead = &Head;
insertNodeSorted(Head, 3);
insertNodeSorted(Head, 20);
insertNodeSorted(Head, 8);
insertNodeSorted(Head, 15);
insertNodeSorted(Head, 11);
displayNode(Head);
return 0;
}
4 lines
#include <list>
#include <iostream>
using namespace std;
//template <typename T, typename L, typename V>
void insert(std::list<int>::iterator begin, std::list<int>::iterator end, list<int> &list, const int &value)
{
std::list<int>::iterator next = begin; next++;
if (begin == end) list.insert(begin, value);
if (*begin < value) insert(next, end, list, value);
else list.insert(begin, value);
}
int main() {
list<int> l;
for (auto i : {1,3,5,7,9})
l.push_back(i);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
insert(l.begin(), l.end(), l, 4);
insert(l.begin(), l.end(), l, 3);
insert(l.begin(), l.end(), l, 5);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
return 0;
}
First version double inserted.
This version 5 lines.
#include <list>
#include <iostream>
using namespace std;
//template <typename T, typename L, typename V>
void insert(std::list<int>::iterator begin, std::list<int>::iterator end, list<int> &list, const int &value)
{
std::list<int>::iterator next = begin; next++;
if (begin == end) list.insert(begin, value);
else {
if (*begin < value) insert(next, end, list, value);
else list.insert(begin, value);
}
}
int main() {
list<int> l;
for (auto i : {1,3,5,7,9})
insert(l.begin(), l.end(), l, i);
//l.push_back(i);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
insert(l.begin(), l.end(), l, 4);
insert(l.begin(), l.end(), l, 3);
insert(l.begin(), l.end(), l, 5);
for (const auto &it : l)
std::cout << ' ' << it;
std::cout << '\n';
return 0;
}
I have been asked this question some 15 years ago and amazingly even today I don't see clean solution for it on the internet. This is why I posted here.
The right solution is this. Pay attention how the insert method is simple and concise:
#include <iostream> using namespace std; struct Node{ int value; Node* next; Node(int v){ value = v;} } *pHead; // the trick is in having a pointer to a pointer to a Node // this will allow to scan the linked list using one variable p // and insert on the head without any checking because every Node** p // represents all pointers (including the pHead variable) // all the algorithm is written in just 5 lines of code void insert (int v){ Node** p = &pHead; while(*p != NULL && v > (*p)->value) p = &(*p)->next; Node* n = new Node(v); n->next = *p; *p = n; } void display(){ Node* p = pHead; while (p != NULL){ cout << p->value << ", "; p = p->next; } } int main() { pHead = NULL; int array[] = {10, 5, 18, 40, 20, 15, 25, 0, 100, 50}; for(int i = 0; i < 10; i++ ){ insert(array[i]); } display(); return 0; }The output is:
- zsalloum May 03, 20150, 5, 10, 15, 18, 20, 25, 40, 50, 100