http://codingrecipies.blogspot.com/2016/09/123.html
Below given are two arrays indicating the size of the arrays and the direction in which they are moving. A bigger fish can eat a smaller fish if they are moving in opposite direction.
Two fishes moving in same direction cannot eat each other because all the fishes are moving at a constant speed. Print the output of the fishes which survives
Fishes with distinct sizes and with their direction of movement from their current index
| 10 |
11
|
8
|
5
|
3
|
4
|
6
|
9
| 2 |
1
|
7
|
| <-- | <-- | --> | --> | --> | <-- | <-- | <-- | <-- | <-- |
-->
|
Output :
| 10 |
11
|
9
|
3
|
1
|
7
|
| <-- | <-- | <-- | <-- | <-- | --> |
Explanation of output:
Fishes with size 10 and 11 won't collide hence escapes,
4 eats 3, 5 eats 4 , 6 eats 5 , 8 eats 6 , 9 eats 8, then 2 and 1 survives because their behind bigger fish 9. Fish 7 survives because from its current position it will not collide with any other fish , hence the output.
static boolean solve(int[] arr,int[] dir){ Stack<Integer> rightDir = new Stack<Integer>(); Stack<Integer> leftDir = new Stack<Integer>(); int i = 0; //Skip all fishes moving to left in the beggining while(dir[i]!=1){ printFish(arr[i],dir[i]); i++; } int len = arr.length ; while(i<len){ if(dir[i] ==1 ) rightDir.push(arr[i]); else leftDir.push(arr[i]); eatFish(leftDir,rightDir); //if Fishes are empty in right stack, print fishes of the left stack //because these fishes moving to the left wont ever collide with subsequent fishes moving the right if(rightDir.isEmpty()) printStackInReverse(leftDir,-1); i++; } //Print Fishes moving the right first printStackInReverse(rightDir,1); printStackInReverse(leftDir,-1); return false; } /** Print stack in reverse order */ static void printStackInReverse(Stack<Integer> stack, Integer direction) { if(stack.isEmpty()) return ; Stack<Integer> temp = new Stack<Integer>(); while (!stack.isEmpty()) temp.push(stack.pop()); while (!temp.isEmpty()) printFish(temp.pop(), direction); } /** Eats fish from the stacks , depending on size */ static void eatFish(Stack<Integer> left, Stack<Integer> right){ while(!(left.isEmpty() || right.isEmpty())){ if(left.isEmpty() || right.isEmpty()) return ; else if(left.peek() > right.peek()) right.pop(); else if(left.peek() < right.peek()) left.pop(); else return ; } } static void printFish(int size, int direction){ System.out.println(direction == 1 ? size + "--> " : "<--"+size + " "); }
