Tencent +360+ Sogou school recruitment test + summary of knowledge points

​9.11 On the evening of 7:00, Tencent written test . Multiple choice questions and programming 、 The design questions are timed separately .

  Is stack a linear structure of sequential storage ?

  First, understand two concepts : Storage structure and logical structure .

  The logical structure of data includes linear structure 、 Trees 、 chart 、 Assemble these four , In the linear structure, there is a linear table 、 Stack 、 Queues, etc .

  There are only two kinds of data storage structures ： Sequential storage structure and Chain storage structure , These two storage structures , The first one is to use the relative position of data elements in memory to represent their logical structure , The other is to express its logical relationship with pointers .

  Conclusion ： Linear data structure in terms of storage structure , It may be sequential storage , It may also be chain storage . A linear table is a linear structure , It is also a sequential storage structure .

Tencent programming question

  A building has 100 layer . You have two identical glass beads in your hand . When you throw glass beads on a certain floor , There must be two results , The glass beads are broken or not broken . This building has a critical floor . The floor below it , Drop the glass beads , Glass beads won't break , Equal to or higher than its floor , Drop the glass beads , The glass beads are bound to break . If the glass bead is broken, you can't throw it anymore . Now let's design a way , In this way , The number of throws in the worst case is less than that in any other way . That is to design the most effective way . I saw an explanation on the Internet :

360 Programming questions

Most brain

  The time limit ：C/C++ Language 1000MS; Other languages 3000MS

  Memory limit ：C/C++ Language 65536KB; Other languages 589824KB

Title Description ：

  Small B Take the train with friends N City to M Travel between cities . She sleeps and wakes up on the way . When she woke up and looked out the window , Notice that every railway station has a special color flag , But the flag she saw was only a small part of it . Small B There are two waking times during the ride , She was asleep when she reached the end of the journey . At the exit , She talked with her friends about what she had seen all the way , My friends think it's very interesting .

  They put the N To and M The colors of flags passing through the station are listed in turn , Then tell you little B Remember the flag color sequence , Let you judge small B From N and M Between which directions can I see the flag of the said color , Or not at all   You might see ？ Colors are represented by letters , The same letters represent the same color , Different letters represent different colors .

  Input

  There are multiple sets of test data in the input . Each set of test data contains three lines , The first line is a non empty string composed of lowercase Latin letters , Length not exceeding 10^5, Express N To M Between stations . Train from M towards N Runtime , The stations are the same , Just in the opposite direction . The second behavior is small B The color sequence you see when you wake up for the first time , The third behavior is small B The color sequence you see when you wake up for the second time . Both sequences are strings of lowercase Latin letters , Length not exceeding 100 Letters . The colors of each sequence are arranged in small order B See the chronological order .

  Output

  For each group of test data , Output small in a separate line B Travel direction .

  forward – from N To M Direction ;

  backward – from M To N Direction ;

  both – Both directions are possible ;

  invalid – It is impossible to see such a color sequence ;

  The sample input

  atob

  a

  b

  aaacaaa

  aca

  aa

  Sample output

 forward

 both

 Hint

The train is supposed to be in motion at all times , You won't see the same flag twice .N City and M There is no flag at the city station .

import java.util.Scanner; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        while (sc.hasNext()) {            String t = sc.next();            String a = sc.next();            String b = sc.next();            boolean res1 = isCan1(t, a, b);            char[] tArr = t.toCharArray();            for (int i=0,j=tArr.length-1; i<j; i++,j--) {                char tmp = tArr[i];                tArr[i] = tArr[j];                tArr[j] = tmp;            }            t = new String(tArr);            boolean res2 = isCan1(t, a, b);            if (res1 && res2)                System.out.println("both");            else if (res1)                System.out.println("forward");            else if (res2)                System.out.println("backward");            else                System.out.println("invalid");        }    }     private static boolean isCan1(String t, String a, String b) {        int i = t.indexOf(a);        if (i == -1)            return false;        int j = t.substring(i+a.length()).indexOf(b);        return j != -1;    }}

memory management

Title Description ：

   The vigorous development of Internet of things technology , Various sensors have appeared . Small B The project team is developing an Internet of things project , They are researching and designing a new sensor . This kind of sensor has its own basic processing unit , Have a certain degree of autonomy , Be able to conduct simple data collection 、 Handle 、 Storage and transmission . In order to reduce system power consumption and ensure system reliability and controllability , They need to do basic memory management . The research team plans to develop an experimental memory manager , Realize the allocation of memory 、 Release and organize . The corresponding interface is new、del and def, The syntax is ：

  new size： Distribute size Byte size memory block , Return the handle of the memory block handle,size As a positive integer ;

  del handle： Release handle handle Point to memory block ;

  def： Defragment memory , Migrate all allocated memory blocks in order of address from low to high , The spare memory fragments are spliced together at the high address end ;

   The initial memory is initSize Bytes of free memory , The number is 1 To initSize .

  new size In operation , If there is no less than size Continuous free memory , Allocate from the free memory area according to the principle of small address first size Memory block size , Mark the memory block status as allocated , And return a handle to the memory block . If unable to allocate , It returns null （NULL）.

  del handle The operation is released by handle Marked memory block , Mark the free memory status as idle . if handle Is an invalid handle , Then return to ILLEGAL_OPERATION.

  def Finish the memory collation , No return value .

   According to design , The handle returned for each successful memory allocation is a positive integer , from 1 Start , Count in turn . Failed storage allocation operations do not affect the count .

   The project team assigned this task to small B, Small B Ask you for help , Can you help her ？

Input

   There are multiple sets of test data in the input . The first behavior of each group of test data is two positive integers T and MaxMem（1<=T<=10000, 1<=MaxMem<=10000）, among T For the number of operations ,MaxMem Is the initial memory size , Then there are T Line operation instruction .

Output

   For each group of test data , Output operation results in operation order . For each new operation , Output the result in a separate line , When successful, output its return handle value , If it fails, output NULL. if del operation failed , Output ILLEGAL_OPERATION.def No output .

The sample input

6 10

new 5

new 3

del 1

new 6

def

new 6

Sample output

1

2

NULL

3

Sogou programming problem

 * 1. Title Description ： Define two greater than 2 The distance between even numbers of , Is the number of prime numbers between these two numbers .

 *    Input from small to large n More than 2 An even number of , Output the sum of the distance between all numbers （ Should have n*(n-1)/2 Distance , Just output the sum ).

 * Input

 *    The first line is to enter the number of even numbers , The minimum is 2, It is possible to reach tens of thousands . After that, each line has an even number , The minimum is 4, The maximum is millions , Ascending order without repetition .

 * Output

 *    Input the sum of the distance between two data , This should be no less than 0 The integer of .

 * The sample input

 *  3

 *  4

 *  6

 *  12

 * Sample output

 *  6

 

 * 2. Title Description ： Find the maximum palindrome prefix length of a string . Palindromes are strings that read the same in both directions , such as “abcdcba” Is a palindrome .

 * Input

 *    A text file , Contains at least one byte . Each byte is a character . The maximum length may be several hundred thousand bytes .

 * Output

 *    The length of the maximum palindrome prefix .

 * The sample input

 *   sogou

 * Sample output

 *   1