Coding Problems

Approach

1. Go through all problems in [brackets]
2. Go through top problems on geeksforgeeks and leetcode
   • https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/
   • https://www.geeksforgeeks.org/top-25-interview-questions/
   • https://www.geeksforgeeks.org/must-do-coding-questions-for-companies-like-amazon-microsoft-adobe/
   • https://leetcode.com/problemset/top-interview-questions/
3. For each problem, write the solution out on paper
4. For tricky problems, implement solution in code and test
5. Review common data structures and algorithms
6. Do more problems :)
7. Operating Systems, Networking, Databases, System design
   • https://leetcode.com/problemset/operating-system/
   • https://discuss.leetcode.com/tags/5/system%20design

Resources

• https://www.hackerrank.com/domains/algorithms/warmup
• https://coderbyte.com/challenges
• https://www.hackerrank.com
• https://leetcode.com/
• http://beust.com/algorithms.pdf
• http://www.codewars.com/dashboard
• http://www.geeksforgeeks.org/
• http://www.problee.com
• http://codingbat.com
• http://codepad.org
• http://crazyforcode.com
• http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
• http://www.interviewbit.com
• http://www.hiredintech.com/app/

Sorting

1. Selection Sort - Implement and describe complexity
2. [Sort Array012] - Sort an array that contains only the integers 0, 1, and 2 in linear time. (e.g. [1,0,2,2,1] == [0,1,1,2,2])
3. Insertion Sort - Implement and describe complexity
4. Bubble Sort - Implement and describe complexity
5. Counting Sort - Implement and describe complexity
6. [Bucket Sort] - Implement and describe complexity
7. Merge Sort - Implement and describe complexity
8. Quick Sort - Implement and describe complexity
9. Heap Sort - Implement and describe complexity
10. Shell Sort - Implement and describe complexity

Searching

1. Binary Search - Write method to return True if integer is in array
2. Binary Search w Pivot - An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time. If not found, return -1.
3. Bitonic Array - An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct integer values, determines whether a given integer is in the array. Given 3LogN and 2LogN solutions.
4. Count Paths - Give a 2d array of size nxm with elements 1 and 0, find the number of paths from location [0,0] to [n-1,m-1] where a 1 indicates a open space and 0 indicates a closed space. [1,0,0,1] [1,1,1,0] = 4 paths [0,1,1,0] [0,1,1,1]
5. [Word Ladder] - Given a starting word, ending word and wordset. Find length of shortest transformation path from begin Word to end Word. Note: All words lowercase and alphabetical chars only. All words have same length. Rules: 1. change only 1 char at a time. 2. intermediate word must be in wordset. ex. beginWord = "hit", endWord = "cog" wordSet = ["hot","dot","dog","lot","log"] Example: Length of transformation: 5 (includes starting and ending words) "hit" -> "hot" -> "dot" or "lot" -> "dog" or "log" -> "cog"

Arrays

1. Sum3EqualsZero - Given array of integers, return true if any 3 elements in array sum to zero
2. [MaxContigSumArray] - Given array of integers, return max sum of contiguous elements in array. Write iterative and recursive solutions.
3. MaxSum3Array - Given array of integers, return max sum of 3 element subset
4. SetMatrixToZero - If an element in a M x N matrix is zero, set its entire row and column to zero.
5. FindOnesInMatrix - Given a 2D SORTED matrix, return the row index with the most ones
6. MajorityElement - given a array of integers, print out the element that appears more than n/2 times. Otherwise print not found.
7. [Platforms Train Station] - Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits. We are given two arrays which represent arrival and departure times of trains that stop. Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}, dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}, Output: 3. There are at-most three trains at a time (time between 11:00 to 11:20)
8. Max Incremental Subsequence - Given an array of unsorted integers, return the largest incremental subsequence (i.e. a sub array where elements are sorted in ascending order). Input: {0,1,2,3,4,2}. Output:{2,3,4}.
9. [Intersection Two Arrays] - Given two unsorted integer arrays, return a 3rd array with the intersection (distinct elements that appear in both arrays). Optimize for time and space complexity.
10. Find Peak - Implement a function taht returns a local max in an array in O(log(n)) Example: [1,5,2,3,4] Sol = 5 or 4. An element is a peak because it's neighbors are less than it.
11. [Sets all Equal] - WAF that takes an array of "sets" of String objects, and determines if they are equal. Each "set" in the input array is represented as an array of String objects, in no particular order, and possibly containing duplicates. Nevertheless, when determining whether two of these "sets" are equivalent, you should disregard order and duplicates. For example, the sets represented by these arrays are all equivalent: {"a", "b"}{"b", "a"}{"a", "b", "a"}
12. [Find Celebrity] - Party of n people. Only one person is known to everyone at the party. This "Celebrity" may or may not be in attendence. Celebrity knows no one at the party. Given an array of unique numbers and a function HaveAquaintance(A,B) which returns true if A knows B. Find the celebrity in a minimum number of questions.
13. [Distinct Elements 2 Arrays] - Given 2 arrays, return array of numbers that exist in array 1 but not in array 2. Provide a solution in linear (2n is possible) time.
14. [Largest Connected Group] - Given 2D array of X/-, find the size of the largest connected group of X's x x - - x - - - x - - x
    • • x -
