First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Approach : Use binary search to find the lowest bad version.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// Forward declaration of isBadVersion API. bool isBadVersion(int version); int first(int low, int high){ if(isBadVersion(low)){ return low; } int mid = low + (high - low) / 2; //if it is the first bad version or the version before it is not a bad version then return this version if((mid == 0 || !isBadVersion(mid - 1)) && isBadVersion(mid)){ return mid; }else if(isBadVersion(mid)){ //find a smaller bad version return first(low, mid - 1); }else{ //find a larger bad version return first(mid + 1, high); } } int firstBadVersion(int n) { return first(0, n - 1); }

Read More

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Approach:

The idea is to traverse the array couple of times from left to right once and right to left once keeping track the accumulated product so far from both the sides. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ vector<int> productExceptSelf(vector<int> &nums) { int numsSize = nums.size(); vector<int> result(numsSize); int temp = 1; // stores the product on the left of each element excluding itself for(int i = 0; i < numsSize; i++){ result[i] = temp; temp = temp * nums[i]; } temp = 1; // stores the product on the left times product on right of each element excluding itself for(int i = numsSize - 1; i >= 0; i--){ result[i] = result[i] * temp; temp = temp * nums[i]; } return result; }

Read More

Reverse String

Write a function that takes a string as input and reverse the same.

Example:

Given s = "hello", return "olleh".

Approach: The idea is to swap the last and the first characters till the middle is reached.

1 2 3 4 5 6 7 8 9 10 11

string reverseString(string &s) { int low = 0, high = s.length() - 1; while(low < high){ char t = s[low]; s[low] = s[high]; s[high] = t; low++; high--; } return s; }

Read More

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Approach:  The idea is to traverse the string from both ends while skipping the non-vowels characters from both ends.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

char* reverseVowels(char* s) { int low = 0, high = strlen(s) - 1; char c; while(low < high){ //move forward to skip consonant while(low < strlen(s) && tolower(s[low]) != 'a' && tolower(s[low]) != 'e' && tolower(s[low]) != 'i' && tolower(s[low]) != 'o' && tolower(s[low]) != 'u'){ low++; } //move backward to skip consonant while(low < high && tolower(s[high]) != 'a' && tolower(s[high]) != 'e' && tolower(s[high]) != 'i' && tolower(s[high]) != 'o' && tolower(s[high]) != 'u'){ high--; } if(low < high){ c = s[low]; s[low] = s[high]; s[high] = c; low++; high--; } } return s; }

Read More

Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void moveZeroes(int* nums, int numsSize){ int i = 0, j = 0; for(i = 0; i < numsSize; i++){ //copy non-zero elements if(nums[i] != 0){ nums[j] = nums[i]; j++; } } //put zeros in the end while(j < numsSize){ nums[j++] = 0; } }

Read More