40 Coding Challenges (SOLVED with CODE) To Kill Your Next Coding Interview

A doubly linked list is simply a linked list where every element has both next and prev mebers, pointing at the elements before and after it, not just the one after it in a single linked list.

so to convert your list to a doubly linked list, just change your node to be:

private class Node
{
    Picture data;
    Node pNext;
    Node pPrev;
};

and when iterating the list, on each new node add a reference to the previous node.

To convert a singly linked list to a circular linked list, we will set the next pointer of the tail node to the head pointer.

• Create a copy of the head pointer, let's say temp.
• Using a loop, traverse linked list till tail node (last node) using temp pointer.
• Now set the next pointer of the tail node to head node. temp->next = head

To detect if a list is cyclic, we can check whether a node had been visited before. A natural way is to use a hash table.

Algorithm

We go through each node one by one and record each node's reference (or memory address) in a hash table. If the current node is null, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash table, then return true.

Given we have queue1 and queue2:

push - O(1):

• enqueue in queue1

pop - O(n):

• while size of queue1 is bigger than 1, pipe (dequeue + enqueue) dequeued items from queue1 into queue2
• dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Keep two stacks, let's call them inbox and outbox.

Enqueue:

• Push the new element onto inbox

Dequeue:

• If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
• Pop and return the top element from outbox

A binary heap is defined as a binary tree with two additional constraints:

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.

We start adding child from the most left node and if the parent is lower than the newly added child than we replace them. And like so will go on until the child got the parent having value greater than it.

Your initial tree is:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55

Now adding 55 according to the rule on most left side:

     77
    /  \
   /    \
  50    60
 / \    / \
22 30  44 55
/
55

But you see 22 is lower than 55 so replaced it:

       77
      /  \
     /    \
    50    60
   / \    / \
  55 30  44 55
 /
22 

Now 55 has become the child of 50 which is still lower than 55 so replace them too:

       77
      /  \
     /    \
    55    60
   / \    / \
  50 30  44 55
 /
22

Now it cant be sorted more because 77 is greater than 55.

Recursive solution looks pretty simple (see code).

Let’s look at the diagram that will help you understand what’s going on here with the rest of our code. Function fib is called with argument 5:

Basically our fib function will continue to recursively call itself creating more and more branches of the tree until it hits the base case, from which it will start summing up each branch’s return values bottom up, until it finally sums them all up and returns an integer equal to 5.

The easiest solution that comes to mind here is iteration:

function fib(n){
  let arr = [0, 1];
  for (let i = 2; i < n + 1; i++){
    arr.push(arr[i - 2] + arr[i -1])
  }
 return arr[n]
}

And output:

fib(4)
=> 3

Notice that two first numbers can not really be effectively generated by a for loop, because our loop will involve adding two numbers together, so instead of creating an empty array we assign our arr variable to [0, 1] that we know for a fact will always be there. After that we create a loop that starts iterating from i = 2 and adds numbers to the array until the length of the array is equal to n + 1. Finally, we return the number at n index of array.

The followings are the steps to reversing a String using Stack:

1. String to char[].
2. Create a Stack.
3. Push all characters, one by one.
4. Then Pop all characters, one by one and put into the char[].
5. Finally, convert to the String.

O(1). Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both O(1).

Stack contains 1,2,3:

[1]->[2]->[3]

Push 5:

[5]->[1]->[2]->[3]

Pop:

[1]->[2]->[3] // returning 5

A byte is made up of 8 bits and the highest value of a byte is 255, which would mean every bit is set.

Now:

Lets take it right to left and add up all those values together:

128 0 + 64 0 + 32 0 + 16 1 + 8 0 + 4 1 + 2 1 + 1 0 = 22

One of the most important applications of stacks is to check if the parentheses are balanced in a given expression. The compiler generates an error if the parentheses are not matched.

Here are some of the balanced and unbalanced expressions:

Algorithm

1. Declare a character stack which will hold an array of all the opening parenthesis.
2. Now traverse the expression string exp.
3. If the current character is a starting bracket (( or { or [) then push it to stack.
4. If the current character is a closing bracket () or } or ]) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
5. After complete traversal, if there is some starting bracket left in stack then “not balanced”

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array.