15. [Find Max Difference] - The maximum difference for a pair of elements in some array a is defined as the largest difference between any a[i] and a[j] where i < j and a[i] < a[j]. Return -1 if the array is in decending order or no such number exists. ex. a = {2, 3, 10, 2, 4, 8, 1} Output: 8. (10-2 = 8)

Strings

1. IsAnagram - Return true if two strings are anagrams (each string contains the exact same alpha-numeric characters and the same count)
2. RemoveDuplicates - Given String of alpha-numeric characters, return String of distinct characters
3. ReverseString - Given String, return String with characters in reverse order
4. ReplaceSpaces - Given String, replace all spaces with HTML '%20'
5. IsRotation - Return true if str2 is rotation of str1
6. ReverseStringInplace - Reverses a string inplace
7. [FindFirstUniqueChar] - Return the first non-repeated character in a string. If not found, return null. Assume the string is NOT sorted.
8. ReverseWords - Given a sentence, return the sentence in reverse order. (e.g. "I am a student" == "student a am I")
9. Longest Substring No Dupes - Given a string, please get the length of the longest substring which does not have duplicated characters. Supposing all characters in the string are in the range from ‘a’ to ‘z’. Input: "ababc", Output: 3.
10. CSV Parser - Write Method that takes a string representing a CSV and returns a useful JSON data structure.
11. Expand it! - Given a String in format "a2c2b5" where a character is followed by an integer of number of times repeated, expand the string. ex: "a2c2b5" sol = "aaccbbbbb"

Math

1. PowersOfTwo - Compute 2^2^n in linear time
2. Swap Integers - Swap two integers in an array without using temporary variables
3. [Sum Two Arrays] - Write method to sum 2 arrays and return a new array. Arrays can be of different lengths. e.g. [1,3] + [1,0,0] == [1,1,3]
4. Smallest Number > k - Write method to find the smallest number which is greater than a given number k and has SAME SET OF DIGITS as given number
5. [Find Missing Integer] - Given an array of sorted consecutive integers, return the missing integer (or -1 if no integer is missing). E.g. [3,4,6,7] == 4. Complete solutions in both O(n) and O(log n) time. Follow-up: write a method that handles an unsorted array of integers between 0 and N in O(N) time. e.g. [3,5,7,4] == 6
6. [P99 Website Latency] - Given an unsorted array of floats between 0 and 1, representing website latency times, return the 99th percentile time (the time that is greater than 99% of other times). This is an important metric in software development to identify worst case issues for users. Follow-up: Instead of an array, assume you are receiving an infinite stream of latency times and can't store them all. Create a Class to return the P99 at any given moment (methods void putTime(double time), double getP99()). Follow-up: Update your methods to handle variable percentiles (60th, 85th) and latency ranges (3 - 7 seconds).
7. Multiply - Implement multiplication of two numbers without using * operator

Hash Tables

1. Open Addressing - Write a HashTable class that uses "linear probing" to resolve collisions (methods Get, Put, Remove)
2. [Chaining] - Write a HashTable class that uses LinkedLists to resolve collisions (methods Get, Put, Remove)
3. Dynamic Resizing - Add dynamic resizing to either above implementations

Linked Lists

1. Double Linked List - Implement a Doubly Linked List
2. Remove Duplicates - Remove duplicates from both sorted and unsorted Singly Linked List
3. Delete Node - Delete node in middle of Single Linked List given access to only that node
4. [Is Circular] - Return true if single linked list is circular (corrupted). Go on to find the first node in the loop. Go on to find the size of the