微策略2018春季校招java研发笔试题

1、Multiple Choice
A hash table contains 10 buckets and uses linear probing to resolve collisions.The key values are integers and the hash function used is( Key % 10).If the values 43,165,62,123,142 are inserted in the table, in what location would the key value 142 be inserted?

Linear probing is a method for resolving collisions in hash tables, data structures for maintaining a collection of key-value pairs and looking up the value associated with a given key. When the hash function causes a collision by mapping a new key to a cell of the hash table that is already occupied by another key, linear probing searches the table for the closest following free location and inserts the new key there.

A. 2

B. 3

C. 4

D. 6

2、Multiple Choice
The average time required to perform a successful sequential search for an element in an array A containing n elements is given by
A. (n+1)/2
B.  n

C. n(n+1)/2

D.

3、Multiple Choice
 For merging two sorted lists of sizes m and n into a sorted list of sizes m+n,the numbers of comparisons required are
 A. O(m)
 B. O(n)
 C. O(m + n)
 D. O(logm + logn)

4、Trees Traversal
The postorder and preorder traversal of a binary tree are given below-
postorder :D E B F G C A
preorder: A B D E C F G respectively
The inorder traversal of the binary tree is（）
Pick one of the choices

A. D B E A F C G
B. E D B G F C A
C. E D B F G C A
D. D E F G B C A

5. Lookup operations
There are several factors that affect the efficiency of lookup operations in a hash table.Which of the following is NOT one of those factors?
A. Number of elements stored in the hash table
B. Size of elements stored in the hash table
C. Number of buckets in the hash table
D. Quality of the hash function

6、 Java :Threads

 What is the output of the following Java snippet?

public class SampleDemo
implements Runnable {
     private
Thread t ;
     private String
threadName;
 
     SampleDemo
(String threadName) {
         this.threadName
= threadName;
     }
 
     public
void run(){
         while
(true)
             System.out.println(threadName);
     }
 
 
 

public void start()
{
         if (t==null) {
             t = new
Thread(this,threadName);
             t.start();
         }
     }
 }

public class TestThread {

    public static void main(String[] args) {

        SampleDemo A = new SampleDemo("A");

        SampleDemo B = new SampleDemo("B");



        B.start();

        A.start();

    }

}

7.Guess the Data Structure
 In what kind of storage structure for strings can one easily insert, delete ,concatenate and rearrange substrings?

A. fixed length storage structure
B. variable length storage with fixed maximum
C. linked list storage
D. array type storage

8、Multiple Choice
Which of the following operation is performed more efficiently by doubly inked list than by linear linked list

 A. Deleting a node whose location is given
 B. Searching an unsorted list
 C. Inserting a node after the node with a given location
 D. Traversing the list to process each node

9.Multiple Choice
What will be the output of the program?

 public class X {

    public static void main(String[] args) {

        try

        {

            badMethod();/*Line7*/



            System.out.println("A");

        } catch (Exception ex) /*Line 10*/

        {

            System.out.println("B");/*Line 12*/



        } finally /*Line 14*/

        {

            System.out.println("C"); /*Line 16*/

        }

        System.out.println("D");/*Line 18*/

    }



    public static void badMethod() {

        throw new RuntimeException();

    }

}

A．AB

B. BC

C. ABC

D. BCD

10.Abstract Classes
Which of the following is true about abstract classes?
Pick the correct choices
A. abstract classes can be used as just any other class
B. abstract classes need to be declared with ‘abstract’ keyword.
C. abstract classes cannot be instantiated
D.a class containing at least one abstract method will be an abstract class

11.Element Present in Tree
 Each node of a Binary Search Tree (BST) has an integer value and pointers to two children,referred to as left child and right child.The value of left child is always less than the value of its parent node,and the value of right child is always greater than or equal to the value of its parent node.
 The isPresent function in your editor has two parameters:a reference to the root node of a Binary Search Tree (BST) and an integer value.Complete isPresent so it returns l if the value is present in the BST, and returns 0 otherwise.

 Constraints
 1≤ total nodess ≤10⁴
 1≤ values ≤5*10⁴
 Sample Input 0

