http://www.geeksforgeeks.org/amazon-interview-set-105-campus/
First PI:
1. A brief discussion on my projects that I have done .
2. One thing that I am most proud of , a discussion on this .
3. Given an array you have to write two functions:
a.) getMinimum();
b.) upate(index, value);
A detailed description on my approach , I gave him 2-3 approaches which were not satisfactory , He told me to give it a fresh thought , then I have him a solution . He was satisfied and then he asked me to code it.
public class MyArray{ private int[] ret; private int min; private int size; public MyArray(int size){ ret = new int[size]; this.size = size; min = 0; } public boolean update(int index, int value){ if(index >= size && index<0) return false; ret[index] = value; if(value < min) min = value; return true; } public int getMinimum(){ return min; } public static void main(String []args){ MyArray array = new MyArray(5); array.update(1,9); array.update(2,-49); array.update(3,39); array.update(4,29); array.update(0,-9); System.out.println(array.getMinimum()); } }
4. Some basic questions on operating system concepts like CPU scheduling, why CPU scheduling , advantages , types. Questions on deadlock.
Selected from among the processes in memory that are ready to execute, and allocates the CPU to one of them http://www.gitam.edu/eresource/comp/gvr(os)/5.3.htm
Second PI :
1 import java.util.ArrayList; 2 import java.util.Arrays; 3 public class TestCycle { 4 private int n; 5 private int[] visited;//节点状态,值为0的是未访问的 6 private int[][] e;//有向图的邻接矩阵 7 private ArrayList<Integer> trace=new ArrayList<Integer>();//从出发节点到当前节点的轨迹 8 private boolean hasCycle=false; 9 10 public TestCycle(int n,int[][] e){ 11 this.n=n; 12 visited=new int[n]; 13 Arrays.fill(visited,0); 14 this.e=e; 15 } 16 17 void findCycle(int v) //递归DFS 18 { 19 if(visited[v]==1) 20 { 21 int j; 22 if((j=trace.indexOf(v))!=-1) 23 { 24 hasCycle=true; 25 System.out.print("Cycle:"); 26 while(j<trace.size()) 27 { 28 System.out.print(trace.get(j)+" "); 29 j++; 30 } 31 System.out.print("\n"); 32 return; 33 } 34 return; 35 } 36 visited[v]=1; 37 trace.add(v); 38 39 for(int i=0;i<n;i++) 40 { 41 if(e[v][i]==1) 42 findCycle(i); 43 } 44 trace.remove(trace.size()-1); 45 } 46 47 public boolean getHasCycle(){ 48 return hasCycle; 49 } 50 51 public static void main(String[] args) { 52 int n=7; 53 int[][] e={ 54 {0,1,1,0,0,0,0}, 55 {0,0,0,1,0,0,0}, 56 {0,0,0,0,0,1,0}, 57 {0,0,0,0,1,0,0}, 58 {0,0,1,0,0,0,0}, 59 {0,0,0,0,1,0,1}, 60 {1,0,1,0,0,0,0}};//有向图的邻接矩阵,值大家任意改. 61 TestCycle tc=new TestCycle(n,e); 62 tc.findCycle(1); 63 if(!tc.hasCycle) 64 System.out.println("No Cycle."); 65 } 66 }
无向图
图就用bfs和dfs来做
import java.util.ArrayList; import java.util.Arrays; public class TestCycle { private int n; private int[] visited;//节点状态,值为0的是未访问的 private int[][] e;//有向图的邻接矩阵 private ArrayList<Integer> trace=new ArrayList<Integer>();//从出发节点到当前节点的轨迹 private boolean hasCycle=false; public TestCycle(int n,int[][] e){ this.n=n; visited=new int[n]; Arrays.fill(visited,0); this.e=e; } void findCycle(int v， int pre) //递归DFS { if(visited[v]==1) { int j; if((j=trace.indexOf(v))!=-1) { hasCycle=true; System.out.print("Cycle:"); if(trace.size()==3) count_ret++; return; } return; } visited[v]=1; trace.add(v); for(int i=0;i<n;i++) { if(e[v][i]==1 && pre!=v) findCycle(i, v); } trace.remove(trace.size()-1); } public boolean getHasCycle(){ return hasCycle; } public static void main(String[] args) { int n=7; int[][] e={ {0,1,1,0,0,0,0}, {0,0,0,1,0,0,0}, {0,0,0,0,0,1,0}, {0,0,0,0,1,0,0}, {0,0,1,0,0,0,0}, {0,0,0,0,1,0,1}, {1,0,1,0,0,0,0}};//有向图的邻接矩阵,值大家任意改. TestCycle tc=new TestCycle(n,e); tc.findCycle(1,-1); if(!tc.hasCycle) System.out.println("No Cycle."); } }
Edit Distance in Java By X Wang From Wiki: In computer science, edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. There are three operations permitted on a word: replace, delete, insert. For example, the edit distance between "a" and "b" is 1, the edit distance between "abc" and "def" is 3. This post analyzes how to calculate edit distance by using dynamic programming. Key Analysis Let dp[i][j] stands for the edit distance between two strings with length i and j, i.e., word1[0,...,i-1] and word2[0,...,j-1]. There is a relation between dp[i][j] and dp[i-1][j-1]. Let‘s say we transform from one string to another. The first string has length i and it‘s last character is "x"; the second string has length j and its last character is "y". The following diagram shows the relation. edit-distance-dynamic-programming if x == y, then dp[i][j] == dp[i-1][j-1] if x != y, and we insert y for word1, then dp[i][j] = dp[i][j-1] + 1 if x != y, and we delete x for word1, then dp[i][j] = dp[i-1][j] + 1 if x != y, and we replace x with y for word1, then dp[i][j] = dp[i-1][j-1] + 1 When x!=y, dp[i][j] is the min of the three situations. Initial condition: dp[i][0] = i, dp[0][j] = j Java Code After the analysis above, the code is just a representation of it. public static int minDistance(String word1, String word2) { int len1 = word1.length(); int len2 = word2.length(); // len1+1, len2+1, because finally return dp[len1][len2] int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 0; i <= len1; i++) { dp[i][0] = i; } for (int j = 0; j <= len2; j++) { dp[0][j] = j; } //iterate though, and check last char for (int i = 0; i < len1; i++) { char c1 = word1.charAt(i); for (int j = 0; j < len2; j++) { char c2 = word2.charAt(j); //if last two chars equal if (c1 == c2) { //update dp value for +1 length dp[i + 1][j + 1] = dp[i][j]; } else { int replace = dp[i][j] + 1; int insert = dp[i][j + 1] + 1; int delete = dp[i + 1][j] + 1; int min = replace > insert ? insert : replace; min = delete > min ? min : delete; dp[i + 1][j + 1] = min; } } } return dp[len1][len2]; }
O(NM);
A detailed discussion on its complexity and the code I wrote.
Third Round :
http://www.cnblogs.com/leetcode/p/3859583.html
1. Get a Caching Plugin . Every time a page loads on your blog, your web host has to serve every element on that page to the visitor‘s web browser. Using a caching plugin, your web host doesn‘t have to retrieve some elements from the server every time a page is displayed. Instead, the host can store elements in a cache and call them from there, which speeds up page loads. 2.Optimize Images using the best file formats for online images, then you‘re slowing down the page load speed for your blog. Always resize images to the actual size you need in your published blog post or page before you upload them to your blog. 3.Delete Unnecessary Javascript, CSS, and HTML Code Extra Javascript, CSS, and HTML code can slow down page load speed. Delete unnecessary code whenever possible. For example, is there duplicate code on your blog, meaning the same function is performed by two different tools but could be reduced to just one? If you come across applications like this, eliminate them and your page speed should improve. 4. Reduce HTTP Requests on Each Page Fewer elements on a page mean faster page load speeds because there are fewer HTTP requests required. For example, every image, piece of text, ad, video, and so on that appears on a web page has to be served to visitors through HTTP requests. Delete elements that add more clutter than value to your pages, and your page load speed will improve. You can also consider combining elements. For example, a series of images could be combined and uploaded as a single, optimized image
TCP is a connection oriented stream over an IP network. It guarantees that all sent packets will reach the destination in the correct order. This imply the use of acknowledgement packets sent back to the sender, and automatic retransmission, causing additional delays and a general less efficient transmission than UDP. UDP a is connection-less protocol. Communication is datagram oriented. The integrity is guaranteed only on the single datagram. Datagrams reach destination and can arrive out of order or don‘t arrive at all. It is more efficient than TCP because it uses non ACK. It‘s generally used for real time communication, where a little percentage of packet loss rate is preferable to the overhead of a TCP connection.
import java.util.*; /* * we are using linked list with hashmap for Lru.Reason behind this is ,since HashMap is able to store data and key but * how do we get info about least recently used cache value?. For this we need to keep track all inserted data into map * by using linked list. When inserting new values , add this value to the top of linked list. When key,value is already * present then refresh it by removing it from the linked list and adding it to top of the linked list. * */ public class CacheStrategies { public interface CacheStrategy<K, T>{ T get(K key); void put(K key,T data); } class CacheStrategyLRU<K, T> implements CacheStrategy<K, T> { class Node{ K key; T data; Node next; Node prev; public Node(K key, T data){ this.key = key; this.data = data; } } Node head,tail; Map< K, Node> map; int maxsize; public CacheStrategyLRU(int mxsize){ this.maxsize = mxsize; map = new HashMap<K ,Node>(); head = new Node(null,null); tail = new Node(null,null); head.next=tail; tail.prev=head; } private void attach(Node head,Node node){ node.prev = head; node.next = head.next; head.next.prev=node; head.next = node; } private void remove(Node node){ node.prev.next = node.next; node.next.prev = node.prev; } @Override public T get(K key) { Node node = map.get(key); if(node==null){ return null; } if(map.size()==1){ return node.data; } remove(node); attach(head,node); return node.data; } @Override public void put(K key, T data) { if(maxsize<=0){ return; } Node node = map.get(key); if(node!=null){ remove(node); attach(head,node); node.data = data; }else{ if(map.size() >= maxsize){ remove(tail.prev);//tail is node pointer ,its not containg any node so delete tail.prev map.remove(tail.prev.key); } Node nd = new Node(key,data); map.put(key, nd); attach(head,nd); } } } }
Fourth Round( Bar Raiser /BR Round):
It was a telephonic round . I was given a design problem . We have a customer using amazon Kindle , suppose he wants to borrow a book for some days , lets say x and wants to finish reading the book within the days limit. The book contains ,lets say y chapters ,once he starts reading a chapter he has to finish that on the same day . He can read the book only in a sequential manner , you have to tell how many chapters should he read on each day so that he can finish reading the book .
A discussion on my approach and
Then he asked me to write a code for it.
Then he asked me some HR related questions .
And some others, I don’t remember.
原文：http://www.cnblogs.com/leetcode/p/3902832.html