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

ReplyDeleteشركة مكافحة البق الكويت شركة مكافحة البق الكويت

شركة مكافحة حشرات الكويت شركة مكافحة حشرات الكويت

نقل عفش مبارك الكبير نقل عفش مبارك الكبير

نقل عفش مشرف نقل عفش مشرف

نقل عفش الاحمدي نقل عفش الاحمدي

نقل عفش نقل عفش

فني صحي الكويت فني صحي الكويت

نقل عفش المنطقة العاشرة نقل عفش المنطقة العاشرة