Sunday 9 December 2012

Flipkart Test

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)


6 comments:

  1. 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?

    ReplyDelete
  2. Yes the swaps need to be adjacent.

    ReplyDelete
  3. We can solve the problem using Binary Index Tree
    http://anandtechblog.blogspot.com/2012/08/insertion-sort.html

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

    ReplyDelete
  5. Second Problem can be solved by performing BFS from Start and End position.

    ReplyDelete
  6. @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!

    ReplyDelete