You have an unsorted array of integers and a function........string getCategory(integer)........which deterministically returns 1 of three possible strings: "low", "medium", or "high", depending on the input integer. You need to output an array with all the "low" numbers at the bottom, all the "medium" numbers in the middle, and all the "high" numbers at the top. This is basically a partial sort. Within each category, the order of the numbers does not matter...For example, you might be give the array [5,7,2,9,1,14,12,10,5,3]. For input integers 1 - 3, getCategory(integer) returns "low", for 4 - 10 it returns "medium," and for 11 - 15 it returns "high". You could output an array (or modify the given array) that looks like this: [3,1,2,5,5,9,7,10,14,12]

Question

You have an unsorted array of integers and a function........string getCategory(integer)........which deterministically returns 1 of three possible strings: "low", "medium", or "high", depending on the input integer. You need to output an array with all the "low" numbers at the bottom, all the "medium" numbers in the middle, and all the "high" numbers at the top. This is basically a partial sort. Within each category, the order of the numbers does not matter...For example, you might be give the array [5,7,2,9,1,14,12,10,5,3].  For input integers 1 - 3, getCategory(integer) returns "low", for 4 - 10 it returns "medium," and for 11 - 15 it returns "high". You could output an array (or modify the given array) that looks like this: [3,1,2,5,5,9,7,10,14,12]

Anonymous · Accepted Answer

There are several suboptimal solutions. The optimal solution solves it in linear time with no additional space. You use three pointers and does swapping. One pointer (or index) starts are the front of the array and keeps track of the location of the next place to put a "low" number. You have another pointer (or index) marking the position near the back of the array for the next "high" number. Then you have another pointer/index for the "middle" numbers.

Anonymous · Answer

The key in these questions is to cover the fundamentals, and be ready for the back-and-forth with the interviewer.
      

Might be worth doing a mock interview with one of the Facebook or ex-Facebook  Software Engineering New Grad experts on Prepfully? They give real-world practice and guidance, which is pretty helpful.
      

prepfully.com/practice-interviews

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches