http://www.careercup.com/page www.codechef.com www.topcoder.com http://www.leetcode.com http://www.hackerrank.com/ http://codekata.pragprog.com/2007/01/code_kata_backg.html#more http://geeksforgeeks.org/forum/forum/interview-questions http://www.impactinterview.com/2009/10/140-google-interview-questions/#software_engineer Dynamic Programming: http://hawstein.com/posts/dp-novice-to-advanced.html 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. Given a function which produces a random integer in the range 1 to 7, write a function which produces a random integer in the range 1 to 10. 2) Write a regular expression which matches a email address. (Ramp up Regular Expression) 3) Implement Union Find, which is used for connectivity detection: http://algs4.cs.princeton.edu/15uf/ 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..). 6-N) What method would you use to look up a word in a dictionary? 7-N) 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. 8-N) Given a file of 4 billion 32-bit integers, how to find one that appears at least twice? 9) Given a set of coin denominators, find the minimum number of coins to give a certain amount of change. Same Problem with C12_2 10) Given a set of ranges, find the two ranges with the greatest overlap. 11) Given a time, calculate the angle between the hour and minute hands 12) Design a algorithm to point all permutation of a string, assume all the character are unique same as C11_4 13) Numbers are randomly generated and stored in an array. How would you keep track of the median. 14) Write a method to get the greatest common divisor(GCD) of two given integer. 15) Write a method to transfrom a string to int. 23) Given an arithmatic expression, evaluate the value of the expression, suppose the expression only contains "+", "-", "*", "/", "(", ")" and numbers are integers. 23A)Given an arithmatic expression, transform the expression into postfix expression, suppose the expression only contains "+", "-", "*", "/", "(", ")" and numbers are integers. 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 26A) Given two integer A and B, write code to find how many bit need to change if want to change A into B. 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) Find un-duplicate integer number in 250 million integer. 30) Remove all the number contains 7 from the integer, and define a method to return corresponding number when giving a regular number 31) Given a string, rearrange the string to a palindrome and return the palindrome if present or -1 32) Given a capacity value N, and a set of different Item types with values v1, v2, ...,vn 1) Existence Check: check whether N can be filled with a certain combination of items 2) All Combinations: get all the combinations of items that fills N 3) Minimum Combination: get the minimum number of items that fills N Same Problem with C12_2 33) Given a timer time() with nanosecond accuracy and given the interface interface RealTimeCounter: void increment() int getCountInLastSecond() int getCountInLastMinute() int getCountInLastHour() int getCountInLastDay() implement the interface. The getCountInLastX functions should return the number of times increment was called in the last X. 34）Implement BitSet 35) Write a function to print out all the amicable numbers pair within 10000; amicable numbers pair is the numbers which the sum of its real factor equals to the other. such as 220 and 284; 36) N integer from 0 - N-1 form a cycle, start to delete number by visit M step. The process is started at 0. Given N and M, please write code to calculate which number will last at the final round. 37) Given a N, write function to calculate how many 1 appear in 1-N. [Google] Such as 12, it should have 1, 10, 11, 12, and it should return 5. 37A)Given a N, write a generic function to calculate how many M appear in 1-N. M is [1-9]. 38) There is N teams in a match. w[N][N] store the competition result between each two team. order[N] store the order of team. At the first round, order[0] vs. order[1], and order[2] vs. order[3], etc. the winner comes to next round. Finally comes the winner. Write code to compute the ranking of the match. 39) Having n string length is m+1, here is a rule to conjoin 2 string together: if the prefix n character equals suffix n character. Write code to find the length of the conjoined string, and give a error when it could find a cycle. 40) Having N, find there exist how many continuous int sequence which sum is N. Such as Given 15, 1+2+3+4+5 = 4+5+6 = 7+8 = 15, so output should be 3. 41) There is k parenthesis, write code to calculate how many permutations could have. For 2 parenthesis, there is 2 permutations: ()() and (()). This problem is the same as: 1. there is N non-duplicate number, how many different sequences when pushing these numbers to a stack. 2. given N non-duplicate number, how many different binary tree could be built. 3. given an N edge convex polygon, how many different way to using non-cross diagonal line to cut polygon into triangle. It's the Catalan number: h(0)=1,h(1)=1, the recursive definition is： h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2) 42) We call the number which factors only include 2,3,5 as "Ugly Number". Write code to compute 1500 ugly number. [Google] 43) Write code to determine the 5 poker card is a straight or not. 44) Given N sieves, write code to calculate the possibility of each sum of all the sieves number. 45) Write code to calculate the math power function: power(base, exp) 46) There is a random method rand(), generate 0 in possibility p, and generate 1 in possibility 1-p. [Baidu] Write code to use this rand() generate 0 and 1 in the same possibility 0.5. Write code to generate 1,2,3 in same possibility 1/3 Write code to generate 1-N in the same possibility 1/N. 47) Given N points, every line go through 2 point, write code to find the line with largest slope. 48) Given a integer, write code to check if it's a square of some integer, can't use sqrt() 49) Given an int array, numbers between 0-9, such as [0,1,3,8], write code to find the closest number built by these numbers larger then K. [Google] Such as [0,1] and K = 21, should return 100. 50) Given 4 points, write code to determine whether the 4 points is a rectangle or not 51) Given a set of chars, write code to print out all the permutations. 52) Have M memory, given a set of task, each have need request R[i] memory for handling, and O[i] memory to store the result (O[i] < R[i]). Write code to assign the task as a sequence to make sure all the task can be done, return a empty assignment if whatever sequence can't be fulfill these requirement. [Google] There assume the task can only be done in sequence, not parallel. 53) There is 25 horses, need find the fastest 5 ones, there are 5 racing tracks, so each race can have 5 horse to have a competition. How any round need it. 54) Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap. Each rectangle is identified by the left-up corner and right-down corner. 55) Sudoku Game: Given a 3*3 matrix, and 1-8 numbers in random order, 1 place as space. Write code to find the min exchange of numbers to make the matrix in order 5 4 1 1 2 3 3 2 ---> 8 4 7 8 6 7 6 5 56) Given a int number, write code to judge the number of all its factor is an even number or an odd number 57-N) Given two number A and B, find how many numbers between A and B follow this rule: assume C = c1c2c3c4(between A and B), when (c1+c2+c3+c4)/4 > 7 count one, otherwise not. such as 8675, (8+6+7+5)/4 < 7 not count one, 8695, (8+6+9+7)/4 > 7 count one. Write code time complexity is O(logA + logB) [Google] 58) Given a int N, write code to find the N which is the closet number is power of 2. 58A)Given a int N, write code to check if N is the power of 2. 59) Write code to get N prime numbers 60) Let A be a set of the first N positive integers :A={1,2,3,4.........N} Write code to find such subset pair, (x,y), x and y are the subset of A Relation 1 pair: x not a subset of y, y is not a subset of x, and x,y have no intersection. Relation 2 pair: x not a subset of y, y is not a subset of x, and x,y have intersection. Given N, write code to calculate how many Relation 1 pair and Relation 2 pair. 61) Given a integer N, find the minimal M to make N * M contains only 0 and 1. such as: N = 2, M = 5, N * M = 10. 62) Given N point in two dimentional space, find the closest two points. 63) Given a source range, and a list of target range, write code to check if the source range is in target range. 64) Given a integer, write code to find a combination of continuous integer which sum is the given integer. Such as: 9 -> 4 + 5, 11 -> 5 + 6, 6 -> 1 + 2 + 3, 20 -> 2 + 3 + 4 + 5 + 6 a. Some integer can't find this kind of combination, please specify the rules of this kind of integer. b. In 32-bit integer, which number have most combination. 65) Giving a triangle ABC (ABC in wise-clock order), and a point D. Write code to check if D is inside of ABC. 66) 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 peo- ple in such a tower EXAMPLE: Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190) 67) Given a string, print all the combinations with the chars in the string. Example: for abc, the combinations are a, b, c, ab, ac, bc, abc. 68) Given a string, print all the permutations of the string. 69) Implement an algorithm to print all valid combinations of n-pairs of parentheses. 70) Write a function that adds two numbers. You should not use + or any arithmetic operators. 71) Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 72) Determine whether an integer is a palindrome. Do this without extra space. [LeetCode] 73) Some about permutation: [LeetCode] 73A) Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 73B) Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. 73C) The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123", "132", "213", "231", "312", "321", the 4th permutation is "312" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive. 73D) Given a collection of numbers that might contain duplicates, return all possible unique permutations. g For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. 74) Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100". 75) The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: [LeetCode] (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows. 76) Some about combination: [LeetCode] 76A) Given a collection of numbers, return all possible combinations 76B) Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]] 76C) Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7], [2, 2, 3] 77) The gray code is a binary numeral system where two successive values differ in only one bit. [LeetCode] Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 As solution, grey code is generated by ((i >> 1) ^ i); 78) Roma to integer and integer to Roma. 79) Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). [LeetCode] N vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines (not need to be adjacent), which together with x-axis forms a container, such that the container contains the most water. 80) Given an array of non-negative integers, you are initially positioned at the first index of the array. [LeetCode] Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. 80A)Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.) 81) Given a digit string, return all possible letter combinations that the number could represent. [LeetCode] A mapping of digit to letters (just like on the telephone buttons) is given below. 2: a b c 3: d e f 4: g h i 5: j k l 6: m n o 7: p q r s 8: t u v 9: w x y z Input:Digit string "23", Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 82) There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. [LeetCode] You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.Read full article from zouzhile/interview
No comments:
Post a Comment