Hello everyone! One of my hobbies is to look for new programming questions online and I put those questions here with the reference website. I will try to solve them and upload my solution code here as well. Obviously, I do not have enough time to intensively test all of them so if you find any error, please be kind and send me an email(mehrzads@umich.edu). All your suggestions and comments are welcome.


Mehrzad

Programming Questions

Linked Lists

  1. Reverse a singly linked list.
    Ref
    Solution
  2. Delete a Node in a singly linked list (you just have a pointer to the node that should be deleted).
    Ref
    Solution
  3. Given a singly linked list, determine whether or not it has a cycle.
    Ref
    Solution
  4. Find nth element from the end of a singly linked list.
    Ref
    Solution
  5. Find merging node of two linked lists.
    Ref
  6. Find the center of a linked list.
    Ref

Arrays

  1. Given and Array of A[1..n] bits, find the length of longest consecutive substring of 0 and 1 such that number of 0s and 1s are equal
    Ref
  2. If [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.....an,bn] , solution should be in-place
    Ref
  3. For an unsorted array a, find the indices i and j ,j> i for which a[j] - a[i] is maximum.
    Ref
  4. Compute h_index.
    Ref
  5. Push all the zero's of a given array to the end of the array.
    Ref
  6. Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. (better than NLOGN).
    Ref
  7. giving lots of intervals [ai, bi], find a point intersect with the most number of intervals.
    Ref
  8. giving lots of intervals [ai, bi], count the number of other intervals that are nested within it.
    Ref
  9. Find local minimum in an array.
    Ref
  10. In an array 1-100 exactly one number is duplicate. How do you find it?
    Ref
  11. In an array 1-100 exactly many numbers are duplicate. How do you find it?
    Ref
  12. In an array 1-100 exactly K numbers are missing. How do you find it?
    Ref
  13. Remove duplicates from a sorted array(Inplace)
    Ref
  14. Write a program to find an element in a 2D matrix whose all rows and columns are sorted(Rows and columns are increasing from top to bottom and from left to right).
    Ref
  15. Given a NxN matrix with 0s and 1s. Set every row that contains a 0 to all 0s and set every column that contains a 0 to all 0s.
    Ref
  16. Search in sorted array X for index i such that X[i] = i.
    Ref
  17. Given a grid with certain intersections marked. I'd like to find the intersection that is closest to all the marked intersections. That is, I need to find a point such that the sum of distances from all points is minimum.Search in sorted array X for index i such that X[i] = i.
    Ref
  18. You're given an unsorted array of integers where every integer appears exactly twice, except for one integer which appears only once. Write an algorithm that finds the integer that appears only once.
    Ref
  19. Given an n x n grid with a person and obstacles, how would you find a path for the person to a particular destination? The person is permitted to move left, right, up, and down.
    Ref
    Wiki
  20. Given 3 sorted arrays. Find(x,y,z), (where x is from 1st array, y is from 2nd array, and z is from 3rd array), such that Max(x,y,z) - Min(x,y,z) is minimum.
    Ref
  21. Say you have three workers: Jim, Steve and Alan. You need to have one of them clean the bathroom, another sweep the floors & the third wash the windows. What.s the best (minimum-cost) way to assign the jobs?
    Ref
  22. An array with elements from 1 to N is given in random order , what is minimum number of (adjacent)swaps required to convert into cyclic sorted array?
    Ref
  23. Given a list of numbers with repetitions, how to generate all unique subsets?
    Ref
  24. Zig-zag scan an N x N array
    Ref
  25. Given an array of numbers, return array of products of all other numbers (no division)
    Ref
  26. You are given an NxN binary (0-1) matrix with following properties: 1.Each row is sorted (sequence of 0's followed by sequence of 1's)2. Every row represents an unsigned integer (by reading the bits) 3.Each row is unique. The bit values in each row is sorted and represents an integer.Find the row representing the smallest integer.
    Ref
  27. Given an array of numbers (a), find the maximum difference between j and i indices where j > i and a[j] > a[i].
    Ref
  28. Given an array of numbers, find the longest equally spaced subsequence.
    Ref

