Suppose you have a web form that allows users to upload JPG, GIF or PNG images. Before you store the images in your system, you want to convert them all to the JPG format. Design an image converter API. Sketch out all classes and interfaces that are involved.
Note: the actual code necessary to convert a JPG image to a GIF image is not the point. Just place a comment at the appropriate location where the actual conversion should occur.
Suppose you have an array of 99 numbers. The array contains the digits 1 to 100 with one digit missing. Describe four different algorithms to compute the missing number. Two of these should optimize for low storage and two of these should optimize for fast processing.
Write a fast implementation for a hash table in Java. You may use arrays and the built in int hashCode() method that returns the hash code for all Java objects.
Define the following object oriented concepts:
Explain big o notation and how it is useful in computer science to classify algorithms.
Describe bitwise operators AND, OR, XOR and NOT. Describe how you might use these.
How do these bitwise operators differ from logical operators?
Name 3 top level class modifiers.
Explain the difference between an inner class and an anonymous class? When would you use these?
Can an inner class be defined inside a method? What variables can be accessed by that class?
Explain the difference between a mutex and a semaphore? If you need to protect access to an increment operation which one would be the best choice?
If you have access to a function that returns a random integer from one to five, write another function which returns a random integer from one to seven.
Discuss an algorithm to traverse a tree, depth first.
Describe a schema (or classes) to power an online car rental system. Describe the tables and the relationships beween the tables.
Construct a regular expression that matches a valid email address.
Implement a function with signature find_chars(string1, string2) that takes two strings and returns a string that contains only the characters found in string1 and string two in the order that they are found in string1. Implement a version of order N*N and one of order N.
Given a circular list of integers (when you reach the end of the list you come back to the beginning), what is the most efficient algorithm to find the smallest integer in the list?
For example: circular_list = [22, 52, 66, 82, 5, 8, 12, 19].
Given a N by N matrix of both negative and positive integers. Write an efficient algorithm to find the sub-matrix with the largest sum of all the contained elements.
Implement a function to divide two integers without using the divide operator.
Design a system to efficiently calculate the top 1MM Google search queries and create a report of these. Additionally:
Given an array A[N] containing N numbers. Crate an array Output[N] where Output[i] is equal to the product of all the elements of A[N] except A[i].
For example Output[0] is the product of A[1] to A[N-1] and Output[1] is the product of A[0] and from A[2] to A[N-1].
Do this without using the division operator. Do it in O(n).
You are given a linked list of integers of length N.
N is very large and you don’t know N.
Write a function to return k completely random numbers from the list.
Do this in O(n).
Hint: Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2.
Write a function to efficiently determine the result of a game of Tic Tac Toe.
The function takes as input the game and the sign (x or o) of the player. The function returns if this player has won the game or not.
Carefully consider both the data structure and the algorithm for your answer.
Efficiently calculate the shortest distance between two Facebook users given an API endpoint that returns all friends of a given user.
Given any integer, efficiently find the next highest integer that uses the same digits.
For example if the number is 15432, you should return 21345.
Write a function to efficiently determine if a linked list has a cycle in it.
Given two arrays of strings, A and B.
B contains every element in A, and has one additional member, for example:
* A = ['dog', 'cat', 'monkey]
* B = ['cat', 'rat', 'dog', 'monkey']
Write a function to find the extra string in B. Do this in O(n)
Express the following table as a static structure, and write a function, find_routes(source, destination) that efficiently outputs all possible routes.
Source | Dest
~~~~~~ ~~~~
Seattle | LA
LA | Florida
LA | Maine
Florida | Seattle
Seattle | Florida
The solution for find_routes('Seattle', 'Florida') should be [Seattle -> Florida, Seattle -> LA -> Florida]
Write a function to efficiently convert a floating point number to a rational number. For example, given 0.125 return "1/8"
Write a function that takes an unsorted integer array, and returns a three element subset whose sum is zero.
Note: This is a special case of the SUBSET-SUM problem. That problem is NP-complete, but we're only looking for subsets of 3 elements. This can be achieved in polynomial time.
Write a function that takes as input a string, and outputs that same string, with any parentheses in it balanced. Do this using the minimum number of edits.
Given a file of size 1TB, containing only 32 bit integers, describe how you would efficiently sort it. You have only 2GB of memory available.
Describe the Strategy design pattern and how you might use it in practice.
Implement it.