The flashcards below were created by user
on FreezingBlue Flashcards.
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.
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.
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.
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.
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.
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.
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
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
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.
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.
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.
implement an algorithm to determine if a string has all unique characters.
Two pointer approach (n2), map/array approach (n)
Determine if two strings are permutations of each other
Count all characters in string and compare or sort both strings and compare
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
Find the node at the beginning of a circular linked list.
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).
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.
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.