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.

Learn Vim Progressively — 1st Level : Survive

I`m now learning vim, and I found a very interesting article which talks about how to learn vim progressively in four steps. I just paste the whole article here to share with others.

Want to learn vim (the best text editor known to human kind) the fastest way possible. I suggest you a way. Start by learning the minimal to survive, then integrate slowly all tricks.

Vim the Six Billion Dollar editor

Better, Stronger, Faster.

Learn vim and it will be your last text editor. There isn’t any better text editor I know. Hard to learn, but incredible to use.
I suggest you to learn it in 4 steps:

1. Survive
2. Feel comfortable
3. Feel Better, Stronger, Faster
4. Use vim superpowers

By the end of this journey, you’ll become a vim superstar.
But before we start, just a warning. Learning vim will be painful at first. It will take time. It will be a lot like playing a music instrument. Don’t expect to be more efficient with vim than with another editor in less than 3 days. In fact it will certainly take 2 weeks instead of 3 days.

1^st Level – Survive

1. Install vim
2. Launch vim
3. DO NOTHING! Read.

In a standard editor, typing on the keyboard is enough to write something and see it on the screen. Not this time. Vim is in Normal mode. Let’s get in Insert mode. Type on the letter i.
You should feel a bit better. You can type letters like in a standard notepad. To get back in Normal mode just tap the ESC key.
You know how to switch between Insert and Normal mode. And now, the list of command you can use in Normal mode to survive:

• i → Insert mode. Type ESC to return to Normal mode.
• x → Delete the char under the cursor
• :wq → Save and Quit (:w save, :q quit)
• dd → Delete (and copy) current line
• p → Paste

Recommended:

• hjkl (highly recommended but not mandatory) → basic cursor move (←↓↑→). Hint: j look like a down arrow.
• :help <command> → Show help about <command>, you can start using :help without anything else.

Only 5 commands. This is very few to start. Once these command start to become natural (may be after a complete day), you should go on level 2.
But before, just a little remark on Normal mode. In standard editors, to copy you have to use the Ctrl key (Ctrl-c generally). In fact, when you press Ctrl, it is a bit like if all your key change meaning. With vim in Normal mode, it is a bit like if your Ctrl key is always pushed down.
A last word about notations:

• instead of writing Ctrl-λ, I’ll write <C-λ>.
• command staring by : will must end by <enter>. For example, when I write :q it means :q<enter>.

Some Linux commands useful for manipulating text files

I have learned some Linux utilities for manipulating text files these days. They are extremely handy which is far beyond my expectation. I should have learned them before I used Java to write those unresuable, verbose and error-prone codes to process texts a week ago.

1. cat

This is the simplest tool in this category. The cat command copies its input to output unchanged (identity filter). When supplied a list of file names, it concatenates them onto stdout.

2. head

Display the first few lines of a specified file. Particularly useful when the file is big and you wants to see only the header. You don`t have to open the whole file (which makes the system slow) using this command.

3. tail

Displays the last part of a file, similar to head.

4. cut 

The cut command prints selected parts of input lines. It can select columns (assumes tab-separated input); can select a range of character positions; can also specify delimiter characters.

5. sort 

Sort each line of the file using either lexicographic or arithmetic order. It can use a key for comparison to sort the lines in delimiter seperated files.

6. uniq 

Remove or report adjacent duplicate lines. Useful for finding duplicate and non-duplicate lines.

7. wc

The word count utility, wc, counts the number of lines, characters or words. The line counting feature is my best favorite because it does not have to open the file.

8. tr

Copies standard input to standard output with substitution or deletion of selected characters. It can be used to filter a range of characters in order to make certain conversions.

9. grep 

Search substrings that match the given regular expression, and print the line they reside in. Often used to search for the results we are interested in.

10. sed

More powerful tool compared to the above. It Looks for patterns one line at a time, like grep , but changes lines of the file. It`s a non-interactive text editor. Editing commands come in as a script. There is an interactive editor ed which accepts the same commands. It`s a A Unix filter which is the superset of previously mentioned tools, and it`s syntax is also used in VIM.

Above are the most common used Linux text manipulating utilities. Although they are already very convenient individually, combining them using pipes can make them even more powerful and flexible. If you are a linux admin or academic researcher, these are the commands you must know.

 

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.