Given a singly linked list: 1->2->3->4->5, Change it to 1->5->2->4->3 using O(1) space
1. Find the mid point of the list
2. Reverse the list
3. Merge the list
Complete working solution can be found in the linked lists page, LinkedList::RearrangeLL() method. linked lists page
Given a string in the form of a Linked List, check whether the string is palindrome or not.
1. Find the length of the total string
2. Get the node that has the mid (middle) position
3. Break the List at that node
4. Reverse the first half
5. Now do string compare
Complete working solution can be found here
Reverse a linked list in place with O(n) time complexity and O(1) space complexity
Hint: Start from the head, store the prev node, move one pointer further, and make it point to prev. Complete solution can be found in the method Reverse() in the page
Given an array of words (i.e. [“apple”, “paris”, “boar”, “cat”, “tree”, “mango”]), find the max value of length(s) * length(t), where s and t are words from the array. The catch here is that the two words cannot share any characters. Assume that there are many words in the array (N words) and average length of word is M. Answer for the example above is “tree” and “mango” and the result is 4 * 5 = 20.
Hint: Hash each word, compare the hashes and get the max. You can find the solution here
Question: Find the maximum contiguous subarray in a given one dimensional array.
Largest Sum Contiguous Subarray
Question: Sort a linked list in ascending order using merge sort
Answer: Dive and Conquer technique can be used to achieve this.
Get the count of the list. Break the list into two equal parts, sort each individual list them merge.
Time complexity: Avg: O(NlogN) Worst: O(N^2)
Space complexity: No extra space required
Solution can be found here
Question: Perform a level order traversal of a binary tree. Convert the tree into doubly linked list (order of the elements should be level ordered). No extra space used and it is fine to destroy the tree.
Hint: Use a Queue, insert the children of each child into the queue. Remove the element from the queue and keep doing this until queue is empty.
Solution: Insert root’s lchild and rchild and make root’s lchild to nullptr and rchild to to the lchild. Keep doing this until queue is empty.
The implementation for this is in the page Binary tree in the method TreeToDoublyLinkedList
Implement queue using singly linked list and explain the advantages of using doubly linked list instead of singly linked list.
Question:Given a linked list which has a next pointer pointing to the next element in the list and a random pointer pointing to the random element in the list. Implement a method to deep copy this linked list such that the random pointer still copies to the same node in the new list.
1. Create a copy of each node and insert the element next to the original node, iterate through the list.
2. Now the new list has 2N elements (assuming original one has N elements). Then assign the random pointer’s next node to the copied node’s random pointer. Iterate through the list.
3. Now break the list in two lists, original and new.
This logic is implemented in the method DeepCopy in the page.
Question: Find if given linked list has a loop or not. If a list has a loop, then you will never stop traversing the list and visit the same set of elements again and again. For example,
1->2->3->4->5 in the list, 5 should point to NULL. However if 5 points to 3 then it has a loop 3->4->5->3->4->5->3….
Answer: Take two pointers temp1 and temp2. Advance temp1 by one element at a time and temp2 by two elements at a time and keep doing this until temp1 / temp2 is null or temp1 and temp2 pointing to the same element. If it is later case then there is a loop, otherwise there is no loop/
The code for this is defined in the method DetectLoop in the page.