Appdirect Onsite技术面试总结

Round 1:
Q: How HashMap is implemented in Java?
A: My answer is that HashMap maintains an array of buckets, each bucket is a doubly linkedlist of <key, value> pairs. When you put a <key, value> pair in this data structure, first you calculate the hashcode for the key, and mode by the size of array to target the bucket, and find if the key is already existed in the bucket. If so, replace the value, if not, put a new <key, value> pair in the linkedlist.Q: What’s the time complexity of searching?
A: Generally is O(1), but if the linked list is too long, since we need to search the element in the linkedlist one by one, the time needed is O(length of the linkedlist).Q: In what situation the linkedlist will be too long?
A: When the array is not big enough and the pairs to put is too many, in this situation, we need to resize the array.Q: Then tell me more about hashcode() and equals() in HashMap.
When you use some selfdefined objects as a key, you need to override the hashcode() and equals(). The HashMap will call hashcode() to find the linkedlist and then call equals() function to determine whether the key is in it or not. And there is a contract between the equals() and hashcode(), that:
If two objects are equal, then they must have the same hashcode.
If two objects have the same hashcode, they may or may not be equal.Q: Use two stacks to implement queue.
A: leetcodeQ: Design database table. If one person can do multiple projects for some hours and one projects can be done by multiple person, design the table.
Round 2:
Q: missing number (leetcode), nonnegative, have duplicates. Input: int[] array1, int[] array2, the length of array 1 is n, the length of array2 is n – 1, find the missing number in array2.
A: Method1: sort two arrays and use two pointers start from each array, find the first unmatched. Time Complexity: O(nlogn).
Method2: use a HashMap to record <number, appeared times> pairs of array2, and scan array1, if array1[i] is not in HashMap, return array1[i]; otherwise, find it in the HashMap, if the value (appeared times) is 0, then return array1[i], else reduce the appeared times by 1. (this deals with duplicates). Time complexity: O(n), Space: O(n).Q: Can you do it in linear time and constant extra space?
A: Yes, by adding each array and calculate the difference. (Consider about overflow, use Big Integer)Round 3:
Q: OOD: design a Car Reserve System, the customer will search for a specific type and a specific color and a time period(start, end), and the system will return a list of available cars(by call filter()).
A: define classes:
Enum Type {}
Enum Color{}
Class Car { int carID, Type type, Color color, Listtickets}
Class Ticket { int ticketID, long startTime, long endTime, int carID, int userID}
Class User {int userID, Listtickets}
Class ReserveSystem { ListcarList,
Method:
Listfilter(Type type, Color color, long startTime, long endTime);
Ticket reserve(Car car)
Void update(Ticket ticket)
}Q: Implement filter() function
所有图片来源于网络
本文作者：Marie
更多精彩内容，欢迎访问官网 ClickHere
或关注 “论码农的自我修养” 微信公众号：bit_tiger