# INTERVIEW QUESTIONS

## Move Zeroes in an Array

### Description
Given an array of random positive numbers, move all the zeroes to the left of the array. 

Conditions:
1) has to be done in place (cannot allocate a new array)
2) the order of non-zero elements on the right do not matter
3) Do not use standard API of your language

### Example

Input: [0, 1, 2, 5, 0, 3, 0, 3];
Output: [0, 0, 0, 2, 1, 3, 3, 5];

## Valid parentheses

### Description
Given a string containing just the characters `(`, `)`, `{`, `}`, `[` and `]`, determine if the input string is valid.

An input string is valid if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

### Example

Input: "()"
Output: true

Input: ")("
Output: false

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

Input: "{[]"
Output: false

Input: "{[]()}"

input: "(aa(ab))"

## Two Sum

### Description
Given an array of integers and, an integer target, return indices of the two numbers that equal to target.

### Example

Input: nums = [2, 8, 5], target = 7
Output: [0,2]
Explanation: nums[0] + nums[2] == 7, we return [0, 2].


Input: nums = [2, 8, 5, 2, 5, 8], target = 13
Output: [1,2]
Explanation: nums[1] + nums[2] == 13, we return [1, 2].


Input: nums = [1,1,1,1,1,4,1,1,1,1,1,7,1,1,1,1,1], target = 11
Output: [5,11]
Explanation: nums[5] + nums[11] == 11, we return [5, 11].

public class MyClass {
    public static void main(String args[]) {
       int[] input1 = new int[]{1,2,3,0,4,5,6,0,7,0};
       int[] input2 = new int[]{1,0,0,0,0,0,0,0,0,0};
       int[] input3 = new int[]{0,0,0,0,0,0,0,0,0,0};
       printArr(input3);
       moveZeroes(input3);
       printArr(input3);

    }
    
    public static void moveZeroes(int[] input) {
        int lastZeroIdx = 0;
        for(int i=0; i<input.length; i++) {
            if (input[i] == 0) {
                // switch the value of lastZeroIdx and i
                input[i] = input[lastZeroIdx];
                input[lastZeroIdx] = 0;
                lastZeroIdx++;
            }
        }
    }
    
    public static void printArr(int[] input) {
        for(int i=0; i<input.length; i++) {
            System.out.print(input[i] + " ");
        }
        System.out.println();
    }
    
}

import java.util.*;
public class MyClass {
    public static void main(String args[]) {
       String input1 = "()";
       String input2 = ")(";
       String input3 = "(aa(ab))";
       
       System.out.println(isValidParanthesisStack(input3));

    }
    
    public static boolean isValidParanthesis(String input) {
        int length = input.length();
        if (length == 0) {
            return true;
        } else if (length % 2 != 0) {
            return false;
        } else {
            char firstChar = input.charAt(0);
            char lastChar = input.charAt(length-1);
            if (((firstChar == '(') && (lastChar == ')')) ||  ((firstChar == '[') && (lastChar == ']')) || ((firstChar == '{') && (lastChar == '}'))) {
                if (input.length() == 2) {
                    return true;
                } else {
                    String nextItr = input.substring(1, length-2);
                    return isValidParanthesis(nextItr);
                }
            }
            return false;
        }
    }
    
    public static boolean isValidParanthesisStack(String input) {
        List<String> stack = new ArrayList();  
        for(int i=0; i<input.length(); i++) {
            if((input.charAt(i) == '(') || (input.charAt(i) == '{') || (input.charAt(i) == '[')) {
                stack.add(Character.toString(input.charAt(i)));
            } else if((input.charAt(i) == ')') || (input.charAt(i) == '}') || (input.charAt(i) == ']')){
                if(stack.size() > 0){
                    if (((stack.get(stack.size()-1).equals("(")) && (input.charAt(i) == ')')) || ((stack.get(stack.size()-1).equals("{")) && (input.charAt(i) == '}')) || ((stack.get(stack.size()-1).equals("[")) && (input.charAt(i) == ']'))) {
                    stack.remove(stack.size()-1);
                    } else {
                        return false;
                    }
                }  else {
                    return false;
                }
                
            }
        }
        return stack.size() == 0;
    }
    
}