Amaon 面试准备

https://instant.1point3acres....
1.Product of Array Except Self
2.给两天的用户log数据，求两天均登陆Amazon的用户，follow up - log很大不可以放入内存
相关问题，统计访问量最高的前10个ip，内存不够怎么办。统计最高的单词，内存不够。

（大数据处理，当内存不够的时候，考虑取模后映射成小文件，然后再用hash分别统计，然后再堆排序）

Time is O(n*log(k)).

class Pair{    int num;    int count;    public Pair(int num, int count){        this.num=num;        this.count=count;    }}public class Solution {    public List topKFrequent(int[] nums, int k) {        //count the frequency for each element        HashMap map = new HashMap();        for(int num: nums){            if(map.containsKey(num)){                map.put(num, map.get(num)+1);            }else{                map.put(num, 1);            }        }        // create a min heap        PriorityQueue queue = new PriorityQueue(new Comparator(){            public int compare(Pair a, Pair b){                return a.count-b.count;            }        });        //maintain a heap of size k.         for(Map.Entry entry: map.entrySet()){            Pair p = new Pair(entry.getKey(), entry.getValue());            queue.offer(p);            if(queue.size()>k){                queue.poll();            }        }        //get all elements from the heap        List result = new ArrayList();        while(queue.size()>0){            result.add(queue.poll().num);        }        //reverse the order        Collections.reverse(result);        return result;    }}

3.HashMap 构造， 如何解决collision.

HashMap works on the principle of hashing, we have put() and get() method for storing and retrieving object from HashMap.When we pass both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and them by applying hashing on that hashcode it identifies bucket location for storing value object. While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list. Also, HashMap stores both key and value tuple in every node of linked list in the form of Map.Entry object.

What will happen if two different objects have the same hashcode?
Since hashcode is same, bucket location would be same and collision will occur in HashMap Since HashMap uses LinkedList to store object, this entry (object of Map.Entry comprise key and value ) will be stored in LinkedList.

How will you retrieve Value object if two Keys will have the same hashcode?
after finding bucket location, we will call keys.equals() method to identify a correct node in LinkedList and return associated value object for that key in Java HashMap.

Read more: http://javarevisited.blogspot...

4.self balancing tree compared with hash table
自平衡的二叉查找树的实现与其竞争对手hash表的实现，各具有优缺点。自平衡二叉查找树在按序遍历所有键值时是量级最优的，hash表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于hash表， O(log n)对比O(n)；但平均时间复杂度逊于hash表，O(log n)对比O(1)。

5. design pattern,最喜欢的design patterns 实现thread-safe 的singleton

1. 给定词典和一个数据流，搜索单词。 follow up - 构造Trie。

关键字：interview, hashmap, object, num

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！