Coding Interview Club

Prepare for coding interviews in simple and structured steps

Problems

Merge Sort Algorithm

To understand merge sort completely you should be thorough about the concepts of recursion and the concept of divide and conquer. The basic idea is to divide the array into smaller segments recursively until there is only 1 element in each array segment. Then the array segments with single elements are merged in sorted form to form bigger and bigger sorted array segments. Read more about Merge Sort Algorithm

Important Problems on Strings and Arrays

  1. Write an algorithm to reverse a string.
    1. Assumptions
      1. You cannot use any library functions.
      2. You may use charAt (if needed.)
  2. Write an algorithm to find out if a string has all unique characters.
    1. Assumptions
      1. You cannot use additional data structures.
    2. References
      1. Forum topic: http://www.javajee.com/forum-topic/find-out-if-a-string-has-all-unique-c...
  3. Given two strings, write an algorithm to find if one string is a permutation of the other.
    1. Definitions
      1. permutation (or anagram) denote two strings that have same characters (with same numbers), but in different order. 
    2. Example 
      1. LISTEN and SILENT (have same characters, but in different order).
  4. Write an algorithm for string compression using counts of repeated characters
    1. Example 
      1. aaaaarrrrbbb will become a5r4b3
    2. Assumptions
      1. if the new compressed string is is bigger than the original string, return original string.
  5. Write an algorithm to find if one word is a substring of other.
    1. Example:
      1. bcd is a substring of abcde
      2. def is not a substring of abcde
    2. Assumptions
      1. You should not use any Java library functions such as contains, but may use charAt alone (if needed).
  6. Using the above algorithm alone (isSubstring), find if one string is a rotation of other.
    1. Example
      1. datastructures is a rotation of astructuresdat.
      2. cdeab is a rotation of abcde
      3. cdaeb is not a rotation of abcde.

Important Problems on Sorting and Searching

  1. Merge two sorted arrays A and B in sorted order. A has enough locations in the end to hold the elements of B.
    • No extra buffer should be used.
    • Every element should be shifted from its current position in A, at most 1 time.
    • Hint:
      • Start filling from the end of A.
  2. Sort an array of Strings. All anagrams should be next to each other.
    • Hint:
      • Approach 1: Modify the comparator to indicate that two anagrams are equal, and then sort.
      • Approach 2: Using a hash table that maps from the sorted version of a word to a list of its anagrams.
  3. How will you sort a very big file (approx 20GB) with one String per line
    • Hint:
      • Don't bring all data into memory.
      • Use external sort: Divide into chunks, sort the chunks and merge the sorted chunks.

Important Problems on Arrays

  1. Find all pairs of integers within an array that sum to a specified value:
    • Approach 1: Using hash table (more time efficient)
    • Approach 2: Through sorting (more space efficient)
  2. Given an M x N matrix, if an element is 0, its entire row and column in the matrix should be set to 0.
  3. You are given a 2-Dimensional array (matrix) and a scale factor. You need to write a method to scale the 2D array according to the scale factor.
    1. The signature of the method should be 
      1. public static int[][] scale1(int[][] arr, int scale)
    2. Example: if you are given a 2*3 array and scale factor is 3, the output array will be 6*9; the input and output arrays will be as follows:
      • Input
        • 1 2 3 
        • 4 5 6 
      • Output
        • 1 1 1 2 2 2 3 3 3 
        • 1 1 1 2 2 2 3 3 3 
        • 1 1 1 2 2 2 3 3 3 
        • 4 4 4 5 5 5 6 6 6 
        • 4 4 4 5 5 5 6 6 6 
        • 4 4 4 5 5 5 6 6 6 

Problems on Linked Lists for Interviews and Self Assessment

I will list down some problems on the topic of linked lists that are commonly asked in interviews.

 

Important concepts to revise before trying out the problems:

  • Linked List
  • Node of a Linked List
  • Singly Linked List
  • Doubly Linked List
  • Inserting and deleting nodes in a Linked List
  • Runner technique - There will be more pointers and they will move forward at different speeds.

 

