Interview essentials: arrays and strings

This article was first published on the wechat public account “Yugang Said”

Interview essentials: Arrays and strings

How important are data structures and algorithms?

I don’t think aspiring programmers will let it go. For example, in Jin Yong’s martial arts world, data structures and algorithms are like a good internal skill. Once mastered, all kinds of martial arts skills are at your fingertips (Zhang Wuji is a typical example), and for programmers, it can determine how far you can go in technology.

This article mainly involves the array, string these data structures, and then through the answer and analysis of several common interview questions, share some of my learning experience and problem solving routines, I hope to help you.

Topic 1: Flip the sentence

Given a sentence in which each word is separated by one or more Spaces, reverse the order of the words in the sentence (including the order of Spaces), but keep the order of the characters in the word the same. For example, enter “WWW Google com”, the output should be “com Google WWW”.

If you read a lot about algorithms, this question should be familiar to you. It appears on various blogs and books, but it doesn’t matter if you’re not familiar with it. Let’s try to solve it together. Note that there is a difference between the meaning of the question and the popular online questions: there is usually only one space between the words on the Internet, but this question needs to consider the case of one or more Spaces.

Their thinking

Imagine flipping the entire string. The result is that the sentences are reversed, but the character order within the words is also reversed. If you want to keep the order within the words the same, you just need to flip each word again.

Because “WWW Google com” is a long string, I will use “Hello world” as an example to analyze the process, see the figure below.

Figure 1.0 Reverse the sentence, but keep the order of characters inside the words in the sentence.

Note :(1) the initial state of the string “hello world”. Note that the first character is a space. (2) What it looks like when you flip the whole sentence “Hello world”. You can see that not only the order of the words in the sentence (including the Spaces), but also the order of the characters in the words. (3) Define two Pointers P1 and P2 to point to the first character of the sentence. (4) the first character d, not space, then p1 does not move, p2 pointer moves 1 bit to the right, pointing to the character L. (Move p2 pointer purpose: check word end position.) (5) Since the second character is L and not a space, P2 continues to move 1 bit to the right. (6) After many moves, p2 stops at the first space, and we know that p2-1 is the end of the word. (7) Reverse the string between two Pointers (p1, P2-1). (8) After switching, reset two pointer positions P1 = P2 ++. And so on, continue looking for the next word and flipping until the pointer moves to the end of the sentence to close the loop.

The key to this idea is: 1. Implement a function/method that flips a segment of a string. 2. Judge and get the words in the sentence.

The test case

Functional test: multiple words, 1 word, only one space between words, multiple Spaces between words.
Special input tests: null characters, strings with only Spaces, null objects (Pointers).

coded

Java code

/** * @param chars The original string * @param start is greater than or equal to 0 * @param end is less than length * @return*/ private char[] v1_0_reverse(char[] chars, int start, int end) {// STR null, index valid valueif (chars == null || start < 0 || end >= chars.length || start >= end) {
        return chars;
    }

    while(start < end) {// End characters are exchanged until the substitution is complete. char temp = chars[start]; chars[start] = chars[end]; chars[end] = temp; start++; end--; }return chars;
}

