## Programming Problems

August 28, 2018 | 3 Minute Read

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:

1. Sub-string Search
2. Duplicate characters in a string. Similarly, first not repeated character in a string.
3. Intersection of two words. Returns the common characters.
4. Changes need to be made in one string to make it look like another string. Changes means deletes and swaps.
5. Anagram, palindrome
6. Find all permutations of a string.
7. Reverse a sentence without touching spaces and special characters.

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