Phone Interview(Nov 2017) Find two sum from given array in constant time(In java)

  • 1

    Find two sum from given array in constant time(In java)

    • you will be calling store method from main
    • at any given point of time if test method is called you should return true or false (if two sum present or not)
    public interface TwoSum {
         * Stores @param input in an internal data structure.
        void store(int input);
         * Returns true if there is any pair of numbers in the internal data structure which
         * have sum @param val, and false otherwise.
         * For example, if the numbers 1, -2, 3, and 6 had been stored,
         * the method should return true for 4, -1, and 9, but false for 10, 5, and 0
        boolean test(int val);
    //hint by interviewer
    //store(1), store(2), store(5)
    // 1, 2, 5 -> key
    // 3(1+2), 6(1+5), 7(2+5) -> key

  • 0

    @vishal80 - Is store() adding new elements to the array? And every time a new element is added, we have to check if a pair of integers sum to param val ?

  • 0

    @parik Yes, IsStore() method is called to add new elements.and At any given point of time, if we call test method with target value.we should return true or false based on if sum is present for given target for present elements

    • we don't need to call test method every time

  • 0

    @vishal80 - If I store array elements in a hash map with key as the number and value as a list of indices for that element, I can get two sum in constant time. But is there a space constraint in the question?

  • 0

    All you need to do is store all the pair-wise sum in a HashSet in the store method and then in the test method you would just check if the input number exist in your set

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.