Value

30

10

12

15

Sample Output 0

1

1

1

0

 Explanation
Value:30. This value is present in the BST, so isPresent returns 1.

Value:10. This value is present in the BST, so isPresent returns 1.

Value:12. This value is present in the BST, so isPresent returns 1.
Value:15. This value is not present in the BST, so isPresent returns O.

Sample Input 1

Value

79

10

20

30

40

Sample Output 1

0

1

1

1

1

 Explanation
Value:79. This value is not present in the BST, so isPresent returns O.

Value:10. This value is present in the BST, so isPresent returns 1.

Value:20. This value is present in the BST, so isPresent returns 1.

Value:30. This value is present in the BST, so isPresent returns 1.

Value:40. This value is present in the BST, so isPresent returns 1.
YOUR ANSWER:

12.Two Strings
Given two arrays of strings,a and b,determine if the elements at corresponding indices in both arrays (i.e,and) contain a common  substring.For example,if ="hi" and ="it", then “i” would be a substring common to both strings.

Complete the commonSubstring function in your editor.It has 2 parameters:
 1.An array of n strings, a.

2.  An array of n strings, b.
The function must iterate through each pair of elements located at corresponding indices (i.e,a_i and b_i) of the arrays and determine if the strings in each pair contain acommon substring.If a pair of elements does contain one or more common substrings,then print YES on a new line; otherwise,print NO on a new line.You must do thisfor each of the (ai b) pairs of strings,printing a total of n lines.

Input Format
The locked stub code in your editor reads the following input from stdin and passes it to your function:

The first line contains an integer, n, denoting size of array a.
Each line i of the n subsequent lines (where 0≤ i < n) contains a string describing element a_i.
The next line contains an integer,n,denoting size of array b (it is guaranteed that both arrays are of equal length).

Each line i of the n subsequent lines (where 0≤ i < n) contains a string describing element bi.

Constraints
 All the strings consist of lowercase English letters only (i.e,a-z).

length of a= length of b

1≤length of a, length of b≤10³
1≤length of a_i，length of b_i≤10⁴

Output Format
Your function must print n lines of YES or NO answers where each line idenotes whether or not a_i and b_i share a common substring.

Sample Input 1
The following arguments are passed to your function:a=["hello""hi"],b=['world,"bye"I
Sample Output 1
YES
NO

Explanation 1
Pair ( ): The string"o" is a subtring of both ao ="hello" and bo ="world,so we print YES on a new line.
Pair (,): There is no such string which is a substring of both ai ="hi" and br ="bye" so we print NO on a new line.
YOUR ANSWER：

13.Count Duplicates
 Consider an array of n integers,numbers.We define a non unique value of numbers to be an integer that appears at least twice in the array.For example,if numbers = [1,1,2,2,2,3,4,3,9],then there are a total of 3 non-unique values in the array (i.e 1,2,and 3).

 Complete the countDuplicates function in the editor below.It has1parameter: an array of integers, numbers.It must return an integer denoting the number of non-unique values in the numbers array.

 Input Format
 Locked stub code in the editor reads the following input from stdin and passes it to the function:

The first line contains an integer,n,denoting the size of the numbers array.
 Each linei of the n subsequent lines (where 0 si <n) contains an integer describing the value of numbers_i.

 Constraints
 1≤n≤1000

 1≤≤1000

 Output Format

 The function must return an integer denoting the number of non-nique values in numbers.This is printed to stdout by locked stub code in the editor.
Sample Input 0

8

1

3

1

4

5

6

3

2

Sample Output 0

2

Explanation 0
 n = 8 and numbers = [1, 3, 1, 4, 5, 6, 3, 2].

The integers 1 and 3 both occur more than once, so we return 2 as our answer.

Sample Input 1

6

1

1

2

2

2

3

Sample Output 1

2
Explanation 1
n = 6andnumbers = [1,1,2,2,2,3].
The integers 1and 2 both occur more than once, so we return 2 as our answer,
YOUR ANSWER:
We recommend you take a quick tour of our editor before you proceed.The timer will pause up to 90 seconds for the tour. Start tour