Here’s a challenge for you! This question is from Facebook recruiting portal, graph topic. https://www.facebookrecruiting.com/portal/coding_practice_question/?problem_id=292715105029046 ——- # Minimizing Permutations In this problem, you are given an integer N, and a permutation, P of the integers from 1 to N, denoted as (a_1, a_2, ..., a_N). You want to rearrange the elements of the permutation into increasing order, repeatedly making the following operation: Select a sub-portion of the permutation, (a_i, ..., a_j), and reverse its order. Your goal is to compute the minimum number of such operations required to return the permutation to increasing order. ## Signature int minOperations(int[] arr) ## Input Size N is between 1 and 8 Array arr is a permutation of all integers from 1 to N ## Output An integer denoting the minimum number of operations required to arrange the permutation in increasing order ## Example If N = 3, and P = (3, 1, 2), we can do the following operations: 1. Select (1, 2) and reverse it: P = (3, 2, 1). 2. Select (3, 2, 1) and reverse it: P = (1, 2, 3). output = 2 ## Other examples: minOperations([3, 1, 2]) // => 2 minOperations([1, 2, 5, 4, 3]) // => 1 ————— I did a O(n!) using backtracking, but not sure how to solve this with graph. Any pointers?
Hey man I know you . Your google picture is good. Next time when u post a screen shot just post a content
Lol I have at least five people on LinkedIn who look just like those beautiful pixels
I’m adding personality to the question, lol
Wow this is really hard and I’d be surprised if someone was asked this in an interview. Here’s my initial thoughts, but I haven’t worked through the problem so maybe this is not entirely correct.... This can be expressed as a graph searching/pathfinding problem. You’re given the starting permutation. Think of each unique permutation as a node in the graph. Each transition between nodes is the given function call. Therefore, each node can only transition to another node if it there’s a valid input it can pass to the function. I think you might be able to create a cost heuristic representing the absolute minimum number of operations required to get to the sorted permutation from any permutation. In theory this could be expressed as the total number of values in the sequence where it is not immediately larger or smaller than the neighbour. Using that heuristic, we can implement A* pathfinding. Time complexity for pathfinding is complicated and runtime complexity in practice depends on the heuristic. Worst case is O(B^D) where B is the branching factor (the number of different inputs you can give to the function for a given permutation) and D is depth (the number of times you call the function). Worst case complexity basically degenerates to Dijkstra’s algorithm.
Maybe FB is trying to weed out LC memorizers? The good thing about such hard questions is that the decision comes down to how well you can think and apply (even if you can't reach the most optimal solution) which is generally better than looking for regurgitated LC answers.
Are they expecting the most optimal solution to this problem still? And if someone does describe the optimal solution, how would you tell if they didn’t see it before?
There used to be an FB coding challenges page a few years ago. Wonder what happened to it? Didn't know FB had it's internal coding prep portal!
Their coding challenges/prep is open to anybody that sign up
Are all questions different from LC? Are they no longer asking 2 FB tagged LC mediums per coding round?
Just BFS start from the sorted state
What would be the running time?
n^k. k is the minimum distance
Can you please post a link?
https://www.facebookrecruiting.com/portal/coding_practice_question/?problem_id=292715105029046
From the console error log, the fb recruiting code prep portal uses hackerearth.
Yes! I noticed that as well!
I'm hard while I leetcode
I suspect there are no polynomial time solutions for this problem. This is similar to pancake sorting, a well known NP hard problem. The difference is that with pancake sorting, you can only select (0 ... aj) and reverse the order. Being able to choose an arbitrary ai instead of 0 only increases the combinations and not decrease it. While this and pancake sorting seems like there are subproblems which can be exploited by DP, it cannot as every substring you can arrange in increasing or decreasing order and eventually get a solution. Anyways I would do BFS of the graph for this question to get a solution.
Bill Gates wrote a paper on pancake sorting
Tech Industry
Yesterday
1367
Women, help me understand why this is inspirational
Health & Wellness
Yesterday
422
Lasik cost
Tech Industry
Yesterday
2370
What happens when most of your team is Indian?
Tech Industry
3d
61873
Crossed a line with my boss
Software Engineering Career
Yesterday
180
Most Amazon folks are rude on blind?
Use BFS.
Example please?
So something like, for all possible next states, calculate how far it is from the target sorted state, (prune those that are farther), then next set of states? Without search space reduction, not sure how BFS would do any better than what OP is doing (worst case). I am dumb; please explain. I do want to know.