Amazon Interview Question
SDE1sCountry: India
If the current value is -ve then we will come into another while loop. Here our aim is to check if their sum is equal to zero or not.
So the sum statement will be :-
sum += stack.pop().value()
not sum -= stack.pop().value()
Because we already know stack is containing +ve values and we are substracting it with -Ve values.
mathematical ---> ( " + " + " -" ) = "-".
I hope it will help you.
// assumes negative numbers are after positive numbers in list
Node removeCancellableNodes(Node listHead)
{
if (listHead == null)
{
return null;
}
Stack<Node> stack = new Stack<Node>();
Node node = listHead;
while(node != null)
{
if (node.value < 0)
{
int sum = node.value;
while (!stack.isEmpty())
{
Node temp = stack.pop();
sum += temp.value;
if (sum == 0)
{
temp = stack.peek();
if(temp==null)
{
listHead = node->next;
}
else
{
temp->next = node->next;
}
break;
}
}
}
else
{
stack.push(node);
}
node = node.next;
}
return listHead;
}
I think there should be another constraint that
only "sub-sequences" (i.e., consecutive in the list) summed to zero can be removed.
If there is no such limitation, I believe this is NP problem.
(correct me if I am wrong)
In this case we can enumerate all the sub-sequence by using
two pointers, namely, start and end; i.e., O(n^2) algorithm.
(assumed we use a head node of the same type LNode)
struct LNode
{
int data;
shared_ptr<LNode> next;
LNode(int d) : data(d){};
};
void cancelOut(shared_ptr<LNode> &head)
{
shared_ptr<LNode> start = head;
shared_ptr<LNode> end;
while(start){
end = start->next;
int sum = 0;
bool modified = false;
while(end){
sum += end->data;
if(sum == 0){
start->next = end->next;
modified = true;
break;
}
end = end->next;
}
if(!modified)
start = start->next;
}
}
Test results:
Test 0
original: {6, -6, 8, 4, -12, 9, 8, -8}
canceled out: {9}
Test 1
original: {4, 6, -10, 8, 9, 10, -19, 10, -18, 20, 25}
canceled out: {20, 25}
struct LNode
{
int data;
shared_ptr<LNode> next;
LNode(int d) : data(d){};
};
void cancelOut(shared_ptr<LNode> &head)
{
shared_ptr<LNode> start = head;
shared_ptr<LNode> end;
shared_ptr<LNode> newHead;
while(start){
end = start->next;
int sum = start->data;
bool modified = false;
while(end){
sum += end->data;
if(sum == 0){
start->next = end->next;
modified = true;
break;
}
end = end->next;
}
if(!modified)
newHead= start;
start = start->next;
}
}
this code uses recursion so given a root goes till end while checking for count of 0.
and this recurses with root->next. so basically it goes to the end and starts coming back one by one so the time it completes all the continuous elements equalling to 0 are removed
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node * new_node(int data)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = data;
temp->next = NULL;
return temp;
}
void print_list(struct node *root)
{
while (root != NULL)
{
cout << root->data << " => ";
root = root ->next;
}
cout << endl;
}
struct node *get_list(struct node* root)
{
if(root == NULL)
return NULL;
int cnt = 0;
struct node *temp = root;
root->next = get_list(root->next);
//print_list(root);
while(temp != NULL)
{
cnt = cnt + temp->data;
if(cnt == 0)
{
cout << " found place to redcue" << endl;
if (temp->data == root->data)
root = temp->next;
else
root = temp->next;
}
temp = temp->next;
}
return root;
}
int main()
{
struct node *head,*temp;
head = new_node(4);
temp = head;
temp->next = new_node(6);
temp = temp->next;
temp->next = new_node(-10);
temp = temp->next;
temp->next = new_node(8);
temp = temp->next;
temp->next = new_node(9);
temp = temp->next;
temp->next = new_node(10);
temp = temp->next;
temp->next = new_node(-19);
temp = temp->next;
temp->next = new_node(10);
temp = temp->next;
temp->next = new_node(-18);
temp = temp->next;
temp->next = new_node(20);
temp = temp->next;
temp->next = new_node(25);
temp = temp->next;
print_list(head);
struct node *final = get_list(head);
print_list(final);
}
//O(n) time where N is the size of the linked list. O(n) space.
public class Node
{
int value;
Node next;
}
private Node stripZeros(Node n)//Assuming nodes with value 0 should be removed.
{
Node s=n;
Node f=s.next;
while(f!=null)
{
if(f.value==0)
{
s.next=f.next;
}else
{
s=f;
}
f=f.next;
}
return n;
}
public Node removeZeroSum(Node n)
{
if(n==null||n.value==0)
{
return null;
}
n=stripZeros(n);
Deque<Integer> stack=new LinkedList<Integer>();
HashMap<Integer,Node> mp=new HashMap<Integer,Node>();
int sum=0;
Node v=n;
while(v!=null)
{
sum+=v.value;
if(mp.containsKey(sum))
{
while(stack.peekLast()!=sum)
{
int top=stack.removeLast();
mp.remove(top);
}
mp.get(sum).next=v;
}else if (sum==0)
{
n=v.next;
mp=new HashMap<Integer,Node>();
stack=new LinkedList<Integer>();
}else
{
stack.addLast(sum);
mp.put(sum,v);
}
v=v.next;
}
return n;
}
//O(n) time where N is the size of the linked list. O(n) space.
public class Node
{
int value;
Node next;
}
private Node stripZeros(Node n)//Assuming nodes with value 0 should be removed.
{
Node s=n;
Node f=s.next;
while(f!=null)
{
if(f.value==0)
{
s.next=f.next;
}else
{
s=f;
}
f=f.next;
}
return n;
}
public Node removeZeroSum(Node n)
{
if(n==null||n.value==0)
{
return null;
}
n=stripZeros(n);
Deque<Integer> stack=new LinkedList<Integer>();
HashMap<Integer,Node> mp=new HashMap<Integer,Node>();
int sum=0;
Node v=n;
while(v!=null)
{
sum+=v.value;
if(mp.containsKey(sum))
{
while(stack.peekLast()!=sum)
{
int top=stack.removeLast();
mp.remove(top);
}
mp.get(sum).next=v;
}else if (sum==0)
{
n=v.next;
mp=new HashMap<Integer,Node>();
stack=new LinkedList<Integer>();
}else
{
stack.addLast(sum);
mp.put(sum,v);
}
v=v.next;
}
return n;
}
Data Structure: Stack (Assuming that negative numbers are added after positive numbers)
int main () {
stack<int> num;
int arraySize,data, sum=0;
cout<<"Enter array size: ";
cin>>arraySize;
for (int i=0; i< arraySize; i++) {
cin >> data;
if (data > 0) {
num.push(data);
} else {
while (data <0) {
int top = num.top();
num.pop();
data += top;
}
}
}
int size =num.size();
for (int i=0; i<size; i++) {
cout << num.top() << " ";
num.pop();
}
return 0;
}
Data Structure: Stack (#assuming that the negative numbers are there after negative numbers)
int main () {
stack<int> num;
int arraySize,data, sum=0;
cout<<"Enter array size: ";
cin>>arraySize;
for (int i=0; i< arraySize; i++) {
cin >> data;
if (data > 0) {
num.push(data);
} else {
while (data <0) {
int top = num.top();
num.pop();
data += top;
}
}
}
int size =num.size();
for (int i=0; i<size; i++) {
cout << num.top() << " ";
num.pop();
}
return 0;
}
stack seems to be the best solution here.
eg: 4, 6, -10, 8, 9, 10, -19, 10, 18, 20 25
int cancellationList(struct node* root)
{
stack<int>s;
temp=root;
while(temp)
{
if(temp->data > 0)
{
s.push(temp->data);
//temp=temp->next;
}
else if(arr[i]<0)
{
int x=s.pop();
while( (arr[i]-x) !=0) && (/**check for stack not empty**/)
{
x +=s.pop();
}
//temp=temp->next;
}
temp=temp->next;
}
int result=0;
if(/**stack empty**/)
return result;
while(/**stack not empty**/)
{
result += s.pop();
}
return result;
}
Keep a running sum, with two runners `start` and `end` that check the subsequences
O(n) and constant space
Node removeRedundantNodes(Node head)
{
if (head == null || head.next == null)
return head;
Node start = head;
Node end = head; // or Node end = start;
int sum = 0;
while (start != null || end != null)
{
sum += end.value;
if (sum == 0)
{
// found a redundant sub-sequence!
start = end.next;
end = start;
}
else
{
end = end.next;
}
}
return start;
}
Counter example:
8, 7, 10, 9, -19, ...
by the time 'end' reaches -19, sum = 34.
34 -19 = 15 different than 0...
public static void main(String arr[])
{
// 6 -6 8 4 -12 9 -8 8
Practice prc = new Practice();
Node head1 = (prc).new Node(3);
Node head2 = (prc).new Node(4);
Node head3 = (prc).new Node(6);
Node head4 = (prc).new Node(-10);
Node head5 = (prc).new Node(8);
Node head6 = (prc).new Node(9);
Node head7 = (prc).new Node(10);
Node head8 = (prc).new Node(-19);
Node head9 = (prc).new Node(10);
Node head10 = (prc).new Node(-188);
Node head11 = (prc).new Node(20);
Node head12 = (prc).new Node(25);
head1.next = head2;
head2.next = head3;
head3.next = head4;
head4.next = head5;
head5.next = head6;
head6.next = head7;
head7.next = head8;
head8.next = head9;
head9.next = head10;
head10.next = head11;
head11.next = head12;
canceloutStuff(head1);
System.out.print(head1);
}
public static Node canceloutStuff(Node node)
{
List<Node> list = new ArrayList<Node>();
int prevItem = 0;
while (node != null)
{
if (list.size() > 0)
{
int item = node.data;
if ((item * prevItem) < 0)
{
int sum = 0;
int index = -1;
for (int j = list.size() - 1; j >= 0; j--)
{
sum = sum + list.get(j).data;
if ((sum + item) == 0)
{
index = j;
break;
}/*
* else if (sum > item) { break; }
*/
}
if (index != -1)
{
for (int j = index; j < list.size(); j++)
{
list.get(j).data = 0;
}
node.data = 0;
} else
{
prevItem = node.data;
}
list.add(node);
} else
{
list.add(node);
prevItem = node.data;
}
} else
{
list.add(node);
prevItem = node.data;
}
node = node.next;
}
System.out.println(list);
Node prev = null, head = null;
for (Node nod : list)
{
if (nod.data != 0)
{
if (prev != null)
{
prev.next = nod;
}
if (prev == null)
{
head = nod;
}
prev = nod;
}
}
System.out.println(head);
return head;
}
public static void main(String arr[])
{
// 6 -6 8 4 -12 9 -8 8
Practice prc = new Practice();
Node head1 = (prc).new Node(3);
Node head2 = (prc).new Node(4);
Node head3 = (prc).new Node(6);
Node head4 = (prc).new Node(-10);
Node head5 = (prc).new Node(8);
Node head6 = (prc).new Node(9);
Node head7 = (prc).new Node(10);
Node head8 = (prc).new Node(-19);
Node head9 = (prc).new Node(10);
Node head10 = (prc).new Node(-188);
Node head11 = (prc).new Node(20);
Node head12 = (prc).new Node(25);
head1.next = head2;
head2.next = head3;
head3.next = head4;
head4.next = head5;
head5.next = head6;
head6.next = head7;
head7.next = head8;
head8.next = head9;
head9.next = head10;
head10.next = head11;
head11.next = head12;
canceloutStuff(head1);
System.out.print(head1);
}
public static Node canceloutStuff(Node node)
{
List<Node> list = new ArrayList<Node>();
int prevItem = 0;
while (node != null)
{
if (list.size() > 0)
{
int item = node.data;
if ((item * prevItem) < 0)
{
int sum = 0;
int index = -1;
for (int j = list.size() - 1; j >= 0; j--)
{
sum = sum + list.get(j).data;
if ((sum + item) == 0)
{
index = j;
break;
}/*
* else if (sum > item) { break; }
*/
}
if (index != -1)
{
for (int j = index; j < list.size(); j++)
{
list.get(j).data = 0;
}
node.data = 0;
} else
{
prevItem = node.data;
}
list.add(node);
} else
{
list.add(node);
prevItem = node.data;
}
} else
{
list.add(node);
prevItem = node.data;
}
node = node.next;
}
System.out.println(list);
Node prev = null, head = null;
for (Node nod : list)
{
if (nod.data != 0)
{
if (prev != null)
{
prev.next = nod;
}
if (prev == null)
{
head = nod;
}
prev = nod;
}
}
System.out.println(head);
return head;
}
The problem sounds like a variation of the subset sum problem. (See Wikipedia.) If you sum the entire list, then the sum is equivalent to the sum of the subset that remains after you remove all of the subsets that sum up to zero.
I did a breadth first search variation, because we want the shortest subset that sums to our target, so it doesn't contain additional subsets that sum to zero. I was a little lazy and just printed out the subset, but code could easily be modified to return the list.
class Solution {
public static class Potential {
int sum;
List<Integer> partial;
List<Integer> remaining;
public Potential(int s, List<Integer> p, List<Integer> r) {
sum = s;
partial = p;
remaining = r;
}
public String toString()
{
return "(" + sum + ", " + Arrays.toString(partial.toArray())
+ ", " + Arrays.toString(remaining.toArray()) + ")";
}
}
static void subsetSum_BFS(List<Integer> numbers, int target) {
Queue<Potential> queue = new LinkedList<>();
Potential start = new Potential(0, new ArrayList<Integer>(), numbers);
queue.add(start);
while (!queue.isEmpty()) {
Potential current = queue.remove();
int sum = current.sum;
for (int i = 0; i < current.remaining.size(); i++) {
List<Integer> remaining = new ArrayList<Integer>();
int n = current.remaining.get(i);
sum += n;
List<Integer> partial = new ArrayList<>(current.partial);
partial.add(n);
if (sum == target) {
System.out.println("sum="+target);
System.out.println(Arrays.toString(partial.toArray()));
return;
}
for (int j= i + 1; j < current.remaining.size(); j++) {
remaining.add(current.remaining.get(j));
}
Potential next = new Potential(sum, partial, remaining);
queue.add(next);
sum -= n;
}
}
System.out.println("Matching subset not found.");
}
static void removeZeroSum(List<Integer> numbers) {
int sum = 0;
for (Integer n : numbers) {
sum += n;
}
System.out.println("target="+sum);
if (sum == 0) {
System.out.println("[]");
System.out.println("Subset empty, bypassing search.");
return;
}
subsetSum_BFS(numbers, sum);
}
public static void main(String[] args) {
// case 1: 6 -6 8 4 -12 9 -8 8
// O/P : 9
Integer[] case1 = {6, -6, 8, 4, -12, 9, -8, 8};
List<Integer> case1List = new LinkedList<>(Arrays.asList(case1));
removeZeroSum(case1List);
// case 2: 20, 5, 6, 10, -11, 10, 2, 2
// O/P : 20 2 2
Integer[] case2 = {20, 5, 6, 10, -11, -10, 2, 2};
List<Integer> case2List = new LinkedList<>(Arrays.asList(case2));
removeZeroSum(case2List);
// case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
// O/P : 20 25
Integer[] case3 = {4, 6, -10, 8, 9, 10, -19, 10, -18, 20, 25};
List<Integer> case3List = new LinkedList<>(Arrays.asList(case3));
removeZeroSum(case3List);
}
}
Much like the subset sum problem, the worst case time complexity is exponential because we can't assume the values are non-negative and hence can't eliminate combinations. So worst case O(2^N*N) when there are no subsets that sum to zero, since there are 2N subsets and, to check each subset, we need to sum at most N elements. Best case would be O(N), when the list sums to zero, because we don't have to check any and the result is just an empty list.
Tested in C# and works fine:
private static void solve(Node head)
{
Stack<int> lst = new Stack<int>();
for(Node cur = head; cur!=null; cur=cur.Next)
{
if (cur.Data == 0) continue;
Stack<int> tmp = new Stack<int>();
int sum = cur.Data;
while ((cur.Data < 0 ? sum < 0 : sum > 0) && lst.Count > 0)
{
var puttotmp = lst.Pop();
tmp.Push(puttotmp);
sum += puttotmp;
}
if (sum != 0)
{
while (tmp.Count > 0)
lst.Push(tmp.Pop());
lst.Push(cur.Data);
}
}
Stack<int> revlst = new Stack<int>();
while (lst.Count > 0)
revlst.Push(lst.Pop());
while (revlst.Count > 0)
Console.Write(revlst.Pop() + " ");
}
import java.util.HashMap;
/*
* class Node<T>
* {
* T data;
* Node<T> next;
*
* public Node<T>(T data)
* {
* this.data=data;
* next=null;
* }
*
*/
public class DeleteSubstringSum {
public static Node<Integer> delete(Node<Integer> head)
{
HashMap<Integer,Node<Integer>> map=new HashMap<>();
Node<Integer> temp=head;
map.put(0, null);
map.put(head.data,head);
int a=head.data;
temp=temp.next;
while(temp!=null)
{
a+=temp.data;
if(a==0)
head=temp.next;
else if(map.containsKey(a))
{
Node<Integer> val=map.get(a);
val.next=temp.next;
}
else
{
map.put(a, temp);
}
temp=temp.next;
}
return head;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node<Integer> temp=InputOutput.insert();
InputOutput.print(delete(temp));
}
}
import java.util.HashMap;
/*
* class Node<T>
* {
* T data;
* Node<T> next;
*
* public Node<T>(T data)
* {
* this.data=data;
* next=null;
* }
*
*/
public class DeleteSubstringSum {
public static Node<Integer> delete(Node<Integer> head)
{
HashMap<Integer,Node<Integer>> map=new HashMap<>();
Node<Integer> temp=head;
map.put(0, null);
map.put(head.data,head);
int a=head.data;
temp=temp.next;
while(temp!=null)
{
a+=temp.data;
if(a==0)
head=temp.next;
else if(map.containsKey(a))
{
Node<Integer> val=map.get(a);
val.next=temp.next;
}
else
{
map.put(a, temp);
}
temp=temp.next;
}
return head;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node<Integer> temp=InputOutput.insert();
InputOutput.print(delete(temp));
}
}
import java.util.HashMap;
/*
* class Node<T>
* {
* T data;
* Node<T> next;
*
* public Node<T>(T data)
* {
* this.data=data;
* next=null;
* }
*
*/
public class DeleteSubstringSum {
public static Node<Integer> delete(Node<Integer> head)
{
HashMap<Integer,Node<Integer>> map=new HashMap<>();
Node<Integer> temp=head;
map.put(0, null);
map.put(head.data,head);
int a=head.data;
temp=temp.next;
while(temp!=null)
{
a+=temp.data;
if(a==0)
head=temp.next;
else if(map.containsKey(a))
{
Node<Integer> val=map.get(a);
val.next=temp.next;
}
else
{
map.put(a, temp);
}
temp=temp.next;
}
return head;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Node<Integer> temp=InputOutput.insert();
InputOutput.print(delete(temp));
}
}
def answer(node):
head = None
stack = []
curSum = 0
while node:
if node.data > 0:
curSum += node.data
stack.append(node)
node = node.next
else:
finalValue = curSum + node.data
while stack:
value = stack.pop()
curSum -= value.data
if curSum == finalValue:
break
node = node.next
previous = None
for x in stack:
if not head:
head = x
previous = x
else:
previous.next = x
previous = x
return head
def traverse(node):
while node:
print(node.data)
node = node.next
public static Node removeAdjNodeWith0Sum(Node head) {
int sum = 0, subSum;
Map<Integer, Node> sumMap = new HashMap<>();
Node node = head, sumNode;
while(node != null) {
sum+=node.data;
if(sum == 0) {
subSum = sum;
while(head != node.next) {
subSum += head.data;
sumMap.remove(subSum);
head = head.next;
}
} else {
sumNode = sumMap.get(sum);
if(sumNode == null) {
sumMap.put(sum, node);
} else {
subSum = sum;
while(sumNode.next != node.next) {
subSum += sumNode.next.data;
sumMap.remove(subSum);
sumNode.next = sumNode.next.next;
}
}
}
node = node.next;
}
return head;
}
if (Head.next == null) return;
Node PrevNode = Head;
Node CurrNode = Head;
Stack<int> ST = new Stack<int>();
while(PrevNode!=null || CurrNode != null)
{
if (CurrNode == null)
{
ST.Push(PrevNode.data);
PrevNode = PrevNode.next;
CurrNode = PrevNode;
sum = 0;
}
sum = sum+CurrNode.data;
if (sum == 0)
{
PrevNode = CurrNode.next;
CurrNode = PrevNode;
}
else
{
CurrNode = CurrNode.next;
}
}
foreach(int a in ST)
{
Console.WriteLine(a);
}
public class CancelSum {
class Node {
int k;
Node next;
public Node(int k) {
this.k = k;
next = null;
}
}
Node head;
public void insert(int k) {
if (head == null) {
head = new Node(k);
return;
}
Node n = head;
while (n.next != null) {
n = n.next;
}
n.next = new Node(k);
}
public void finddMid() {
Node slow_ptr = head;
Node fast_ptr = head;
while (fast_ptr != null && fast_ptr.next != null) {
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
System.out.println("The mid element is at: " + slow_ptr.k);
}
public void print() {
Node n = head;
while (n != null) {
System.out.print(n.k + " ");
n = n.next;
}
System.out.println();
}
public void cancel() {
Node n = head;
while (n != null) {
if (findMatch(n.k)) {
delete(n.k);
delete(-n.k);
}
n = n.next;
}
}
public boolean findMatch(int t) {
Node n = head;
while (n != null) {
int y = n.k;
if ((y + t) == 0) {
return true;
}
n = n.next;
}
return false;
}
public void delete(int k) {
Node n = head;
Node prev = null;
if (n != null && n.k == k ) {
n = head.next;
return ;
}
while (n != null && n.k != k) {
prev = n;
n = n.next;
}
if ( n == null) return;
prev.next = n.next;
}
public static void main(String[] args) {
CancelSum md = new CancelSum();
md.insert(12);
md.insert(-6);
md.insert(555);
md.insert(-555);
md.insert(333);
md.print();
md.finddMid();
md.cancel();
md.print();
}
}
///class Node():
def __init__(self,data):
self.data = data
self.next = None
class Linkedlist():
def __init__(self):
self.head = None
def append(self,data):
new_node = Node(data)
h = self.head
if self.head is None:
self.head = new_node
return
else:
while h.next!=None:
h = h.next
h.next = new_node
def remove_zeros_from_linkedlist(self, head):
stack = []
curr = head
list = []
while (curr):
if curr.data >= 0:
stack.append(curr)
else:
temp = curr
sum = temp.data
flag = False
while (len(stack) != 0):
temp2 = stack.pop()
sum += temp2.data
if sum == 0:
flag = True
list = []
break
elif sum > 0:
list.append(temp2)
if not flag:
if len(list) > 0:
for i in range(len(list)):
stack.append(list.pop())
stack.append(temp)
curr = curr.next
return [i.data for i in stack]
if __name__ == "__main__":
l = Linkedlist()
l.append(4)
l.append(6)
l.append(-10)
l.append(8)
l.append(9)
l.append(10)
l.append(-19)
l.append(10)
l.append(-18)
l.append(20)
l.append(25)
print(l.remove_zeros_from_linkedlist(l.head))\\\
class Node():
def __init__(self,data):
self.data = data
self.next = None
class Linkedlist():
def __init__(self):
self.head = None
def append(self,data):
new_node = Node(data)
h = self.head
if self.head is None:
self.head = new_node
return
else:
while h.next!=None:
h = h.next
h.next = new_node
def remove_zeros_from_linkedlist(self, head):
stack = []
curr = head
list = []
while (curr):
if curr.data >= 0:
stack.append(curr)
else:
temp = curr
sum = temp.data
flag = False
while (len(stack) != 0):
temp2 = stack.pop()
sum += temp2.data
if sum == 0:
flag = True
list = []
break
elif sum > 0:
list.append(temp2)
if not flag:
if len(list) > 0:
for i in range(len(list)):
stack.append(list.pop())
stack.append(temp)
curr = curr.next
return [i.data for i in stack]
if __name__ == "__main__":
l = Linkedlist()
l.append(4)
l.append(6)
l.append(-10)
l.append(8)
l.append(9)
l.append(10)
l.append(-19)
l.append(10)
l.append(-18)
l.append(20)
l.append(25)
print(l.remove_zeros_from_linkedlist(l.head))
#this code works perfectly
class Node():
def __init__(self,data):
self.data = data
self.next = None
class Linkedlist():
def __init__(self):
self.head = None
def append(self,data):
new_node = Node(data)
h = self.head
if self.head is None:
self.head = new_node
return
else:
while h.next!=None:
h = h.next
h.next = new_node
def remove_zeros_from_linkedlist(self, head):
stack = []
curr = head
list = []
while (curr):
if curr.data >= 0:
stack.append(curr)
else:
temp = curr
sum = temp.data
flag = False
while (len(stack) != 0):
temp2 = stack.pop()
sum += temp2.data
if sum == 0:
flag = True
list = []
break
elif sum > 0:
list.append(temp2)
if not flag:
if len(list) > 0:
for i in range(len(list)):
stack.append(list.pop())
stack.append(temp)
curr = curr.next
return [i.data for i in stack]
if __name__ == "__main__":
l = Linkedlist()
l.append(4)
l.append(6)
l.append(-10)
l.append(8)
l.append(9)
l.append(10)
l.append(-19)
l.append(10)
l.append(-18)
l.append(20)
l.append(25)
print(l.remove_zeros_from_linkedlist(l.head))
Following code passes all testcases:
class Node():
def __init__(self,data):
self.data = data
self.next = None
class Linkedlist():
def __init__(self):
self.head = None
def append(self,data):
new_node = Node(data)
h = self.head
if self.head is None:
self.head = new_node
return
else:
while h.next!=None:
h = h.next
h.next = new_node
def remove_zeros_from_linkedlist(self, head):
stack = []
curr = head
list = []
while (curr):
if curr.data >= 0:
stack.append(curr)
else:
temp = curr
sum = temp.data
flag = False
while (len(stack) != 0):
temp2 = stack.pop()
sum += temp2.data
if sum == 0:
flag = True
list = []
break
elif sum > 0:
list.append(temp2)
if not flag:
if len(list) > 0:
for i in range(len(list)):
stack.append(list.pop())
stack.append(temp)
curr = curr.next
return [i.data for i in stack]
if __name__ == "__main__":
l = Linkedlist()
l.append(4)
l.append(6)
l.append(-10)
l.append(8)
l.append(9)
l.append(10)
l.append(-19)
l.append(10)
l.append(-18)
l.append(20)
l.append(25)
print(l.remove_zeros_from_linkedlist(l.head))
///
class Node():
def __init__(self,data):
self.data = data
self.next = None
class Linkedlist():
def __init__(self):
self.head = None
def append(self,data):
new_node = Node(data)
h = self.head
if self.head is None:
self.head = new_node
return
else:
while h.next!=None:
h = h.next
h.next = new_node
def remove_zeros_from_linkedlist(self, head):
stack = []
curr = head
list = []
while (curr):
if curr.data >= 0:
stack.append(curr)
else:
temp = curr
sum = temp.data
flag = False
while (len(stack) != 0):
temp2 = stack.pop()
sum += temp2.data
if sum == 0:
flag = True
list = []
break
elif sum > 0:
list.append(temp2)
if not flag:
if len(list) > 0:
for i in range(len(list)):
stack.append(list.pop())
stack.append(temp)
curr = curr.next
return [i.data for i in stack]
if __name__ == "__main__":
l = Linkedlist()
l.append(4)
l.append(6)
l.append(-10)
l.append(8)
l.append(9)
l.append(10)
l.append(-19)
l.append(10)
l.append(-18)
l.append(20)
l.append(25)
print(l.remove_zeros_from_linkedlist(l.head))
\\\
this code uses recursion so given a root goes till end while checking for count of 0.
and this recurses with root->next. so basically it goes to the end and starts coming back one by one so the time it completes all the continuous elements equalling to 0 are removed
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node * new_node(int data)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = data;
temp->next = NULL;
return temp;
}
void print_list(struct node *root)
{
while (root != NULL)
{
cout << root->data << " => ";
root = root ->next;
}
cout << endl;
}
struct node *get_list(struct node* root)
{
if(root == NULL)
return NULL;
int cnt = 0;
struct node *temp = root;
root->next = get_list(root->next);
//print_list(root);
while(temp != NULL)
{
cnt = cnt + temp->data;
if(cnt == 0)
{
cout << " found place to redcue" << endl;
if (temp->data == root->data)
root = temp->next;
else
root = temp->next;
}
temp = temp->next;
}
return root;
}
int main()
{
struct node *head,*temp;
head = new_node(4);
temp = head;
temp->next = new_node(6);
temp = temp->next;
temp->next = new_node(-10);
temp = temp->next;
temp->next = new_node(8);
temp = temp->next;
temp->next = new_node(9);
temp = temp->next;
temp->next = new_node(10);
temp = temp->next;
temp->next = new_node(-19);
temp = temp->next;
temp->next = new_node(10);
temp = temp->next;
temp->next = new_node(-18);
temp = temp->next;
temp->next = new_node(20);
temp = temp->next;
temp->next = new_node(25);
temp = temp->next;
print_list(head);
struct node *final = get_list(head);
print_list(final);
}
class node:
def __init__(self,data=None):
self.data=data
self.next=None
class linkedlist:
def __init__(self):
self.head=node()
def insert(self):
temp=self.head
while(temp.next):
temp=temp.next
while(int(input("Want to continue?"))):
no=node(int(input("Enter the data")))
temp.next=no
temp=temp.next
def find(self):
l=[]
sum=0
count=0
temp=self.head
while(temp.next):
temp=temp.next
if temp.data > 0:
l.append(temp.data)
if temp.data < 0:
for j in reversed(l):
sum+=j
count+=1
if sum==-temp.data:
sum=0
for z in range(count):
l.pop()
count=0
break
print(l)
ll=linkedlist()
ll.insert()
ll.find()
package com.practise.dsa;
import java.util.Scanner;
import java.util.Stack;
public class DeleteLinkedListElementsWhoseSumEqualToZero {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = new int[scanner.nextInt()];
Node head = null;
for (int i = 0; i < arr.length; i++) {
head = add(scanner.nextInt(), head);
}
head = deleteElementsWhoseSumEqualToZero(head);
while(head != null){
System.out.print(head.data + " ");
head = head.next;
}
}
private static Node add(int val, Node head){
if(head == null){
head = new Node();
head.data = val;
}else{
head.next = add(val, head.next);
}
return head;
}
private static Node deleteElementsWhoseSumEqualToZero(Node head){
Stack<Integer> stack = new Stack<>();
if(head == null || head.next == null){
return head;
}
while(head != null){
if(stack.isEmpty()){
stack.push(head.data);
}else{
Stack<Integer> temp = new Stack<>();
int sum = 0;
boolean flag = false;
while(!stack.isEmpty()){
int val = stack.pop();
sum += val;
if(sum + head.data == 0){
flag = true;
break;
}
temp.push(val);
}
if(!flag){
while(!temp.isEmpty()){
stack.push(temp.pop());
}
stack.push(head.data);
}
}
head = head.next;
}
for (int i = 0; i < stack.size(); i++) {
head = add(stack.elementAt(i), head);
}
return head;
}
}
class Node{
int data;
Node head;
}
package com.practise.dsa;
import java.util.Scanner;
import java.util.Stack;
public class DeleteLinkedListElementsWhoseSumEqualToZero {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = new int[scanner.nextInt()];
Node head = null;
for (int i = 0; i < arr.length; i++) {
head = add(scanner.nextInt(), head);
}
head = deleteElementsWhoseSumEqualToZero(head);
while(head != null){
System.out.print(head.data + " ");
head = head.next;
}
}
private static Node add(int val, Node head){
if(head == null){
head = new Node();
head.data = val;
}else{
head.next = add(val, head.next);
}
return head;
}
private static Node deleteElementsWhoseSumEqualToZero(Node head){
Stack<Integer> stack = new Stack<>();
if(head == null || head.next == null){
return head;
}
while(head != null){
if(stack.isEmpty()){
stack.push(head.data);
}else{
Stack<Integer> temp = new Stack<>();
int sum = 0;
boolean flag = false;
while(!stack.isEmpty()){
int val = stack.pop();
sum += val;
if(sum + head.data == 0){
flag = true;
break;
}
temp.push(val);
}
if(!flag){
while(!temp.isEmpty()){
stack.push(temp.pop());
}
stack.push(head.data);
}
}
head = head.next;
}
for (int i = 0; i < stack.size(); i++) {
head = add(stack.elementAt(i), head);
}
return head;
}
}
class Node{
int data;
Node head;
}
private static void DeleteSumZero(Node head)
{
Node curr = head;
Stack sum = new Stack();
int sumData = 0;
while (curr != null)
{
int data = curr.data;
if (sum.Count() == 0)
{
sum.Push(data);
sumData = data;
}
else
{
if (data + sumData == 0)
{
while (sum.Count() != 0)
sum.Pop();
sumData = 0;
}
else if (data + sum.Peek() == 0)
{
sum.Pop();
sumData += data;
}
else
{
sum.Push(data);
sumData += data;
}
}
curr = curr.link;
}
sum.PrintStack();
}
private static void DeleteSumZero(Node head)
{
Node curr = head;
Stack sum = new Stack();
int sumData = 0;
while (curr != null)
{
int data = curr.data;
if (sum.Count() == 0)
{
sum.Push(data);
sumData = data;
}
else
{
if (data + sumData == 0)
{
while (sum.Count() != 0)
sum.Pop();
sumData = 0;
}
else if (data + sum.Peek() == 0)
{
sum.Pop();
sumData += data;
}
else
{
sum.Push(data);
sumData += data;
}
}
curr = curr.link;
}
sum.PrintStack();
}
For simplification I haven't used concept of Encapsulation / data hiding.
public class Test {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(4);
list.insert(6);
list.insert(-10);
list.insert(8);
list.insert(9);
list.insert(10);
list.insert(-19);
list.insert(10);
list.insert(-18);
list.insert(20);
list.insert(25);
list.removeZeroSum();
list.show();
}
}
public class LinkedList {
Node head;
public void insert(int data) {
if(head == null) {
Node node = new Node();
node.data = data;
node.next = null;
head = node;
} else {
Node search = head;
while(search.next != null) {
search = search.next;
}
Node node = new Node();
node.data = data;
node.next = null;
search.next = node;
}
}
public void removeZeroSum() {
int sum = 0;
Node subStart =head, subEnd = head;
while(subEnd != null) {
sum = sum + subEnd.data;
if(sum == 0) {
if(subStart == head) {
head = subEnd.next;
} else {
}
removeZeroSum();
break;
}
subEnd = subEnd.next;
}
Node join = subStart;
subEnd = subStart.next;
subStart = subStart.next;
sum = 0 ;
while(subEnd != null) {
sum = sum + subEnd.data;
if(sum == 0) {
if(join.next == null) {
break;
} else {
join.next = subEnd.next;
}
removeZeroSum();
break;
}
subEnd = subEnd.next;
}
}
}
For simplification I haven't used concept of Encapsulation / data hiding.
public class Test {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(4);
list.insert(6);
list.insert(-10);
list.insert(8);
list.insert(9);
list.insert(10);
list.insert(-19);
list.insert(10);
list.insert(-18);
list.insert(20);
list.insert(25);
list.removeZeroSum();
list.show();
}
}
public class LinkedList {
Node head;
public void insert(int data) {
if(head == null) {
Node node = new Node();
node.data = data;
node.next = null;
head = node;
} else {
Node search = head;
while(search.next != null) {
search = search.next;
}
Node node = new Node();
node.data = data;
node.next = null;
search.next = node;
}
}
public void removeZeroSum() {
int sum = 0;
Node subStart =head, subEnd = head;
while(subEnd != null) {
sum = sum + subEnd.data;
if(sum == 0) {
if(subStart == head) {
head = subEnd.next;
} else {
}
removeZeroSum();
break;
}
subEnd = subEnd.next;
}
Node join = subStart;
subEnd = subStart.next;
subStart = subStart.next;
sum = 0 ;
while(subEnd != null) {
sum = sum + subEnd.data;
if(sum == 0) {
if(join.next == null) {
break;
} else {
join.next = subEnd.next;
}
removeZeroSum();
break;
}
subEnd = subEnd.next;
}
}
}
For simplification I haven't used concept of Encapsulation / data hiding.
public class Test {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(4);
list.insert(6);
list.insert(-10);
list.insert(8);
list.insert(9);
list.insert(10);
list.insert(-19);
list.insert(10);
list.insert(-18);
list.insert(20);
list.insert(25);
list.removeZeroSum();
list.show();
}
}
public class LinkedList {
Node head;
public void insert(int data) {
if(head == null) {
Node node = new Node();
node.data = data;
node.next = null;
head = node;
} else {
Node search = head;
while(search.next != null) {
search = search.next;
}
Node node = new Node();
node.data = data;
node.next = null;
search.next = node;
}
}
public void removeZeroSum() {
int sum = 0;
Node subStart =head, subEnd = head;
while(subEnd != null) {
sum = sum + subEnd.data;
if(sum == 0) {
if(subStart == head) {
head = subEnd.next;
} else {
}
removeZeroSum();
break;
}
subEnd = subEnd.next;
}
Node join = subStart;
subEnd = subStart.next;
subStart = subStart.next;
sum = 0 ;
while(subEnd != null) {
sum = sum + subEnd.data;
if(sum == 0) {
if(join.next == null) {
break;
} else {
join.next = subEnd.next;
}
removeZeroSum();
break;
}
subEnd = subEnd.next;
}
}
}
public Node cancelZero(Node head) {
Node curr = head;
Node old = curr;
lo:
while (curr.getNext() != null) {
Node p = curr.getNext();
int res = curr.getData();
while (p != null) {
res += p.getData();
if (res == 0&&p.getNext()!=null) {
curr = p.getNext();
continue lo;
}
else if(res == 0&&p.getNext()==null){
curr=p.getNext();
old.setNext(curr);
break lo;
}
else{
p = p.getNext();
}
}
if (res != 0 && p == null) {
old = curr;
curr=curr.getNext();
}
}
return old;
}
public Node cancelZero(Node head) {
Node curr = head;
Node old = curr;
lo:
while (curr.getNext() != null) {
Node p = curr.getNext();
int res = curr.getData();
while (p != null) {
res += p.getData();
if (res == 0&&p.getNext()!=null) {
curr = p.getNext();
continue lo;
}
else if(res == 0&&p.getNext()==null){
curr=p.getNext();
old.setNext(curr);
break lo;
}
else{
p = p.getNext();
}
}
if (res != 0 && p == null) {
old = curr;
curr=curr.getNext();
}
}
return old;
}
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node*next;
Node(int x)
{
data=x;
next=NULL;
}
};
Node* push(Node*head,int x)
{
Node*t=head;
head=new Node(x);
head->next=t;
return head;
}
Node* pop(Node*head)
{
head=head->next;
return head;
}
Node*zerosum(Node*list)
{
if(list==NULL) return list;
Node*temp=list,*head=NULL;
while(temp!=NULL)
{
if(temp->data<0)
{
int sum=temp->data;
while(head!=NULL)
{
sum+=head->data;
head=pop(head);
if(sum>=0) break;
}
}
else
{
head=push(head,temp->data);
}
temp=temp->next;
}
return head;
}
int main()
{
int n;
cin>>n;
Node*t=NULL,*head=NULL;
while(n--)
{
int num;
cin>>num;
if(!head)
{
head=new Node(num);
t=head;
}
else{
t->next=new Node(num);
t=t->next;
}
}
Node*temp=zerosum(head);
while(temp)
{
cout<<temp->data<<" ";
temp=temp->next;
}
}
package com.datastructure.linkedList.interview;
import java.util.Stack;
public class DeleteZeroSumElement {
Node head;
public static void main(String args[]) {
DeleteZeroSumElement dzs = new DeleteZeroSumElement();
dzs.insert(4);
dzs.insert(6);
dzs.insert(-9);
dzs.insert(8);
dzs.insert(9);
dzs.insert(10);
dzs.insert(-19);
dzs.insert(10);
dzs.insert(-18);
dzs.insert(20);
dzs.insert(25);
dzs.deleteZeroSum();
dzs.print();
}
private void print() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
private void deleteZeroSum() {
Stack<Node> stack = new Stack<>();
Node temp = head;
int sum = 0;
int count = 0;
while (temp != null) {
if (stack.isEmpty() || (sum > 0 && temp.data > 0) || (sum < 0 && temp.data < 0)) {
stack.push(temp);
sum = sum + temp.data;
} else {
if (sum > 0 && temp.data < 0) {
int d = temp.data;
int size = stack.size();
while (d < 0 && !stack.isEmpty()) {
count++;
size--;
int dat = stack.get(size).data;
d = d + dat;
if (d == 0) {
while (count != 0 && !stack.isEmpty()) {
Node p = stack.pop();
sum = sum - p.data;
count--;
}
count = 0;
break;
}
if (d > 0) {
stack.push(temp);
sum = sum + temp.data;
}
}
} else if (sum < 0 && temp.data > 0) {
int d = temp.data;
while (d > 0 && !stack.isEmpty()) {
count++;
d = d + stack.peek().data;
if (d == 0) {
while (count != 0) {
Node p = stack.pop();
sum = sum - p.data;
}
count = 0;
break;
}
if (d < 0) {
stack.push(temp);
sum = sum + temp.data;
}
}
}
}
temp = temp.next;
}
Node temp1 = stack.pop();
temp1.next = null;
Node temp2;
while (!stack.isEmpty()) {
temp2 = stack.pop();
temp2.next = temp1;
temp1 = temp2;
if (temp != null)
temp.next = null;
}
head = temp1;
}
private void insert(int i) {
if (head == null) {
head = new Node(i);
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(i);
}
}
}
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
package com.datastructure.linkedList.interview;
import java.util.Stack;
public class DeleteZeroSumElement {
Node head;
public static void main(String args[]) {
DeleteZeroSumElement dzs = new DeleteZeroSumElement();
dzs.insert(4);
dzs.insert(6);
dzs.insert(-9);
dzs.insert(8);
dzs.insert(9);
dzs.insert(10);
dzs.insert(-19);
dzs.insert(10);
dzs.insert(-18);
dzs.insert(20);
dzs.insert(25);
dzs.deleteZeroSum();
dzs.print();
}
private void print() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
private void deleteZeroSum() {
Stack<Node> stack = new Stack<>();
Node temp = head;
int sum = 0;
int count = 0;
while (temp != null) {
if (stack.isEmpty() || (sum > 0 && temp.data > 0) || (sum < 0 && temp.data < 0)) {
stack.push(temp);
sum = sum + temp.data;
} else {
if (sum > 0 && temp.data < 0) {
int d = temp.data;
int size = stack.size();
while (d < 0 && !stack.isEmpty()) {
count++;
size--;
int dat = stack.get(size).data;
d = d + dat;
if (d == 0) {
while (count != 0 && !stack.isEmpty()) {
Node p = stack.pop();
sum = sum - p.data;
count--;
}
count = 0;
break;
}
if (d > 0) {
stack.push(temp);
sum = sum + temp.data;
}
}
} else if (sum < 0 && temp.data > 0) {
int d = temp.data;
while (d > 0 && !stack.isEmpty()) {
count++;
d = d + stack.peek().data;
if (d == 0) {
while (count != 0) {
Node p = stack.pop();
sum = sum - p.data;
}
count = 0;
break;
}
if (d < 0) {
stack.push(temp);
sum = sum + temp.data;
}
}
}
}
temp = temp.next;
}
Node temp1 = stack.pop();
temp1.next = null;
Node temp2;
while (!stack.isEmpty()) {
temp2 = stack.pop();
temp2.next = temp1;
temp1 = temp2;
if (temp != null)
temp.next = null;
}
head = temp1;
}
private void insert(int i) {
if (head == null) {
head = new Node(i);
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(i);
}
}
}
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> num1;
vector<int> num2;
int n;
cout << "The the value of size of list: ";
cin >> n;
cout << "\nEnyter the data\n";
while (n--)
{
int data;
cin >> data;
if (data < 0)
num1.push_back(data);
else
num2.push_back(data);
}
sort(num1.begin(), num1.end());
sort(num2.begin(), num2.end());
int sum1 = 0, sum2 = 0;
for (int i = 0; i < num1.size(); i++)
{
sum1 += (-1) * num1[i];
}
for (int i = 0; i < num2.size(); i++)
{
sum2 += num2[i];
}
if (sum1 < sum2)
{
for (int i = num2.size()-1; i>=0; i--)
{
if((sum2-num2[i])>=sum1)
{
cout<<num2[i]<<" ";
sum2-=num2[i];
}
}
}
else if(sum1>sum2)
{
for (int i = num1.size()-1; i>=0; i--)
{
if((sum1-(-1)*num1[i])>=sum2)
{
cout<<num1[i]<<" ";
sum1=sum1-(-1)*num1[i];
}
}
}
else if(sum2=sum1)
{
return 0;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> num1;
vector<int> num2;
int n;
cout << "The the value of size of list: ";
cin >> n;
cout << "\nEnyter the data\n";
while (n--)
{
int data;
cin >> data;
if (data < 0)
num1.push_back(data);
else
num2.push_back(data);
}
sort(num1.begin(), num1.end());
sort(num2.begin(), num2.end());
int sum1 = 0, sum2 = 0;
for (int i = 0; i < num1.size(); i++)
{
sum1 += (-1) * num1[i];
}
for (int i = 0; i < num2.size(); i++)
{
sum2 += num2[i];
}
if (sum1 < sum2)
{
for (int i = num2.size()-1; i>=0; i--)
{
if((sum2-num2[i])>=sum1)
{
cout<<num2[i]<<" ";
sum2-=num2[i];
}
}
}
else if(sum1>sum2)
{
for (int i = num1.size()-1; i>=0; i--)
{
if((sum1-(-1)*num1[i])>=sum2)
{
cout<<num1[i]<<" ";
sum1=sum1-(-1)*num1[i];
}
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> num1;
vector<int> num2;
int n;
cout << "The the value of size of list: ";
cin >> n;
cout << "\nEnyter the data\n";
while (n--)
{
int data;
cin >> data;
if (data < 0)
num1.push_back(data);
else
num2.push_back(data);
}
sort(num1.begin(), num1.end());
sort(num2.begin(), num2.end());
int sum1 = 0, sum2 = 0;
for (int i = 0; i < num1.size(); i++)
{
sum1 += (-1) * num1[i];
}
for (int i = 0; i < num2.size(); i++)
{
sum2 += num2[i];
}
if (sum1 < sum2)
{
for (int i = num2.size()-1; i>=0; i--)
{
if((sum2-num2[i])>=sum1)
{
cout<<num2[i]<<" ";
sum2-=num2[i];
}
}
}
else if(sum1>sum2)
{
for (int i = num1.size()-1; i>=0; i--)
{
if((sum1-(-1)*num1[i])>=sum2)
{
cout<<num1[i]<<" ";
sum1=sum1-(-1)*num1[i];
}
}
}
return 0;
}
Use a stack.
- confused_coder July 25, 2016