TripAdvisor常考面经总结

TripAdvisor常考面经总结 TripAdvisor Coding Practice List
Constaints: 1. No duplicate returning value 2. getRandom( will at most be invoked 100 million times Then optimize for space 47. Implement LRU algorithm; Write code to implement a general Binary Search Tree 48. Write a routine to print the numbers 1 to 100 and back to 1 again without using any loops 49. coding up a binary search tree and implementing an insert and findSum atlevelint n)routine 50. Given a tree of world regions locations and specific destinations and attractions find the most efficient ways to determine the common parent of two arbitrary nodes in terms of space and time 51. Write a web crawler to count number of pages in a website 52. count the number of duplicates in a binary tree in o(n) time o() space 53. Find the next larger node of a node in a binary search tree 54. Describe a hashtable and what's the time complexity for searching for a particular element 55. Write an algorithm for finding all pairs in a set of integers that add to a given target sum 56. Given two stacks, how can you implement a queue? What are the costs of push and pop operations? 57. How would you implement a bit vector data structure? Optimizing for memory 58. How would you implement a binary Search Tree? 59. What are the properties of a good hash? 60. Given two strings; boston and obtons how can you determine that they and any other set of strings, are anagrams of each other try and make it as efficient as possible 61. Other than an array what data structure has o(1) insertion and o(1 search? 62. How can you tell efficiently how many consecutive zero s are in a number without looping through its digits? 63. 64 Implement String Builder in Java 65. The most difficult question was when the interviewer asked that if we sum up the elements in the nodes by first visiting the left subtree, then the middle, and then the right what kind of traversal is this? 66. Check if one binary tree is the subtree of another 67 68. He gave me a set of nodes and asked me to search for a given node. Note: Consider the nodes are in a binary tree 69. how to get the middle index in an array list 70. Given a dictionary of words and a 4x 4 boggle board see which dictionary words you can make 71. Given a binary search tree, set up a variable in each node that points to its right neighbor 72. 73. Identify the best alert Given an alert find the closest area that the alert must be sent to Had some Java code in front and had to complete it 74. the first interviewer described to me a system that he called h-score h-score is a score that publishers get if articles that they publish get citations in other articles. a publisher gets h-score of x if they wrote at least x articles that got x citations each given an array with the number of citations per article write a function to calculate the h-score for the publisher. 75. Finding the depth of any arbitrary node in a binary tree 76.2sum 77. find if two linked lists join each others or not and if yes where is the intersection point 78 What's the difference for and foreach. He expect me to say: if I use LinkedList a, use for and a get(index) would take o(n 2 time complexity 79. Write a function that raises a number to an exponent in c or Java 80. Check if a tree is symmetric. 81. If you can do unlimited pre-processing, how would you find the lowest common ancestor of any two nodes in a tree, in o(1) time?