private String v1_0_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        returnsentence; } int length = sentence.length(); Char [] chars = v1_0_reverse(sentence.tochararray (), 0, length-1); char[] chars = v1_0_reverse(sentence.tochararray (), 0, length-1); System.out.println(new String(chars)); Int start = 0, end = 0;while (start < length) {
        if (chars[start] == ' ') {// continue to look for start++ if you see a space; end++; }else if (end == length || chars[end] == ' 'End -1 chars = v1_0_reverse(chars, start, end-1); System.out.println(new String(chars)); Start start = end++; }else{// end+ 1, to check if the word ends end++; }}return new String(chars);
}
Copy the code

C++ code implementation

Void Reverse(char *pBegin, char *pEnd) {if(pBegin == NULL || pEnd == NULL)
        return;

    while(pBegin < pEnd) { char temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; pBegin ++, pEnd --; }} // Reverse the order of the words in the sentence, but keep the order of the characters in the words unchanged. char* ReverseSentence(char *pData) {if(pData == NULL)
        return NULL;

    char *pBegin = pData;

    char *pEnd = pData;
    while(*pEnd ! ='\ 0')
        pEnd ++;
    pEnd--;

    // 翻转整个句子
    Reverse(pBegin, pEnd);

    // 翻转句子中的每个单词
    pBegin = pEnd = pData;
    while(*pBegin ! ='\ 0')
    {
        if(*pBegin == ' ')
        {
            pBegin ++;
            pEnd ++;
        }
        else if(*pEnd == ' ' || *pEnd == '\ 0')
        {
            Reverse(pBegin, --pEnd);
            pBegin = ++pEnd;
        }
        else{ pEnd ++; }}return pData;
}

Copy the code

If you come across this problem in an interview and it’s easy to come up with this algorithm, an experienced interviewer will try to improve on the problem and test the candidate. So, here comes the second question:

The resulting “com Google WWW” needs to be used as a parameter to a URL, so what we need to do here is remove invalid Spaces at the beginning and end and replace each space between the two words with “%20”. For example, “com Google WWW “should be converted to “com%20%20google%20www”.

Their thinking

The first step is to remove invalid Spaces at the end; For example, “com Google WWW “and you get “com Google WWW”.
Step 2 Replace each space between the two words with “%20”.

Let’s take “Hello World” as an example.

Figure 1.1 strips out trailing invalid Spaces and replaces each space between words with “%20”.

Note :(1) string “hello world”, note that the first character is a space. (2) After removing the space at the beginning and end. (3) Expand the original string. NewLen = len + 2 x blackCount; To explain how the length of the new array is calculated, since each space is replaced by “%20”, it is equivalent to replacing one character with three characters. In other words, each space is two characters longer, hence the expression above. (4) Two Pointers P1 and P2 are defined to point to len-1 and newlen-1 respectively. (5) Check whether p1 points to a space. If so, insert the character ‘%20’ at p2. If not, copy the value p1 points to to P2 and move the two Pointers one to the left. Here we assign the character D that p1 points to to P2 and move the two Pointers one to the left. (6) Assign l to P2 and move pointer. (7) After multiple assignments and moves, P1 points to the first space. (8) Insert characters 0, 2, % at P2, and move p2 three places to the left. After the end, move P1 one place to the left. At this point, p1 and P2 overlap to end the cycle.

The test case

Functional test: before and after the blank case, one or more blanks in the middle case.
Special input tests: null characters, strings with only Spaces, null objects (Pointers).

coded

Java code

private String v1_1_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        returnsentence; } // Remove the space at the end of string sentence = trim(sentence); int len = sentence.length(); char[] chars = sentence.toCharArray(); int count = getSpaceCount(sentence); int newLen = 2 * count + len; // The System. Arraycopy method is used internally. chars = Arrays.copyOf(chars, newLen); int index = len - 1; int newIndex = newLen - 1;while (index >= 0 && newIndex > index) {
        if (chars[index] == ' ') {
            chars[newIndex--] = '0';
            chars[newIndex--] = '2';
            chars[newIndex--] = The '%';
        } else {
            chars[newIndex--] = chars[index];
        }
        index--;
    }

    returnnew String(chars); } /** ** removes Spaces at the end of the string ** @param origin * @return
 */
private String trim(String origin) {
    char[] chars = origin.toCharArray();
    int length = chars.length;
    int st = 0;
    while (st < length && chars[st] == ' ') {
        st++;
    }

    while (st < length && chars[length - 1] == ' ') { length--; } // If there is a space at the end, a new string is generatedif (st > 0 || length < chars.length) {
        origin = new String(chars, st, (length - st));
    }
    return origin;
}

private int getSpaceCount(String sentence) {
    char[] chars = sentence.toCharArray();
    int count = 0;
    for (char c : chars) {
        if (c == ' ') { count++; }}return count;
}

