Microsoft Interview Question
Program Managers InternsCountry: India
I am sorry, but this will not work. How would your Step 1 find the middle and the last when there is a loop in the LL?
Even Step 2 is wrong. You don't really need to care if you are deleting a middle node or any other node. Yes, there will be special handling if the node to be deleted is the last node to restore the loop.
SushantSingh1987 are you mad bro ? If u delete a node, then size of the linked list changes and so does the middle element in some cases. For example if there are 9 nodes and u delete any node, then size is 8, so middle element remains the same. But if there are 10 nodes and you delete 1, the the new middle is the previous node of the current middle. Hope you understand the point
**TO FIND THE LAST AND MIDDLE NODE**
1. use the fast and slow pointer to find a node in loop
2. count the number of nodes in the loop
3. if the count is k then ther are two possibilities
1. there are k+(k-1) nodes in sll
2. there are 2k nodes in sll
4. with this find the middle and last node of the sll
**DELETE THE GIVEN NODE**
now the delete the node, and point the last node to
1. if length of sll is odd, to the previous node
2. if even point to the next node
correct me, if i am wrong
: 4. with this find the middle and last node of the sll
how do you achieve this? how do you know which of the two possibilities from step 3 we have here?
package oracle.prakash.investmentbank.test;
public class MicrosoftStack<T extends Comparable> {
public MicrosoftStack() {
super();
}
public MicrosoftStack(T data) {
this.setData(data);
}
private MicrosoftStack<T> next;
private MicrosoftStack<T> prev;
private int count;
private MicrosoftStack<T> mid;
private MicrosoftStack<T> head;
private MicrosoftStack<T> tail;
private T data;
public static void main(String[] args) {
MicrosoftStack<Integer> microsoftStack = new MicrosoftStack<Integer>();
int[] ints = { 20, 30, 40, 50, 60, 70, 80,90 };
for (int i : ints) {
microsoftStack.push(i);
}
microsoftStack.traverse();
System.out.println("---------------------------------------");
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead());
System.out.println(microsoftStack.getTail());
System.out.println(microsoftStack.getMid());
}
public void push(T data) {
MicrosoftStack<T> item = new MicrosoftStack<T>(data);
this.setCount(this.getCount() + 1);
if (this.getHead() == null) {
this.setHead(item);
this.setMid(item);
this.setTail(item);
} else {
item.setNext(this.getHead());
this.getHead().setPrev(item);
this.setHead(item);
if (this.getCount() % 2 != 0) {
this.setMid(this.getMid().getPrev());
}
this.getTail().setNext(this.getMid());
}
}
public T pop() {
T data = null;
if (this.getHead() == null)
return null;
MicrosoftStack<T> head = this.getHead();
data = head.getData();
this.setCount(this.getCount() - 1);
this.setHead(head.getNext());
head.setNext(null);
if (this.getCount() % 2 != 0) {
this.setMid(this.getMid().getNext());
}
this.getTail().setNext(this.getMid());
if(this.getCount()==0) {
this.setHead(null);
this.setTail(null);
this.setMid(null);
}
return data;
}
public void traverse() {
MicrosoftStack<T> head = this.getHead();
while (head != null) {
System.out.println(head.getData());
head = head.getNext();
if (head.getData().equals(this.getTail().getData())) {
System.out.println(head.getData());
break;
}
}
}
public void setNext(MicrosoftStack<T> next) {
this.next = next;
}
public MicrosoftStack<T> getNext() {
return next;
}
public void setPrev(MicrosoftStack<T> prev) {
this.prev = prev;
}
public MicrosoftStack<T> getPrev() {
return prev;
}
public void setCount(int count) {
this.count = count;
}
public int getCount() {
return count;
}
public void setMid(MicrosoftStack<T> mid) {
this.mid = mid;
}
public MicrosoftStack<T> getMid() {
return mid;
}
public void setHead(MicrosoftStack<T> head) {
this.head = head;
}
public MicrosoftStack<T> getHead() {
return head;
}
public void setTail(MicrosoftStack<T> tail) {
this.tail = tail;
}
public MicrosoftStack<T> getTail() {
return tail;
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return data;
}
}
Hi,
I need a clarification from Saran.
Are we given access to only the node we need to delete and nothing else. What I mean here is in a SLL it is possible to delete a node with just the information of the node to be deleted and nothing else such as head , tail etc. Is such info available here
Thanks
I can think of two things here:
1. we have to maintain the property that last node is pointing to middle node, so when any node is deleted, change the last node pointer to one node in backward direction.
2. Delete the node and reset the pointers, for this we need to traverse the linked list and keep two pointers prevNode and currentNode. Once we find the node to be deleted then delete that node and reset the pointers.
find the middle element with slow and fast runner for a circularly linked list. find element that is before and after middle element. find lastElement by traversing until .next is the middle element for the second time. When deleting
if(even && element to be delete occurs before middle) {
middle = afterMiddle;
}
else if(odd && element to be delete occurs after middle) {
middle = beforeMiddle;
}
Last element will be anyway pointing to middle element so is finding middle node required? I think we should just find out where loop is starting, and that will be middle node. But looks like finding middle node is easier than finding loop.
Let's split the question into two parts :
1. One is to delete any node in the linked list.
2. To make the last node of a linked list point to the middle element.
First delete the node in the linked list in O(n) time.
Next start from the head node using two pointers, slow and fast.
Slow moves one node at a time and fast moves two nodes at a time.
When fast reaches the end of the list, slow will be pointing to the middle element in the list. Make the last node point to slow and we're done.
First find the middle node in the list
Make count no of elements on left and right of middle node (Node_left, Node_right)
(Node_left, Node_right) could be equal or Node_left = Node_right-1
Now when delete the random node in the list check if it is right or left of the middle node,
and change this count
on the basis of this count you have to then move middle right or left
if(Node_left < Node_right-1 )
move right
else if(Node_right <Node_left)
move left
We can take it with the cases:
Step 1: Try to find out the middle node and also the number of the nodes in the linked list whether they are even or odd.
How to: Start from Head (using fast and the slow pointers).
if fast -> next == slow (Then the number of nodes would be odd).
else if (fast->next->next == slow) then the number of nodes would be even.
Now after this iteration we would be able to get the pointer to the middle element and also to the last element in the linked list.
Step 2: Remove the node:
How To: Go to the desired node.
if the number of nodes are odd then after removal of the desired node the number of nodes would be even so the location of the middle element wont change.
In case there are odd nodes currently then the new middle node would be the node previous to the current middle node.
Note: Some special cases have to be taken care of.
1. If the desired node itself is the middle element.
2. If the desired node is the last element in the linked list.
ListNode* delete(ListNode* head, int key)
{
if (head == NULL) return head;
ListNode* slow = head, fast = head->next, slowPrev = NULL;
while (fast->next != slow)
{
slow = slow->next;
fast = fast->next;
if (fast->next != slow ) fast = fast->next;
}
fast->next = NULL // change the last to new middle and now try to delete the element.
ListNode* h = head, prev = NULL;
while (h != NULL ) {
if (h->val = key) {
if (h == new_middle) {
if (prev == NULL) { head = h->next; }
else { prev->next = h->next; last->next = h->next; }
break;
}
if (h == last) {
prev->next = new_middle;
delete h;
}
else { prev->next = h->next; delete h; break; }
}
else if (h == last) break;
else { h = h->next; }
}
return head;
}
Can we do it this way :--
(I m assuming that we know the number of nodes in the list. If not we can find it easily using cycle finding algo in the list.)
1. Simply delete the required node first as in SLL.
2. Now we know how many nodes remain in the list. Based on this restore the last node pointer which is pointing to the middle node.
Can we do it this way :--
(I m assuming that we know the number of nodes in the list. If not we can find it easily using cycle finding algo in the list.)
1. Simply delete the required node first as in SLL.
2. Now we know how many nodes remain in the list. Based on this restore the last node pointer which is pointing to the middle node.
i think thr will be several cases (after finding mid,end)
1 if node to be deleted is head : see if its mid
2.if node to be deleted is end : change end ptr
3.if node to be deleted is mid : see if odd length(mid will change to prev to mid) and if even length(mid will change to next to mid)
4.if node to be deleted is other : see if b4 mid(see if odd length then mid will change) else if after mid (see if even length then mid will not change)
tell if wrong line of thinking!
Can be done as following:
1. use two pointers with x and 2x speed to find the mid node and whether the length of array is even or odd.
2. traverse the list for second time to find the node to delete, while tracking if it comes before mid or not.
3. if length is odd and element to delete is mid or before mid, set newMid to next of mid. If length is even and deleted element is mid or after mid set newMid to prev of mid.
4. delete the node. if newMid is not NULL, set the end of modified list to newMid.
#include<stdlib.h>
typedef struct list_s {
int val;
struct list_s *next;
} list;
list *delete(list *head, int val)
{
if(head == NULL)
return head;
list *t1, *t2, *prev, *mid, *newMid = NULL;
enum {even, odd} length;
/*find the mid and length(odd/even) using two runners*/
t1 = head;
t2 = t1->next;
while(t1 != t2 && t1 != t2->next){
t1 = t1->next;
t2 = t2->next->next;
}
if(t1 == t2)
length = odd;
else
length =even;
mid = t1;
/*search for node to delete and track if node is previous to the mid*/
enum {false, true} isPrevToMid = true;
t1 = head;
prev = NULL;
while(t1->next != mid || isPrevToMid = true){
if(t1 == mid){
isPrevToMid = false;
/*if length is odd, newMid is prev element to mid*/
if(length == odd)
newMid = prev;
}
if(t1->val == val)
break;
prev = t1;
t1 = t1->next;
}
/*if node not found, return the same list*/
if(t1->val != val)
return head;
/*set newMid to next of mid if length is even and node to be deleted is prevToMid*/
if((isPrevToMid == true || t1 == mid) && length == even)
newMid = mid->next;
if(prev == NULL){ /*if the node is head, modify the head*/
if(head->next == head)
head = NULL;
else
head = head->next;
}
else /*else remove node from the list*/
prev->next = t1->next;
/* if newMid is not NULL, find the end node in the modified list and set it to newMid,*/
if(newMid != NULL){
t2 = t1;
while(t2->next != mid || isPrevToMid == true){
if(t2 == mid)
isPrevToMid = false;
t2 = t2->next;
}
t2->next = newMid;
}
free(t1);
return head;
}
Why make it complicated; when most (if not all) of the solutions require you to scan the list twice why not just follow the normal LL deletion logic.
1) scan the list and delete target node
2) scan the list and make last node point to the middle node (can achieve this by using slow and fast pointers)
We will need two pointers 'fast' and 'slow' to iterate the list.
fast=fast->next->next;
slow=slow->next;
conditions to check
1. if (fast->next==slow) //the list has odd number of nodes.
2. if (fast->next->next==slow) //the list has even number of nodes.
Now we have pointer to middle node and a pointer to last node.
check if the node to be deleted is before or after the middle node or its middle node or last node.Proceed with deletion and update the list accordingly ( even and odd criteria as stated in problem)
Logic is as follows:
Break the logic into two functions :
deleteNode(Node head, int k) and updateTailNext(Node head)
a) deleteNode(Node head, int k)
1. if(given value == head.data) ;
then update the head pointer, Linked List size --; return head;
2. else ,
create slow and fast pointer, fast pointer is one step ahead of slow pointer.
increment fast pointer until fast.data == given or fast ==null;
Linked List size --; return head;
b)updateTailNext(Node head)
(Note: index is 0 based)
if(size%2 == 0){
newMiddle = this.getNodeAtIndex((size -2)/2);
}else {
newMiddle = this.getNodeAtIndex((size)/2);
}
public class DeleteNodeTailMiddle extends LinkedList {
public Node deleteNode(Node head, int k){
int size = this.getSize();
Node slow = head;
Node fast =head;
if(head.data == k){
head = head.next;
size --;
this.setHead(head);
this.setSize(size);
return head;
}
while(fast != null && fast.data != k){
slow =fast;
fast = fast.next;
}
slow.next = fast.next;
fast = null;
size --;
this.setSize(size);
return head;
}
public Node updateTailNext(Node head){
int size = this.getSize();
Node Tail =this.getNodeAtIndex(size-1);
Node newMiddle ;
if(size%2 == 0){
newMiddle = this.getNodeAtIndex((size -2)/2);
}else {
newMiddle = this.getNodeAtIndex((size)/2);
}
System.out.println("newMiddle is :" + newMiddle.data +"\n");
Tail.next = newMiddle;
return head;
}
public static void main(String[] args){
DeleteNodeTailMiddle l = new DeleteNodeTailMiddle();
l.add(0,10);
l.add(1,12);
l.add(2,2);
l.add(3,3);
l.add(4, 45);
System.out.println("After adding elements \n");
l.display();
//Set the loop/ set the last node's next to the middle node in given input
Node head = l.getHead();
Node head2 = l.updateTailNext(head);
//delete the Node with value k = 45
int k = 45;
Node head3 = l.deleteNode(head2, k);
Node head4 = l.updateTailNext(head3);
}
}
public class LinkedList {
private Node head;
private int size;
public LinkedList(){
head =null;
}
public void add(int index, int value){
if(index ==0){
Node tmp = new Node(value);
tmp.next = head;
head= tmp;
size ++;
}else{
Node current = goTo(index-1);
Node newNode = new Node(value);
newNode.next = current.next;
current.next =newNode;
size ++;
}
}
public Node getNodeAtIndex(int x){
Node node = this.getHead();
int size= getSize();
if(x>size){
return null;
}
for (int i =0;i<size;i++){
if(i== x){ break;}
node = node.next;
}
return node;
}
public void setSize(int size){
this.size = size;
}
public void setHead(Node h){
head = h;
}
}
void printList(){
lNode curr = head;
lNode mid = head;
lNode prev = null;
int count = 0;
while(curr!=null){
System.out.println(curr.value + " ");
if(curr.next==null){
curr.next = mid;
}
if(count%2==0){
prev = curr;
curr=curr.next;
}
else{
prev=curr;
curr=curr.next;
mid = mid.next;
}
count++;
}
You can do normal delete function and when accessing the list, call this function.
**TO FIND THE LAST AND MIDDLE NODE**
1. use the fast and slow pointer to find a node in loop
2. count the number of nodes in the loop
3. if the count is k then ther are two possibilities
1. there are k+(k-1) nodes in sll
2. there are 2k nodes in sll
4. with this find the middle and last node of the sll
**DELETE THE GIVEN NODE**
now the delete the node, and point the last node to
1. if length of sll is odd, to the previous node
2. if even point to the next node
comment if anything wrong.
Not exactly.
The steps should be as follows:
1. use a fast and a slow pointer to find the middle node and the last node and the node before the middle node, and also count the number of nodes in the list.
2. from the head, find the node containing the target value, and its previous node.
3. adjust the next pointer of the last node.
4. delete the target node.
public class LinkedListNode
{
public LinkedListNode next=null;
public int val=Integer.MIN_VALUE;
public LinkedListNode(int v)
{
this(v, null);
}
public LinkedListNode(int v, LinkedListNode node)
{
val=v;
next=node;
}
public String toString()
{
return String.format("[LinkedListNode: val=%d]", val);
}
public String toStringAll()
{
return String.format("[LinkedListNode: val=%d, next=%s]", val, (next!=null) ? next.toStringAll() : null);
}
}
public class ID24819662
{
public LinkedListNode delete(LinkedListNode head, int target)
{
if (head==null)
return null;
else if (head.next==head)
{// only one node
if (head.val==target)
return null;
else
return head;
}
else if (head.next.next==head)
{// two nodes
LinkedListNode node=head;
while (node.val!=target)
{
node=node.next;
if (node==head)// no target node
return head;
}
if (node==head)
{
LinkedListNode newHead=head.next;
newHead.next=newHead;
return newHead;
}
else
{
head.next=head;
return head;
}
}
// 1. use a fast and a slow pointer to find the middle node
// and the last node and the node before the middle node,
// and also count the number of nodes in the list.
LinkedListNode beforeMiddle=null;
LinkedListNode middle=null;
LinkedListNode last=null;
LinkedListNode slow=head;
LinkedListNode fast=head;
int countNodes=1;
while (true)
{
beforeMiddle=slow;
slow=slow.next;
fast=fast.next.next;
countNodes += 2;
if (fast.next==slow)
{// odd number of nodes
middle=slow;
last=fast;
break;
}
else if (fast.next.next==slow)
{// even number of nodes
countNodes++;
middle=slow;
last=fast.next;
break;
}
}
// 2. from the head, find the node containing the target value, and its previous node.
LinkedListNode previous=null;
LinkedListNode node=head;
boolean passedMiddle=false;
while (true)
{
if (node==middle)
passedMiddle=true;
if (node.val==target)
break;
previous=node;
node=node.next;
if (passedMiddle && node==middle)// no such node found
return head;
}
LinkedListNode newHead=(node==head) ? head.next : head;
// 3. adjust the next pointer of the last node
if (!passedMiddle)
{
if ((countNodes&1)==0)// even number of nodes
last.next=middle.next;
// if odd number of nodes, do nothing
}
else if (node==middle)
{
if ((countNodes & 1) == 1)// odd number of nodes
last.next = beforeMiddle;
else
last.next=middle.next;
}
else if (passedMiddle)
{
if ((countNodes&1)==1)// odd number of nodes
last.next=beforeMiddle;
// if even number of nodes, do nothing
}
// 4. delete the node
if (previous!=null)
previous.next=node.next;
return newHead;
}
public static void main(String[] args)
{
LinkedListNode head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
System.out.println(head.toString());
ID24819662 wpd=new ID24819662();
wpd.delete(head, 4);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 10);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 2);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 0);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 1);
head=new LinkedListNode(0,
new LinkedListNode(1,
new LinkedListNode(2,
new LinkedListNode(3,
new LinkedListNode(4,
new LinkedListNode(5))))));
head.next.next.next.next.next.next=head.next.next;
wpd.delete(head, 5);
}
}
So isn't there a much simpler solution than looping through the list? I believe so.
First let's utilize a list.size() function to return the size of the list. That will help us find even/odd.
Now when a node is deleted from anywhere in the list, we find the middle element via:
if(list.size() %2 == 0)
mid = list.size()/2
else
mid = ciel(list.size()/2)
Note that the ciel function rounds up to the next largest int. You could also allow it to divice, truncate the remainder, then simply add 1.
Either way, we now know our middle location based on the size of the list after deletion. Now simply iterate through your list to that element (mid) and set the end node mid-pointer to that.
If our list has a built in pointer to the end, this becomes very easy as we do not need to loop through to find the end. We do have to design for the edge case that occurs when we delete the end node though.
It would be a two step process.
- Murali Mohan August 06, 20131. In step 1, start two pointers, one moving ahead one node at a time and the other two nodes at a time. This lets us find out the middle and the last element.
2. In step 2, using 3-pointer mechanism that points to previous, current and next nodes, delete the given node. Handle the special case of adjusting the pointers if the deleted node is the middle node.(The middle and last-element pointers obtained in step 1 are used here) Otherwise fix, the pointers or previous, current and next nodes regularly along with fixing the pointer to the middle node from the last node.