In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i, its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one).

The HeapSort steps are:

• Create a max heap from the unsorted list
• Swap the max element, located at the root, with the last element
• Re-heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place.
• Repeat Steps 2–3 until complete (when the list size is 1)

Visualisation:

Complexity:

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself (or in simple english: permutation is each of several possible ways in which a set or number of things can be ordered or arranged). A string of length n has n! permutation:

ABC // original string (3)
ABC ACB BAC BCA CBA CAB // permutations 3! = 6

To print all permutations of a string use backtracking implemented via recursion:

• Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call.
• The base case is when the input is an empty string the only permutation is the empty string.
• In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

This is Floyd's algorithm for cycle detection. Once you've found a node that's part of a cycle, how does one find the start of the cycle?

• In the first part of Floyd's algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.
• Once tortoise and hare meet, let's put tortoise back to the beginning of the list and keep hare where they met (which is k steps away from the cycle beginning). The hypothesis (see math explanation) is that if we let them move at the same speed (1 step for both), the first time they ever meet again will be the cycle beginning.

Another solution to mention is Hash Map:

• Traverse the nodes list.
• For each node encountered, add it to the identity hash map
• If the node already existed in the identity map then the list has a circular link and the node which was prior to this conflict is known (either check before moving or keep the "last node")

You can make use of Floyd's cycle-finding algorithm, also known as tortoise and hare algorithm.

The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.

• If the linked list has a loop they will definitely meet.
• Else either of the two references(or their next) will become null.

1. Floyd's cycle detect algorithm, also called the tortoise and hare algorithm as it involves using two pointers/references that move at different speeds, is one way of detecting the cycle. If there is a cycle, the two pointers (say slow and fast) will end up pointing to the same element after a finite number of steps. Interestingly, it can be proved that the element at which they meet will be the same distance to the start of the loop (continuing to traverse the list in the same, forward direction) as the start of the loop is to the head of the list. That is, if the linear part of the list has k elements, the two pointers will meet inside the loop of length m at a point m-k from the start of the loop or k elements to the 'end' of the loop (of course, it's a loop so it has no 'end' - it's just the 'start' once again). And that gives us a way to find the start of the loop:

2. Once a cycle has been detected, let fast remain pointing to the element where the loop for the step above terminated but reset slow so that it's pointing back to the head of the list. Now, move each pointer one element at a time. Since fast began inside the loop, it will continue looping. After k steps (equal to the distance of the start of the loop from the head of the list), slow and fast will meet again. This will give you a reference to the start of the loop.

3. It is now easy to set slow (or fast) to point to the element starting the loop and traverse the loop until slow ends up pointing back to the starting element. At this point slow is referencing the 'last' element list and it's next pointer can be set to null.

Consider:

function fibs(n){
  let [a, b] = [0, 1]
  while (n > 0){
    [a, b] = [b, a + b]
    n -= 1
  }
  return a
}

This solution is in linear O(n) time complexity, and constant O(1) space complexity. The number of loops it takes to calculate the nth fib number will still increase at a linear rate as n increases, but we are overriding the previous numbers in the sequence as we build it out, making the space complexity constant for any input n. It's also called Iterative Top-Down Approach.

A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction. You can check if a string is a palindrome by comparing it to the reverse of itself either using simple loop or recursion.

Two words are anagrams of each other if they contain the same number of characters and the same characters. There are two solutions to mention:

1. You should only need to sort the characters in lexicographic order, and determine if all the characters in one string are equal to and in the same order as all of the characters in the other string. If you sort either array, the solution becomes O(n log n).
2. Hashmap approach where key - letter and value - frequency of letter,

• for first string populate the hashmap O(n)
• for second string decrement count and remove element from hashmap O(n)
• if hashmap is empty, the string is anagram otherwise not.

Use lockstep solution. The key to this algorithm is to set two pointers p1 and p2 apart by n-1 nodes initially so we want p2 to point to the (n-1)th node from the start of the list then we move p2 till it reaches the last node of the list. Once p2 reaches end of the list p1 will be pointing to the Nth node from the end of the list.