Copy the code

C + + implementation

/* trim(char *strIn, char *strOut){int I = 0; /* trim(char *strIn, char *strOut){int I = 0; int j = strlen(strIn) - 1;while(strIn[i] == ' ')
        ++i;

    while(strIn[j] == ' ')
        --j;
    strncpy(strOut, strIn + i , j - i + 1);
    strOut[j - i + 1] = '\ 0'; } /* replaceBlank(char string[], int length) {/* replaceBlank(char string[], int length) {if(string == NULL && length <= 0)
        return; /*originalLength is the actual length of string */ int originalLength = 0; int numberOfBlank = 0; int i = 0;while(string[i] ! ='\ 0')
    {
        ++ originalLength;

        if(string[i] == ' ') ++ numberOfBlank; ++ i; } /*newLength is used to replace Spaces with'% 20'*/ int newLength = originalLength + numberOfBlank * 2;if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = The '%';
        }
        else{ string[indexOfNew --] = string[indexOfOriginal]; } -- indexOfOriginal; }}Copy the code

Topic 2: Reordering elements in an array

Given an array of integers, implement a function to adjust the order of the numbers in the array so that all odd numbers come before even numbers.

Their thinking

We maintain two Pointers (indexes). One pointer points to the first number in the array, called the head pointer, and moves to the right. A pointer to the last number, called a tail pointer, moves to the left.

Figure 2.0 the process of adjusting the array {2,1,3,6,4,7,8,5} so that odd numbers precede even numbers.

Note :(1) initialize two Pointers P1 and P2 to the head and tail of the array respectively. (2) According to the previous step, pointer P1 points to an even number 2, while P2 points to an odd number 5. If the condition is met, we exchange the two numbers. (3) P1 continues to move to the right until it points to an even number 6, and P2 continues to move to the left until it points to an odd number 7. (4) Swap the digits pointed to by the two Pointers. (5) P1, P2 continue to move and overlap, indicating that all odd numbers are in front of even numbers.

End of loop condition: exit loop when two Pointers overlap or when P2 moves in front of P1. You can see that this algorithm is done in one loop, so it’s O(n) in time, and O(1) in space because it’s operating on the original array.

The test case

Functional test: all odd, all even, odd even exist but sorted/not sorted.
Special input tests: null objects, array elements 0, negative numbers.

coding

Java implementation

