Implement atoi

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.


Used Java because it`s cleaner

public int atoi(String str) {
        // Start typing your Java solution below
        // DO NOT write main() function
        String expression = str.trim();
        if(expression==null||expression.equals("")){
            return 0;
        }
        int sign = 1;
        int index = 0;
        if(expression.charAt(0) == '-'){
            sign = -1;
        }
        if(expression.charAt(0) == '-' || expression.charAt(0) == '+'){
            index++;
            if(expression.length()==1){
                return 0;
            }
        }
        int ret = 0;
        while(index < expression.length()){
            char c = expression.charAt(index);
            if(c < '0' || c > '9') break;
            int value = c - '0';
            if(sign > 0){
                if(ret > Integer.MAX_VALUE / 10) return Integer.MAX_VALUE;
            }else{
                if(ret < Integer.MIN_VALUE / 10) return Integer.MIN_VALUE;
            }
            ret = ret*10;
            if(sign > 0){
                if(ret > Integer.MAX_VALUE - value)  return Integer.MAX_VALUE;
            }else{
                if(ret < Integer.MIN_VALUE + value ) return Integer.MIN_VALUE;
            }
            ret += value * sign;          
            index++;
        }
        return ret;
    }

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.
Some hints: Could negative integers be palindromes? (ie, -1)


If you are thinking of converting the integer to string, note the restriction of using extra space.


You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?


There is a more generic way of solving this problem.

    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        int numOfDigits = 1;
        int base = 1;
        while(x / base > 9) {
            base *= 10;
            ++numOfDigits;
        }
     
        int head, tail;
        for(int i = 0; i < numOfDigits / 2; ++i) {
            head = x / base;
            tail = x % 10;
            if(head != tail) return false;
            x -= head * base;
            x /= 10;
            base /= 100;
        }
        return true;
    }

In-place array rotation

The idea that is commonly seen in skill testing interview questions is using three reversals to perform the rotations: rev(1,k) rev(k+1,n-k) rev(1,n). This leads us to the following code:

int reverse(struct baseType * a, int n) { 
    int i, j; 
    j = n / 2;
    n--;
    for (i=0; i < j; i++) { 
        struct baseType tmp = a[i]; 
        a[i] = a[n-i];
        a[n-i] = tmp;
    }
    return 0;
}

int rotate(struct baseType a[], int n, int k) { 
    if(a == NULL || n <= 0) 
       return -__LINE__;
    if(k < 0 || k >= n){ 
       k %= n; 
       if (k < 0) k += n; 
    }
    if (k == 0) return 0;
    reverse (a, k);
    reverse (a + k, n - k);
    reverse (a, n);
    return 0;
 }

This solution reads and writes each element twice, however, some quick performance testing on random arrays shows that this code is faster for very small sized baseTypes. The reason being that the reverse() is very good for memory access locality. However, for any larger sized baseTypes, the first code sequence given will win by the simple virtue of performing fewer operations.

Rotating a 2D array of integers (matrix) by a given angle (+90, -90, +180, -180)

This is posted by Rajendra Kumar Uppal

So, I came across this problem on a forum and before looking up, I tried to solve it. After 15 minutes of trying, I figured out that the solution is pretty easy and elegant which was messy otherwise if you are going to do it in an insane way. So, here we go:

Problem definition: You are given a 2D square matrix, or 2D array of integers of size n (n rows and n columns), your output should be n by n 2D matrix rotated by a given angle, which could be +90, -90, +180, -180.

Example:

Input                                              Output

1 2 3                                              7 4 1

4 5 6     Rotate by +90                   8 5 2

7 8 9                                              9 6 3

If you go by solving it something like manually, swapping elements, its going to be messy, tedious, and error prone in that there will be much more edge cases, test cases to handle. So, after trying on paper, I figured out following elegant solution to solve this in an easy manner.

Rotate by +90 (clockwise once):

Input: n by n matrix M, where n >= 2

Algorithm:

Step 1: Transpose M

Step 2: Reverse each row

Dry run:

Step 1: Transpose

M                   M'

1 2 3              1 4 7

4 5 6      --     2 5 8

7 8 9              3 6 9

Step 2: Reverse each row

M'                  M''

1 4 7              7 4 1

2 5 8      --     8 5 2

3 6 9              9 6 3

M'' is rotated form of M by +90 degree.

Pseudocode: is here which is self explanatory and easily convertible to source code in a language of your choice.

Transpose

    for i in [0, n)

        for j in [0, n)

            if ( i < j )

                swap( M[i][j], M[j][i] )

Reverse a row (rowidx)

    start = 0

    end = cols - 1

    while ( start < end ) {

        swap( M[rowidx][start], M[rowidx][end] )

        ++start

        --end

    }

Rotate

    Transpose

    for i in [0, rows)

        Reverse( i )

That was fair enough until only asked to rotate by +90 degree. If problem is further extended to be solved for any given angle, of course the rotation should make sense, for example, 47 degree is not a choice ;-). So, here are some elegant techniques (I'll be brief now for other angles, because for +90 degree I have elaborated the solution):

Rotation by -90 degree (anticlockwise once):

Step 1: Transpose

Step 2: Reverse each column

Rotation by +180 degree (clockwise twice): Two methods follows

First:

Rotate input matrix +90 degree twice, if routine for which is available to you

Second: (You'll be amazed!)

Step 1: Reverse each row

Step 2: Reverse each column

Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows

First:

Rotate input matrix -90 degree twice, if routine for which is available to you

Second: (You'll be amazed again!)

Step 1: Reverse each column

Step 2: Reverse each row

Third: (Aha!)

Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.

Concluding note: Above techniques are elegant and very simple and straightforward to implement. Try them for some input of your choice and rotate it in all angles. These techniques are tested with a working C program.

More array problems

Today I summarize some array problems that an be solved using hash tables.

Remove duplicates in an array.

Before starting with this question, we should ask the interviewer what`s the type of elements in the array. If the answer is character, well, the only thing we need is a boolean array of size 256 (assuming the charset is ASCII). If the answer is integer or other larger types, we should use a hash table.

