Facebook Interview Question
Move non-zero elements in int array to the left and return number of non-zero elements in the original array.
The order of the non-zero elements is not important. What is left on the right side of the array is not important. Minimize written to array.
Approach 1: go from back or go from front
[1, 0, 3, 0, 0, 4] -> [1, 4, 3, 0, 0, 0]
Use similar partition algorithm like quicksort partition array
1. Use two indexes to keep track the zero element and non-zero element
2. Initialize the two indexes to be last index
3. One index is decreased by one only if other index is zero element
public static int moveNonZeroToTheRightFB(int[] arr){
int bigIndex = 0;
int pivot = 0;
int len = arr.length;
for(int i = 0; i < len; i++){
if(arr[i] <= pivot){
swap(arr, bigIndex, i);
bigIndex++;
}
}
return len - bigIndex;
}
Quicksort partition technic
// add code here
Given two words, determine if there is a path to get from word A to word B by changing one letter at a time to create valid intermediate words.
For example:
BARK -> BACK -> RACK -> RANK
r->c
b-r
c-n
Inputs are
- Start word
- End word
- Set of valid words
- Return path of words [inclusive]