Programming Problems
In this post, I will list and briefly discuss some important programming problems specially for an interview.
Tree, BST
- Find the size or depth of the binary tree.
- Find leaves and internal nodes.
- How pre-, post-, and in-order traversal works?
- Traverse a given binary tree in preorder without recursion?
- Flattening a binary tree as list of nodes.
- List of nodes at a certain level k, where the deepest level in n.
- Finding graph diameter
Graph:
- Shortest Path
String:
- Sub-string Search
- Duplicate characters in a string. Similarly, first not repeated character in a string.
- Intersection of two words. Returns the common characters.
- Changes need to be made in one string to make it look like another string. Changes means deletes and swaps.
- Anagram, palindrome
- Find all permutations of a string.
- Reverse a sentence without touching spaces and special characters.
Linked-list:
Linked list goes really well with recursion.
- How do you find the middle element of a singly linked list in one pass?
- Hint: Can be done with two pointers. [Solution]
- Find if a linked list is palindrome withour using extra space.
- Hint: Linked-list reverse.
- Find sum of two numbes represented as Linked list and return the sum as a linked list.
- Merge two sorted linked lists with recursion.
- Check whether a linked list has a cycle or not.
- Reverse linked list without recursion.
- How to find the the third node from the end in a singly linked list?
Array, Number and list manipulation
- How do you find the missing number in a given integer array of 1 to N? Canbe done in O(logn) time.
- Can be done in O(n) if the numbers are not sorted. Hint: use n(n+1)/2
- Can be done in O(log n) if the numbers are sorted.
- If a list contains some numbers exactly twice except for one number, find the number that occurs once.
- Use bitwise operation to solve in O(n) time and O(1) space complexity.
- can uyse python set with add/remove, but would be O(n) time and space complexity.
- Swapping two numbers without using a temporaryk memory or variable.
- Merge some intervals. Merging [[1-5], [4-6],[3-9], [8-14], [10-12], [16-19]] returns [[1-14], [16-19]].
- Follow-up: How to find a number that occurs the most in these intervals.
- Find and possibly remove the duplicate number from a given integer array? Can you do it w/o using library.
- Find 3-SUM where sum of any 3 numbers in a list of numbers equals to K. Do it in O(n^2).
- Quicksort in place.
- Implement merge sort, bucket sort,
- Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum. KADANE’s algorithm.
Matrix:
- How to rorate a NxN image that is represented as a 2D array of integers in memory?
- Follow-up: Can we do it without using extra memory?
- Can we do it 1 pass?
Miscellaneous
- How do you check if two rectangles overlap with each other?
System design
- How do you design a vending machine?
