easypython

Simple python scripts solving well known programming interview questions

• test1 - clones an undirected graph represented with a label and list of neighboring nodes
• test2 - solves NQueens puzzle which is the problem of placing n queens on an n×n chessboard such that no two queens attack each other
• test3 - finds the best time to buy and sell a stock once or unlimited times or fix number of times to make the maximum profit
• test4 - recovers a binary search tree with 2 replaced nodes
• test5 - implements a search typehead
• test6 - implements preorder, inorder, and postorder traversals of a binary tree with and without using recursion
• test7 - finds the largest rectangle in a histogram
• test8 - finds the kth minimum number in a list
• test9 - determines if two strings are anagram or not
• test10 - implements bubble sort, insertion sort, quick sort, merge sort, and bucket sort algorithms
• test11 - reorders a linked list L1->L2->...->LN-1->LN into L1->LN->L2->LN-1->...
• test12 - finds the median of an array which is created by merging two sorted arrays in O(log n+m)
• test13 - implements a simple vending machine
• test14 - removes duplicate entries in a list
• test15 - checks if 2 strings are rotation of each other
• test16 - reverses words in a given sentence without using any library method
• test17 - finds the nth node from the end in a singly linked list in one pass
• test18 - finds the shortest sequence between two words start and end by changing single character each time and requiring all intermediary words in a word dictionary
• test19 - finds all combinations of a string
• test20 - checks if a string is a palindrome
• test21 - reverses a singly linked list
• test22 - creates a binary tree iterator
• test23 - searches an integer in a presorted integer array which was rotated from an unknown pivot point (array has no duplicates)
• test24 - finds the middle node in a linked list in one pass
• test25 - prints all leaves of a binary tree
• test26 - counts the occurrence of each word in a list
• test27 - implements a binary tree
• test28 - finds the least common ancestor in a binary search tree
• test29 - finds the maximum depth of a binary tree
• test30 - returns level order of a binary tree
• test31 - finds the common words in two lists
• test32 - finds list of all unique triplets in a list of integers satisfying a+b+c=0 in non-descending order
• test33 - reads a text file and creates another text file with the reversed file content
• test34 - finds starting position of substrings in a string S where each substring is a combination of all substrings provided in a list L
• test35 - intermixes two strings after crerating chunks in size n e.g. ABCDEFG and 1234567890 with 2 char chunks -> AB12CD34EF56G7890
• test36 - reverses words in a paragraph
• test37 - finds a, b, c, d values such that A[a]+A[b] = A[c] + A[d] where a < b and c < d and a < c and b != d and b != c
• test38 - finds largest distance between nodes of a tree
• test39 - finds stepping numbers between two integers e.g. A=10, B=40 output = [10, 12, 21, 23, 32, 34]
• test40 - checks if a string has all digits
• test41 - demonstrates trying and catching exceptions while getting a positive integer as an input and printing its square
• test42 - finds the kth minimum number in a list (another version)
• test43 - manipulates a number string by adding a "*" between two consecutive even numbers and "-" between two consecutive odd numbers
• test44 - implements power function with modulo operator
• test45 - searches for a range (a, b) in a sorted integer array A where a and b represent the first and last occurences of integer B
• test46 - reverses a linked list partially between two values
• test47 - calculates combination sum of a set of numbers (C) such that sum equals to target number (T)
• test48 - finds all unique permutations of a list of numbers
• test49 - evaluates an expression in reverse polish notation
• test50 - finds contiguous subarray within an array, A of length N which has the largest sum
• test51 - finds duplicate characters in a string
• test52 - finds if parentheses are balanced in a string
• test53 - generates all combinations of n pairs of well-formed parentheses
• test54 - finds Fibonacci numbers for a given positive integer (finds the Fibonacci of 10M on a Mac with 32GB memory)
• test55 - rearranges a list such that A[i] becomes A[A[i]] where A[i] has N elements such that 0<=A[i]<=N-1
• test56 - rotates a matrix 90 degrees clockwise without using another matrix
• test57 - finds a substring in a string
• test58 - converts an integer N into a roman numeral where 1 < N < 4000
• test59 - converts a JSON string into prettyJSON format
• test60 - finds if the list A with sorted integers have 2 indices such that A[i] - A[j] = k where k is a positive integer and i != j (space optimized)
• test61 - finds 3 numbers with a sum closest to a given integer T in a list of integers S
• test62 - implements eval function for arithmetic operands *,/,+,-
• test63 - finds all unique paths in a grid of MxN size between points (1,1) and (M,N)
• test64 - sorts a list of colors 0, 1, and 2 in minimum number of swaps (O(N) complexity)
• test65 - computes and returns the square root of integer A as floor(sqrt(A)) where 1<=A<=10^9
• test66 - calculates the nth integer in "count and say" list
• test67 - adds two binary strings
• test68 - finds the length of the shortest string to be appended to turn a string into a palindrome
• test69 - matches two regular expression strings
• test70 - finds all possible letter combinations of for digits dialed on a letter phone
• test71 - finds sliding window maximums of an integer array
• test72 - finds all permutations of items in a list
• test73 - solves gas station problem
• test74 - finds the maximum length of list of disjoint intervals for a given list of intervals
• test75 - finds the majority element in a list
• test76 - prints the first non-repeated character from a string
• test77 - finds the minimum number of cuts to create palindromes from a string
• test78 - solves the word break problem which determines if a string consists of substrings all found in a dictionary
• test79 - finds the size of the largest rectangle in a binary matrix
• test80 - finds the size of the largest rectangle in a binary matrix in O(NxN) time complexity
• test81 - finds the minimum number of steps to convert string A into string B
• test82 - cuts a rod from the weak points of the rod in an order to minimize the rod cutting cost where cutting each rod costs the length of the rod
• test83 - distributes minimum number of candies to N children each with a priority
• test84 - inserts a new interval into a list of intervals which are non-overlapping and sorted based on start times
• test85 - deletes all nodes with duplicate numbers in a sorted linked list
• test86 - merges two sorted linked lists
• test87 - swaps all two adjacent nodes in a linked list and returns its head
• test88 - partitions a linked list such that all nodes with a value less than X come before all nodes with value greater than or equal to X
• test89 - reverses a string by using recursion
• test90 - returns elements of an NxM matrix in spiral order
• test91 - sorts a linkled list by using insertion sort
• test92 - finds subsets of a list of distinct integers and returns them in the non-descending order
• test93 - creates a list with only unique items
• test94 - approximates the Pi value by accumulating the distance among point increments on the upper right quartile of the circle
• test95 - finds the intersection of two linked lists in O(N) time and O(1) memory
• test96 - finds if the list A with sorted integers have 2 indices such that A[i] - A[j] = k where k is a positive integer and i != j (time optimized)
• test97 - adds two non-negative numbers stored in two linked lists where digits are stored in reverse order and each node contains a single digit.
• test98 - evaluates an expression in reverse polish notation
• test99 - reverse a linked list