{{ message }}

# harishvc / challenges Public

A personal log of learning and solving problems

Switch branches/tags
Nothing to show

## Files

Failed to load latest commit information.

# Cracking the coding interview

Collection of interesting questions and solutions that involve data structures, algorithms and concepts. Solutions are in Python version 3.4.3

### Data Structures, Algorithms & Concepts

1. Data structures, algorithms, time complexity and concepts π πΆ
2. Introduction to Concurrency π πΆ
3. Introduction to Design Pattern πΆ
4. Introduction to Bit Manipulation π₯ πΆ
5. Fun with Bits & Bytes π
6. Fun with Permuation and Combination π₯ πΆ

### Brain Teasers (Moderate)

1. Check if a given number is prime
2. How many trailing zeros are in n! (n factorial) π
3. Reverse an integer
4. Find the Greatest Common Divisior (GCD) of two positive integers
5. Validate Sudoku π¨
6. Flatten an object representation. Example {a:1, b:2, c:{d:3}} flattens to {a:1,b:2,c.d:3} π₯ π
7. Matrix
7.1 Print the matrix from outside to inside (Spiral) π₯
7.2 Given a two dimentional matrix where values are increasing. Search for a target value π πΆ
7.3 Rotate a 2D matrix clockwise 90 degrees
7.4 Rotate a 2D matrix anti-clockwise 90 degrees π
8. Number of perfect squares between two given numbers
9. Find the coordinates of the rectangle in the 2 dimensional list [TODO]
10. Check if a number is a happy number
11. Given an integer and returns all possible combinations of its factors
12. Given a digit string (from phone keypad), return all possible letter combinations that the number could represent

### Sort

1. Sorting Algorithms & Notes
1.1 Quick Sort π
1.2 Quick Selection Sort π
1.3 Merge Sort
1.4 Heap Sort π π₯
1.5 Insertion Sort
1.6 Bucket Sort
2. Sort lists,lists of lists and list of dictionaries
3. Sort a list of ones, twos and threes
4. Given two sorted list merge them
5. Merge sorted lists
6. Sort version numbers π π₯
7. Median
7.1 Find median of a sorted list
7.2 Find median of two sorted list π‘ π π
7.3 Find median of unsorted list π‘ πΆ
7.4 Find median in a stream of integers (running median) π πΆ π¨
8. Unsorted list of values
8.1 Find the smallest K
8.2 Find the largest K
9. Merge K sorted list of size N π¨ π‘
10. Sort a string
11. Find the first and second largest value in an unsorted list
12. Given a sequence of words, print all anagrams together π‘
13. Sort a string of printable characters π

### Search

1. Implement skip list
2. Implement Trie - insert, search, searchWith, delete (Prefix Tree) πΆ π‘
3. Implement Bloom Filter π‘ π₯
4. Implement Suffix Array πΆ π‘
5. Search using Regular Expression
6. KMP (Knuth Morris Pratt) algorithm π₯ π
7. Implement Z algorithm
8. Find the missing number in an increasing sequence (1 ...N) π‘
9. Given a list of integers with duplicates (can be more than one) find any integer than appears more than once
9.1 Can modify the input list
9.2 Cannot modify the input list
10. Given unsorted values with several duplicates and one value that occurs once find the value TODO
11. Find duplicates given 2 sorted lists
11.1 both list of same size
11.2 one list is >> other
12. Given a two dimentional matrix where values are increasing. Search for a target value π πΆ
13. Given a sorted list find if a value exists π₯

### Lists & Dictionaries