Trees and Graphs

  1. Check if a binary tree is balanced.
    Ref
  2. Find an ancestor of given two node from a binary tree in O(n) time.
    Ref
  3. The two nodes in BST are swapped.Correct the BST.
    Ref
  4. You have a sorted array, create a binary tree with minimal height.
    Ref
  5. Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.
    Ref
  6. Construct a binary tree from inorder/preorder/postorder traversal
    Ref
  7. Determine if a Binary Tree is a Binary Search Tree (BST)
    Ref
  8. Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization
    Ref
  9. Find the maximum Height (Depth) of a Binary Tree.
    Ref
  10. Compute sum of the root to leaf numbers(Read Description).
    Ref
  11. Find the length of the longest non-decreasing sequence through adjacent, non-repeating cells (including diagonals) in a rectangular grid of numbers.
    Ref
  12. How to search for a given word in a dictionary?
    Wiki
  13. Find the shortest distances between every pair of vertices in a given edge weighted directed Graph.
    Wiki
  14. Find the diameter of a binary tree.
    Wiki
  15. Detect cycles in a directed graph.
    Wiki

Strings

  1. Reverse the ordering of words in a string
    Ref
  2. Check if two strings are anagrams
    Ref
  3. Find Crazy Distance Between Strings.
    Ref
  4. String reduction.
    Ref

Stacks and Queues

  1. Implement a stack using singly linked list.
    Ref
  2. Implement a queue using singly linked list.
    Ref
  3. Implement a queue using stacks.
    Ref
  4. Sort a stack.
    Ref
  5. Implement a queue in which push, pop, and min are O(1)
    Ref

Dynamic Programming/ Recursion

  1. Pour water on a histogram, calculate the water volume the histogram can hold.
    Ref
  2. Given a knapsack that can hold at most W weight items, also given a list of items with their weight wi and value vi (no items share the same weight), try to find a valid assignment which achieve the highest value in the knapsack (can't be over-weighted at the same time).
    Ref
  3. Maximum subarray problem.
    Ref
  4. Given a long string and a given word find out how many times you can write that word using subsets of the string. (i.e., you can create "dog" with "doom dogged" 8 times.
    Ref
  5. Cutting a rod problem.
    Ref
  6. Ugly numbers are numbers whose only prime factors are 2, 3 or 5. Find Nth ugly number.
    Ref
  7. Given a Binary Tree, find size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset.
    Ref
  8. Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.
    Ref
    Wiki
  9. The longest Increasing Subsequence (LIS) problem.
    Ref
    Wiki
  10. You are given N blocks of height 1.N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}. How should we solve this problem by programming? Any efficient ways?
    Ref

Divide and Conquer

  1. Find the closest pair of many points.
    Ref

Math

  1. Determine whether an integer is a palindrome.
    Ref
  2. Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1. Write a function g(x) using f(x) that 1/2 times returns 0, 1/2 times returns 1.
    Ref
  3. Determine if two rectangle overlap.
    Ref
  4. Given n, find pair of integers(x,y) where 1/x + 1/y = 1/(n!).
    Ref
  5. Describe an algorithm that takes an unsorted array of axis.aligned rectangles and returns any pair of rectangles that overlaps, if there is such a pair. Axis.aligned means that all the rectangle sides are either parallel or perpendicular to the x. and y.axis. You can assume that each rectangle object has two variables in it: the x.y coordinates of the upper.left corner and the bottom.right corner.
    Ref
  6. Given a target number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the target.
    Ref
  7. Test if a number is Fibonacci.
    Ref

Big Data/Stream

  1. Sorting 1 million 8-digit numbers in 1MB of RAM.
    Ref
  2. Find an integer not among four billion given ones.
    Ref
  3. Most efficient way to store thousand telephone numbers.
    Ref
  4. Print last 100 bytes in a stream.
    Ref
  5. Find running median from a stream of integers.
    Ref
    Wiki

Bit Manipulation


Bit Twiddling Hacks(Great Website!)

Puzzles

  1. Josephus problem
    Ref

Websites:


Techinterview
Leetcode
hackerrank