Day 11 Interview

LeetCode – Remove Duplicates from Sorted Array

 

1. Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory.

For example, given input array A = [1,1,2], your function should return length = 2, and A is now [1,2].

2. Idea

In the presence of the limit not to allocate extra space for another array, we have two alternatives to remove duplicates: one is to actually remove duplicates by moving the following numbers forward, and the other one is to maintain an index of the last “effective” number and copy each different number to that index. With an easy observation, it turns out that the first solution yields O(n2) time complexity, while the second one does O(n) . Therefore, I took and implemented the second one and passed LeetCode OJ.

3. Implementation

4. Wrap-up

No extra space is used for the above implementation. One pass of all the numbers suffices.

 

LeetCode – Remove Element

 

1. Problem

Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

2. Idea

This is a variant of LeetCode – Remove Duplicates from Sorted Array, except that in this case, the number that is the same with given value is removed. Anyway, the same idea applies.

3. Implementation

public int removeElement(int[] A, int elem) {
   int count = A.length;
int result = 0;

for (int i=0; i<count; i++) {
if (A[i] != elem) {
A[result++] = A[i];
}
}
return result; }

LeetCode – Divide Two Integers

 

1. Problem

Divide two integers without using multiplication, division and mod operator.

2. Idea

Consider a simple case where both the dividend and divisor are positive. Without using multiplication, division and mod operator, we could subtract the divisor from the dividend until the remainder is smaller than the divisor. Then the number of subtraction (denoted by q ) is the quotient between the dividend and the divisor. However, this solution is rather slow, with a time complexity of O(q) . As it turns out, an implementation of it would exceed the time limit when the dividend is large (say 231 ) and the divisor is small (say 2).

However, based on this intuitive idea, we can propose an improved solution to reduce the time complexity and thus to pass the test. The insight is that instead of subtracting the divisor each time, we could have subtracted multiples of the divisor. And though direct multiplication is forbidden, left shift operation can be used as an alternative. In other words, we first find the maximum 2-power multiples (2x, 4x, 8x, etc.) of the divisor that does not exceed the dividend, subtract it from the dividend, and try a smaller 2-power multiples of the divisor repeatedly until we arrive at the divisor itself. And of course, all possible cases involved in the computation, such as possibility to overflow and positive/negative numbers,  need to be handled carefully.

3. Implementation

4. Wrap-up

It can be seen that the time required depends on the number of the digits in the binary representation of the quotient. That is, the time complexity isO(logq) .

 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s