We solve this question using two indecies, reader and writer. We iterate each element using reader and find its existence in hash table. If it does not exist, we insert an entry in hash table, copy the value indexed by reader to that of writer, and increment both indecies. Otherwise, we increment only the reader index.

This solution costs O(n) time and O(n) space. If extra space is not allowed, we can use any in-place sorting algorithm (e.g. quick sort) to sort the array and then use similar reader and writer technique to remove duplicates. This will cost O(nlogn) time and O(1) space.

Decide if two strings are anagrams.

If number of each character in two strings are the same, then they are anagrams. We can scan the first string and increment the number of occurence of each character using a hash table. Then we scan the second string, decrementing the counter of each encountered character. In the end, if all the entries in the hash table are zero, then the two strings are anagrams.

Another extremely simple solution is to sort two strings and compare if there are equal.

Find the intersection of two arrays.

We assume that there is no duplicate in each array. We scan the first array and mark the occurence of each element. Then we scan the second array and find if each element can be found in hash table. If so, we append it to the result.

Given a number N, find pairs of number a1, a2 in an array such that a1 + a2 = N.

We will scan the array for two passes. In the first pass, we calculate N - a1, where a1 is each element. We insert it into hash table which key is N - a1 and value is a1`s index. Then in the second pass, we use N - a2, where a2 is each element, to find the target index using the hash table.

More linked list problems

There are a lot of commonly asked linked list questions. They can range from simple to much more challenging. The following are some questions that can all be solved using two pointers ptr1 and ptr2 with different moving speed. They are relatively simple so I won`t post code here, but just the method:

Find the middle element of a linked list.

Let ptr1 moves 1 step and ptr2 moves 2 steps in each loop. When ptr2 reaches the end, ptr1 is pointing the middle element. 

Find the nth last element of a linked list.

Let ptr2 move n steps ahead first, and then let two pointers move together. When ptr2 reaches the end, ptr1 is pointing the nth last element.

Two linked lists of different length intersect at one node. Find this node.

We should first find the lengths of two linked lists by iterating through the whole list. Suppose the length of two lists are len1 and len2, len1 < len2, the difference d = len2 - len1. Now reset two pointers and let the pointer of longer list move d steps first. Then move two pointers simultaneously and compare the data of them. When data is equal, we find the node.

Given a circular linked list, find node at the beginning of the loop.

Let N be the node we want to find. In each loop, ptr1 moves 1 step and ptr2 moves 2 steps, until they meet at one node. The distance from this node to N is equal to the distance from head node to N. Now we reset ptr1 to head node and begin to move two pointers simultaneously. When they meet again, N is found there.