Problems

  1. Reverse a linked list
  2. Remove duplicates from a sorted linked list.
  3. Remove duplicates from an unsorted linked list.
  4. Find the Kth to last element in a linked list
  5. Delete a node in the middle of a singly linked list, given only access to that node.
  6. Given a linked list with a loop (circular linked list), find the node at the beginning of the loop.
  7. Partitian a linked list around a given value x, with all nodes with values less than x should come before all nodes with values greater than or equal to x.
  8. Given two sorted (ascending) linked lists L1 and L2. Write a program to merge them into a single descending linked list. 
    • Example:
      • List1 = 5>15>25>35>null.
      • List2 = 1>10>20>30>null.
      • ResultList = 35>30>25>20>15>10>5>1>null.
  9. Find the middle element of linked list in one Pass?

Important Note!

  • I will add more to the list whenever I come across a new one.
  • If you were asked a problem not listed here, please let us know and we will add it here. You will also receive points. If you can provide a good solution and explanation also for your problem, you will get extra points and even cash prizes. 

Problems on Stacks and Queues for Interviews and Self Assessments

Below are some of the problems based on stacks and queues. You will also find applications of stacks and queues in other sections such as Trees and Graphs.

 

Important Points to Remember 

  1. Stack uses the LIFO (Last In First Out) ordering.
  2. Queue uses the FIFO (First In First Out) ordering.

 

Important Points to Revise

  1. Arrays, Linked Lists

 

Problems

  1. Implement a stack
  2. Implement a queue
  3. Add a getMinimum() function to a Stack class of integers.
    • Assumptions and requirements:
      • Stack has push() and pop() method
      • push(), pop() and getMinimum() should operate in O(1)

Problems Based on Mathematics and Probability

  1. Write methods to implement the multiply, substract and divide operations for integers, using only the add operator.
    • Hint:
      • a + b => a + negate(b)
      • a * b => add b a times
      • x = a / b => a = bx.
  2. Find the kth number such that the only prime factors are 3,5 and 7

Important Problems Based on Sequences

Problems related to sequence generation and finding if an element fits in a sequence.

 

Problems

  1. Generate the below sequence with n elements.
    • 1, 10, 11, 100, 110, 111, 1000.
    • Note:
      • Every element in the sequence is a series of 1 or more 1's followed by zero or more 0's.
        • For example 101 is an invalid element and does not belong to the sequence, but 1, 10, 11, 100, 110, 111, 1000 etc. belong to the sequence.
      • Hint: Binary sequence of numbers is 1, 10, 11, 100, 101, 110, 111, 1000 etc.
  2. Find if the element belongs to the sequence 4, 40, 44, 400, 440, 444, 4000, without generating the sequence.
    • Note:
      • Every element in the sequence is a series of 1 or more 4's followed by zero or more 0's.
        • For example 404 is an invalid element and does not belong to the sequence, but 4, 40, 44, 400, 440, 444, 4000 etc. belong to the sequence.

Important Problems on Trees and Graphs for Interviews and Self Assessment

I will list down some problems on the topic of trees and graphs that are commonly asked in interviews. Please revise topics on tress such as Binary Trees, Binary Search Tree (BST), Balancing a Tree, Full and Complete Trees, Binary Tree Traversals (recursive), Tries, Depth First Search (DFS), Breadth First Search (BFS).

 

Problems

Trees

  1. Check if a binary tree is a Binary Search Tree (BST)
  2. Check if a given binary tree is balanced.
  3. Create a binary search tree with minimal height from a sorted increasing order array.
  4. Find difference between sum of nodes at odd levels and sum of nodes at even levels of a binary tree.
  5.  Given a Binary Search Tree (BST), create a linked list of nodes for every level.
  6. Given a binary tree with an integer data element; find all paths whose sum of data nodes will be equal to a given value
  7. Check if a binary tree (T2) is a sub tree of another tree (T1)
    • T1 has millions of nodes and T2 has hundreds of nodes
  8.  Find the inorder successor (next node) of a given node in a Binary Search Tree (BST)?
    • Each node has a link to its parent
  9. Find the first common ancestor of two nodes in a binary tree
    • Avoid storing additional nodes in any data structure
    • The binary tree might not be a Binary Search Tree (BST)
  10. Traverse the tree in spiral (zig zag) form and print nodes.
    • Consider below tree levels:
      • 1
      • 2 3
      • 4 5 6 7
      • 8 9
    • Result should be: 1 3 2 4 5 6 7 9 8

 

Graphs

  1. Find out if there is a route between two nodes in a directed graph.

Find the middle element of linked list in one Pass

Find the middle element of linked list in one Pass. Read more about Find the middle element of linked list in one Pass

Pages

Back to Top