If you have an interview coming up at a company like Google or Amazon (and many others ...) that you know will ask technical questions, then you have come to a good place to prepare yourself! Listed in this README are a bunch of technical computer science questions that will ALL be answered inside separate packages/class-files. Each solution also may include an associated demo file which will contain a main class and demo that solution, it is advised to play around with these and learn about all the corner cases!
- Data Structures
- Implement this data structure
- Implement this method for a data structure
- Sorts and Searches
- Implement this sort
- Implement this search
- Interview Problems
- Solve this problem
It is not organized like this for no reason! It is recommended to have a good understanding of different data structures and sorts and searches before moving on to general interview problems. These will be your tools to help understand and solve different interview problems. Doing all the sorts is optional, but it is recommended that you have a good understanding of at minimum one O(nlogn) sort.
This README was designed to be simple and fast to browse using only control-f. If you quickly want to jump to somewhere in the readme, simply search (using control-f) for it in square brackets. Make sure your search is not case sensitive!
Quick Search Options:
- data-structures: [name-of-data-structure]
- sorts: [name-of-sort]
- interview problems: [P#]
- section: [name-of-section-header]
If you find any mistakes in my code, and there will be mistakes, try and fix them as an exercise! Once you think you have a working implementation, shoot me a pull request, I always appreciate friendly help :) If you have any ideas for things you wanna add, feel free to code it up and shoot me a pull request, just please keep your code clean - clean code or no code at all. Again I always appreciate help and thanks in advance :)
- Implement a Queue of ints using a circular array. Deal with under/overflow using exceptions appropriately. This Queue must have the following methods:
publicQueue(intmaxSize)
publicvoidenqueue(intdata)
publicintdequeue()
publicintpeek()
publicbooleanisFull()
publicbooleanisEmpty()
publicStringtoString()- Implement a Queue using two stacks, make use of generics. This StackQueue must have the following methods:
publicStackQueue()
publicStackQueue(Type[] list)
publicvoidenqueue(Typeobj)
publicTypedequeue()
publicbooleanisEmpty()- Implement a LinkedList that can store any type using generics. To make this class, it helps to have a class for Node that also uses generics to store any type. This LinkedList must have the following methods:
publicLinkedList()
publicNode<Type> find(Typedata)
publicintgetLength()
publicvoidaddDataAtHead(Typedata)
publicvoidaddNodeAtHead(Node<Type> nextNode)
publicNode<Type> deleteHead() throws ...
publicStringtoString()Do the exact same as question 2, but use a DoubleLinkedList. You will need a new Node class
Reverse a SinglyLinkedList, the method header should look like:
publicvoidreverse() // put this method inside your LinkedList class- Check if a SinglyLinkedList is cyclic, the method header should look like:
publicbooleancyclic() // put this method inside your LinkedList class- Implement a Stack that can store any type using generics. For the underlying data type, use an ArrayList. What are the speeds of each of these methods in big-O notation if implemented correctly? It must have the following methods:
publicStack()
publicTypepop()
publicvoidpush(Typedata)
publicTypepeek()
publicStringtoString()- Implement a Heap that stores integers. Implement the heap in any way you think is best, but make sure it is fast! What are the speeds of each of these methods in big-O notation if implemented correctly? It must have the following methods:
publicHeap(intinitialSize)
publicHeap(int[] initialValues)
publicvoidadd(intinteger) publicbooleandelete(intinteger) publicintpeek()
publicintpop()
publicbooleancontains(intinteger)
publicbooleanisEmpty()
publicintsize()- Implement a Priority Queue that stores integers. It must have the following methods:
publicPriorityQueue(intinitialSize)
publicPriorityQueue(int [] list)
publicvoidenqueue(intdata)
publicintdequeue()
publicintpeek()
publicbooleanisEmpty()- Implement a BST that stores Integers. To make this BST, it will be useful to have a TreeNode as well. For the traversal methods, simply print out the node data values as you traverse them. This BST must have the following methods:
publicBinarySearchTree(Integerdata)
publicBinarySearchTree()
publicTreeNodefind(IntegersearchKey)
publicvoidinsert(TreeNodeinsertNode)
publicbooleandelete(IntegersearchKey) // return true if object deleted, false if object not in listpublicvoidinOrderTraversal()
publicvoidpreOrderTraversal()
publicvoidpostOrderTraversal()
publicTreeNodesmallest()
publicTreeNodebiggest()For all sorts, analyze the speed using Big-O notation. Program all sorts as static methods in individual classes that each have a main method that tests out the sort
- Implement [Bubble sort], the method header should look like:
privatestaticvoidbubbleSort(int[] list)- Implement [Selection sort], the method header should look like:
privatestaticvoidselectionSort(int[] list)- Implement [Insertion sort], the method header should look like:
privatestaticvoidinsertionSort(int[] list)- Implement [Merge sort], the method header should look like:
privatestaticvoidmergeSort(int[] list) - Implement [Quick Sort], the method header should look like:
privatestaticvoidquickSort(int[] list)- Implement [Shell Sort], the method header should look like:
privatestaticvoidshellSort(int[] list)- Implement [Counting Sort], the method header should look like:
privatestaticvoidcountingSort(int[] list , intstartRange , intendRange)- Implement [Radix Sort], the method header should look like:
privatestaticvoidradixSort(int[] list)- Implement [Bucket Sort], the method header should look like:
privatestaticvoidbucketSort(int[] list)- Implement [Heap Sort] (this is a great place to test your own heap), the method header should look like:
privatestaticvoidheapSort(int[] list)- Implement a [binary search] that takes in a sorted array, the method header should look like:
privatestaticintbinarySearchArray(int [] list, intsearchKey)[P1] Implement factorial recursively. Implement it again, but this time use tail recursion. What is tail recursion? Is Java optimized for tail recursion?
[P2] Solve the famous Towers of Hanoi problem. Is it tail recursive? Why or why not?
[P3] Assuming I give you an array of numbers, lets say they represent stock prices, find me the most money you could make that day by buying and selling a single stock. If the stocks go down all day, you should find me the least amount of money I could lose that day. The method header should look like:
privatestaticintbestStockTrade(int[] stockPrices) throws ...[P4] Given an array of integers, eg [1 , 2 , 3, 4], return an array where at each index you get the result of multiplying by all the other values. Eg. [1 , 2 , 3 , 4] --> [2x3x4 , 1x3x4, 1x2x4 , 1x2x3]. Do NOT use division. The method header should look like:
privatestaticint[] productAllButMe(int[] data) throws ...[P5] Given an array of integers, what is the maximum product you could get from multiplying any 3 of the integers. The method header should look like:
privatestaticintproductOfThree(int[] data) throws ...[P6] Given an array of pairs of integers, write a function that goes through and see which parts of the timeline are covered. Eg. Given the array of [(1,4) , (2,7) , (9,11) , (1,3) , (12,14)] --> [(1,7) , (9,14)]. You could imagine this being useful if we had a list of everyones schedule and we wanted to see when everyone was free. For the actual representation of the input, use the following class:
classSchedule {
publicintstartTime;
publicintendTime;
publicSchedule(intstartTime , intendTime) {
this.startTime = startTime;
this.endTime = endTime;
}
@OverridepublicStringtoString() {
return"(" + startTime + " , " + endTime + ")";
}
}For the method header:
privatestaticList<Schedule> scheduler(List<Schedule> schedules)[P7] Given an array of People, where a person is represented by a startTime and finishTime for their work shift, return the shortest list possible of people where those people see all other people during their shifts. For example, if given these people (1 , 2) , (2 , 10) , (5 , 6) then you should return (2 , 10) because this person sees everyone else during his shift. If given (1 , 5) , (4 , 10) , (2 , 3) , (11 , 13) --> (1 , 5) , (11 , 13). For the actual representation of person, use the following class:
classPerson {
publicintstartTime;
publicintfinishTime;
publicPerson(intstartTime , intfinishTime) {
this.startTime = startTime;
this.finishTime = finishTime;
}
@OverridepublicStringtoString() {
return"(" + startTime + " , " + finishTime + ")";
}
}For the method header:
privatestaticList<Person> selectPeople(List<Person> people) throws ...[P8] Given an array of integers, where there is guaranteed to be one number that is not duplicated, find that number. Note that in this list of coupled numbers, only 1 number has no duplicate, and every other number has one and only one duplicate. Possible inputs: [1 , 2 , 2 , 3 , 3 , 4 , 4] , [2] , [3 , 7 , 3] etc...
For the method header:
privatestaticintuncoupledInteger(int[] list) Extra Points: Can you do it in constant memory and linear time?
[P9] Given a string that is full of delimiters, check whether the string had balanced delimiters. The only delimiters we will worry about in this problem are the following: [ ] { } ( ). There are no other characters in this string except for the delimiters. The following strings are balanced and should return true: "" , "()" , "{}()[]" , "([{}])". The following strings are not balanced and should return false: "[" , "{}}" , "{{]}" , "{[}]"
For the method header:
privatestaticbooleanbalancedDelimiters(Stringdelimiters) [P10] Given an array of integers and a target sum, make a function that returns true if the target sum is a sum of two of the integers in the array. For example, given the array [1 , 2 , 3 , 4, -100 , 0 , 0] and target 5 it should return true because 4 + 1 = 5. Note that if the same array was given, but the target was 8, the answer would return false. You cannot add an integer to itself to produce the target, you must find two separate integers. Note that these two separate integers could have the same value, eg. if the same array was given but 0 was given as the target, it should return true because there are two integers in the array that sum to 0 - the 0 in the 5th index and the 0 in the 6th index.
For the method header:
privatestaticbooleantargetSummable(int[] array , inttarget)