## Coding Interview Questions

1. Given two strings in Java, write a method to decide if one is a permutation of the other.
2. Paindrome Permutation: Given a string, write a function to check if it is the permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to dictionary words.
Example
Input: Tact Coa
Output: True
3. String Compression: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the 'compressed' string does not become smaller than the original string, your method should return the original string. You can assume that the string has only uppercase and lowercase letters in the Roman alphabet.
4. Zero Matrix: Write an algorithm such that if an element in an MxN matrix is zero, its entire row and column are set to 0.
5. Implement a function to check if a linked list is a palindrome.
6. String rotation: Assume you have a method `isSubstring` which checks if one word is a substring of another. Given two string, `s1` and `s2`, write code to check if `s2` is a rotation of `s1` using only one call to `isSubstring`. For example, 'waterbottle' is a rotation of 'erbottlewat'.
7. Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
8. Write a program to swap even and odd bits in an integer with as few instructions as possible. That is, for each even position i, swap the bits in positions i and i+1. Positions are numbered starting with 0.
9. A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte. The screen has width w, where w is divisible by 8. Implement a function that draws a horizontal line from (x1,y) to (x2,y).
10. Given a positive integer x, print the next smallest and the next largest number that have the same number of 1's in their binary representation as x. If such numbers do not exist, indicate accordingly.
11. You have an integer and your goal is to create the longest possible contiguous sequence of 1's in its binary representation by flipping at most one bit from 0 to 1. Output the length of such a sequence.
12. How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? All three functions should run in O(1) time.
13. Design an algorithm and write code to determine the least common ancestor of two nodes in a binary tree. Avoid using additional data structures.
14. You are given a binary tree in which each node contains an integer value (which might be positive or negative). Design an algorithm that counts the number of paths that add to a given a value. The paths need not begin at the root nor end with a leaf. However, the paths must go downwards, from a parent to a child.
15. Given two (singly) linked lists, determine if they intersect. Return the intersecting node if any. Two lists intersect in a node if the k'th node of one list is exactly the same (by reference) as the j'th node of the other.
16. Sorted Merge: You are given two sorted arrays, A and B, where A has a large enough buffer at the end of hold B. Write a method to merge B into A in sorted order.
17. Given an input file with four billion non-negative integers, provide an algorithm to generate an integer that is not contained in the file. Assume that you have 1 GB of memory available for this task.
18. Find Duplicates: You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4 kilobytes of memory available, how would you print all duplicate elements in the array?
19. Sorted Matrix Search: Given an M x N matrix in which each row and column is sorted in ascending order, write a method to find an element.
20. Searching in Rotated Array: Given a sorted array of N elements that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was sorted originally in increasing order.
21. Group Anagrams: Write a method to sort an array of strings so that all anagrams are next to each other
22. Sparse Search: Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.
23. Rank from Stream: Imagine a you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x). Implement the data structures and algorithms to support these operations. That is, implement the method track(int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x in the stream.
24. Given two straight line segments in two-dimensional space (represented by a start point and end point), compute the point of intersection, if any.
25. A child is running up a staircase with n steps and an hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible wasy the child can run up the stairs.
26. Robot in a Grid: Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are 'off limits' such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
27. Magic Index: A magic index is an array A[0...n01] is defined to be an index such that A[i]=i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists in array A.
28. Towers of Hanoi: In the classic problem of Towers of Hanoi, you have three towers and N disks of different sizes, which can slide on to any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (that is, each disk sits on top of even larger one). You have the following constraints.
1. Only one disk can moved at a time
2. A disk is slid off the top of one tower onto another tower.
3. A disk cannot be placed on top of a smaller disk
Write a program to move the disks from the first tower to the last.
29. Paint Fill: Implement the 'paint fill' function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.
30. Factorial Zeros: Write an algorithm which computes the number of trailing zeros in n factorial in decimal number system.
31. English Integer: Given any integer, print an English phrase that describes the integer (for example, 'One thousand two hundred and thirty four' for 1234)
32. Best Line: Given a set of points in the plane, find a line which passes through most points.
33. Bisect Squares: Given two squares in a two-dimensional plane, find a line that would cut these two squares in half. Assume that the sides of the squares are parallel to the axes.
34. Pond Sizes: You have an integer matrix representing a plot of land, where the value at a location represents the height above sea level. A value of zero indicates water. A pond is a region of water connected vertically, horizontally, or diagonally. The size of a pond is the total number of connected water cells. Write a method to compute the sizes of all ponds in the matrix.
35. Sum Swap: Given two arrays of integers, find a pair of values (one value from each array) that you can swap so that the two arrays have the same sum. If such a pair does not exist, output 'Impossible'.
36. Word rectangle: Given a list of millions of words, design an algorithm to create the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). The words need not be chosen consecutively from the list, but all rows must have the same length and all columns must have the same height.
37. Smallest K elements: Design an algorithm to remove the smallest K elements in an array.
38. Max Submatrix: Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.