Company : **Flipkart**

I was interviewed for Flipkart SDE 2 role few days back. I want to share interview experience with other geeks.

**Written Test:**

It was online coding round on interview street. (1Hr)

**Technical Rounds:**

Q1. Check whether given Binary Tree is a Binary Search Tree. Discuss various approaches?

Q2. Given a large list of numbers in a file and a very small amount of memory, sort the file.

Q3. Implement a phone book. You can search either by name or phone number. You can search by prefix also. Write whole code with proper syntax.

Q4. Given an array of integers, find Pythagorean triplets. i.e. find a,b and c which satisfies a^2 + b^2 = c^2. Integers could be positive or negative.

Q5. Given a number, compute the nearest palindrome number. This palindrome number should be greater than given number.

Q6. Given two string str and pat. Find minimum window in str which contains all characters from string pat.

Q7. Input : 4 jars and 50 balls of different colors (Red, Green, Yellow, Blue) where each jar can contain a maximum of 100 balls.

Problem : When a user draws a red ball he loses his money while if he draws a ball of some other color his money is doubled. Arrange the balls in such a way that the user has highest probability to lose.

The technical questions asked mostly deal with data structures and common algorithms. We hope this help you in your preparations and you get the job you want. Good luck!

Q7: Take all balls except red colored into one jar and distribute red balls into remaining 3 jars equally, so the probability of selecting jar with red balls is 3/4 and selecting red ball from from previously selected jar 1. So by doing this we can increase the probability of selecting red ball..

Correct me if my method is wrong..

Put one red balls in each of the three jar. This would make the probability of choosing red 0.75 and the remaining red balls let say x, would be in last jar. Hence total probability will be 0.75+ x/188.

Q7: Take all balls except red colored into one jar and distribute red balls into remaining 3 jars equally, so the probability of selecting jar with red balls is 3/4 and selecting red ball from from previously selected jar is 1. So by doing this we can increase the probability of selecting red ball. i.e. 3/4 every time

Correct me if my method is wrong..

public class NextPalindrome {

public static void main(String[] args) {

int num=0;

num=999;

System.out.println(“num= “+num +” palindrome =”+ getNextHigherPalnidromeNumber(num));

num=1234;

System.out.println(“num= “+num +” palindrome =”+ getNextHigherPalnidromeNumber(num));

num=191;

System.out.println(“num= “+num +” palindrome =”+ getNextHigherPalnidromeNumber(num));

}

public static int getNextHigherPalnidromeNumber(int input){

if(input==9) return 11; // For 9 next palindrome is 11

if(input<9) return input+1; // for 0 to 8 next palindrome is next number

// So now number is two digits or more

// Separate out digits

int temp = input;

ArrayList digitList = new ArrayList();

while(temp>0){

digitList.add(temp%10);

temp = temp /10;

}

// digitList(0) is digit at unit place

// digitList(n) will be digit at highest place.

// Now check if input is equal to max palindrome of that length

// In that case next palindrome is min palindrome of lenght+1

if(input==getMaxPalindromeOfLenthN(digitList.size()))

return getMinPalindromeOfLenthN(digitList.size()+1);

// It is not max palindrome of that length. next palindrome is of same length as input.

/* if input is 1356 then we will start with first & digit same as input 1 _ _ 1

* Now we will call same function to get palindrome of internal number by striping first and last digit viz. 35. So function will return 44

* So answer is 1 4 4 1

*

* Now if number is 1996 the we will start with 1 _ _ 1

* Now we will call same function to get palindrome of internal number by striping first and last digit viz. 99. So function will return 101

* So it returned palindrome of length more than 2; it means we should increase outer digit

* 2 _ _ 2

* And we should fill it up with zeros so answer for 1996 is 2002

*

*/

// Strip first and last digit

// for number 7986 List is -> 6,8,9,7

// So starting with digit at index n-2 till index 1; prepare number

int outerdigit =digitList.get(digitList.size()-1);

// So 7 _ _ 7 is time being 7007.

int returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1) + outerdigit;

temp = 0;

for(int i=digitList.size()-2;i>=1;i–){

temp = temp*10 + digitList.get(i);

}

int palindromeForInnerNumber= getNextHigherPalnidromeNumber(temp);

// for inner number 99 palindrome will be 101. In this case we should increase higher number and use all zeros

// Inner number is of length digitList.size()-2. So palindrome of biggger length id digitList.size()-2+1

// For input number 79998 inner number is 999. And its palindrome is 1001.

// Now outer number was decided as 7 and we had prepared temporary palindrome as 7_ _7. So we should make it 8_ _ 8 means 8008

if(palindromeForInnerNumber==getMinPalindromeOfLenthN(digitList.size()-2+1)){

outerdigit++;

returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1)+ outerdigit;

}else{

// For input 7865 palindrome is decided as 7_ _7 i.e. 7007. Inner number is 86. Its palindrome is 99.

// Now 99 is to be fit into middle slot. So we will multiply it by 10 and add into number

// 7007 + 99*10 = 7007 + 990= 7997

returnVal= returnVal+ palindromeForInnerNumber*10 ;

}

return returnVal;

}

public static int getMinPalindromeOfLenthN(int n){

/* For length min palindromes are as follows

* 1 1

* 2 11

* 3 101

* 4 1001

* 5 10001

*/

// So 1 is present at 10^(n-1) and unit digit

// so number is 10^(n-1) + 1

if(n==1)

return 1;

return (int)Math.pow(10, n-1) + 1;

}

public static int getMaxPalindromeOfLenthN(int n){

/* For legth max palindromes are as follows

* 1 9

* 2 99

* 3 999

* 4 9999

*/

int num =0;

for(int i=1;i<=n;i++){

num = num*10+9;

}

return num;

}

}