Maximum subsequence sum problem

The problem we’d like to solve can be stated as:

Given a sequence of numbers, find the maximum sum of a contiguous subsequence of those numbers.

One obvious solution is that we can simply enumerate every possible subsequence and calculate their sum. This will take O(n^2) time.

There is a linear solution called Kadane`s algorithm. Following is the code:

int max_sub_sum(int arr[], int len) {
    int max_local = 0;
    int max_global = 0;
    for(int i = 0; i < len; i++) {
        max_local += arr[i];
        if(max_local < 0)
            max_local = 0;
        if(max_local > max_global)
            max_global = max_local;
    }
    return max_global;
}

Why does it work? If max_local becomes negative, it will not contribute to the next subsequence by adding the next element. Actually the next element itself would be larger than the sum of it and max_local, so we can simply restart summing from here.

Note that this algorithm only works when there is at least one positive integer in the array.

Some interviewers may ask this question with slight modification that the input array is a circular array. In this case, we can concatenate the input array with itself, and apply Kadane`s algorithm.

Find the sum of all prime numbers below N

This is another classic question. Everyone would immediately come up with an idea that we can iterate from 2 to N and check if it is a prime number. If so, we add it to the sum.

bool isprime(int num) {
    int j = sqrt((float)num);
    for(int i = 2; i <= j; i++) {
        if(num % i == 0)
            return false;
    }
    return true;
}

int primesum(int range) {
    int sum = 2;
    for(int i = 3; i <= range; i += 2) {
        if(isprime(i))
            sum += i;
    }
    return sum;
}

This solution uses Trail Division to test if a number is prime. The trial factors need go no further than sqrt(n) because, if n is divisible by some number p, then n = p * q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q. 

When calculating the sum, we only need to check even numbers. This would save half of the time.

The time complexity of this method is O(n * sqrt(n)), and it requires O(1) space. The algorithm can be further optimized if we have a smaller pre-generated prime number table and test only prime factors.


If extra space is allowed, there is a better solution which is called Seive of Eratosthenes. The basic idea is to directly generate composite numbers rather than testing for prime numbers. The Seive of Eratosthenes algorithm is described as follows:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4. Find the first number greater than p in the list that is not marked; let p now equal this number (which is the next prime).
5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

int primesum(int range) {
    int sum = 2;
    bool* prime_table = new bool[range];
    memset(prime_table, true, sizeof(bool));

    for(int i = 2; i <= range / 2; i++) {
        if(prime_table[i]) {
            for(int j = 2 * i; j <= range; j += i) {
                prime_table[j] = false;
            }
        }
    }
    for(int i = 3; i <= range; i += 2) {
        if(prime_table[i])
            sum += i;
    }
    return sum;
}

The time complexity is O(nloglogn), and space complexity if O(n).

Above is only the implementation of original version. There are some refinements of this algorithm. For further informaton, please go to this link http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

Reverse a singly linked list

This is a very classic interview question. It demonstrates the ability to work with basic data structure and pointers. The seemingly easy question has some pitfalls. Nearly every candidate starts with two temporary pointers and eventually finds out that you need three. You need to point to the current node (the one you’re handling), the previous node (so you can point back to it), and the next node (so you can prevent lost of the next node). Also, you should not forget to make the first node point to NULL.

There are two solutions to this question. One is iterative and the other is recursive. 

Node* reverse_iterative(Node* head) {
    Node* prev = head;
    Node* curr = head->next;
    Node* next = head->next->next;
    prev->next = NULL;

    while(curr->next) {
        curr->next = prev;
        prev = curr;
        curr = next;
        next = next->next;
    }
    curr->next = prev;
    return curr;
}

The recursive version is shown as follow:

Node* reverse(Node* prev, Node* curr) {
    // If reached the end of the list, return the head
    if(curr->next == NULL) {
        curr->next = prev;
        return curr;
    }
    // Remember the next node
    Node* next = curr->next;
    // Change current pointer to previous node
    curr->next = prev;
    return reverse(curr, next);
}

Node *reverse_recursive(Node* curr)
{
    return reverse(NULL, curr);
}

Although recursive version is more straightforward, in general we prefer the iterative version because if the list is very large, this version would fail because of stack overflow.

Note that there are some variations of this question like "How to print a singly linked list in reverse order". In this case, if we are allowed to alter the data structure, we can reverse linked list first and print it from the beginning.