Card Set Information

2014-02-07 00:54:04
linked list algorithms
Interview questions
Show Answers:

  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 If dupe is found, set =
  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. 

    IF in forward order, we must add padding, and then add numbers to head instead of tail
  15. Find the node at the beginning of a circular linked list.
  16. Describe Mergesort
    MergeSort divides an array up by two Log(N) times. Each of the N/2 arrays are then "merged" by looping through the first array element by element, and comparing with the other array element by element. this keeps occuring until eventually, you have the sorted array. Thus, it is N Log(N).
  17. Implement a function to test if linked list is a palindrone
    iterate through the loop with a fast and slow runner. fast runner moves 2x as fast. As slow runner moves, add items to stack. Once fast runner is at end, slow is at halfway.Then go through rest and compare to stack.
  18. Describe how you can use a single array to implement three stacks
    Either have three stacks of fixed size, or have moving stacks size. Moving stack size means elements have to be shifted which is more expensive.