Count Possible Decodings of a given Digit Sequence

Find number of ways a string can be decoded into, if A=1, B=2, C=3 ... Z=25 and encoding number is 123 ways decoding can be done is
1 2 3 = A B C
1 23  = A X
12 3  = L C

Word Break Problem

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies now a days.

Consider the following dictionary 
{ i, like, go, hired, gohired, site, sweet,fruit, man, go, mango}

Input:  ilike
Output: Yes 
The string can be segmented as "i like".

Input:  ilikemango
Output: Yes
The string can be segmented as "i like mango" or "i like man go".

HackeEarth Flipkart's Drone

After listening to the news of testing of Delivery Drones by ....
But this was only possible if two of the shipping addresses had "V1-type" road connecting them(V1-type roads are the fastest in the city). So, Sachin and Binny ask you for a little help. They want you to tell them if they could send two orders together for two given locations or not.
Read Question at : http://www.hackerearth.com/problem/algorithm/sachins-drones/

Print all nodes that are at distance k from a leaf node

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance k from a leaf means k levels higher than a leaf node.
For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.

           [1]
          /   \
       [2]     [3]
      /  \     /  \
    [4]  [5] [6]  [7]
    /
  [8]

Here Output should be 1, and 2 for K=2 as both are at 2 distance from leaf nodes.
1 is at K=2 distance from 5 and  2 is K=2 distance from 8.

Generate next palindrome number

Several Companies like MS, Amazon and Flipkart has started asking this question to generate next number which is palindrome.

Say K is given, Generate N such that N is palindrome and N > K.

Flipkart SDET Interview Experience

I have recently appeared for Flipkart Interview for SDET-1 position
Sharing my Interview experience.

There were Total 5 rounds
Round 1 ) Telephonic Round
I was asked two questions
     Q1) Find Pythagoras triplet in array (Just logic required)
          Write Testcases for that in code.
     Q2) Implement LRU Cache ( give DStructure used and why)
     Q3) SQL queries to get id of manager, and some other to where we need to use inner queries.

Search element in a matrix with all rows and columns in sorted order

Given a matrix containing unique numbers in which all rows and columns are in sorted order.
And You have to search an element output its location row,column number .
If no such element the just print ”-1 -1”.

Example:

5  5                               //size of matrix
 -10   -5   -3    4     9     //matrix
-6     -2     0    5    10
-4     -1     1    6    12
  2      3     7    8    13
100  120 130 140 150

Implement LRU Cache

Generally Interviewer can ask you simply to implement LRU cache, first explain which data structure you will use and why.

Its well known coding question being asked by all Tech giants like Amazon , Flipkart, Microsoft. 

LRU (Least Recently Used) Cache holds Page numbers which are recently used and throws out old or least recently used page number or entries.

Given Set of words or A String find whether chain is possible from these words or not

You are given N strings or N words. You have to find whether a chain can be formed with all the strings given namely n ?

Chain : A chain can be formed between 2 strings if last character of the 1st string matches with the first character of the second string.

Example : cat ,eng, galactic, tree

These words Create chain as  ...  TREE,ENG,GALACTIC,CAT or CAT, TREE, ENG, GALACTIC

Try to think as its simple solution.

Connect n ropes with minimum cost

There are given n ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. We need to connect the ropes with minimum cost.

For example if we are given 4 ropes of lengths 4, 3, 2 and 6. We can connect the ropes in following ways.
1) First connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6 and 5.
2) Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.
3) Finally connect the two ropes and all ropes have connected.

TicTacToe Game As Asked in Flipkart

Write a running code in any language to implement the famous tic-tac-toe game.
Decide which basic functions which would be required to implement the same. 

Then try to code it your self else basic code is given. below

Get Minimum element in O(1) from input numbers

Question : Get Minimum element in O(1) from input numbers..

- With any traditional way we can't get minimum element in O(1)
- so we need to come up with different data structure.
- As its very old and famous question We are directly explaining logic

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Given an array of n distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array such that Arr[i] = i .
If there is any Fixed Point present in array, else returns -1.
Note that integers in array can be negative.

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Main DNA sequence(a string) is given (let say strDNA) and another string to search for(let say strPAT).
You have to find the minimum length window in strDNA where strPAT is subsequence.

Add Sub Multiply very large number stored as string

(Flipkart Machine coding round)
Very large number like 2994320121 and 125346232 is given in character string.
You need to add, subtract and multiply two numbers and store number in character array only.

Flipkart Set 1 On Campus with Answers

Round 1(Online):
There were 2 questions time limit 90 mins.
1. A person wants to go from origin to a particular location, he can move in only 4 directions(i.e East, West, North, South) but his friend gave him a long route, help a person to find minimum Moves so that he can reach to the destination.
Input – NESNWES
Output – E

CodeChef Code SGARDEN

This time Sheriff gathered all the bandits in his garden and ordered them to line up. After the whistle all bandits should change the order in which they stand.
Sheriff gave all the bandits numbers from 1 to N. For each place i he determined the unique position j. After whistling the bandit staying on position i should run to the j-th position. Sheriff loved seeing how the bandits move around, and he continued whistling until the evening. He finished the game only when he noticed that the bandits are in the same order in which they were standing originally.
Now the Sheriff asks the question: How many times has he whistled?

Check Binary Tree is Binary Search Tree or not

To search Binary Search Tree
First lets understand characteristics of BST
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
• Each node (item in the tree) has a distinct key.

Find Percentage of Words matching in Two Strings

There are two strings s1 and s2. Find the maximum of percentage word matching from s1 to s2 and s2 to s1.

Where, percentage word matching= (Total words matched in s2/total number of words in s1) *100

Test Cases for Round Function

Write the test data for the function which takes input value as floating number and precision. It returns the output by rounding the value nearest to precision value.
e.g roundOff (3.4567,2) output will be 3.46.