Round 1
Questions:
-
Problem 1: Search Insert Position
Link: Search Insert Position
My Solution:int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; }
Time Complexity: O(logN)
-
Problem 2: Find Peak Element
Link: Find Peak Element
My Solution:int findPeakElement(vector<int> nums) { int n = nums.size(); if(n == 1) return 0; if(nums[0] > nums[1]) return 0; if(nums[n-1] > nums[n-2]) return n-1; int low = 1, high = n-2; while (low <= high) { int mid = (low + high) / 2; if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid; else if(nums[mid] > nums[mid-1]) low = mid + 1; else high = mid - 1; } return -1; }
Candidate's Approach
The candidate implemented binary search for both problems. For the first problem, they efficiently found the insert position by checking the middle element and adjusting the search range accordingly. For the second problem, they checked the boundaries and used a similar binary search approach to find a peak element.
Interviewer's Feedback
The round went pretty well, and the interviewer was impressed with the candidate's solutions.