cracking-the-coding-interview/interviewQuestions.txt at master · shyal/cracking-the-coding-interview
// These are the questions I have not yet answered: 6.2 There is an 8x8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example or showing why it's impossible). 6.3 You have a five-quart jug, a three-quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped, such that filling up exactly "half" of the jug would be impossible. 6.4 A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8:00pm every evening. Each person can see everyone else's eye color, but they do not know their own (nor is anyone allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave? 6.5 There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it's dropped from any floor below, it will not break. You're given two eggs. Find N, while minimizing the number of drops for the worst case. 6.6 There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes it if it is open or opens it if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open? 7.1 You have a basketball hoop and someone says that you can play one of two games. Game 1: You get one shot to make the hoop. Game 2: You get three shots and you have to make two of three shots. If p is the probability of making a particular shot, for which values of p should you pick one game or the other? 7.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed. Similarly, find the probability of collision with n ants on an n-vertex polygon. 7.5 Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis. 7.6 Given a two-dimensional graph with points on it, find a line which passes the most number of points. 7.7 Design an algorithm to find the kth number such that the only prime factors are 3,5, and 7. 8.2 Imagine you have a call center with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can't handle the call, he or she must escalate the call to a manager. If the manager is not free or not able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implement a method dispatchCall() which assigns a call to the first available employee. 8.3 Design a musical jukebox using object-oriented principles. 8.4 Design a parking lot using object-oriented principles. 8.5 Design the data structures for an online book reader system. 8.6 Implement a jigsaw puzzle. Design the data structures and explain an algorithm to solve the puzzle. You can assume that you have a f itsWith method which, when passed two puzzle pieces, returns true if the two pieces belong together. 8.7 Explain how you would design a chat server. In particular, provide details about the various backend components, classes, and methods. What would be the hardest problems to solve? 8.8 Othello is played as follows: Each Othello piece is white on one side and black on the other. When a piece is surrounded by its opponents on both the left and right sides, or both the top and bottom, it is said to be captured and its color is flipped. On your turn, you must capture at least one of your opponent's pieces. The game ends when either user has no more valid moves. The win is assigned to the person with the most pieces. Implement the object-oriented design for Othello. 8.9 Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible. 9.3 A magic index in an array A [ 0 . . .n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A. FOLLOW UP What if the values are not distinct? 9.5 Write a method to compute all permutations of a string. 9.9 Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column or diagonal. In this case, "diagonal" means all diagonals, not just the two that bisect the board. 9.10 You have a stack of n boxes, with widths w., heights h ir and depths d r The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack is strictly larger than the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box. 10.1 Imagine you are building some sort of service that will be called by up to 1000 client applications to get simple end-of-day stock price information (open, close, high, low). You may assume that you already have the data, and you can store it in any format you wish. How would you design the client-facing service which provides the information to client applications? You are responsible for the development, rollout, and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach. Your service can use any technologies you wish, and can distribute the information to the client applications in any mechanism you choose. 10.2 How would you design the data structures for a very large social network like Facebook or Linkedln? Describe how you would design an algorithm to show the connection, or path, between two people (e.g., Me -> Bob -> Susan -> Jason -> You). 10.3 Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory available for this task. FOLLOW UP What if you have only 10 MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers. 10.4 You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4 kilobytes of memory available, how would you print all duplicate elements in the array? 10.5 If you were designing a web crawler, how would you avoid getting into infinite loops? 10.6 You have 10 billion URLs. How do you detect the duplicate documents? In this case, assume that "duplicate" means that the URLs are identical. 10.7 Imagine a web server for a simplified search engine. This system has 100 machines to respond to search queries, which may then call out using processSearch(string query) to another cluster of machines to actually get the result. The machine which responds to a given query is chosen at random, so you can not guarantee that the same machine will always respond to the same request. The method processSearch is very expensive. Design a caching mechanism for the most recent queries. Be sure to explain how you would update the cache when data changes. 11.2 Write a method to sort an array of strings so that all the anagrams are next to each other. 11.3 Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order. EXAMPLE Input: find 5 in {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14} Output: 8 (the index of 5 in the array) 11.4 Imagine you have a 20 GB file with one string per line. Explain how you would sort the file. 11.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string. 11.6 Given an M x N matrix in which each row and each column is sorted in ascending order, write a method to find an element. 11.7 A circus is designing a tower routine consisting of people standing atop one another's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower. 11.8 Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal tox). Implement the data structures and algorithms to support these operations.That is, implement the method track(int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x (not including x itself). 12.2 You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? 12.3 We have the following method used in a chess game: boolean canMoveTo( int x, int y). This method is part of the Piece class and returns whether or not the piece can move to position (x, y). Explain howyou would test this method. 12.4 How would you load test a webpage without using any test tools? 12.5 How would you testa pen? 12.6 How would you test an ATM in a distributed banking system? 13.2 Compare and contrast a hash table and an STL map. How is a hash table implemented? If the number of inputs is small, which data structure options can be used instead of a hash table? 13.3 How do virtual functions work in C++? 13.4 What is the difference between deep copy and shallow copy? Explain how you would use each. 13.5 What is the significance of the keyword "volatile" in C? 13.6 Why does a destructor in base class need to be declared virtual? 13.7 Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed in data structure. The Node data structure contains two pointers to other Nodes. 13.8 Write a smart pointer class. A smart pointer is a data type, usually implemented with templates, that simulates a pointer while also providing automatic garbage collection. It automatically counts the number of references to a SmartPointer<T*> object and frees the object of type T when the reference count hits zero. 13.9 Write an aligned malloc and free function that supports allocating memory such that the memory address returned is divisible by a specific power of two. EXAMPLE align_malloc (1000,128) will return a memory address that is a multiple of 128 and that points to memory of size 1000 bytes. aligned_free() will free memory allocated by align_malloc. 13.10 Write a function in C called my2DAlloc which allocates a two-dimensional array. Minimize the number of calls to malloc and make sure that the memory isaccessible by the notation arr[i][j]. 15.1 Write a SQL query to get a list of tenants who a re renting more than one apartment. 15.2 Write a SQL query to get a list of all buildings and the number of open requests (Requests in which status equals 'Open'). 15.3 Building #11 is undergoing a major renovation. Implement a query to close all requests from apartments in this building. 15.4 What are the different types of joins? Please explain how they differ and why certain types are better in certain situations. 15.5 What isdenormalization? Explain the pros and cons. 15.6 Draw an entity-relationship diagram for a database with companies, people, and professionals (people who work for companies). 15.7 Imagine a simple database storing information for students' grades. Design what this database might look like and provide a SQL query to return a list of the honor roll students (top 10%), sorted by their grade point average.Read full article from cracking-the-coding-interview/interviewQuestions.txt at master · shyal/cracking-the-coding-interview
No comments:
Post a Comment