Stacks: implement 2 stacks in an array.

Describe how you could use a single array to implement three stacks.

Approach 1:
Divide the array in three equal parts and allow the individual stack to grow in that limited space.
note: “[“ means inclusive, while “(“ means exclusive of the end point.
»»for stack 1, we will use [0, n/3)
»»for stack 2, we will use [n/3, 2n/3)
»»for stack 3, we will use [2n/3, n)
This solution is based on the assumption that we do not have any extra information about the usage of space by individual stacks and that we can’t either modify or use any extra space. With these constraints, we are left with no other choice but to divide equally.


Approach 2:
In this approach, any stack can grow as long as there is any free space in the array.
We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.
In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array. So, in that case, we would not be able to use those newly freed spaces.
To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.
In this implementation we would be able to have flexibility in terms of variable space utilization but we would need to increase the space complexity.

Singly Linked List: loop start detection

Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C

Approach:
If we move two pointers, one with speed "v" and another with speed "2v", they will end up meeting if the linked list has a loop. Why? Think about two cars driving on a track—the faster car will always pass the slower one!

The tricky part here is finding the start of the loop. Imagine, as an analogy, two people racing around a track, one running twice as fast as the other. If they start off at the same place, when will they next meet? They will next meet at the start of the next lap.

Now, let’s suppose Fast Runner had a head start of k meters on an n step lap. When will they next meet? They will meet k meters before the start of the next lap. (Why? Fast Runner would have made k + 2(n - k) steps, including its head start, and Slow Runner would have made n - k steps. Both will be k steps before the start of the loop.)


For the slow ptr we have:
n = v * t
for fast ptr we have
k+x = 2*v * t

now if we solve for x we have
(k+x)/2 = n
x = 2*n - k

So if fast pointer has a head start of k meters on an n step lap then both will meet k meters before the start of the next lap.

Now, going back to the problem, when Fast Runner (n2) and Slow Runner (n1) are moving around our circular linked list, n2 will have a head start on the loop when n1 enters. Specifically, it will have a head start of k, where k is the number of nodes before the loop. Since n2 has a head start of k nodes, n1 and n2 will meet k nodes before the start of the loop.

So, we now know the following:
1. Head is k nodes from LoopStart (by definition).
2. MeetingPoint for n1 and n2 is k nodes from LoopStart (as shown above).
Thus, if we move n1 back to Head and keep n2 at MeetingPoint, and move them both at the same pace, they will meet at LoopStart.

Adding 2 Singly linked lists

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5), (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

Approach:
We can implement this recursively by adding node by node, just as we would digit by digit.
1. result.data = (node1 + node2 + any earlier carry) % 10
2. if node1 + node2 > 10, then carry a 1 to the next addition.
3. add the tails of the two nodes, passing along the carry.


Input/Output:
A = 8 -> 7 -> 1 -> 1 -> null
B = 6 -> 3 -> 4 -> null
Adding the above linked lists:
Result: 4 -> 1 -> 6 -> 1 -> null

Singly LinkedList: Delete Node

Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e


Approach:
Lets say the list is a->b->c->d->e
We have point p1 pointing to "c" node.
Get a pointer p2 to point to the next node of p1 ie to node "d" here.
Now copy "d" node data to node pointed by p1 and delete node pointed by p2.
new list is "a->b->d->e";

NOTE: this problem can not be solved if pointer p1 is pointing to the last node of the singly linked list.

Singly Linked List: Nth Node from end

Implement an algorithm to find the nth to last element of a singly linked list.

Approach:
lets assume n = 3;
declare 2 ptrs, prev and current which point to the head of the linked list.
advance current by n (3) positions.
then advance both prev and current pointers one at a time till current becomes null.
At this point prev is the nth node from end of the linked list.

Input/Output:
51 -> 70 -> 74 -> 32 -> 10 -> 90 -> 18 -> 21 -> 30 -> null
3 node from end: 18
7 node from end: 74
9 node from end: 51
10 node from end is null

19 -> 16 -> 15 -> null
3 node from end: 19
7 node from end is null
9 node from end is null
10 node from end is null

Time complexity: O(n) - where n is the size of the singly linked list.

Remove duplicates from singly link list.

Write code to remove duplicates from an unsorted linked list.

Approach:
Create a hashtable.
Iterate through the list and check the node if its already present in the hashtable, if present then delete it from the list.
If not then add it to the hashtable and move ahead in the list.


Input/Output:
Original linked list:
2 -> 3 -> 2 -> 5 -> 2 -> 8 -> 2 -> 3 -> 8 -> null
After deleting duplicate node:
2 -> 3 -> 5 -> 8 -> null

Time complexity: O(n) -> n is the length of the linked list.
Space complexity: O(n) -> size of the hashtable.

Is Rotation

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).



Approach:
Let S1 = "waterbottle";
S2 = "erbott";

concatanate S1 with itself
So we have S3 = S1 + S1 = "waterbottle" + "waterbottle" ;
S3 = "waterbottlewaterbottle";

Now we need to check if the S2 is a substring of S1.

if (s2.isSubstring(s3)) then return true;
else return false;