## SDE-2 Interview Questions

- 0of 0 votes
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

You have to print the sub-sequence also.

- 1of 1 vote
Generate all Kaprekar Number (refer Wiki for Kaprekar number's definition) from 1 to 999999.

I gave a brute force approach of generating all number in the range and checking if it is Kaprekar or not.

- 1of 1 vote
For a given array with positive and negative element, find sub array with maximum sum. Sub array must have same sequence of element as that of parental array.

Eg: P = {4,6,-3,1,5,9,-2} then S ={4,6,-3,1,5,9} //Correct output.

- 1of 1 vote
Construct an array of size 10 such that if a[x] =y then x should be repeated y times in that array. Eg: If a[1] = 2 then 1 should be present in that array 2 times.

- 0of 0 votes
As you are on Seattle, tell me how many rain drops pour on earth every year

- 0of 0 votes
We have a bag containing numbers 1, 2, 3, …, 100. Each number appears exactly once, so there are 100 numbers. Now one number is randomly picked out of the bag. Find the missing number.

- 0of 0 votes
Given 2 sorted lists that are of even and equal size, output the median. If there is no middle number, return the average of the 2 middle numbers

- 0of 0 votes
Design a web-site like Paypal.

The interviewer was interested in the

i) Major components & the way they will interact.

ii) Various way of scaling the web-site to support many users

iii) Handling the failure cases like when the DB goes down, etc.

- 1of 1 vote
Given a binary matrix of 0 and 1. Find the longest sequence of 1's either row wise or column wise.

For example

0 0 0 0 0 0

0 1 1 1 0 0

0 0 0 1 0 0

It should return 1 1 1

- 0of 0 votes
Given a list of interval , find the maximum overlapping interval. For ex if input is (0,5) (2,9) (8,10) (6,9) then ans is 2,9 as its overlap are 3.

- 4of 4 votes
Given stock price of Amazon for some consecutive days. Need to find the maximum span of each day’s stock price. Span is the amount of days before the given day where the stock price is less than that of given day

E.g i/p = {2,4,6,9,5,1}

o/p= { -1,1,2,3,2,-1}

- 1of 1 vote
Given a matrix of characters and a string, find whether the string can be obtained from the matrix. From each character in the matrix, we can move up/down/right/left. for example, if the matrix[3][4] is

o f a s

l l q w

z o w k

and the string is follow, then the function should return true.

- 0of 0 votes
Given 2 strings str1 and str2. What is the efficient way to navigate from str1 to str2? The constraints are i) a string can be changed to another string by changing only one character. ii) all the intermediate strings must be present in dictionary. If not possible, return “not possible to navigate from str1 to str2″. (pre-processing is allowed and enough memory is available). for example: str1 = feel and str2 = pelt, then the navigation is feel -> fell -> felt -> pelt

- 0of 0 votes
A number series have numbers in the increasing order where numbers are of the form 2^m*3^n*5^p. where m,n,p are an non negative integers. The initial few number of the series are

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18......

Write a function to get the nth term of such a sequence.

- -2of 4 votes
Asked to explain how to check Binary tree is BST?

- -3of 3 votes
Find Nodes which are at "K" distance from given node.

- -3of 3 votes
Find In order predecessor in BST.

- -4of 4 votes
asked me about assembly line problem.

- -4of 4 votes
asked me to solve Knapsack Problem

- -3of 3 votes
Asked to explain how to check Binary tree is BST?

then asked me to write whole code of it.

- -1of 3 votes
Find Nodes which are at "K" distance from given node.

explain logic and write full code with all boundary conditions.

- -3of 3 votes
Find In order predecessor in BST.

explain logic and write full code with all boundary conditions.

