Computing Interview Questions
From BenningtonWiki
[edit] Questions You Should Ask
- How much time do I have to write it?
- Is it important to get it done quickly?
- How much program space do I have?
- Does it matter how big the program is?
- How much time do I have to run it?
- Does it matter how long the program takes?
- Can it use more time the first time it runs?
- Can I cache values and then use them subsequently?
- Can I write to the hard disk?
- Where can I cache the results?
- Can I write more than one version of the program?
- Can I try different techniques and test them before submitting one?
- Can I have more time to write it if it'll be a lot better?
- Do you want quick and dirty?
- Are function calls slow?
- Should I bother factoring the code into functions?
- Are library calls slow?
- Should I use library calls for trivial functions, or should I write my own?
- Should I avoid recursion?
- Are you impressed by recursion, at the risk of stack overflow errors? How 'bout I tell you about the recursive solution so that you can see that I know what recursion is, but I code it without recursion.
- Should I write it to be worked on by someone else?
- How much legibility can I sacrifice in order to save size, gain speed, etc.?
[edit] Problems
The number in brackets preceding each problem is the length of time it would take me, on a good day, to write a program solution. Appropriate scale factor for you may be 0.9 to 10. (If you're less than 2 you're hired.)
Use the problem name when referring to a problem, as the number (from the Table of Contents above) may change.
[edit] Counting
[1] Print the numbers from 1 to 100.
[edit] Odd Numbers
[1] Print out the odd numbers from 1 to 99.
[edit] Asterisks on Odd Numbers
[2] Print the numbers from 1 to 100, putting an asterisk next to the odd numbers.
1* 2 3* 4 5* ...
[edit] Counting Backwards
[1] Print the numbers from 100 to 1.
[edit] Odd Numbers Backwards
[1] Print the odd numbers from 99 to 1.
[edit] Swap
[1] Write a program that swaps two variables.
[edit] Upper Case?
[2] Write a function that determines if a string starts with an upper-case letter A-Z.
[edit] Multiplication Table
[5] Print out a formatted grade-school multiplication table, 12 by 12.
1 2 3 4 5 6 7 8 9 10 11 12 2 4 6 8 10 12 14 16 18 20 22 24 3 6 9 12 15 18 21 24 27 30 33 36 4 8 12 16 20 24 28 32 36 40 44 48 5 10 15 20 25 30 35 40 45 50 55 60 6 12 18 24 30 36 42 48 54 60 66 72 7 14 21 28 35 42 49 56 63 70 77 84 8 16 24 32 40 48 56 64 72 80 88 96 9 18 27 36 45 54 63 72 81 90 99 108 10 20 30 40 50 60 70 80 90 100 110 120 11 22 33 44 55 66 77 88 99 110 121 132 12 24 36 48 60 72 84 96 108 120 132 144
[edit] Days in a Month
[3] Make a function that returns the number of days in a month, given the month number and year. Handle leap years properly.
def days_in_month(month, year) ... return days end
? 3, 2008 Days: 31 ? 2, 2008 Days: 29 ? 1, 1950 Days: 31
[edit] Calendar
[10] Print a formatted calendar for the current month.
April 2007
S M Tu W Th F S
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
[edit] Reverse a String
[5] Input a string and print it out in reverse. You can't use the language's built-in method, if it has one.
? Donald Knuth has my back. > .kcab ym sah htunK dlanoD
[edit] Summing Numbers
[1] Sum the numbers in this array:
numbers = [92, 48, 2, 42, 11, 54, 23, 95, 52, 45, 45, 69, 48, 45, 51, 83, 28, 32, 14, 21, 0, 87, 70, 82, 90, 9, 3, 16, 63, 54, 8, 3, 56, 33, 79, 10, 14, 83, 1, 11, 93, 89, 3, 32, 88, 42, 70, 91, 7, 86, 31, 2, 94, 23, 48, 25, 17, 23, 73, 53, 29, 33, 23, 91, 97, 15, 62, 39, 55, 71, 80, 51, 25, 48, 2, 32, 40, 69, 58, 76, 57, 24, 15, 84, 36, 26, 52, 36, 50, 58, 50, 1, 18, 68, 80, 42, 7, 69, 11, 64]
[edit] Min, Max Values in an Array
[2] Print out the smallest and largest values in the array above.
[edit] Number Guessing, You Guess
[10] Your program picks a random number from 1 to 100. You try to guess what it is by entering numbers. The program responds by saying too high, too low or got it.
I'm thinking of a number... ? 23 Too low. ? 98 Too high. ? 83 You got it.
[edit] Number Guessing, Your Program Guesses
[15] Same game as above, only you pick the random number and your program tries to guess it. The program prints the guessed number and you reply by telling it too high, too low or got it. (Extra points for snarky comments.)
You're thinking of a number... I guess 17. ? too low Okay, I guess 70. ? too low Really?! Okay, I guess 91. ? you got it Machine intelligence be bangin.
[edit] Alphabetical List of Names
[15] Create an unsorted array of names. Sort the names using your own algorithm, not a built-in sort function. Print out the sorted list.
names = ["Hannah", "Alexander", "Kate", "Soley", "Max"] def my_sort(n) ... return sorted_n end p my_sort names
["Alexander", "Hannah", "Kate", "Max", "Soley"]
[edit] Random Pairs of Names
[10] Given an array of names, print out a random pairing of names using every name exactly once. Handle the case where there is an odd number of names in the array.
[edit] Hashing
[5] Given an array of numbers, generate a single number that is a hash of the array. Consider the hash algorithm's strengths and weaknesses. What kinds of changes to the array (eg, two numbers are swapped) won't be reflected in the hash?
[edit] FizzBuzz, the Cheap Version
[2] Write a program that prints the numbers from 1 to 100. But if a number is divisible by three print “Fizz” instead of the number, and if a number is divisible by seven print “Buzz”. For numbers which are divisible by both three and seven print “FizzBuzz”.
1, 2, Fizz, 4, 5, Fizz, Buzz, 8, Fizz, 10, 11, Fizz, 13, Buzz, Fizz, 16, 17, Fizz, 19, 20, FizzBuzz, 22, 23, ...
[edit] FizzBuzz, the Real Version
[5] Write a program that prints the numbers from 1 to 100. But if a number is divisible by three or contains the digit three print “Fizz” instead of the number, and if a number is divisible by seven or contains the digit seven print “Buzz”. For numbers which are both “Fizz” and “Buzz” print “FizzBuzz”.
1, 2, Fizz, 4, 5, Fizz, Buzz, 8, Fizz, 10, 11, Fizz, Fizz, Buzz, Fizz, 16, Buzz, Fizz, 19, 20, FizzBuzz, 22, Fizz, ...
[edit] Reading a Text File
[5] Read the contents of a text file into an array, one line per array element. Print the first line, the last line, and the number of lines.
[edit] Word Lookup
[10] Load a dictionary into an array. Input a word and look for it in the dictionary, reporting whether it was found or not.
Use this dictionary.
Word? syzygy Found. Word? quincunx Found. Word? brilig Not found. Word? quit Found. Word? exit Found. Word? I want to stop this program now. Not found.
[edit] Optimal Word Lookup
[10] Using the Word Lookup program above, count the number of word compares you do while looking in the array for the entered word. Print out this number. Rework your program to use as few word compares as possible.
[edit] Nonsense Anagrams
[10] Generate all of the possible combinations of letters for a word that's entered. All you're doing is generating the permutations, not caring if the generated words are real words or not.
? apocalypse apocalypse paocalypse aopcalypse apcoalypse apoaclypse apoclaypse apocaylpse apocalpyse apocalyspe ...
[edit] One-word Anagrams
[10] Generate all of the legitimate one-word anagrams for a word that's entered.
? listen silent
[edit] Multi-word Anagrams
[30] Generate all of the anagrams for a word or phrase entered. Ignore white space and punctuation.
[edit] Counting Lines in a File on Disk
[5] Given a text file, count the number of lines in the file and print out the result. Don't load the entire file into memory.
Question: what constitutes a line?
[edit] Summing Numbers in a File
[5] Sum the numbers in a text file, where there is one number per line. Use this file of numbers.
[edit] Names Count
[5] Given a text file of first and last names, make a list of every first name and the number of times that name occurs. The names are in first last order with a single space between them, one name per line. Some names have middle initials. Some names may not have a last name. Print the names in alphabetical order.
Use this file of names (Bennington class list, 2006).
Aaron 2 Aarti 1 Abigail 2 ...
[edit] Most Popular Name
[5] Using the text file of names from above, print out the first name that appears most often.
[edit] Adding Line Numbers
[10] Add line numbers to the beginning of every line of a text file. It helps a lot to be familiar with the standard file operations in your language of choice in order to appreciate the pros and cons of the various possible solutions.
Possibilities: loading the text file into memory and then writing it back out. Using a temporary file.
[edit] The Interweb
[3] Fetch a random page from Wikipedia. Print how many characters long it is. (This can be a one-liner.)
[edit] The Interweb, part 2
[5] Print the first paragraph of the article from the fetched Wikipedia page.
[edit] Encoding and Decoding
[10] Input a message. Run it through an encoding algorithm of your design and print out the coded message. Input the coded message into a decoder and have it print out the original message. No cheating.
[edit] Chess
[500] Write a chess-playing program that beats you.
[edit] Parsing a Phone Number
[1] Input a phone number. Break it into area code and number. Be as flexible as possible with what you allow on the input. (Doesn't it drive you nuts when a web form insists on a dash here or parens there? Can't the computer be smart about what you enter?)
? 802 445-5401 Area code: 802 Number: 445-5401 ? (802) 445-5401 Area code: 802 Number: 445-5401 ? 8024455401 Area Code: 802 Number: 4455401 ...
[edit] Parsing an Email Address
[5] You're a spambot scraping web pages for email addresses to include in your master spam database. It's to your advantage to be able to spot as many email addresses as possible, so be very liberal. Can you work around the common tricks folks use to try to disguise their emails from scrapers (e.g., jholt AT bennington DOT edu). Input a line of text and attempt to extract an email address out of it. It may not necessarily have an address.
? jholt@bennington.edu Email: jholt@bennington.edu ? jholt No email. ?jholt @ bennington.edu Email: jholt@bennington.edu ? jholt AT bennington DOT edu Email: jholt@bennington.edu ...
[edit] Parsing an Expression, Simple
[10] Write a simple expression parser for interpreting and evaluating arithmetic expressions. No variables or parentheses allowed. Evaluate the expression in a strictly left-to-right order. Integer numbers only, add, subtract, multiply and divide.
? 5 + 2 = 7 ? 3 * 5 = 15 ? 2 + 3 * 5 = 25
[edit] Parsing an Expression, Advanced
[120] Same as above, only now allow parentheses for determining the order of evaluation, and evaluate the basic operators in standard order (multiply/divide before add/subtract). Allow floating point numbers. Allow numeric constants such as 'pi'. Allow functions such as sqrt(). Use a parse tree for interpretation and evaluation. Sell it as Mathematica Lite.
? 2 + 5 = 7 ? 2 + 3 * 5 = 17 ? (2 + 3) * 5 = 25 ? sqrt(2) = 1.4142135 ? 5 * (sqrt(2) + 1) = 12.0710678 ? pi * 3^2 = 28.2743343
