Flipkart conducted its test on Interviewstreet. There were 20 objective questions and 2 programming questions. Test was for 2 hours.

Here are the 2 programming questions :

1) You are given an array of integers. You need to find the minimum number of swaps necessary to make the array sorted.

Eg. [3,2,1] -> 3 swaps needed

[1,2,3] -> 0 swaps needed

2) Snakes and ladders game. Find the smallest number of jumps (ie optimal no of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes. (Hint: Think about the problem in terms of a graph)

Here are the 2 programming questions :

1) You are given an array of integers. You need to find the minimum number of swaps necessary to make the array sorted.

Eg. [3,2,1] -> 3 swaps needed

[1,2,3] -> 0 swaps needed

2) Snakes and ladders game. Find the smallest number of jumps (ie optimal no of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes. (Hint: Think about the problem in terms of a graph)

In the first question the first example can be made sorted by swapping 1 with 3 (i.e. only one swap). Were the swaps supposed to be adjacent?

ReplyDeleteYes the swaps need to be adjacent.

ReplyDeleteWe can solve the problem using Binary Index Tree

ReplyDeletehttp://anandtechblog.blogspot.com/2012/08/insertion-sort.html

To Be specifi we can solve the first problem using Binary Index Tree

ReplyDeleteSecond Problem can be solved by performing BFS from Start and End position.

ReplyDelete@Anand Yes your ideas seem correct! I simply used modified-merge sort to find number of inversions in the array (need to prove that this is the minimum no of swaps needed to sort the array). For 2nd question, I too used BFS!

ReplyDeleteBuy Led tv in Delhi from

ReplyDeleteSargam Electronics