1. Randomize list elements
2. Given two numbers as list add them and return result as list
3. Say as you see - given an input string of integers print the output π
4. Given a list of numbers, return a list of products of all other numbers without using division in O(n) time π‘ πΆ
5. Design a dictionary that performs insert, lookup and delete in constant time O(1)
6. Find the majority element π₯
6.1 From unsorted list in linear time and constant storage π
6.2 From sorted list in logrithmic time and constant storage π π‘
7. Two lists
7.1 Find the intersection of two sorted lists π
7.2 Given two lists, find a pair of values (one from each array) such that you can swap so that both arrays sum to the same value [TODO]
7.3 Given two sorted list merge them
7.4 Merge sorted lists
7.5 Find min value of two unsorted lists π‘ π
8. Duplicates
8.1 Given a list of integers return a list of integers that only occurred once π‘ π
8.2 Given a sorted list, remove the duplicates in place, return modified list and #unique values πΆ
9. Given a list and condition
9.1 Find all possible 2 numbers in the list that add up to the given sum
9.2 Find all possible triplets in the list that add up to the given sum
9.3 Find all possible triplets in the list that satisfies a^2 + b^2 = c^2 πΆ π₯
9.4 There are numbers from 1 to N in an array. One of the number gets duplicated and one is missing. Find out the duplicate number πΆ [TODO]
9.5 Given two arrays of integers, find a pair of values (one from each array) you can swap so that both arrays sum to the same value [TODO]
9.6 Find three numbers when multipled provide max value from the given input
9.7 Find all possible quadruplets in the list that add up to the given sum
10. Subarray and condition
10.1 Find a continuous subarray of sum zero πΆ π
10.2 Find a continuous subarray of sum target given positive values πΆ
10.3 Find a continuous subarray of sum target given positive and negative values πΆ π
10.4 Print alternate positive and negative values while retaining order π₯
10.5 Find pairs in an integer whose sum is equal to a given value
10.6 Given a list of integers and two target values find the shortest distance between the two target values π₯ πΆ
10.7 Find the pivot value that splits the list into balanced partitions πΆ π‘
10.8 Find the maximum subarray sum - Kadane Algorithm πΆ π‘
10.9 Find #occurrences of the largest sum contiguous subarray of modulo K π¨ π‘
10.10 Given a list and a number K, print the maximum sum subarray of size K
11. Rotated list
11.1 Rotate a list to the right or left by n places
11.2 Find minimum in a rotated sorted list #RotationPoint π π°
11.3 Search a target number in a rotated sorted list π‘
12. Time intervals
12.1 Merge overlapping time intervals πΆ
12.2 Find #conflicting appointments π
12.3 Find conflicting appointments
12.4 Find the next earliest availability given availability and meeting duration π πΆ
13. Design π‘
13.1 Design a data structure that implements insert, remove, contains and get random in O(1) time π‘ π π
13.2 Design a data structure that implements increment, decrement, max and min in constant time π¨ πΆ π
13.3 Implement a function that inserts, deletes and getrandom in O(1) time πΆ π‘
13.4 Write a function that returns values randomly, according to their weight π‘ πΆ

### Strings

1. Find #words in a sentance
2. Find most and least frequently used words in a sentance
3. Write a function which finds a closest pair of equal entries π
4. Write a function that given an integer returns a formatted number string π π‘ π
5. Given a string for a text message and character limit. Break the message without breaking the words and include message count πΆ
6. Properties
6.1 Given two strings find if they are Anagrams
An Anagram is a rearrangement of the letters of one word or phrase to form another word or phrase
6.2 Check if two given strings are Isomorphic
Two strings str1 and str2 are called isomorphic if there is a one to one mapping possible for every character of str1 to every character of str2. And all occurrences of every character in βstr1β² map to same character in βstr2β²
6.3 Generate all Numeronyms for a given string
A numeronym is a number-based word. Letters between the first and last are replaced with a number representing the number of letters omitted, such as "i18n" for "internationalization"
7. Reverse
7.1 Reverse an integer π
7.2 Reverse a string recursively
7.3 Reverse all words in a sentance
8. Palindrome
8.1 Test if a string is a Palindrome. Ignore all non-alphanumeric characters
8.2 Given a number find the next largest Palindrome π‘ πΆ
8.3 Find the longest palindromic substring - Manacher's algorithm π‘ πΆ π
9. Substring (A substring is a prefix or suffix of any string. There are n^2 substrings.)
9.1 Find the number of distinct substrings of a given string π‘
9.2 Generate all the substrings of a string
9.3 Find first occurance of substring
9.4 Find the longest repeating substring (longest substring of a string that occurs at least twice) π₯ π‘ πΆ
9.5 Find the longest substring with two unique characters πΆ π
9.6 Find the longest substring with k unique characters
9.7 Find the longest substring with non-repeating characters
9.8 Longest Substring with At Most K Distinct Characters π¨ π
9.9 Find the minimum length of the substring that contains all characters in a given input π
10.Given an input string and pattern find the minimum window in the input string that will contain all the characters in the pattern πΆ π
10. Find the first non repeating character in string

