March 28, 2020 - 5:30 PM - 7:00 PM - mock interview

Mock interview

5:34 PM



Input: [1,2,-1,8,1,-1]
Output: [-1,-1,1,2,8,1]

Is [-1, -1, 1,1 ,2 ,8] acceptable? 

Brute force - go through twice, first time you go through negative number, put into the list, second time you go through the positive number, append -> list 
O(N), space O(N) list -> array - new list

In place - O(N) time complexity, O(1) space 
Keep the order 
1, 2, -1, 8, 1, -1
-1, 2, 1, 8, 1, -1
-1, -1, 1, 8, 1, 2  -> 8, 1, is not position properly - swap 

From consider left to right
1, 2, -1, 8, 1, -1
I
1, 2, -1, 8, 1, -1
        J

1, 2, -1, 8, 1, -1
                 i   
1, 2, -1, 8, 1, -1
                       J
1, 2, -1, 8, -1, 1
             i    j
1, 2, -1, -1, 8, 1
     i         j
1, -1, -1, 2, 8, 1
i         j
-1, -1, 1, 2, 8, 1

I = 1 is leftmost one to terminate the search 





-1 <= elements <= 10^5

// 1, 2, -1, 8, 1, -1 <   pos = 5, i = 5
// 1, 2, -1, 8, 1, -1 <   pos = 5, i = 4  - pos--
//  1,2,-1,  -1,8,  1 <   pos = 4, i = 3
//  1, -1, -1, 2,8, 1 <   pos = 3, i =2		i: pos:
//  1, -1, -1, 2, 8, 1 <  pos = 2, i = 1
//  -1, -1, 1, 2, 8, 1 < pos = 1, i = 0
283. Move Zeroes
Void MoveNegativeOneToFrontKeepOrder(int[] numbers) // -1, 3, 2
{
if(numbers == null ||numbers.Length == 0)
 return;
   // count -1 number in total
  // put all positive from last one to the end - do one pass
 // var countNegative = 0; 
  var length = number.Length; 
  var pos = length - 1; // 3

  for(int i = length - 1; i >= 0; i--) 
 {
     var current = numbers[i]; // 2
     Var isNegative = current == -1; 
     if(!isNegative)
         {
 numbers[pos] = current; // numbers[2] = 2
// numbers[i] = -1; // replace its value
 pos--;// 1
 	}
     }
}


public class Solution {
    public void MoveZeroes(int[] nums)
        {
            if (nums == null)
                return;

            var nonZeroCount = 0;
            var length = nums.Length;

            for(int i = 0; i < length; i++)
            {
                var current = nums[i];
                if (current == 0)
                    continue;

                nums[nonZeroCount] = current;
                nonZeroCount++;
            }

            for(int i = nonZeroCount; i < length; i++)
            {
                nums[i] = 0;
            }
        }
}