Data Structures
1. Integer
– find number of 1s
– next largest smaller
– smallest larger number
– determine if is palindrom
– itoa, atoi
– add 2 numbers w/o using + or arithmetic operators
– implement *, -, / using only +
– find max of two numbers w/o comparison
– swap two numbers with +/-
– swap two numbers with ^
– given an integer, find the closest number that is palindrome
– implement putlong() by putchar()
2. Bit array
3. Linked list
– find cycle,
– find position of cycle starts
– reverse LL
– delete a node in middle
– each node contains a value pointer pointing to a node,
duplicate LL.
– remove duplicates from sorted/un-sorted LL.
– find n-th to last node to end
– number is represented by LL, add 2 numbers
4. Array
– Longest common substring (LCSubstr)
– Longest common subsequence (LCS).
– Longest increasing subsequence (LIS).
– Longest palingdrome in string.
– array, elements are +/-, find subsequence of max sum
– circular array, elements are +/-, find subsequence of max sum
– find all pairs of integers add up to a sum
– find all pairs of integers add up to a sum,
integers are +/- and sorted
– find one missing number in N numbers in range [0, N]
– find two missing number in N numbers in range [0, N].
– binary search circular array
– Given {a1, a2, a3, ..}, {b1, b2, b3, …},
get {a1, b1, a2, b2, …}
– Given 2 arrays A and B, A large enough to hold both,
merge B into A.
5. String
– KMP, Rabin-Karp, Boyer Moore
– reverse string
– reverse words in string
– strcpy, strcmp, strstr, atoi, itoa, strdup
– remove duplicate characters in O(1) space
– Given dictionary, transform one word to another of same length.
– Given large text, find min cover distance of n words.