1. Linked List Library π π₯
3. Find the nth node from the end of a linked list πΆ π‘
4. Circular Linked List, Cycle & Intersection
4.1 Find the length and start node for the cycle in a linked list π‘ πΆ
4.2 Find the node at which the intersection of two single linked lists begins
4.3 Add a node to a sorted circular linked list π‘ πΆ
5. Merge
5.1 Merge two sorted linked lists [TODO]
5.2 Merge K sorted linked lists [TODO] π₯
6. Given a single linked list with one digit positive integer value
7. Reverse a linked list π π
8. Check if a linked list is a Palindrome
9. Find the middle element in a linked list π‘
10. Delete a node in the linked list πΆ π₯
11. Zip a linked list πΆ π
12. Split a link list into odd and even values with no additional space π
13. Remove duplicate values & retain order of existing values π₯
14. Design and implement Least Used Cache (LRU) π‘ πΆ π
15. Implement skip list
16. Given linked list return max value at any given time in constant time
18. Return a linked list that contains the intersection of two linked lists πΆ

### Queue & Double-ended Queue

1. Implement queue using list
2. Implement queue using linked list
3. Implement a queue using two stacks
4. Queue implementation using dynamic array
5. Queue implementation using fixed size array
6. [Design an algorithm to sort a stack in descending order] (https://github.com/harishvc/challenges/blob/master/sort-stack-in-descending-order.py)
7. Sliding Window Maximum π πΆ π₯
8. Implement getMax() that operates in constant time π
8.1 Given a queue return max value at any given time in constant time
8.2 Given linked list return max value at any given time in constant time
9. Given a screen with all pixels having one of two colors. When a random pixel is clicked, then that pixel & all the adjacent pixels with same color should change the color to the second color [TODO]
10. Implement blocking queue [TODO]
11. Implement non-blocking queue [TODO]

### Binary Trees

1. Binary Tree Traversal Library π π
1.1 Pre-order
1.2. In-order
1.3. Post-order
1.4 Level-order
2. Essentials
2.0 Binary Tree Essentials Library π π
2.1 Find # of leaves, half nodes and nodes in a binary tree
2.2 Find the size of a binary tree
2.3 Find the height (max depth) of the binary tree πΆ π
2.4 Find the depth (level) of a node and the path from the root
2.5 Find the deepest node in binary tree
2.6 Find diameter (width) of a binary tree π πΆ π‘
2.8 Find all edge nodes (boundary/perimeter) in the binary tree π
3. Path Sum
3.1 Find the max value of the binary tree
3.2 Find level than has maximum sum π
3.3 Given path sum check if the path exists π
3.4 Root to leaf path (Iterative)
3.5 Root to leaf path (Recursive) π¨ π‘
3.6 Find the sum of all root to leaf paths where each path represents a binary number π π π‘
3.7 Find sum of all leaf nodes
3.8 Find the sum of all left leaves
4. Moderate Difficulty
4.1 Flip/Invert a binary tree π
4.2 Clone a binary tree π
4.3 Check if a binary tree is symmetric (mirror)
4.4 Check if two binary trees are structurally identical? π
4.5 Complete Binary Tree
Β Β Β Β Β  4.5.1 Find # nodes in a Complete Binary Tree π‘ π
Β Β Β Β Β  4.5.3 Check if a Binary Tree is Complete Binary tree?
4.6 Balanced Binary Tree
Β Β Β Β Β  4.6.1 Check if a binary tree is fully balanced π π‘
Β Β Β Β Β  4.6.2 Add a node to a balanced binary tree
Β Β Β Β Β  4.6.3 Given a full binary tree, add a pointer to the next sibling
4.7 Given two binary trees T1 and T2, check if T2 is a subset of T1 π‘ πΆ π
4.8 Find the ancestors of a node in a binary tree π πΆ π
4.9 Find the Lowest (nearest/first) Common Ancestor (LCA) of two nodes in a binary tree
Β Β Β Β Β  4.9.1 Traverse down - parent node to child node π πΆ π
Β Β Β Β Β  4.9.2 Traverse up - child node to parent node
4.10 Find the shortest path between two nodes in a binary tree π πΆ π
Β Β Β Β Β  4.10.1 solution 1: Modify LCA
Β Β Β Β Β  4.10.2 solution 2: Using root to node path
4.11 Given a binary tree where path are from parent node to child node, root and leaf can be excluded in the path
Β Β Β Β Β  4.11.1 Count # path that add up to a given value π‘ π
Β Β Β Β Β  4.11.2 List all the path that add up to a given value π
4.12 Serialize and Deserialize a Binary tree π₯ π π
Β Β Β Β Β  4.12.1 From pre-order with leaves and half-nodes marked π‘
Β Β Β Β Β  4.12.2 From pre-order & in-order
Β Β Β Β Β  4.12.3 From post-order & in-order
4.13 Given preorder and inorder traversal construct postorder traversal π₯ π
4.14 Construct a binary tree from per-order traversal where leaf nodes are marked π‘ πΆ

### Binary Search Tree (BST)

1. BST Library (add node,delete node, isBST? max, min)
2. Create BST
1.1 Convert a unsorted list to BST
1.2 Convert a sorted list to BST πΆ
3. Delete node from BST π
4. Find max value of BST
5. Find min value of BST
6. Find if an element exists in BST
7. Check if valid BST π
8. Find inorder successor of node N π π¨ π πΆ
9. In a BST given a target find a value close to the target
10. Find smallest K in a BST π π‘
11. Find largest K in a BST π π‘ π
12. Given a BST find # nodes that lie in the given range
13. Search in sorted list X for index i such that X[i] = i π‘ π
14. Given a sorted list create a BST with minimal height π π‘
15. Given ordered nodes construct a fully balanced BST π
16. Find all possible combinations that can generate identical Binary Search Tree (BST) π‘ π π π¨
17. Given a sorted list and a value, find the first and last occurance of the value π‘ πΆ
18. Find the square root of an integer without using square root function π‘
19. Find mean of a BST
20. Find the Lowest (nearest/first) Common Ancestor (LCA) of a BST π‘ πΆ
21. Find depth of a binary search tree without using recursion
22. Implement BST iterator π π‘ πΆ
23. Find size of BST tree in a Binary Tree πΆ π
24. Delete nodes outside the given range in BST π‘ πΆ

### Heap

1. Fundamentals
1.1 Convert unsorted list to max heap in linear time π π
1.2 Insert value into a heap π
1.3 Check if a Binary tree is a Complete Binary Tree [TODO]
1.4 Heap Sort
2. Moderate
2.1. Find Kth maximum in an unsorted list
2.2. Find the Kth most popular value in an unsorted list
2.3. Find K popular values in an unsorted list
3.1 Merge K sorted list of size N
3.2 Maintain a Max Heap of size K

### Graph

1. Fundamentals
1.1 Directed Acyclic Graph (DAG)
1.2 Depth First Traversal
1.3 Breadth First Traversal π π₯
1.4 In a directed graph given two nodes find out whether if a path exists
1.5 Topological Sort (given edges)
1.6 Topological Sort using Kahn's algorithm (given adjacency list) πΆ π
2. Moderate
A cycle is a closed path - visit a node for the second time before all its decendents have been visited
2.1 Detect cycle using Depth First Traversal π πΆ
2.2 Detect cycle using Topological Sort
2.3 Given a sorted dictionary (array of words) of an alien language, find order of characters in the language
2.4 Given a trip start and destination print the itenary
2.5 Find longest path in a Directed Acyclic Graph from a source vertex π₯
3.1 Dijkstra shortest path algorithm [TODO]
3.2 Given a source word, target word and dictionary, transform the source word to target by changing/adding/removing 1 character at a time, while all intermediate words being valid words in the dictionary. Return the transformation chain which has the smallest number of intermediate words #WordLadder π π
3.3 Given a boolean 2D matrix, find the number of islands πΆ π
3.4 Given a graph find the Strongly Connected Components (SSC) πΆ π

### Dynamic Programming

1. Multiply two numbers without using operators *, / and with minimal operations π
2. Find the power set πΆ π‘
Power Set is a set that includes all the subsets including an empty set and the set itself.
2^N subsets for a set of size N
3. Generate all possible N pairs of balanced parentheses π π‘
4. Find string combinations of length K
5. Find all permutations of a string in sorted (lexicographic) order - should handle duplicate values πΆ π π‘
6. Given stock prices during a time period find maximum gain
6.1 singe purchase and sale π
6.2 Multiple single purchases and sales without overlaps π¨ π
7. Partition
7.1 Can the given list be partitioned into two sub-lists with equal sum (balanced partition)?πΆ
7.2 Given a list, identify two sub-lists with equal sum (balanced partition, using DP) π π‘
7.3 Given a list, identify all sub-lists with equal sum (balanced partition, using back tracking) πΆ
8. Longest Increasing Subsequence (LIS)
8.1 Given a list of random numbers. Find length of Longest Increasing Subsequence (LIS) and the sequence πΆ
8.2 Given a list of random numbers. Find all the increasing subsequences
9. Given n stairs to reach the top and you can take 1 or 2 steps at each stair
9.1 Find #ways a person can reach the top of the stairs πΆ
9.2 Find all possible combinations π‘
10. Given target and possible values
10.1 Find #combinations to achieve the target πΆ π
10.2 Find all unique combinations to achieve the target π¨
11. Given denominations and a total
11.1 Minimum # coins needs to reach the total and what are the coins? π πΆ
11.2 Find all possible combinations to reach a total π‘ π₯
11.3 Find all possible combinations to reach a total using lookup π‘ π₯
12. Determine the maximum possible value from the coin play game π πΆ π‘
13. What is the minimum attempts to find out from which floor egg will break?
13.1 2 Eggs π¨ π π‘
13.2 N eggs πΆ π
14. How many different 10-digit numbers can be formed starting from 1? movement from 1 digit to the next is similar to the movement of the Knight in a chess game π‘ π
15. Find the nth Fibonacci number
15.1 Iterative, Recursive, Bottom-up & Top-down
15.2 Recursive with lookup
16. Longest Common Subsequence (LCS) π₯ π
subsequence is a generalization of substring. For example, "Itwastimes" is a subsequence of "It was the best of times", but not a substring
16.1 Length of the LCS
16.2 Find the LCS
16.3 Find all the sequences π
16.4 Implement Unix diff command
17. Longest Common Substring
17.1 Length of the Longest Common Substring
17.2 Find the Longest Common Substring
17.3 Longest common substring of more than two strings
18. Find #steps to convert string1 to string 2 using operations insert,remove,replace π π
19. Input string and dictionary of words
19.1 Can the input word be split using space-separated sequence of dictionary words? πΆ π¨
19.2 Construct all possible sentences where each word is a valid dictionary word π‘ π
20. Given two sequences find the longest palindrome
21. Text justification
21.1 Given a string and limit provide line breaks based on even distribution of empty spaces π‘ πΆ
21.2 Pack your words in a greedy approach, evenly distribute space TODO
22. Binary matrix
22.1 Find #path from top left to bottom right π‘
22.2 Find out the maximum square size sub-matrix π πΆ
22.3 Find area of the largest rectangle π π‘ πΆ
22.4 Find #rectangles
23. Matrix multiplication
23.1 Find the most efficient way to multiply these matrices πΆ π‘
23.2 Find the order in which the matrices need to be multiplied
24. Given the weight and a value of cakes and a duffel bag with max capacity, find the max value that can be filled in the duffel bag π‘ π¨

### GitHub Resources

A personal log of learning and solving problems

## Releases

No releases published

## Packages 0

No packages published