problem solving programming interview questions

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

You may hate code challenges and coding interviews but reality is a lot of companies from Google to Amazon do care that you understand the difference between O(n log n) and O(n²) , that you do understand when different data structures are appropriate, and that you can leverage these (very basic) skills to solve simple problems. Follow along and check 40 most common Coding Challenges and Questions that solved with code on Java, C#, Python and JS to crack and close your next coding interview.

Q1 :   Convert a Single Linked List to a Double Linked List

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:

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

Q2 :   Convert a Singly Linked List to Circular Linked List

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

Q3 :   Detect if a List is Cyclic using Hash Table

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.

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.

Space: O(n)

• Time complexity : O ( n ) . We visit each of the n elements in the list at most once. Adding a node to the hash table costs only O ( 1 ) time.
• Space complexity: O ( n ) . The space depends on the number of elements added to the hash table, which contains at most n elements.

Q4 :   Implement Stack using Two Queues (with efficient push )

Given two queues with their standard operations ( enqueue , dequeue , isempty , size ), implement a stack with its standard operations ( pop , push , isempty , size ). The stack should be efficient when pushing an item.

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

Space: O(1)

If queue is implemented as linked list the enqueue operation has O(1) time complexity.

Q5 :   Implement a Queue using two Stacks

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

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

• Push the new element onto inbox
• 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

In the worst case scenario when outbox stack is empty, the algorithm pops n elements from inbox stack and pushes n elements to outbox, where n is the queue size. This gives 2*n operations, which is O(n) . But when outbox stack is not empty the algorithm has O(1) time complexity that gives amortised O(1) .

Q6 :   Insert item into the Heap. Explain your actions.

Suppose I have a Heap Like the following:

Now, I want to insert another item 55 into this Heap. How to do this?

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:

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

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

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

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

Q7 :   Return the N-th value of the Fibonacci sequence Recursively

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.

Time: O(2^n)

In case of recursion the solution take exponential time, that can be explained by the fact that the size of the tree exponentially grows when n increases. So for every additional element in the Fibonacci sequence we get an increase in function calls. Big O in this case is equal to O ( 2 n ) . Exponential Time complexity denotes an algorithm whose growth doubles with each addition to the input data set.

Q8 :   Return the N-th value of the Fibonacci sequence. Solve in O(n) time

The easiest solution that comes to mind here is iteration:

And output:

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.

An algorithm in our iterative solution takes linear time to complete the task. Basically we iterate through the loop n-2 times, so Big O (notation used to describe our worst case scenario) would be simply equal to O (n) in this case. The space complexity is O(n) .

Q9 :   Reverse a String using Stack

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

• String to char[] .
• Create a Stack .
• Push all characters, one by one.
• Then Pop all characters, one by one and put into the char[] .
• Finally, convert to the String .

Q10 :   What is complexity of push and pop for a Stack implemented using a LinkedList?

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:

Q11 :   What would the number 22 look like as a Byte?

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

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

Q12 :   Check if parentheses are balanced using Stack

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:

