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!
ReplyDelete