In my last blog, I mentioned to share the following test questions. Recently, I just joined a new company for a short time, so I was busy getting familiar with the environment, and I went out for a trip not long ago (I wrote a travel note by the way, if you are interested, you can have a look). Therefore, I didn’t have time to organize my blog. During this period, I was finally free on weekends, so I recorded several algorithm problems encountered in the interview process.

This blog is not going to cover some of the most powerful algorithms (Winnow, Bagging, Ada Boost, etc.), but rather some of the most recent algorithms I’ve encountered in interviews and the answers I’ve given in interviews. (I’ve listed some of the most popular algorithms, but I won’t mention the rest.) Algorithms are the cornerstone of all problems. A lot of things can be converted into algorithm problems, the biggest role of learning algorithm is to understand a lot of things more clearly. As the saying goes, knowing what is is better than knowing why. Many people think of programs as data structures + algorithms + appropriate annotations. If you don’t learn algorithms, don’t learn programming. It’s probably not that much of an exaggeration, because there are actually a lot of small projects that don’t require a lot of algorithms, just code piling on top of each other. But as a programmer, it is important to think logically as an algorithm, even if it is not exaggerated. — This is from an interviewer in a company.

Let me write v out front

Once again, here is just a list of some algorithm interview questions recently encountered, take out to share with you the interview experience (only common algorithm experience, there are some uncommon experience will not bother to list, the technical direction will not be introduced). And here’s my answer. Ps: Neither the algorithmic questions nor the answers are representative or correct. They are just the answers I gave in the interview. They are just shared. In addition, if you have any questions or better solutions to the questions and answers I have listed, please feel free to share them! Writing algorithms is a great treat!

By the way, for one interview the interviewer was in London, so we had to do it remotely, so we used CollabEdit, which was quite useful.

V Algorithm Encyclopedia

—- algorithm encyclopedia from Baidu Encyclopedia (PS: do not pick point introductory text in this, straight to the topic. It’s kind of duangduang. Impatient can just skip here!)

Algorithm refers to the accurate and complete description of problem solving scheme and a series of clear instructions to solve problems. Algorithm represents the strategy mechanism to solve problems in a systematic way. In other words, the required output can be obtained in a limited time for a given specification of the input. If an algorithm is flawed or inappropriate for a problem, executing the algorithm will not solve the problem. Different algorithms may perform the same task with different time, space, or efficiency. The advantages and disadvantages of an algorithm can be measured by space complexity and time complexity. The instructions in an algorithm describe a computation that, when run, can start with an initial state and (possibly empty) initial input, pass through a finite and well-defined series of states, and eventually produce an output that stops in a final state. The transition from one state to another is not necessarily deterministic. Some algorithms, including the randomization algorithm, involve some random input. The concept of formal algorithms is derived in part from attempts to solve Hilbert’s decision problems and from subsequent attempts to define efficient computability or efficient methods. These attempts included Kurt Godel’s recursive functions in 1930, Jacques Herbrand in 1934 and Stephen Cole Kleiney in 1935, Alonzo Church’s lambda calculus in 1936, Emil Leon Post’s Formulation 1 in 1936 and Alan Turing’s Turing machine in 1937. Even today, there are often situations where intuitive ideas are difficult to define as formal algorithms.

V algorithm problem

  • Find a number in a sorted Int array. If the number exists, return the position in the array. If the number exists, return -1
  • 12 for the second question: {” Bob “, “3, sky”, “6, cool”, “1, the good”, “22, go”}, according to the elements in the first column sorting view blogger interview answers
  • The string array removes duplicates
  • Type an unsorted integer array. Move the negative number to the left and the positive number to the right. Ps: WHEN I started to do this, I was going to do it in a mindless sort, and as SOON as I started to write it, the interviewer said, “Well, I need to remind you that the array is just negative numbers on the left and positive numbers on the right. It doesn’t have to be a traditional order, bonus points if it’s not.” ) Check out the blogger’s interview answers

All answers are for reference only, not standard or correct answers, only answers given during the interview, so you are welcome to give better answers

All the answers were written by Notepad during the interview. After I came back, I did not have double check and directly posted the code, among which I attached some pictures. If you’re interested, I suggest you start with Notepad, because the algorithm itself is just an idea. No need to use VS.

V.

The first question

