June 27, 2020 3:13 PM - 4:22 PM - mock interview with a friend - Bryant, he likes to focus on communication, testing, and easy level algorithms only

Mock interview transcript

Intention for session
Do test better, optimal solution, quick first 20 minutes - less second > 20 minutes
Communication, walk through the … 

3:13 start time
1470. Shuffle the Array
Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].
Return the array in the form [x1,y1,x2,y2,...,xn,yn].
 
Example 1:
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
brute force extra space O(N) space - for loop, backup x1 to xn, and then move y1, yn to the space - backup x1, x2, ... , xn, fill from left to right, even you take x2 space, you have a copy x2, keep the order of x1, x2, …, xn in extra space O(n/2)
Brute force 

8 minutes - optimal solution 
Come out inplace solution using O(1) space,x2 > y1, x2 -> y1 position
X1, y1
X3, …, xn, x2, y2, …., yn 
Swap x2 and x2
X1, y1, 
X2, …, xn, x3, y2,...yn
Work on y2 now 
X1, y1,
X2, y2, …, xn, x3, x4, … yn

3:21 
Code a brute force solution 
Public void shuffle
Input X1, x2, y1, y2
Output X1, y1, x2, y2

Go through iteration from left to right
If x2 is replaced, then x2 into queue,  y1 replace index = 1 position
Next y1, index = 2, dequeue, got x2, put y1 position
Finish all the x -> complete 
Input X1, x2, x3, y1, y2, y3
0 - 2
IndexY - half 3
X1, y1, 
[x1, x3] - maintain the order of x1, x3

End 3:29
Went well?
Start from brute force solution, using extra space O(n/2), find optimal space O(2), O(1), using queue -> change my mind to communicate with interviewer

Do better/differently?
Should ask 
 
Example 1:
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is  [2,3,5,4,1,7].
I      j
2,5,1
3,4,7
List<Integer>res
while(i<nums.length/2){
res.add(i++)
res.add(j++)
}
Return res;

Intention
Start brute force solution
Ask permission for next step - write or continue to search optimal 
Make sure that interviewer understands me, give an example to explain clearly. 

3:38 PM
1342. Number of Steps to Reduce a Number to Zero
Input: num = 14
Output: 6
Step: If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.
14 -> 7 -> 6-> 3 -> 2 -> 1->0  true  - test number = 14, step = 6
-5 -> 
Int reduceToZero(int number) // -5
{
	Int steps = 0; //
  Int start = number; //
 
  while(start > 0)
  {
    if(start %2 == 0){
  	  start = start/ 2;
    }
    else{
      start -= 1;
    }
    
    steps++; 
  }

  return steps;
} 
 
3:49 after quick feedback
Int reduceToZero(int number) // 14, 7, 6, 3, 2, 1, 0
{
	Int steps = 0; 
  while(number >0) 
  {
		if(number%2 == 0)
    {
      Number = number/2; 
    }
    else 
    {
      Number -=1;
    }
    
    steps++; // 1, 2, 3, 4, 5, 6
  }
  
  Return steps;
}

Went well:
Writing in google docu - advise if/else for interviewer
Testing is more readable from interviewer, numbers at the function, easy to verify, do not cheat in testing

Do different
Ask question about edge cases, negative, -> get to zero, if possible, 
Time complexity: 

4:01PM

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
The result can be in any order.
Each element in the result must be unique.
Go over the first array each number, find it is in second array.
Time complexity: O(N * M), N is size of array A, M
Space: O(1)

Sorting ascending O(nlogN + MlogM + M + N) = O(NlogN) if N > M
O(NlogN)  N = Math.Max(M, N)
4, 5, 9
        i
4, 4, 8, 9, 9
             j
4 -> [4]
  
Put first array into hashset, put second array into hashset, then call A intersection B 

A hashset
Go over each number in B, check if number is hashset
Add the number to result list   

I need to remove duplicate numbers in result list, so it is better to save into a hashset first, and convert to list in final step 
Time O(M + N)
Space: O(Math.Min(M, N))

// [2, 2, 3]
// [2, 2, 4]
// output [2]
Public IList<int> findIntesectionUnique(int[] A, int[] B)
{
	if(A == null || B == null)
    Return null;

	// put one array into hashset - 
 	Var hashset = new HashSet<int>(A); // {2, 3}
	Var found = new hashSet<int>(); // {}
	for(int i = 0; i < B.Length; i++) // 2, 2,4
  {
    if(hashset.Contains(B[i])
    {
      found.Add(B[i]); // 2,2
    }
  }
  
	Return found.ToList(); //[2]
}

4:22 pM
Went well
Brute force - interviewer understood the idea
Move to better solution - sorting, two sorting - idea - 
Talk about - use one hashset, wrote the code , test is more clear to interviewer

Do better
I am not so sure… sorting idea -