This lockstep approach will generally give better cache utilization, because a node hit by the front pointer may still be in cache when the rear pointer reaches it. In a language implementation using tracing garbage collection, this approach also avoids unnecessarily keeping the beginning (thus entire) list live for the duration of the operation.

Another solution is to use circular buffer. Keep a circular buffer of size x and add the nodes to it as you traverse the list. When you reach the end of the list, the x'th one from the tail is equal to the next entry in the circular buffer.

Let's look at the merge principle:

Given two separate lists A and B ordered from least to greatest, construct a list C by:

• repeatedly comparing the least value of A to the least value of B,
• removing (or moving a pointer) the lesser value, and appending it onto C.
• when one list is exhausted, append the remaining items in the other list onto C in order.
• The list C is then also a sorted list.

Imagine all items are organized into two stacks, draw them facing each other where face is where you put and peek:

1,2,3,4-><-5,6,7,8

now you can move 4 to 5:

1,2,3-><-4,5,6,7,8

and 3 to 4:

1,2-><-3,4,5,6,7,8

and you can go backwards.

You may also need another two stacks so that you can traverse List via the tail:

1,2,3,4 -> <-5,6,7,8 // first pair of stacks
8,7,6,5 -> <-4,3,2,1 // second pair of stacks kept in reverse order

once current stack runs out

empty-><-1,2,3,4,5,6,7,8 // first pair of stacks is currently being traversed
empty-><-8,7,6,5,4,3,2,1 // second pair of stacks

simply switch to the second pair of stacks!

Here is the algorithm on how to merge two sorted linked lists A and B:

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

Here C will be the output list.

There are two solutions possible:

• Recursive approach is
  1. Of the two nodes passed, keep the node with smaller value
  2. Point the smaller node's next to the next smaller value of remaining of the two linked lists
  3. Return the current node (which was smaller of the two nodes passed to the method)

• Iterative approach is better for all practical purposes as scales as size of lists swells up:
  1. Treat one of the sorted linked lists as list, and treat the other sorted list as `bag of nodes'.
  2. Then we lookup for correct place for given node (from bag of nodes) in the list.

We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter. The counter will increase when it is ( and decrease when it is ). Whenever the counter is negative, we have more ) than ( in the prefix.

To make the prefix valid, we need to remove a ). The problem is: which one? The answer is any one in the prefix. However, if we remove any one, we will generate duplicate results, for example: s = ()), we can remove s[1] or s[2] but the result is the same (). Thus, we restrict ourself to remove the first ) in a series of concecutive )s.

After the removal, the prefix is then valid. We then call the function recursively to solve the rest of the string. However, we need to keep another information: the last removal position. If we do not have this position, we will generate duplicate by removing two ) in two steps only with a different order. For this, we keep tracking the last removal position and only remove ) after that.

Now one may ask. What about (? What if s = (()(() in which we need remove (? The answer is: do the same from right to left. However a cleverer idea is: reverse the string and reuse the code!

The idea of the solution is to hold all values in system stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order.

A stack performs push and pop operations. So, the push and pop operations are carried out between the input_stack and the auxilary_stack in such a way that the auxiliary stack contains the sorted input stack.

Solution Steps:

1. Create a temporary stack say aux_stack.
2. Repeat until the input_stack is not empty
3. Pop an element from input_stack call it temp_value.
4. While aux_stack is not empty and top of the aux_stack < temp_value, pop data from aux_stack and push it to the input_stack
5. Push temp_value to the aux_stack
6. return the aux_stack.

• The first difference is that the while loop from iterative approach is replaced by a recursive call back to the same method with the new values of low and high passed to the next recursive invocation along with Array and key or target element.
• The second difference is that instead of returning false when the while loop exits in the iterative version, in case of the recursive version, the condition of low > high is checked at the beginning of the next level of recursion and acts as the boundary condition for stopping further recursive calls by returning false.
• Also, note that the recursive invocations of binarySearch() return back the search result up the recursive call stack so that true or false return value is passed back up the call stack without any further processing.
• To further optimize the solution, in term of running time, we could consider implement the tail-recursive solution, where the stack trace of the algorithm would not pile up, which leads to a less memory footprint during the running time. To have the tail-recursive solution, the trick is to simply return the result from the next recursive function instead of further processing.