CareerCup

Implement HashTable in java , especially hash function that should take care of any type of keys. The key may be integer or String or Object. But based on that the hash function should find index in the hashArray

Implement Array Class in java.

An arraylist containing datatype studentsScores are given where studentId, and results are twostates of this datatype. Each student takes more than 10 exams. We need to return the averages score of each student as a Map<student, average score> where the average score is calculated by taking the average of top 5 exams of a student.
First we iterate the arraylist and create another Map<Integer, ArrayList<>> where the inner ArrayList has values of test scores. Iterating the arrayList to find avergae score and adding it to the another Map<student, averageScore>. What is the complexity of this?

Implement an algorithm to print all possible valid combinations of braces when n pairs of paranthesis are given.

I tried this code executing. I checked with System.out.println statements too. But I couldn't understand how this prints ( ( ) ). I have two questions.

1) If we give count as 2, this code should generate only ( )( ). But how does it go for another execution of whole addParen to generate (( ))

2) The second if block(that is, if(rightRem > leftRem) within the else block of allParen is always after if(leftRem > 0), then how come this is able to generate
( ( ) )

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
if (leftRem < 0 || rightRem < leftRem) return; // invalid state

if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
String s = String.copyValueOf(str);
// System.out.println(str);
list.add(s);
} else {
if (leftRem > 0) { // try a left paren, if there are some available
str[count] = '(';

addParen(list, leftRem - 1, rightRem, str, count + 1);
}
if (rightRem > leftRem) { // try a right paren, if there’s a matching left
str[count] = ')';
// System.out.println(str);
addParen(list, leftRem, rightRem - 1, str, count + 1);
}
}
}

public static ArrayList<String> generateParens(int count) {
char[] str = new char[count*2];
ArrayList<String> list = new ArrayList<String>();
addParen(list, count, count, str, 0);

return list;
}

public static void main(String args[]) {

ArrayList<String> list = generateParens(2);
for (String s : list) {
System.out.println(s);
}
System.out.println(list.size());

}
}

Finding the minimum in a BST.

The known solution is
public Node minimum(){
Node current, last;
current = root;
while(current != null){
last = current;
current = current.left;
}
return last;
}

The above code doesn't find 0.5 as the minimum.

1 and 3 are children of 2, 0.5 is left child of 3 and 3.5 is right child of 3
2
/ \
1 3
/ \
0.5 3.5

Check if a binary tree is BST.

I know the solution but I want to know will this code work

public boolean IsBST(Node root){




if(root.left <= root && root.right > root){
IsBST(root.left);

IsBST(root.right);
}else{
return false;
}

return true;
}

How do you check if a binary tree is balanced or not? Please traverse through this code and explain how the complexity is O(N).

public boolean isBalanced(Node root){
if(checkHeight(root) == -1){
return false;
}else{
return true;
}
}

private int checkHeight(Node root){

if(root == null){
return 0;
}

int leftHeight = checkHeight(root.left);
if(leftHeight = -1 ){
return -1;
}

int rightHeight = checkheight(root.right);
if(rightHeight = -1){
return -1;
}

int heightDiff = leftHeight - rightHeight;
if(Math.abs(heightDiff) > 1){
return -1;
}else{
return Math.max(leftHeight, rightHeight) + 1;
}

}

Please traverse for the following tree.

A
/ \
B C
/ \ / \
D E F G
\
H

Rotate a M*N matrix by 90 degree.

Is this answer right?

public void rotateMN(int[][] input){

int i = input.length;
int j = input[0].length;

int m = j;
int n = i;

int[][] newArray = new int[m][n];

for(int j = input[0].length-1, m=0; ;i--, m++ ){
for(int i = input.length-1, n=0; i >= 0 ; i--, n++){

newArray[m][n] = input[i][j];

}
}

}


Will this also work for N*N matrix rotation by 90 degrees?

The time complexity is O(N) since it just traverse the input matrix and copy it to the new matrix. The space complexity is (MN) + (MN) = So MN.

Is it possible to do rotation for M * N matrix in space? If so please provide that answer
Whats this space and time complexity?

In what situations bubble sort, selection sort, insertion sort, merge sort, quick sort and heap sort will have best time complexity. Provide example for each sort and explain

1000 elements in one bag and 1 million elements in another. how do you find common elements among them. Also give the complexity of your solution.

If a key has to be inserted in binary tree, say the value of root as well as the key to be inserted as same. Will the key becomes left child or right child of Root? Can binary tree have duplicate values? If yes, why, If no why?

Consider there are n matrices. For eg, A, B, C and D are four matrices. Find the groupings of matrices during their product, the operations involved in your choice of grouping is minimal.

For eg, you can group like (AB)CD or (ABC)D or A(BC)D or A(BCD) .... But among these options in which grouping the operations of matrix multiplication will be minimal. Remember in matrix multiplication , multiplication and sum of elements are involved.

Solution found in CareerCup

public static int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
public static int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
public static boolean isBalanced(TreeNode root){
return (maxDepth(root) - minDepth(root) <= 1);
}


Why not the following solution work?? Please explain in detail

public static int maxDepth(TreeNode root){
if(root==null)
return 0;
return 1+ Math.max(maxDepth(root.left), maxDepth(root.right));
}

public static boolean isBalanced(TreeNode root){
return (maxDepth(root.left) - maxDepth(root.right) <=1);
}