hack121 / interview-2 Goto Github PK

Useful Interview Question Links:
    http://geeksforgeeks.org/forum/forum/interview-questions
    http://www.careercup.com/page
    http://www.careercup.com/page?pid=google-interview-questions
    http://codekata.pragprog.com/2007/01/code_kata_backg.html#more
    http://www.impactinterview.com/2009/10/140-google-interview-questions/#software_engineer

Categorized Interview Questions:

C1: General
    1) Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
    2) Write a regular expression which matches a email address. (Ramp up Regular Expression)
    3) Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.
    4) Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D,..Z,AA,AB,AC,..,ZZ,AAA..) and returns a corresponding integer value (A=1,B=2,..,AA=26..).
    5) You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
    6) There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).
    7) Write some code to find all permutations of the letters in a particular string.
    8) What method would you use to look up a word in a dictionary?

    12) Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.

    14) Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
    15) Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
    16) Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
    17) Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
    18) Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
    19) How would you reverse the image on an n by n matrix where each pixel is represented by a bit?

    22) How to find the median among the given numbers whose values are unknown but falls into a narrow range.
    23) Given a set of ranges, find the two ranges with the greatest overlap.
    24) Verify whether an arithmatic expression is valid, suppose the expression only contains "+", "-", "*", "/", "(", ")" and numbers are integers.
    25) The bet problem
    26) Count the amount of '1's in an integer's binary form
    27) There are k exactly same boxes, and we have to put n exactly same items into them. Assume there is no limitation on box, and the only requirement is that each item should be put into one box. Please write out the code to print out all the possible possibilities, print error the input can not get any result.
    28) Get the amount of ending zeros of N! without calculating N!
    29) Implement a function to get the greatest common divisor of two given numbers.
    30) Remove all the number contains 7 from the integer, and define a method to return corresponding number when giving a regular number

C2: CS Theory
    1) What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?
    2) How are cookies passed in the HTTP protocol?
    3) Design the SQL database tables for a car rental database.
    4) What is multithreaded programming? What is a deadlock?
    5) Implement division (without using the divide operator, obviously).
    6) Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
    7) How long it would take to sort 1 trillion numbers? Come up with a good estimate.
    8) What's the difference between a hashtable and a hashmap?

C3: List
    1) You are given a list of numbers, and the list is circular list. Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don�� know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
    2) Write a function to find the middle node of a single link list.
    3) Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists.

C4: Array
    1) Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.
    2) Given an array, find the longest continuous increasing subsequence.
    3) You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum. Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))��Please give a solution in O(n) time complexity
    4) Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.
    5) Given an array, print the array elements cyclicly from outside to center.
    6) Given an array, use Binary Search to find a given element
    7) Given a sorted array, there is only one value K has multiple occurrence, find the repeating element and its first occurrence.
    8) Find the Kth small element in an array.
    9) Given an array, there is an element whose occurence is greater than the half of the array's length, find this element.
   10) Given an m*n grid, how many paths are there from the left bottom corner to the up right corner.
   11) Randomly shuffle an array.
   12) Given an array, find all sub-arrays whose elements' sum is equal to a given K.
   13) Given an array containing both positive and negative numbers, find the sub array whose elements' sum is maximum.
   14) Given a set S, find all the maximal subsets whose sum <= k.
   15) Find the uniq amount of absolute values in a given sorted array
   16) Write code to reverse a array of int
   
C5: Tree
    1) Describe the algorithm for a depth-first graph traversal.
    2) Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
    3) How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.
    4) How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
    5) Given a binary tree, programmatically you need to prove it is a binary search tree.
    6) Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
    7) Given a tree, find pairs of nodes with each pair nodes' values sum equal to a given number K.

C6: Graph
    1) What's the maximum number of edges in a Directed Asynclic Graph with N node.

C7: Stack
    1) Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

C8: Sorting
    1) If you have 1 million integers, how would you sort them efficiently?
    2) You are given a small sorted list of numbers, and a very very long sorted list of numbers ��so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
    3) What sort would you use if you had a large data set on disk and a small amount of ram to work with?
    4) What sort would you use if you required tight max time bounds and wanted highly regular performance.

C9: Design Patterns and OOP
    1) Design a class library for writing card games.

C10: System Design
    1) Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: a) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC��); b) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. c) You can use only custom written applications or available free open-source software.
    2) Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
    3) Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t).
    4) Remove duplicated lines in a very large block of text.

C11: String
	1) Implement an algorithm to determine if a string contains all 26 characters. What if you can not use additional data structures?
	2) Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
	   Addition, remove all the duplicate characters
	3) Write a method to decide if two strings are anagrams or not.