- 0of 2 votes
In a Binary tree, every element(node's value) must contain the sum of its left and right sub-trees.

Follow up question: how would you solve this if you can ONLY increment the value of a node

Eg. If a node’s value is 20 and its sub-tree sum is 10, the node’s value can’t be set to 10 because you can only increment.

How would you solve this if you can ONLY increment the value of a node

Further clarifications.

1. You can make assumption that leaf nodes retain their original value and does not change.

2. "Sum of its left and right subtrees" means sum of all nodes' values in its left subtree + sum of all nodes' values in its right subtree.

PS: I am asking this question coz I am not sure of its solution myself. Hence seeking experts' advice.

- 1of 1 vote
In Amazon web site, the product items has to show with different attributes combination for clothers.

Example:

color - red blue green

size - XL X M S

pattern - checks lines

so output should be in below format in different combinations:

red - xL - checks

red - xL - lines

red - X - checks

red - x - lines

red - M - checks

:

:

green - S - checks

green - S - lines

Note:- In above example, no. of attributes is 3. but attributes can be N.

Below is the code, I have written. Hope it will be useful for anyone.

This is an non-recursive logic which will work for large value of N. time Complexity is O(n2).`------------------------------------------------------------------------------------- package com.test; import java.util.Scanner; public class Solution { public static void main(String args[] ) throws Exception { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ Scanner in = new Scanner(System.in); int n = in.nextInt(); in.nextLine(); //to read new line String[][] attributes = new String[n][]; int i=0; while(i < n) { String temp = in.nextLine(); String[] values = temp.split(" "); attributes[i] = values; i++; } printAttributesCombination(attributes); } static void printAttributesCombination(String[][] attributes) { int count[] = new int[attributes.length]; int totalcount[] = new int[attributes.length]; //initialize the totalcount and temp index count initialize(count, totalcount, attributes); while(isDone(count,totalcount)) { printArray(attributes,count); } } static void initialize(int count[], int totalcount[], String[][] attributes) { for(int i = 0; i < count.length; i++) { count[i] = 0; totalcount[i] = attributes[i].length - 1; } count[count.length-1] = -1; } static boolean isDone(int count[], int totalCount[]) { boolean prevIndexSet = true; boolean canTerminateLoop = false; int i = 0; for(i = count.length - 1; i >= 0 ; i--) { if(count[i] == totalCount[i]) { count[i] = 0; prevIndexSet = true; canTerminateLoop = true; } else { count[i] = count[i] + 1; prevIndexSet = false; canTerminateLoop = false; } if(!prevIndexSet) break; } if(canTerminateLoop && i == -1 ) return false; return true; } static void printArray(String[][] arr, int count[]) { System.out.println(); for(int i = 0; i < arr.length; i++) { System.out.print(" " + arr[i][count[i]]); } } } -------------------------------------------------------------------------------------`

Output:

==============

Sample1:-

============

3

a b c

d e f

g h i

a d g

a d h

a d i

a e g

a e h

a e i

a f g

a f h

a f i

b d g

b d h

b d i

b e g

b e h

b e i

b f g

b f h

b f i

c d g

c d h

c d i

c e g

c e h

c e i

c f g

c f h

c f i

Sample2:-

============

4

a b

a b c

d e

f i

a a d f

a a d i

a a e f

a a e i

a b d f

a b d i

a b e f

a b e i

a c d f

a c d i

a c e f

a c e i

b a d f

b a d i

b a e f

b a e i

b b d f

b b d i

b b e f

b b e i

b c d f

b c d i

b c e f

b c e i

- 0of 0 votes
Develop a program to demonstrate your implementation of a CSV parsing framework which can be used to generically parse given CSV file into Java beans and prints out information about parsed objects using toString(). The program should follow OOAD open-closed principle to avoid/minimize modification of code when new types are added in future.

You should accept input from STDIN and print the output to STDOUT.

Assume following input format and study sample inputs given below:

Data-type

Header-Row

Data-Row-1

Data-Row-2

....

Data-Row-N

The first line indicates the entity type, 2nd line is comma separate list of column names, 3rd line onwards is the comma separated data values.

Test Case 1 Input

Type:Employee

name,age,salary

Ashok,36,20000

Kishor,30,15000

Bharath,25,30000

Expected Output

Name : Ashok;Age : 36

Name : Kishor;Age : 30

Name : Bharath;Age : 25

Test Case 2 Input

Type:Department

code,name

acc,accounts

prl,payroll

Expected Output

Code : acc;Name : accounts

Code : prl;Name : payroll

Your solution should parse the input into Java Beans (POJOs). For example, in test case 1, you will be make use of following Java bean (if you chose Java as programming language, and equivalent if you were using other language).

class Employee {

private String name;

private int age;

private int salary;

public Employee() {

}

public void setName(String name) {

this.name = name;

}

public String getName() {

return this.name;

}

public void setAge(int age) {

this.age = age;

}

public int getAge() {

return this.age;

}

public void setSalary(int salary) {

this.salary = salary;

}

public int getSalary() {

return this.salary;

}

public String toString() {

return "Name : " + this.name + ";" + "Age : " + this.age;

}

}

You can create a similar bean for Department as required for test case 2.

- 0of 0 votes
An array is given like {3,6,10,4,5,7,8}. Pick any two number suppose 10 and then 7, as 10 >7, it's an inversion, now if you choose 3 & 5, 3<5, it's not an inversion.

So you have to write a program to calculate total no of such inversion, in a given array. You can use extra space of O(n).

- 2of 4 votes
Given an Array, replace each element in the Array with its Next Element(To its RHS) which is Larger than it. If no such element exists, then no need to replace.

Ex:

i/p: {2,12,8,6,5,1,2,10,3,2}

o/p:{12,12,10,10,10,2,10,10,3,2}

- 1of 3 votes
One of the questions in one of the interviews -

Given a stack S and another empty stack T and a variable v, write a function that returns S but with its elements reversed.

- 0of 0 votes
Design a download manager. The download manager would be shipped with a browser. Detailed design of components and interaction between them.

Follow up question - What features would you add to the download manager so that it is more marketable than others.

- 0of 0 votes
Shopkeeper want sells in the packs of 20,9 and 6. Given an n, you need to find whether its possible to buy the items or not.For example n=21, you can buy 2 packs of 6 and one pack of 9(2*6 + 9)

Output 1 if possible and 0 if not

Test cases:

1) n=47 ==> possible, output = 1

2) n=7 ===> not possible, output = 0