Because many friends ask me to write a blog about how to deal with VO or mock interviews, I write this to share the process I will do during VO. This blog only represents personal suggestions, if you disagree, please try to avoid using it! If you have any suggestions to make it better, please feel free to contact me!

Background

VO is the online video interview, the interviewer will give you one or two algorithm questions and you need to give the best solutions with minimal time complexity and space complexity.
The No. 1 thing we need to know is that the interview is a chance for you to cooperate interviewer and they may your future colleagues, and expect you can clearly express solutions you have or problems you meet and can solve problems after receiving the hints.

Interview Process

Problem Description

  1. Try to ask the interviewer to give the text version of the problems and specific examples

  2. Request information about arguments’ boundary

Solution

  1. If you have enough time, you can write down brief solutions from brute force solution to an optimized solution

  2. Write down the best solution steps with a brief description and ask the interviewer whether you are on the right track and can implement it or not

Coding

  1. Write the best algorithm with continuing to describe what you are writing

  2. Give necessary comments for important steps with order number

Dry run

  1. Dry run your code with the example you get previous

  2. Step-by-step dry run to check whether you can get the expected result

Analysis

Ask whether the solution works for your interviewer, if works, then you can give your algorithm’s time complexity and space complexity.

Template example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example:
[4,5,6,7,0,1,2] target = 7, 2 , 3
return 3, 3 is the index of the target value
return 6
return -1
input : rotated array
        target: number
output: index of the number  

solution:
use binary search find pivot point and then make sure target number in which snap
use binary search in target snap find target num's index

dry run
[4,5,6,7,0,1,2] target = 7
pivotIndex = 3

left :
[4, 5, 6, 7]
low 0 2 3
high 3
target 7
mid index : 
1 -> 5
2 - > 6
3 -> 7

Time Complexity: Olog(n)
Space Complexity: O(1)

*/


public class Main {
    public static void main(String[] args) {
        System.out.println("Hello LeetCoder");
        int[] nums = {4,5,6,7,8,1,2,3};
        int target = 8;
        System.out.println(findTargetIndex(nums, target));
    }

    public static int findTargetIndex(int[] nums, int target){
        // find pivot point
        int low = 0;
        int high = nums.length - 1;
        //
        while(low < high){
            if(nums[low] > nums[low +1]){
                 break;
            }
            low++;
        }
        //[1, 2, 3, 4]
        if(low == nums.length-1){
            // binary seach whole array
            return bs(nums, 0, nums.length-1, target);
        }
        int pivotIndex = low;


        if(nums[pivotIndex] < target){
            return -1;
        }
        if(target <= nums[nums.length -1] && target >= nums[pivotIndex+1] ){
            // binary search from pivot right
            return bs(nums, pivotIndex+1,nums.length -1, target );
        }

        if(target >= nums[0] && target <= nums[pivotIndex]){
            // binary search from pivot left
            return bs(nums, 0 ,pivotIndex , target );
        }
        return -1;
    }

    public static int bs(int[] nums, int low, int high, int target){
        while(low <= high){
            int mid = (low + high) /2;
            if(nums[mid] > target){
                high = mid-1;
            }else if(nums[mid] < target){
                low = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}