Amazon Interview Question for SDE1s


Country: India




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

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}

- linuxchain September 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a stack.

// Note: does not compile! assumes negative numbers are after positive numbers in list
Node removeCancellableNodes(Node listHead)
{
	if (listHead == null) return null; // or listHead
	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;
				temp = null;
				if (sum == 0)
				{
					node = stack.peek();
					break;
				}
			}
		}
		else
		{
			stack.push(node);
		}
		node = node.next;
	}
	
	return listHead;
}

- confused_coder July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a problem with your code and test case #3 above.
case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
O/P : 20 25

HashMap<Integer,Node> mp=new HashMap<Integer,Node>();

HashMap can't handle multiple values of 10 in the same list, so it overwrites the node value.

- funktional September 11, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- divm01986 July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- patil16nit July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Poon August 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- confused_coder August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Koustav August 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- koustav.adorable August 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- funktional September 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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() + " ");

    }

- arviman September 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- SHARMA May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- sharma May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sharma May 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Hash table ......insert +ve value in the hash table and then on -ve see its inverse(+ve)
exist in the hash table or not ......mean if we insert 8 in the hash and then on coming -8 we will then see that 8 exist in the hash table

- Karamat June 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Akil Kumar Thota November 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pleasejustsayno January 05, 2018 | 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