• Declare a character stack which will hold an array of all the opening parenthesis.
• Now traverse the expression string exp.
• If the current character is a starting bracket ( ( or { or [ ) then push it to stack.
• 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.
• After complete traversal, if there is some starting bracket left in stack then “not balanced”
• We are traversing through each character of string, Time complexity O ( n ) .
• We are storing the opposite parentheses characters in the stack, in the worst case there can be all the opposite characters in the string, Space complexity O ( n ) .

Q13 :   Explain how Heap Sort works

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:

Time: O(n log n)

• Best : O ( n log n )
• Average : O ( n log n )
• Worst : O ( n log n )

Q14 :   Find all the Permutations of a String

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:

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.

Time: O(n!)

Space: O(n!)

For any given string of length n there are n! possible permutations, and we need to print all of them so Time complexity is O(n * n!) . The function will be called recursively and will be stored in call stack for all n! permutations, so Space complexity is O(n!) .

Q15 :   Floyd's Cycle Detect Algorithm: Explain how to find a starting node of a Cycle in a Linked List?

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")

Q16 :   Floyd's Cycle Detect Algorithm: How to detect a Cycle (or Loop) in a Linked List?

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 .

We only use two nodes (slow and fast) so the space complexity is O ( 1 ) .

Q17 :   Floyd's Cycle Detect Algorithm: Remove Cycle (Loop) from a Linked List

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:

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.

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 .

Q18 :   Get the N-th Fibonacci number with O(n) time and O(1) space complexity

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 .

Q19 :   How to check if String is a Palindrome?

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 .

The time complexity is O(n/2) that is still O ( n ) . We doing n comparisons, where n = s.length() . Each comparison takes O ( 1 ) time, as it is a single character comparison. You can cut the complexity of the function in half by stopping at i == (s.length() / 2)+1 . It is not relevant in Big O terms, but it is still a pretty decent gain. Loop approach has constant space complexity O ( 1 ) as we not allocating any new memory. Reverse string approach needs O ( n ) additional memory to create a reversed copy of a string. Recursion approach has O ( n ) space complexity due call stack.

Recursion :

You may want to solve the problem by inverting the original string in a whole but note the space complexity will be worst than for the loop solution ( O(n) instead of O(1) ):

Q20 :   How to check if two Strings (words) are Anagrams ?

Explain what is space complexity of that solution?

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:

• 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) .
• 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.

The major space cost in your code is the hashmap which may contain a frequency counter for each lower case letter from a to z . So in this case, the space complexity is supposed to be constant O(26) .

To make it more general, the space complexity of this problem is related to the size of alphabet for your input string. If the input string only contains ASCII characters, then for the worst case you will have O(256) as your space cost. If the alphabet grows to the UNICODE set, then the space complexity will be much worse in the worst scenario.

So in general its O(size of alphabet) .

Q21 :   How to find Nth element from the end of a singly Linked List?

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.

The lockstep approach moves all array elements in every step, resulting in a O(n + x 2 ) running time, whereas circular buffer approach uses a circular array and runs in O(n) . The circular buffer solution requires an additional x in memory.

Circular buffer approach:

Q22 :   How to merge two sorted Arrays into a Sorted Array ?

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.

Space: None

This problem will have O(n) complexity at best.

Q23 :   Implement Double Linked List from Stack with min complexity

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

now you can move 4 to 5:

and 3 to 4:

and you can go backwards.

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

once current stack runs out

simply switch to the second pair of stacks!

Q24 :   Merge two sorted singly Linked Lists without creating new nodes

You have two singly linked lists that are already sorted, you have to merge them and return a the head of the new list without creating any new extra nodes. The returned list should be sorted as well.

The method signature is:

Node class is below:

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

Here C will be the output list.

There are two solutions possible:

• Of the two nodes passed, keep the node with smaller value
• Point the smaller node's next to the next smaller value of remaining of the two linked lists
• Return the current node (which was smaller of the two nodes passed to the method)
• Treat one of the sorted linked lists as list, and treat the other sorted list as `bag of nodes'.
• Then we lookup for correct place for given node (from bag of nodes) in the list.

The run time complexity for the recursive and iterative solution here or the variant is O ( n ) .

Recursive solution:

Recursion should not be needed to avoid allocating a new node:

Q25 :   Remove Invalid Parentheses

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!

Q26 :   Sort a Stack using Recursion

Note we can't use another stack or queue.

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.

Time: O(n^2)

Q27 :   Sort a Stack using another Stack

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:

• Create a temporary stack say aux_stack .
• Repeat until the input_stack is not empty
• Pop an element from input_stack call it temp_value.
• 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
• Push temp_value to the aux_stack
• return the aux_stack .

Q28 :   Write a program for Recursive Binary Search

• 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.

Q29 :   Explain Knuth-Morris-Pratt (KMP) Algorithm in Plain English

The KMP algorithm is an efficient string matching algorithm due to Donald Knuth, Vaughan Pratt, and James H. Morris.

For the string matching problem (find p in S ) the naive approach would be to slide a window of size p all over S and check if it matches. That works but actually is inefficient. It takes O(p*S) time.

Instead of naive approach KMP is a linear time ( O ( n ) ) algorithm that exploits the observation that every time a match (or a mismatch) happens, the pattern itself contains enough information to dictate where the new examination should begin from. Every time the naive function fails (or succeeds), it starts matching over from the next character. This might not be necessary. We could use our knowledge of the point of last matching and the "structure" of the test string to know where the next matching should begin from.

How To Understand Prefix Function and Partial Match Table?

The "structure" of the string is encapsulated in the Prefix (or Failure) Function that we use to create Partial Match Table . Now, in order to talk about the meaning, we need to know about proper prefixes and proper suffixes.

• Proper prefix : All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”.
• Proper suffix : All the characters in a string, with one or more cut off the beginning. “agrid”, “grid”, “rid”, “id”, and “d” are all proper suffixes of “Hagrid”.

Saying that here’s the partial match table for the pattern abababca where each cell value is "The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern" .

Let’s also try it for cell five, which concerns “ababa”. We have four proper prefixes (“a”, “ab”, “aba”, and “abab”) and four proper suffixes (“a”, “ba”, “aba”, and “baba”). Now, we have two matches: “a” and “aba” are both proper prefixes and proper suffixes. Since “aba” is longer than “a”, it wins, and cell five gets value 3.

How To Use Partial Match Table?

We can use the values in the partial match table to skip ahead (rather than redoing unnecessary old comparisons) when we find partial matches. The formula works like this:

If a partial match of length partial_match_length is found and table[partial_match_length] > 1 , we may skip ahead partial_match_length - table[partial_match_length - 1] characters.*

Let’s say we’re matching the pattern “abababca” against the text “bacbababaabcbab”. Here’s our partial match table again for easy reference:

The first time we get a partial match is here:

This is a partial_match_length of 1. The value at table[partial_match_length - 1] (or table[0] ) is 0, so we don’t get to skip ahead any. The next partial match we get is here:

This is a partial_match_length of 5. The value at table[partial_match_length - 1] (or table[4] ) is 3. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 5 - table[4] or 5 - 3 or 2 ) characters:

This is a partial_match_length of 3. The value at table[partial_match_length - 1] (or table[2] ) is 1. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 3 - table[2] or 3 - 1 or 2 ) characters:

At this point, our pattern is longer than the remaining characters in the text, so we know there’s no match.

Things to remember:

• Once table is built, this algorithm has complexity O(n) even for binary alphabet (compare with O(m*n) for brute force).
• Table is built very quickly at start since pattern is usually very small.
• Table-building part is O(m) . Search part is O(n) . Total complexity O(m+n) even on binary alphabet.
• Compare with O(m*n) for brute force on binary alphabet.
• Because the prefix-function already tells us what needs to be done about the already matched parts, we do not need to check those parts again and hence, only one pass over the string is sufficient. So, the time complexity of the matching is O ( n ) .
• What about the pre-computation? It turns out that, if correctly implemented, it can be done in O(m) time where m is a length of a pattern.
• Overall, it takes O(m+ n) time. But since m≤ n , the time is bounded by O(n) . This is certainly better than the usual O ( n 2 )
• We only require as much space as the pattern. So, the space requirement is O(m) .

Q30 :   Find Merge (Intersection) Point of Two Linked Lists

Say, there are two lists of different lengths, merging at a point ; how do we know where the merging point is?

Conditions:

• We don't know the length

This arguably violates the "parse each list only once" condition, but implement the tortoise and hare algorithm (used to find the merge point and cycle length of a cyclic list) so you start at List 1, and when you reach the NULL at the end you pretend it's a pointer to the beginning of List 2, thus creating the appearance of a cyclic list. The algorithm will then tell you exactly how far down List 1 the merge is.

Algorithm steps:

• it goes forward every time till the end, and then
• jumps to the beginning of the opposite list, and so on.
• Create two of these, pointing to two heads.
• Advance each of the pointers by 1 every time, until they meet in intersection point ( IP ). This will happen after either one or two passes.

To understand it count the number of nodes traveled from head1-> tail1 -> head2 -> intersection point and head2 -> tail2-> head1 -> intersection point . Both will be equal (Draw diff types of linked lists to verify this). Reason is both pointers have to travel same distances head1-> IP + head2->IP before reaching IP again. So by the time it reaches IP , both pointers will be equal and we have the merging point.

Q31 :   Flip k least significant bits in an integer

The ~ unary operator is bitwise negation. If you need fewer bits than what fits in an int then you'll need to mask it with & after the fact.

To flip the k least significant bits, use the right mask.

or you can create a mask without loop:

Q32 :   Given a singly Linked List, determine if it is a Palindrome

Could you do it in O ( 1 ) time and O ( 1 ) space?

Solution: is Reversed first half == Second half ?

Let's look to an example [1, 1, 2, 1] . In the beginning, set two pointers fast and slow starting at the head.

(1) Move: fast pointer goes to the end, and slow goes to the middle.

(2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.

(3) Compare: run the two pointers head and slow together and compare.

Q33 :   How come that hash values are not reversible?

The input material can be an infinite length, where the output is always 128 bits long (for MD5 hash). This means that an infinite number of input strings will generate the same output.

If you pick a random number and divide it by 2 but only write down the remainder, you'll get either a 0 or 1 - even or odd, respectively. Is it possible to take that 0 or 1 and get the original number?

Q34 :   How implement a Queue using only One (1) Stack?

I know how to do that with 2 stacks but how to implement it with one?

Tricky question.

You can "cheat" by using recursive function calls to pop the stack, then you push the item being queued, then as the recursive calls unwind you push what was popped. But this is really two stacks, because the function call stack counter is a stack .

Following is the implementation:

• During Enqueue operation, we can straight away push the element into the stack.

During Dequeue operation,

• Pop all the elements from a Stack recursively until Stack size is equal to 1 .
• If Stack size = 1 , Pop item from Stack , and return the same item.
• Push all popped element back to Stack .

Q35 :   How to implement 3 Stacks with one Array ?

Find an algorithm/write pseudocode with high performance for a stack with only two operations, pop() and push() .

Space (not time) efficient. You could:

• Define two stacks beginning at the array endpoints and growing in opposite directions.
• Define the third stack as starting in the middle and growing in any direction you want.
• Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.

You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.

Above you may see an example. The shifting is done with an equal space partitioning policy, although other strategies could be chosen depending upon your problem heuristics.

the middle stack could be implemented using an alternating sequence for subsequent pushes. The resulting stack structure will be something like:

In this case, you'll need to store the number n of elements on the middle stack and use the function:

to know the next array element to use for this stack.

Although probably this will lead to less shifting, the implementation is not homogeneous for the three stacks, and inhomogeneity (you know) leads to special cases, more bugs and difficulties to maintain code.

Q36 :   How to recursively reverse a Linked List?

Start from the bottom up by asking and answering tiny questions:

• What is the reverse of null (the empty list)? null .
• What is the reverse of a one element list? the element.
• What is the reverse of an n element list? the reverse of the rest of the list followed by the first element.

How to understand that part?

Think about the origin link list:

Now assume that the last node has been reversed. Just like this:

And this time you are at the node 3 , you want to change 3->4 to 3<-4 , means let 3->next->next = 3 (as 3->next is 4 and 4->next = 3 is to reverse it)

Assume that n is the list's length, the time complexity is O ( n ) . The extra space comes from implicit stack space due to recursion. The recursion could go up to n levels deep then space complexity is O ( n ) .

Q37 :   How to use Memoization for N-th Fibonacci number?

Why? Any problems you may face with that solution?

Yes. It's called Memoization . Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls .

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. Can you see that we calculate the fib(2) results 3(!) times?

Basically, if we just store the value of each index in a hash , we will avoid the computational time of that value for the next N times. This change will increase the space complexity of our new algorithm to O ( n ) but will dramatically decrease the time complexity to 2N which will resolve to linear time since 2 is a constant O ( n ) .

There’s just one problem : With an infinite series, the memo array will have unbounded growth. Eventually, you’re going to run into heap size limits, and that will crash the JS engine. No worries though. With Fibonacci, you’ll run into the maximum exact JavaScript integer size first, which is 9007199254740991 . That’s over 9 quadrillion, which is a big number, but Fibonacci isn’t impressed. Fibonacci grows fast . You’ll burst that barrier after generating only 79 numbers.

Q38 :   Copy a Linked List with Random (Arbitrary) Pointer using O ( 1 ) Space

Every node of the linked list has a random pointer (in addition to the next pointer) which could randomly point to another node or be null. How would you duplicate such a Linked List? Could you do that in O ( 1 ) space complexity?

Let's assume you have

An intuitive solution is to keep a hash table for each node in the list, via which we just need to iterate the list in 2 rounds ( 2N steps) respectively to create nodes and assign the values for their random pointers. As a result, the space complexity of this solution is O(N) , although with a linear time complexity.

• Walk the old list following the next pointers. For each node you visit, add a node to your new list, connect the previous node in your new list to the new node, store the old node random pointer in the new new node, then store a mapping of the old node pointer to the new node pointer in a map .
• Walk the new list, and for each random pointer, look it up in the map to find the associated node in the new list to replace it with.

As an optimised solution, we could reduce the space complexity into constant. The idea is to associate the original node with its copy node in a single linked list. In this way, we don't need extra space to keep track of the new nodes.

The algorithm is composed of the follow three steps which are also 3 iteration rounds.

• Iterate the original list and duplicate each node. The duplicate of each node follows its original immediately.
• Iterate the new list and assign the random pointer for each duplicated node.
• Restore the original list and extract the duplicated nodes.

Or mapped to code below:

Hash table version:

Q39 :   Find all the repeating substrings in a given String (or DNA chromosome sequence)

Suffix Tree is the way to go.

• If you analyze the output for the string "AAAAAAAAAAAAAA" , then there are O ( n 2 ) characters in it, so the algorithm is at least O ( n 2 ) .
• To achieve O ( n 2 ) , just build the suffix tree for each suffix of s (indices 1..n , 2..n , 3..n , ..., n..n ). It doesn't matter if one of the strings has no own end node, just count how often each node is used.
• At the end, iterate over each node with count > 1 and print its path.

There are multiple way to construct the suffix tree:

• Using Ukkonen's algorithm.
• Using Suffix array and LCP (longest common prefix array)

Q40 :   How to check for braces balance in a really large (1T) file in parallel?

There is a large file( 1TB) containing braces. How to check for braces balance? Make this process parallel.

If ( = 1 and ) = -1 . We should check the same two conditions:

• The total sum of the brackets is 0
• We never go negative at any point of time.

The first instinct to solving the parallel problem might be to split the work up into equal-sized chunks for each processor. If there are N characters in the file and K processors, give each processor a chunk of N/K characters. When processing a chunk, we can no longer simply return false when the count drops below 0, because there may be more opening braces in an earlier chunk processed by a different processor. We also can't return false if the counter is not 0 at the end, because it may be that there are more closing braces in later chunks. What we should calculate for each chunk, instead, is:

If we were doing a global brace counter as in the single-threaded approach, by how much would this chunk change the counter? This can be a positive or negative number. Call this the " brace delta ". This number is equal to the number of opening braces minus the number of closing braces in the chunk.

While we are calculating the " brace delta ", what is the lowest point to which the brace delta drops anytime during the processing of the chunk? Call that the " brace delta minimum ". This number is important because this is the point in the chunk where the global counter would be the smallest. We can check whether the global counter would have ever been negative by seeing whether (global counter before chunk) + (brace delta minimum in chunk) < 0 for any chunk.

These two things would be calculated by:

The complexity of the above code is O(N/K) for each of K processors. However, we can consider it O(N/K) time because all the processors can work in parallel.

After we process each chunk in parallel, we combine the results in a single-threaded way. We use the brace deltas to calculate the value of the global counter at the beginning of every chunk, and we use the brace delta min of the chunks to verify that the global counter never drops below 0. The global counter value should be 0 at the end of all the chunks as before.

The non-parallel part takes O(K) time, making the overall time for the solution O(N/K + K) .

Rust has been Stack Overflow’s most loved language for four years in a row and emerged as a compelling language choice for both backend and system developers, offering a unique combination of memory safety, performance, concurrency without Data races...

Clean Architecture provides a clear and modular structure for building software systems, separating business rules from implementation details. It promotes maintainability by allowing for easier updates and changes to specific components without affe...

Azure Service Bus is a crucial component for Azure cloud developers as it provides reliable and scalable messaging capabilities. It enables decoupled communication between different components of a distributed system, promoting flexibility and resili...

FullStack.Cafe is a biggest hand-picked collection of top Full-Stack, Coding, Data Structures & System Design Interview Questions to land 6-figure job offer in no time.

Coded with 🧡 using React in Australia 🇦🇺

by @aershov24 , Full Stack Cafe Pty Ltd 🤙, 2018-2023

Privacy • Terms of Service • Guest Posts • Contacts • MLStack.Cafe

100+ Coding Interview Questions for Programmers and Software Engineers in 2024

Solve these frequently asked coding problems to do well on your next programming job interviews..

Coding Interviews are such an important thing in a programmer’s life that he just can’t get away with that. It’s the first hurdle they need to cross to get the software developer job they wish throughout their school and college days.

To make the matter worse, you will find that so many people on the internet telling that coding interview is flawed, the hiring process for programmers sucks, and so on but you don’t need to pay attention to them, not at least at the start of your career.

They may be right but they are inside the train which you are trying to get into. No matter, how much they criticize the coding interviews and programmers hiring process, many of them have gone through the same route to where they are.

We all know that Coding Interview System is not perfect and many are trying to change it but until it's changed, you got to follow its rules to get into the System. This is something for experience developers to deal with, as a junior developer your priority should be to clear the coding interview and get the job you want.

As an author of a Java blog and a Medium publication , I receive a lot of queries related to coding problems and how to deal with them and that’s why I keep writing articles like this which have helped a lot of programmers directly and in-directly in their career.

In this article, I am going to share with you the top 100 coding interview problems from programming job interviews which every programmer should know.

What to prepare for Coding Interviews?

Now that, I have cleared the confusion that Coding interviews is important and you should not distract, let’s get into real work. The big question is what to prepare for Coding interviews?

Well, the most important thing to prepare is Data Structure-based coding problems like array-based coding problems, string problems, linked list problems, binary tree problems, etc.

Apart from data structure-based questions, most of the programming job interviews also ask algorithm, design, bit manipulation, and general logic-based questions, which I’ll describe in this section.

It’s important that you practice these concepts because sometimes they become tricky to solve in the actual interview. Having practiced them before not only makes you familiar with them but also gives you more confidence in explaining the solution to the interviewer.

One of the main problems with coding problems is that there are hundreds and thousands of coding problems on interviews, there are even sites like LeetCode , HackerRank , Codewars , Topcoder , freeCodeCamp , HackerEarth which train programmers for coding interviews with lots of tough questions, which sometimes just overwhelms a beginner looking for a job.

I believe in simplicity and the 10% of effort which produce 90% of results and that’s why I have collected top 100 coding problems which are not too tough and also frequently asked on real interviews.

Solving these problems not only gives you confidence but also helps you to recognize some of the most common algorithmic patterns which will also help you to solve some unseen problems in real interviews.

Best Resources for Coding Interviews

The selection of good resources is very important for success in your coding interviews. If you chose the wrong resource then more than money, you will lose the valuable time you need for preparation, hence spending some time researching for a good resource.

If you need recommendations, the following are some of my the tried and tested resources to learn Data Structure and Algorithms in-depth for coding interviews:

• Data Structures and Algorithms: Deep Dive Using Java for Java developers. Learn about Arrays, Linked Lists, Trees, Hashtables, Stacks, Queues, Heaps, Sort algorithms, and Search algorithms

Data Structures and Algorithms: Deep Dive Using Java

So you've worked with the basics of data structures and algorithms in java (or another oo programming language) but….

• Algorithms and Data Structures in Python for those who love Python A guide to implementing the most up to date algorithms from scratch: arrays, linked lists, graph algorithms, and sorting

Algorithms and Data Structures in Python

This course is about data structures and algorithms. we are going to implement the problems in python. i highly….

• JavaScript Algorithms and Data Structures Masterclass by Colt_Steele for JavaScript programmers. The Missing Computer Science and Coding Interview Bootcamp. Learn everything you need to ace difficult coding interviews.

JavaScript Algorithms and Data Structures Masterclass

This course crams months of computer science and interview prep material into 20 hours of video. the content is based….

• Mastering Data Structures & Algorithms using C and C++ for those who are good at C/C++
• Data Structures in Java: An Interview Refresher by The Educative Team to refresh important Data Structure and algorithms concepts in Java. This course contains a detailed review of all the common data structures and provides implementation-level details in Java to allow readers to become well equipped.
• Grokking the Coding Interview: Patterns for Coding Questions by Fahim ul Haq and The Educative Team This is like the meta course for coding interviews, which will not teach you how to solve a coding problem but, instead, teach you how to solve a particular type of coding problem using patterns. Master these 15 underlying patterns to interview questions, and you’ll be able to tackle anything you face on the interview

Grokking the Coding Interview: Patterns for Coding Questions

Coding interviews are getting harder every day. a few years back, brushing up on key data structures and going through….

www.educative.io

System Design is another topic which is quite important for coding interviews and when it comes to System design , there are not many places where you can learn System design concepts and architecture in depth, but ByteByteGo is exceptional.

ByteByteGo | Ace Your Next System Design Interview

Everything you need to take your system design skill to the next level.

bytebytego.com

It’s one of those sites where I have learned a lot. They explain many key System design concept like Microservices , load balancing, caching, Algorithms like CAP theorem and how to design a particular system with easily digestible diagram. It’s created by Alex Xu, author of System Design Interview — An insider’s guide , one of the best System Design book , and I highly recommend this to everyone preparing for coding interviews.

System Design Interview - An insider's guide

Buy system design interview - an insider's guide on amazon.com ✓ free shipping on qualified orders.

www.amazon.com

And, if you prefer books, there is no better than the Cracking The Coding Interview , by Gayle Laakmann McDowell which presents 189+ Programming questions and solutions. A good book to prepare for programming job interviews in a short time. Btw, I will also earn some money if you buy any of these resources mentioned here.

5 Best Tips to Crack Coding Interviews in 2023

Here are a few of my practical tips to crack your next coding interview. These are hard-earned and I learned from my own mistakes and experience.

• There is no better way to do well in Coding interviews than practicing as many coding problems as possible. This will not only train your mind to recognize algorithmic patterns in problems but also give you the much-needed confidence to solve problems you have never seen before.
• My second tips are to learn about as many data structure and algorithms as possible. This is an extension of the previous tip but it also involves reading and not just practicing. For example, If you know about the hash table you can also many array and counter-based problems easily. The same is true for trees and graphs.
• Choosing the right data structure is a very important part of software development and coding interview and unless and until you know them, you won’t be able to choose.
• Time yourself — candidates who solve interview problems within the time limit and quickly are more likely to do well in the interview so you should also time yourself.
• Think of edge cases and run your code through them. Some good edge cases might be the empty input, some weird input, or some really large input to test the boundary conditions and limits.
• After solving the problem, try explaining it to a friend or colleague how is also interested in coding problems. This will tell you whether you have really understood the problem or not. If you can explain easily means you understood . Also, the discussion makes your mind work and you could come up with an alternative solution and be able to find some flaws in your existing algorithms.
• Another useful tip to excel in Coding interviews is to appear in the coding interview and lots of them. You will find yourself getting better after every interview and this also helps you to get multiple offers which further allows you to better negotiate and get those extra 30K to 50K which you generally leave on a table if you just have one offer in hand.
• Btw, If you are ready for Coding Interview then you can also take TripleByte’s quiz and go directly to the final round of interviews with top tech companies like Coursera , Adobe Acrobat , Dropbox , Grammarly , Uber , Quora , Evernote , Twitch , and many more. I didn’t know about Triplebyte before, but they are providing a great service to job seekers. A big thanks to them.

Triplebyte: Software Engineer Job Search

Take a quiz. get offers from multiple top tech companies at once..

triplebyte.com

Top 100 Coding Problems from Programming Job interviews

Without wasting any more of your time, here is my list of 100 frequently asked coding problems from programming job interviews. In order to get most of this list, I suggest actually solving the problem.

Do it yourself, no matter whether you are stuck because that’s the only way to learn. After solving a couple of problems you will gain confidence.

I also suggest you look at the solution when you are stuck or after you have solved the problem, this way you learn to compare different solutions and how to approach a problem from a different angle.

• How is a bubble sort algorithm implemented? ( solution )
• How is a merge sort algorithm implemented? ( solution )
• How do you count the occurrence of a given character in a string? ( solution )
• How do you print the first non-repeated character from a string? ( solution )
• How do you convert a given String into int like the atoi() ? ( solution )
• How do you implement a bucket sort algorithm? ( solution )
• How do you implement a counting sort algorithm? ( solution )
• How do you remove duplicates from an array in place? ( solution )
• How do you reverse an array in place in Java? ( solution )
• How are duplicates removed from an array without using any library? ( solution )
• How is a radix sort algorithm implemented? ( solution )
• How do you swap two numbers without using the third variable? ( solution )
• How do you check if two rectangles overlap with each other? ( solution )
• How do you design a vending machine? ( solution )
• How do you find the missing number in a given integer array of 1 to 100? ( solution )
• How do you find the duplicate number on a given integer array? ( solution )
• How do you find duplicate numbers in an array if it contains multiple duplicates? ( solution )
• Difference between a stable and unstable sorting algorithm? ( answer )
• How is an iterative quicksort algorithm implemented? ( solution )
• How do you find the largest and smallest number in an unsorted integer array? ( solution )
• How do you reverse a linked list in place? (solution)
• How to add an element at the middle of the linked list? (solution)
• How do you sort a linked list in Java? ( solution )
• How do you find all pairs of an integer array whose sum is equal to a given number? ( solution )
• How do you implement an insertion sort algorithm? ( solution )
• How are duplicates removed from a given array in Java? ( solution )
• how to remove the duplicate character from String? ( solution )
• How to find the maximum occurring character in a given String? ( solution )
• How is an integer array sorted in place using the quicksort algorithm? ( solution )
• How do you reverse a given string in place? ( solution )
• How do you print duplicate characters from a string? ( solution )
• How do you check if two strings are anagrams of each other? ( solution )
• How do you find all the permutations of a string? ( solution )
• How can a given string be reversed using recursion? ( solution )
• How do you check if a given string is a palindrome? ( solution )
• How do you find the length of the longest substring without repeating characters? (solution)
• Given string str, How do you find the longest palindromic substring in str? (solution)
• How do you check if a string contains only digits? ( solution )
• How to remove Nth Node from the end of a linked list? ( solution )
• How to merge two sorted linked lists? (solution)
• How to convert a sorted list to a binary search tree? ( solution )
• How do you find duplicate characters in a given string? ( solution )
• How do you count the number of vowels and consonants in a given string? ( solution )
• How do you reverse words in a given sentence without using any library method? ( solution )
• How do you check if two strings are a rotation of each other? ( solution )
• How to convert a byte array to String? ( solution )
• How do you remove a given character from String? ( solution )
• How do you find the middle element of a singly linked list in one pass? ( solution )
• How do you check if a given linked list contains a cycle? How do you find the starting node of the cycle? ( solution )
• How do you reverse a linked list? ( solution )
• How do you reverse a singly linked list without recursion? ( solution )
• How are duplicate nodes removed in an unsorted linked list? ( solution )
• How do you find the length of a singly linked list? ( solution )
• How do you find the third node from the end in a singly linked list? ( solution )
• How do you find the sum of two linked lists using Stack? ( solution )
• What is the difference between array and linked list? ( answer )
• How to remove duplicates from a sorted linked list? ( solution )
• How to find the node at which the intersection of two singly linked lists begins. ( solution )
• Given a linked list and a value x , partition it such that all nodes less than x come before nodes greater than or equal to x . ( solution )
• How to check if a given linked list is a palindrome? (solution)
• How to remove all elements from a linked list of integers which matches with given value? (solution)
• How is a binary search tree implemented? ( solution )
• How do you perform preorder traversal in a given binary tree? ( solution )
• How do you traverse a given binary tree in preorder without recursion? ( solution )
• How do you perform an inorder traversal in a given binary tree? ( solution )
• How do you print all nodes of a given binary tree using inorder traversal without recursion? ( solution )
• How do you implement a postorder traversal algorithm? ( solution )
• How do you traverse a binary tree in postorder traversal without recursion? ( solution )
• How are all leaves of a binary search tree printed? ( solution )
• How do you count a number of leaf nodes in a given binary tree? ( solution )
• How do you perform a binary search in a given array? ( solution )
• How to Swap two numbers without using the third variable? ( solution )
• How to check if two rectangles overlap with each other? ( solution )
• How to design a Vending Machine? ( solution )
• How to implement an LRU Cache in your favorite programming language? ( solution )
• How to check if a given number is a Palindrome? ( solution )
• How to check if a given number is an Armstrong number? ( solution )
• How to find all prime factors of a given number? ( solution )
• How to check if a given number is positive or negative in Java? ( solution )
• How to find the largest prime factor of a given integral number? ( solution )
• How to print all prime numbers up to a given number? ( solution )
• How to print Floyd’s triangle? ( solution )
• How to print Pascal’s triangle? ( solution )
• How to calculate the square root of a given number? ( solution )
• How to check if the given number is a prime number? ( solution )
• How to add two numbers without using the plus operator in Java? ( solution )
• How to check if a given number is even/odd without using the Arithmetic operator? ( solution )
• How to print a given Pyramid structure? ( solution )
• How to find the highest repeating world from a given file in Java? ( solution )
• How to reverse a given Integer in Java? ( solution )
• How to convert a decimal number to binary in Java? ( solution )
• How to check if a given year is a leap year in Java? ( solution )
• Can you implement a Binary search Algorithm without recursion? ( solution )
• What is Depth First Search Algorithm for a binary tree? (solution)
• What is the difference between Comparison and Non-Comparison Sorting Algorithms? ( answer )
• How do implement Sieve of Eratosthenes Algorithms for Prime Number? ( solution )

These many questions should be enough but If you need more such coding questions you can take help from books like Cracking The Code Interview , by Gayle Laakmann McDowell which presents 189+ Programming questions and solutions. A good book to prepare for programming job interviews in a short time.

Now You’re Ready for the Coding Interview

These are some of the most common questions outside of data structure and algorithms that help you to do really well in your interview.

I have also shared a lot of these questions on my blog , so if you are really interested, you can always go there and search for them.

These common coding, data structure, and algorithm questions are the ones you need to know to successfully interview any company, big or small, for any level of programming job.

This list provides good topics to prepare and also helps assess your preparation to find out your areas of strength and weakness.

Good knowledge of data structure and algorithms is important for success in coding interviews and that’s where you should focus most of your attention.

Further Learning Data Structures and Algorithms: Deep Dive Using Java 10 Books to Prepare Technical Programming/Coding Job Interviews 10 Algorithm Books Every Programmer Should Read Top 5 Data Structure and Algorithm Books for Java Developers From 0 to 1: Data Structures & Algorithms in Java Data Structure and Algorithms Analysis — Job Interview 20+ String based coding problems from interviews 20+ linked list problems from interviews 20+ basic algorithms based problems from interviews ByteByteGo for System Design and Architecture

And, if you like to watch videos, here are videos where you will data structure and algorithms courses and tutorials:

and here are free DSA tutorials

Closing Notes

Thanks, You made it to the end of the article … Good luck with your programming interview! It’s certainly not going to be easy, but by following these searching and sorting algorithm questions, you are one step closer than others.

By the way, the more questions you solve in practice, the better your preparation will be.

So, if you think 100 coding problems are not enough and you need more, then check out these additional 50 programming questions for telephone interviews and these books and courses for more thorough preparation.

All the best for your coding interview.

Other Articles you may like:

Top 10 Free Data Structure and Algorithms Courses for Beginners — Best of Lot

Algorithms and data structure are two of the most fundamentals and essential topics from computer science, which is…, 10 best books for data structure and algorithms for beginners in java, c/c++, and python, algorithms are language agnostic, and any programmer worth their salt should be able to convert them to code in their…, my favorite free courses to learn data structures and algorithms in depth, by javinpaul data structures and algorithms are some of the most essential topics for programmers, both to get a job….

www.freecodecamp.org

Written by javinpaul

I am Java programmer, blogger, working on Java, J2EE, UNIX, FIX Protocol. I share Java tips on http://javarevisited.blogspot.com and http://java67.com

More from javinpaul and codeburst

Javarevisited

5 JavaScript Concepts Every Developer Should Know

These are 5 features every javascript developer should learn.

How To Create Horizontal Scrolling Containers

As a front end developer, more and more frequently i am given designs that include a horizontal scrolling component. this has become….

Jinja2 Explained in 5 Minutes!

(part 4: back-end web framework: flask).

10 Best Resources to Learn Software Architecture in 2025

My favorite software architecture books, white papers, enginering blogs, and courses for experienced developers and software architects., recommended from medium.

Rajan Sharma

Top DSA Sheets To Crack Any Coding Interview

What is a dsa sheet.

Machine Mindset

How I Master Recursion and Backtracking: 48 Coding Challenges

These 48 coding questions are designed to help you master recursion and backtracking.

General Coding Knowledge

Coding & Development

Stories to Help You Grow as a Software Developer

Predictive Modeling w/ Python

Ashish Pratap Singh

AlgoMaster.io

How I Mastered Data Structures and Algorithms

Getting good at data structures and algorithms (dsa) helped me clear interviews at amazon, google and microsoft..

Surabhi Gupta

Code Like A Girl

Why 500 LeetCode Problems Changed My Life

How i prepared for dsa and secured a role at microsoft.

Alexander Nguyen

Level Up Coding

The resume that got a software engineer a $300,000 job at Google.

1-page. well-formatted..

Love Sharma

ByteByteGo System Design Alliance

System Design Blueprint: The Ultimate Guide

Developing a robust, scalable, and efficient system can be daunting. however, understanding the key concepts and components can make the….

Text to speech

15 Common Problem-Solving Interview Questions

In an interview for a big tech company, I was asked if I’d ever resolved a fight — and the exact way I went about handling it. I felt blindsided, and I stammered my way through an excuse of an answer.

It’s a familiar scenario to fellow technical job seekers — and one that risks leaving a sour taste in our mouths. As candidate experience becomes an increasingly critical component of the hiring process, recruiters need to ensure the problem-solving interview questions they prepare don’t dissuade talent in the first place. 

Interview questions designed to gauge a candidate’s problem-solving skills are more often than not challenging and vague. Assessing a multifaceted skill like problem solving is tricky — a good problem solver owns the full solution and result, researches well, solves creatively and takes action proactively. 

It’s hard to establish an effective way to measure such a skill. But it’s not impossible.

We recommend taking an informed and prepared approach to testing candidates’ problem-solving skills . With that in mind, here’s a list of a few common problem-solving interview questions, the science behind them — and how you can go about administering your own problem-solving questions with the unique challenges of your organization in mind.

Key Takeaways for Effective Problem-Solving Interview Questions

• Problem solving lies at the heart of programming. 
• Testing a candidate’s problem-solving skills goes beyond the IDE. Problem-solving interview questions should test both technical skills and soft skills.
• STAR, SOAR and PREP are methods a candidate can use to answer some non-technical problem-solving interview questions.
• Generic problem-solving interview questions go a long way in gauging a candidate’s fit. But you can go one step further by customizing them according to your company’s service, product, vision, and culture. 

Technical Problem-Solving Interview Question Examples

Evaluating a candidates’ problem-solving skills while using coding challenges might seem intimidating. The secret is that coding challenges test many things at the same time — like the candidate’s knowledge of data structures and algorithms, clean code practices, and proficiency in specific programming languages, to name a few examples.

Problem solving itself might at first seem like it’s taking a back seat. But technical problem solving lies at the heart of programming, and most coding questions are designed to test a candidate’s problem-solving abilities.

Here are a few examples of technical problem-solving questions:

1. Mini-Max Sum  

This well-known challenge, which asks the interviewee to find the maximum and minimum sum among an array of given numbers, is based on a basic but important programming concept called sorting, as well as integer overflow. It tests the candidate’s observational skills, and the answer should elicit a logical, ad-hoc solution.

2. Organizing Containers of Balls  

This problem tests the candidate’s knowledge of a variety of programming concepts, like 2D arrays, sorting and iteration. Organizing colored balls in containers based on various conditions is a common question asked in competitive examinations and job interviews, because it’s an effective way to test multiple facets of a candidate’s problem-solving skills.

3. Build a Palindrome

This is a tough problem to crack, and the candidate’s knowledge of concepts like strings and dynamic programming plays a significant role in solving this challenge. This problem-solving example tests the candidate’s ability to think on their feet as well as their ability to write clean, optimized code.

4. Subarray Division

Based on a technique used for searching pairs in a sorted array ( called the “two pointers” technique ), this problem can be solved in just a few lines and judges the candidate’s ability to optimize (as well as basic mathematical skills).

5. The Grid Search 

This is a problem of moderate difficulty and tests the candidate’s knowledge of strings and searching algorithms, the latter of which is regularly tested in developer interviews across all levels.

Common Non-Technical Problem-Solving Interview Questions 

Testing a candidate’s problem-solving skills goes beyond the IDE . Everyday situations can help illustrate competency, so here are a few questions that focus on past experiences and hypothetical situations to help interviewers gauge problem-solving skills.

1. Given the problem of selecting a new tool to invest in, where and how would you begin this task? 

Key Insight : This question offers insight into the candidate’s research skills. Ideally, they would begin by identifying the problem, interviewing stakeholders, gathering insights from the team, and researching what tools exist to best solve for the team’s challenges and goals. 

2. Have you ever recognized a potential problem and addressed it before it occurred? 

Key Insight: Prevention is often better than cure. The ability to recognize a problem before it occurs takes intuition and an understanding of business needs. 

3. A teammate on a time-sensitive project confesses that he’s made a mistake, and it’s putting your team at risk of missing key deadlines. How would you respond?

Key Insight: Sometimes, all the preparation in the world still won’t stop a mishap. Thinking on your feet and managing stress are skills that this question attempts to unearth. Like any other skill, they can be cultivated through practice.

4. Tell me about a time you used a unique problem-solving approach. 

Key Insight: Creativity can manifest in many ways, including original or novel ways to tackle a problem. Methods like the 10X approach and reverse brainstorming are a couple of unique approaches to problem solving. 

5. Have you ever broken rules for the “greater good?” If yes, can you walk me through the situation?

Key Insight: “Ask for forgiveness, not for permission.” It’s unconventional, but in some situations, it may be the mindset needed to drive a solution to a problem.

6. Tell me about a weakness you overcame at work, and the approach you took. 

Key Insight: According to Compass Partnership , “self-awareness allows us to understand how and why we respond in certain situations, giving us the opportunity to take charge of these responses.” It’s easy to get overwhelmed when faced with a problem. Candidates showing high levels of self-awareness are positioned to handle it well.

7. Have you ever owned up to a mistake at work? Can you tell me about it?

Key Insight: Everybody makes mistakes. But owning up to them can be tough, especially at a workplace. Not only does it take courage, but it also requires honesty and a willingness to improve, all signs of 1) a reliable employee and 2) an effective problem solver.

8. How would you approach working with an upset customer?

Key Insight: With the rise of empathy-driven development and more companies choosing to bridge the gap between users and engineers, today’s tech teams speak directly with customers more frequently than ever before. This question brings to light the candidate’s interpersonal skills in a client-facing environment.

9. Have you ever had to solve a problem on your own, but needed to ask for additional help? How did you go about it? 

Key Insight: Knowing when you need assistance to complete a task or address a situation is an important quality to have while problem solving. This questions helps the interviewer get a sense of the candidate’s ability to navigate those waters. 

10. Let’s say you disagree with your colleague on how to move forward with a project. How would you go about resolving the disagreement?

Key Insight: Conflict resolution is an extremely handy skill for any employee to have; an ideal answer to this question might contain a brief explanation of the conflict or situation, the role played by the candidate and the steps taken by them to arrive at a positive resolution or outcome. 

Strategies for Answering Problem-Solving Questions

If you’re a job seeker, chances are you’ll encounter this style of question in your various interview experiences. While problem-solving interview questions may appear simple, they can be easy to fumble — leaving the interviewer without a clear solution or outcome. 

It’s important to approach such questions in a structured manner. Here are a few tried-and-true methods to employ in your next problem-solving interview.

1. Shine in Interviews With the STAR Method

S ituation, T ask, A ction, and R esult is a great method that can be employed to answer a problem-solving or behavioral interview question. Here’s a breakdown of these steps:

• Situation : A good way to address almost any interview question is to lay out and define the situation and circumstances. 
• Task : Define the problem or goal that needs to be addressed. Coding questions are often multifaceted, so this step is particularly important when answering technical problem-solving questions.
• Action : How did you go about solving the problem? Try to be as specific as possible, and state your plan in steps if you can.
• Result : Wrap it up by stating the outcome achieved. 

2. Rise above difficult questions using the SOAR method

A very similar approach to the STAR method, SOAR stands for S ituation, O bstacle, A ction, and R esults .

• Situation: Explain the state of affairs. It’s important to steer clear of stating any personal opinions in this step; focus on the facts.
• Obstacle: State the challenge or problem you faced.
• Action: Detail carefully how you went about overcoming this obstacle.
• Result: What was the end result? Apart from overcoming the obstacle, did you achieve anything else? What did you learn in the process? 

3. Do It the PREP Way

Traditionally used as a method to make effective presentations, the P oint, R eason, E xample, P oint method can also be used to answer problem-solving interview questions.  

• Point : State the solution in plain terms. 
• Reasons: Follow up the solution by detailing your case — and include any data or insights that support your solution. 
• Example: In addition to objective data and insights, drive your answer home by contextualizing the solution in a real-world example.
• Point : Reiterate the solution to make it come full circle.

How to Customize Problem-Solving Interview Questions 

Generic problem-solving interview questions go a long way in gauging a candidate’s skill level, but recruiters can go one step further by customizing these problem-solving questions according to their company’s service, product, vision, or culture. 

Here are some tips to do so:

• Break down the job’s responsibilities into smaller tasks. Job descriptions may contain ambiguous responsibilities like “manage team projects effectively.” To formulate an effective problem-solving question, envision what this task might look like in a real-world context and develop a question around it.  
• Tailor questions to the role at hand. Apart from making for an effective problem-solving question, it gives the candidate the impression you’re an informed technical recruiter. For example, an engineer will likely have attended many scrums. So, a good question to ask is: “Suppose you notice your scrums are turning unproductive. How would you go about addressing this?” 
• Consider the tools and technologies the candidate will use on the job. For example, if Jira is the primary project management tool, a good problem-solving interview question might be: “Can you tell me about a time you simplified a complex workflow — and the tools you used to do so?”
• If you don’t know where to start, your company’s core values can often provide direction. If one of the core values is “ownership,” for example, consider asking a question like: “Can you walk us through a project you owned from start to finish?” 
• Sometimes, developing custom content can be difficult even with all these tips considered. Our platform has a vast selection of problem-solving examples that are designed to help recruiters ask the right questions to help nail their next technical interview.

Get started with HackerRank

Over 2,500 companies and 40% of developers worldwide use HackerRank to hire tech talent and sharpen their skills.