private int[] v2_0_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }
     int st = 0;
     int end = nums.length - 1;

     while (st < end) {
         // find even number
         if(isOdd(nums[st])) { st++; // odd, index moved right}else if(! isOdd(nums[end])) { end--; // Even, index moved left}else{// int temp = nums[st]; nums[st] = nums[end]; nums[end] = temp; st++; end--; }}returnnums; } private Boolean isOdd(int n) {private Boolean isOdd(int n) {private Boolean isOdd(int n) {return(n & 1) ! = 0; }Copy the code

C + + implementation

Void swap(int* num1, int* num2) {int temp = *num1; *num1 = *num2; *num2 = temp; } bool isOdd(int data) {return(data & 1) ! = 0; } void oddEvenSort(int *pData, unsigned int length) {if (pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while(pBegin < pEnd) {// If the pBegin pointer points to an odd number, normal, move to the rightif(isOdd(*pBegin)) { pBegin++; } // If the pEnd pointer points to an even number, normal, move to the leftelse if(! isOdd(*pEnd)) { pEnd--; }else{// If not, swap(pBegin, pEnd); }}}Copy the code

Experienced interviewers come again, the difficulty of the topic needs to rise lower, 😶~

Topic: In question, the interviewer will continue to demand reform this function to ensure that the original input array of an odd number of internal order and even internal order, namely if the input is,1,3,6,4,7,8,5 {2}, the output should be,3,7,5,2,6,4,8 {1}, odd order between and even between order shall not be changed.

Their thinking

To ensure the order of the elements in the original array, use the O(n) temp space to cache the even numbers in order, place the odd numbers in front of the original array, and finally remove the even numbers from the temp array and place them behind the original array.

Figure 2.1 The temp array of O(n) caches even numbers, thus preserving the order of the original array.

Note: Variable explanation: st is the index of the odd number to be inserted in the original array, evenCount is the number of even numbers cached. (1) Initialize the temp array of the same length as the original array, pointer P1 to the first element, st=eventCount=0. (2) Place the even number 2 pointed to by P1 in temp, and evenCount increases by 1. (3) Since p1 pointer moves one bit to the right to point to an odd number of 1, assign the value pointed to by P1 to Array[st]. At this time, ST =0. After the assignment, ST increases by 1. (8) Sequence logic, until the end of the loop, the original array of odd elements are inserted into the head in order, the even number is sequentially cached in the TEMP array, that is, the state in the figure.

** The figure above shows that even numbers are sequentially cached in the TEMP array and odd numbers are sequentially placed in front of the original array. ** Finally, place the even numbers of the temp array in order after the original array. This process is relatively simple and is not reflected in the figure. See the code below for details.

The test case

Same as the previous problem. I’m going to omit it here.

coding

Java implementation

private int[] v2_1_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }

     int st = 0;
     int evenCount = 0;
     int[] temp = new int[nums.length];
     for (int i = 0; i < nums.length; i++) {
         if(! isOdd(nums[i])) { evenCount += 1; temp[evenCount - 1] = nums[i]; }else {
             if(st < I) {nums[st] = nums[I]; } st++; }}if (evenCount > 0) {
         for(int i = st; i < nums.length; i++) { nums[i] = temp[i - st]; }}return nums;
}
Copy the code

C + + implementation

void v2_1_solution(int* nums,unsigned int len)
{
     if(! nums || len <= 1) {return; } int st = 0; int evenCount = 0; Temp int temp[len];for (int i = 0; i < len; i++) {
         if(! isOdd(nums[i])) { evenCount += 1; temp[evenCount - 1] = nums[i]; }else {
             if(st < I) {nums[st] = nums[I]; } st++; }} // Take the even number from temp and place it after the original arrayif (evenCount > 0) {
         for(int i = st; i < len; i++) { nums[i] = temp[i - st]; }}}Copy the code

Learning experience & problem solving routines

Careful readers may have noticed that the process of solving the problem is roughly like this: analyze ideas -> test cases -> code -> debug and pass the test. You might ask how do you get good at algorithmic programming? My advice is: have nothing to brush a problem. Practice makes perfect. Haha, please clap.

For solution ideas (see Offer for details)

Draw pictures to visualize abstract problems
Examples make abstract problems concrete
Decomposition simplifies complex problems

Various data structure and algorithm books: Data structure, offer, introduction to algorithms, etc. Online programming: LeetCode, niuke.com, July online rookie practice recommended: C++ online tools

conclusion

Now when you go to a big company for an interview, there will be algorithm questions, so it’s not whether you want to master it or not, but the company will eliminate some people through it. It may be a little scary to say, but this is how it works in reality. All codes in this paper have been compiled and run and passed the test case check. Due to space limitation, the code is not posted completely. Please click the link to obtain the complete runnable code: github.com/yangjiantao… . Due to the author’s limited level, the errors in this article are unavoidable, so please correct them.

Welcome to follow my wechat public account “Yugang said” to receive first-hand technical dry goods

Interview essentials: arrays and strings

How important are data structures and algorithms?

Topic 1: Flip the sentence

Their thinking

The test case

coded

Their thinking

The test case

coded

Topic 2: Reordering elements in an array

Their thinking

The test case

coding

Their thinking

The test case

coding

Learning experience & problem solving routines

conclusion

Related Posts

Android architecture Selection

Dagger2 Learning journey

[Andme series] Basic framework Application, Activity, Fragment, ViewModel base class encapsulation