CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Arrange the shuffled cards


Forum Post 1 Answer Arrange the shuffled cards

You have a pack of cards. Each one is a plain card with a number on it. They are all shuffled. You are provided with an algorithm move(int cardNo). This method will pick the card (you passed as param) and put it at the top of all cards. i.e, push back all cards one step down and make your card at the top. Write an algorithm to sort all the cards so that No 1 is at the top and say No.52 is at the bottom. Your algorithm should order it in minimum number of moves. Use the method move(cardNo) in your code. Solution time complexity should be O(n). Assume move(cardNo) as O(1).

Eg :[k 3 4 2 1 5 ] – your move should be to move 2 first and then 1. – No. of moves – 2 . Result : [ 1 2 3 4 5]
[ 1 2 4 5 3 ] – No. of moves – 3

 - vinodhinic August 19, 2013 | Flag |


Comment hidden because of low score. Click to expand.
0
of 0 vote

We need to find the highest card which has higher cards before it.
[3, 4, 2, 1, 5] -> 2 is the highest misplaced card (3,4,5 are in the right order)
[1, 2, 4, 5, 3] -> 3 (has 4 and 5 before it)

Finding this card can be done in O(n): traverse the array from left to right and keep the highest card seen so far. If the current card is smaller than the highest seen so far, then it is misplaced.
Afterwards, we need to place this card correctly. To do so, we need to put it on top of all cards. Hence, all cards smaller than this card will be misplaced as well.
So we need to put all cards smaller of equal to the highest misplaced card on top of the pile. Do this in decreasing order and we are done. The number of moves is equal to the highest misplaced card.

[3, 4, 2, 1, 5] -> 2. Move 2 = [2,3,4,1,5]. Move 1 = [1,2,3,4,5]
[1, 2, 4, 5, 3] -> 3. Move 3 = [3,1,2,4,5]. Move 2 = [2,3,1,4,5]. Move 1 = [1,2,3,4,5]

- Miguel Oliveira August 26, 2013 | Flag Reply




Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More