Sample questions from Programming Pearls

How do you sort 10 million 7-digit phone numbers with ~1MB RAM? How would you solve this using one pass and no intermediate files? What if 1MB RAM was a firm limit?
Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn’t in the file (and there must be at least one missing...why?). How would you solve this with unlimited main memory? How would you solve it if you could use several external files but only a few bytes of main memory?
Rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 and i=3, the vector abcdefg is rotated to defghabc. Simple code uses an n-element intermediate vector to do the job in n steps. Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?
Given a dictionary of English words, find sets of anagrams. For instance, “pots”, “stop”, and “tops” are all anagrams of one another because each can be found by permuting the letters of the others.
Write functions for the following date problems: given two dates, compute the number of days between them; given a date, return it’s day of the week; given a month and year, produce a calendar of the month as an array of characters
Given a very long sequence (say, billions or trillions) of bytes, how would you efficiently count the total number of one bits? (i.e. how many bits are turned on in the entire sequence)
Although Quicksort uses only O(logn) stack space on the average, it can use linear space in the worst case. Explain why, then modify the program to use only logarithmic space in the worst case.
Write a program for finding the kth-smallest element in the array x[0...n-1] in O(n) expected time. Your algorithm may permute the elements of x.
Build the fastest possible complete function to generate a sorted array of random integers without duplicates. (You need feel constrained to use any prescribed interface for set representation)

10.Implement heap-based priority queues to run as quickly as possible; at what values of n are they faster than sequential structures?

If you have not already read through Steve Yegge's Technical Prep Tips on his blog

The Algorithm Design Manual ‐ A lot you'd want to know about designing and implementing lots of fundamental algorithms Structure and Interpretation of Computer Programs ‐ (esp. Pragmatic Unit Testing, Effective Java, Code Complete 2, Agile Estimation and Planning).

Classic problems

Mostly while preparing for technical interviews.

Towers of Hanoi

There's a temple in the middle of Hanoi. In that temple, there are three very large diamond-encrusted posts, and on those posts are sixty-four disks, all of a different size. There are a set of priests in that temple, and their task is to move the entire stack of sixty-four disks from one post to a second post. The rules, though, are, they can only move one disk at a time, and they can never cover up a smaller disk with a larger disk. Write a recursive program to solve this problem. What is the complexity?

Searching and sorting algorithms

Write code to search a sorted list. Write a binary search algorithm. Write a selection sort algorithm. Write code to create a hash table of size 256

Shortest path problem Write an algorithm to plan a route by minimising distance or time (eg Google Maps)

Traveling salesman Write an algorithm to determine the least cost round-trip, given multiple cities and varying costs of flights

Knapsack problem Write an algorithm to optimize the value of items you can fit into a backpack based on weight and volume

Sorting algorithms - know how they work, average/worst case running times, stack space

Insertion sort
Quicksort
Mergesort
Heapsort

Searching algorithms: know how they work, average/worst case running times, stack space

Sequential search
Binary search
Hashing
Binary search trees
Key indexing

Other algorithms

Priority queues

Back of the envelope calculations Know your powers of 2 (binary) Be able to express mega/giga/etc in binary and/or scientific notation Know cycle times and disk seek times for CPUs

Data Structures and Algorithms

Problem A1: Prime Number Generation

Given a positive number N, generate all the prime numbers from 2 to N. The primary emphasis in the solution to this problem should be on speed. In addition, you must not consume an inordinate amount of memory.

Problem A2: Arbitrary Precision Arithmetic

Implement an arbitrary precision arithmetic calculator. You should implement addition, subtraction, multiplication and division in the respective order. Try to make your program as fast as possible and keep memory usage to the bare minimum.

Problem A3: Sub-string Search

Given two strings S1 and S2, determine whether S2 occurs as a substring in S1 and if so, find the first occurrence of S2 in S1. Your program should be extremely fast. Try to come up with a linear solution to the problem.

Section B

Problem B1: Simple File-system Implementation

Implement a simple filesystem within a normal file on the hard disk, i.e. treat the file as a virtual disk and implement the filesystem by manipulating records within the file.

You are free to devise your own scheme for the file system but it should minimally support the following operations:

1) Create - Create a virtual hard disk on a file of the specified size and "format" it. Formatting would essentially involve initialising disk allocation structures and whatever else you need to do before you can have a valid filesystem.

2) Open, Read, Write, Close - All the normal file operations to use the files.

3) Delete, Rename - Remove unwanted files or rename existing files.

Do not place artificial restrictions on file names, sizes, etc.

In addition, if you can, provide support for folders (also known as directories) which can be arbitrarily nested. Provide all the common operations for folders.

You should implement this as a library of routines that can be used by anyone wanting to treat a file as a filesystem. Demonstrate the correctness of your routines by writing a demo program that lets one manipulate files interactively.

uthcode / learntosolveit