## sivaji8

BAN USER- -1of 1 vote

AnswersImplement 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

- sivaji8 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Data Structures - -4of 4 votes

AnswersImplement Array Class in java.

- sivaji8 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Data Structures - -9of 9 votes

AnswersAn 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.

- sivaji8 in United States

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?| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer - -1of 9 votes

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

- sivaji8 in United States

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

}

}| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer - -21of 23 votes

AnswersFinding the minimum in a BST.

- sivaji8 in United States

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| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer - -13of 15 votes

AnswersCheck if a binary tree is BST.

- sivaji8 in United States

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;

}| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer - -2of 2 votes

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

- sivaji8 in United States

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| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Data Structures - -4of 6 votes

AnswersRotate a M*N matrix by 90 degree.

- sivaji8 in United States

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?| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Data Structures - -4of 6 votes

AnswersIn 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

- sivaji8 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Sorting - 0of 0 votes

AnswersIf 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?

- sivaji8 in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Trees and Graphs - -1of 1 vote

AnswersConsider 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.

- sivaji8 in United States

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.| Report Duplicate | Flag | PURGE

Amazon Software Engineer / Developer Matrix

- 1 Answer
**Check if a tree is balanced. Why should we check MinDepth? Please help me.**Solution found in CareerCup

- sivaji8 January 18, 2013

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

}| Flag | PURGE

Thanks for replying. May I know what is the Big O of the following solutoin for same problem and why?

public boolean isBalanaced(Node root){

if(root == null) return true;

int heightDiff = getHeight(root.left) - getHeight(root.right);

if(Math.abs(heightDiff > 1)){

return false;

}else{

return isBalanced(root.left) && isBalanced(root.right);

}

}

private int getHeight(Node root){

if(root == null) return 0;

else{

return Math.max(getHeight(root.left) + getHeight(root.right)) + 1;

}

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?

Will this still be a correct solution.

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) - minDepth(root.right) <= 1);

}

Why do we find MinDepth. Please explain.

Rep**joycejflora**, Android Engineer at ABC TECH SUPPORTI am excited about cooperation and interesting projects. Last year I work for a person who provides the black magic ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

public static void merge(int[] A, int[] B, lastA, lastB){

- sivaji8 October 09, 2013int indexA = A.length - 1;

int indexB = B.length - 1

while(lastB >= 0 || lastA >= 0){

if(B[lastB] >= A[lastA]){

A[indexA] = B[lastB];

indexA--;

lastB--;

}else{

A[indexA] = A[lastA];

indexA--;

lastA--;

}

}

}

I have used OR operator in the while loop. So should we still need while(lastB){

A[lastA] = B[lastB];

lastA--;

lastB--;

}