HackerRank Super Stack Solution

SuperStack.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Solution
{
    class Solution
    {
        static void Main(string[] args)
        {
            var noCommands = Convert.ToInt32(System.Console.ReadLine());

            var stack = new LinkedList<int>();
            for (var i = 0; i < noCommands; ++i)
            {
                var command = Console.ReadLine();
                var split = command.Split(' ');

                if (split[0] == "push")
                {
                    var number = Convert.ToInt32(split[1]);
                    stack.AddFirst(number);
                }
                else if (split[0] == "pop" && stack.Count > 0)
                {
                    stack.RemoveFirst();
                }
                else if (split[0] == "inc")
                {
                    var count = Convert.ToInt32(split[1]);
                    var increment = Convert.ToInt32(split[2]);
                    count = Math.Min(stack.Count, count);

                    var node = stack.Last;
                    for (var j = 0; j < count; ++j)
                    {
                        node.Value += increment;
                        node = node.Previous;
                    }
                 }

                PrintTop(stack);
            }
        }

        static void PrintTop(LinkedList<int> stack)
        {
            if (stack.Count == 0)
            {
                System.Console.WriteLine("EMPTY");
            }
            else
            {
                System.Console.WriteLine("{0}", stack.First.Value);
            }
        }
    }
}

Fails for some edge cases that I might not have spotted.

Did you managed to find why it fails for certain test cases? Mine failed for few too.... similar approach

Can you paste the full question?

it fails because in the "inc" operation if k is large, time will exceed limit,one way to solve this is to use a hashmap to remember the values that should add to the bottom. java code here:

static void superStack(String[] operations) {
        List<Integer> stack = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (String s : operations) {
            if (s.startsWith("push")) {
                int value = Integer.parseInt(s.split(" ")[1]);
                stack.add(value);
            } else if (s.startsWith("pop")) {
                stack.remove(stack.size() - 1);
                //modify the hashmap
                for(Integer i: map.keySet()) {
                    if (stack.size() < i) {
                        map.put(i-1, map.get(i));
                        map.remove(i);
                    }
                }
            } else if (s.startsWith("inc")) {
                String[] splits = s.split(" ");
                int e = Integer.parseInt(splits[1]);
                int value = Integer.parseInt(splits[2]);
                map.put(e, map.getOrDefault(e, 0) + value);
            }

            if (stack.size() == 0) {
                System.out.println("EMPTY");
            } else {
                int value = stack.get(stack.size()-1);
                for(Integer i: map.keySet()) {
                    if (stack.size() <= i) {
                        value+=map.get(i);
                    }
                }
                System.out.println(value);
            }
        }
    }

Hi Liaoxsong, using your exact Java8 code fragment only 5/14 test cases pass. And the O(n*n) test cases still timeout. Sorry.

if we use treemap to save the inc operations
we can just process the tailmap for the pop operation instead whole hashmap.
will this work?