//------------------------------------------------------------------------------ // <copyright file="Runner.cs" Company ="CNBlogs Corporation" owner=" CNBlogs Corporation" owner=" CNBlogs Corporation" >  http://www.cnblogs.com/toutou/ // </copyright> //------------------------------------------------------------------------------ namespace TestApp { using System; using System.Collections.Generic; using System.Text.RegularExpressions; class Runner { static void Main(string[] args) { int[] arr = { 3, 5, 6, 7, 8, 9, 14, 23, 45, 56, 63, 72, 87, 91, 92, 93, 95, 97, 98, 534, 555, 676, 878, 988, 1365}; int number = 555; int result = Search(arr, number); Console.WriteLine(result); Console.ReadKey(); } public static int Search(int[] arr, int number) { int result = 0; if (arr == null || arr.Length == 0 || number > arr[arr.Length - 1] || number < arr[0]) { result = -1; } else { result = Bisearch(arr.Length - 1, arr, number); } return result; } public static int Bisearch(int endIndex, int[] arr, int number, int startIndex = 0) { int result = 0; if ((endIndex - startIndex) < 2) { for (int i = startIndex; i <= endIndex; i++) { if (arr[i] == number) { result = i; break; } else { result = -1; } } } else { if (arr[startIndex] <= number && number <= arr[(endIndex + startIndex) / 2]) { Bisearch((endIndex + startIndex) / 2, arr, number, startIndex); } else { Bisearch(endIndex, arr, number, (endIndex + startIndex) / 2 + 1); } } return result; }}}Copy the code

On the way back from the interview, I thought about this problem, which is roughly like this:

Of course, this is definitely not the best solution.

I have a different view of the first question

The second question

namespace TestApp { using System; using System.Text.RegularExpressions; class Program { static void Main(string[] args) { string[] source = new string[] { "12,bob", "3,sky", "6,cool", "1,good", "22,go" }; for (int i = 0; i < source.Length; i++) { for (int j = i; j < source.Length; j++) { if (Convert.ToInt32(Regex.Match(source[i], @"\d+").Value) > Convert.ToInt32(Regex.Match(source[j], @"\d+").Value)) { string temp = source[i]; source[i] = source[j]; source[j] = temp; } } } for (int i = 0; i < source.Length; i++) { Console.WriteLine(source[i]); }}}}Copy the code

This problem I choose is to use a relatively stupid re out of the number, and then use bubble sort to complete the algorithm. Later came back to think about it, is really shouldn’t ah! So here’s a traditional bubble sort visual.

I have a different view of the second question

The third question

namespace TestApp { using System; class Program { static void Main(string[] args) { string[] source = { "aaa", "bbb", "aaa", "ccc", "bbb", "ddadd", "ccc", "aaa", "bbb", "ddd" }; foreach (var item in ArrDistinct(source)) { Console.WriteLine(item); } } public static String[] ArrDistinct(string[] source) { if (source ! = null && source.Length > 0) { Array.Sort(source); int size = 1; for (int i = 1; i < source.Length; i++) if (source[i] ! = source[i - 1]) size++; string[] tempArr = new string[size]; int j = 0; tempArr[j++] = source[0]; for (int i = 1; i < source.Length; i++) if (source[i] ! = source[i - 1]) tempArr[j++] = source[i]; return tempArr; } return source; }}}Copy the code
// If you want to sort a string array, you need to sort it. Of course, that would be unprofessional. But if necessary, you can sort the string algorithmically first and then do what I did. ConvertAll<string, int>(strArray, s => int.parse (s)); // Do you have a better way? If there is, don't hide it. Come on!Copy the code

I have a different view of the third question

The fourth question

public int[] IntArrSort(int[] source)
        {
            if (source == null || source.Length == 0)
                return source;
            int rightIndex = source.Length - 1, tempNumber = 0;
            for (int i = 0; i < source.Length; i++)
            {
                if (i > rightIndex)
                    break;
                if (source[i] <= 0)
                {
                    continue;
                }
                else if (source[i] > 0)
                {
                    for (int j = rightIndex; j >= 0; j--)
                    {
                        if (source[j] < 0)
                        {
                            tempNumber = source[j];
                            source[j] = source[i];
                            source[i] = tempNumber;
                            rightIndex = j;
                            break;
                        }
                    }
                }
            }
            return source;
        }
Copy the code

Question 4 I have a different view

V Blog Summary

Dear friends, all the above algorithmic interview questions are accumulated in my ordinary interview, and I have listed the ones with high attendance rate (the attendance rate is only relative to my interview experience).

In addition: in particular, I give the algorithm interview answers may also be wrong, just give my reference, the algorithm itself does not have any standard answer at all, and there may be some questions my way of thinking or solving the problem is not the same. Welcome you to give better answers or problem-solving ideas, common progress!

About the author: Focus on basic platform project development. If you have any questions or suggestions, please feel free to comment! Copyright notice: The copyright of this article belongs to the author and the blog garden, welcome to reprint, but without the consent of the author must retain this statement, and give the original text link in a prominent place on the page of the article. For the record: all comments and messages will be answered as soon as possible. You are welcome to correct your mistakes and make progress together. Or direct private message I support the blogger: if you think the article is helpful to you, you can click on the lower right corner of the article [recommendation]. Your encouragement is the author to adhere to the original and continuous writing of the biggest power! \