# Algorithms

Home > Preview

The flashcards below were created by user iamtron on FreezingBlue Flashcards.

1. Remove duplicate from Linked List
Use two pointers, current and front. iterate current element by element, move front through remaining elements looking for dupes at front.next. If dupe is found, set front.next = front.next.next.
2. Find the closest X points to origin given N points
Need to use Pythagorean theorem. We know two sides of triangle and can calculate the distance from them. a2+b2 = c2. From this, we put each point in a list with max size X. Compare each point with current in list and you have N*X operations.
3. Find kth to last element in List
Iterate through list with front and back pointers. Back point is k elements behind front. When front reaches end, Back is kth element.
4. What is object oriented programming?
Represents concepts as "objects" which have fields (state) that describe it and procedures (behavior) known as methods. It it a design first approach. It encapsulates objects in the users domain and hides their implementations in doing so. It also keeps code from interfering with other code sequences by altering state through methods and not directly.
5. Write an algorithm to compress strings.
aaabccccaaa -> a2b1c5a3
If the compressed string length > the original length then return the original string
iterate through the string and keep a count of characters. Either use a string buffer and concatenate as you go, or use a character array.
6. Given an isSubstring method and two strings, check if s1 is a rotation of s2
s2 will always be a substring of s1+s1 if it is a rotation.
7. Given an N by N matrix write an algorithm to rotate it by 90 degrees.
Copy entries over in layers. to do so place, first save the top entry and do the following order.

• left - > top
• bottom - > left
• right -> bottom
• top -> right.

When there are no more in a row, just skip it
8. Write an algorithm such that if an element in an m by n matrix is 0, its entire row and column are set to zero
Keep two arrays to track rows and columns which have zeroes (you only mark them once). When done, use these arrays to transform matrix
9. write a method to replace spaces in a string with %20
make one pass to count all spaces, use this to initialize a new array. copy string in reverse to new array, replacing space with %20.
10. implement an algorithm to delete a node in the middle of a linked list, given only access to that node
Copy data from next node, and then delete next. If last node in list, cannot be solved.
11. write an algorithm to partition nodes in a linked list around a value  x such that all nodes less than x come before and all greater than or equal to x.
Create two lists, one less than, one equal to or greater. Then just simple compare and add to each list. At end concatenate.
12. implement an algorithm to determine if a string has all unique characters.
Two pointer approach (n2), map/array approach (n)
13. Determine if two strings are permutations of each other
Count all characters in string and compare or sort both strings and compare
14. you have two numbers repsented by a linked list  where each node contains a single digit. the digits are stored in reverse order such that the ones are at the head.write a function that sums the two numbers and returns the result as a linked list.

Repeat in forward order.
Just simply build list by putting % 10 in current, and carrying over to the next digit.