domenicohyatt / algorithms Goto Github PK

Algorithms My personal Java practises for some well-studied algorithms and problems commonly asked in technical interviews

My Solutions

Given a number, return all possible strings that the number could represent if 0 -> {A, B, C}, 2 -> {D, E, F}, and so on. (Modified from Original question) Solutions: Java

You have a room-full of balances and weights. Each balance weighs ten pounds and is considered perfectly balanced when the sum of weights on its left and right sides are exactly the same. You have placed some weights on some of the balances, and you have placed some of the balances on other balances. Given a description of how the balances are arranged and how much additional weight is on each balance, determine how to add weight to the balances so that they are all perfectly balanced. (Original question) Solutions: Java

Algorithms on binary trees (Java). Comprises of the following algorithms:

• Given a node value, finds the node in tree using dfs
• Pre-order traversal
• In-order traversal
• Post-order traversal
• Checks if tree is a BST
• Gets the height of the BST
• Checks if the tree is height balanced
• Determines the Lowest Common Ancestor (LCA) of two nodes
• Prints the tree level wise using BFS
• Prints the average value for each level in tree
• Determines the in-order successor for a node

Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. Write a program to find the total number of different ways of making changes for any amount of money in cents. (Original question) Solutions: Java

Let 1 represent ‘A’, 2 represents ‘B’, etc. Given a digit sequence, count the number of possible decodings of the given digit sequence. (Original question) Solutions: Java

Given a number, obtain the next larger permutation and next lower permutation by swapping around the digits in the number. Solutions: Java

Implement Fibonacci in bottom-up dynamic programming fashion. Solutions: Java

Given n stairs, how many number of ways can you climb if u use either 1 or 2 at a time? (Original question) Solutions: Java

Solve the “FizzBuzz” problem (needs no introduction). Solutions: Java

Implement Conway's game of life by predicting the next state of a matrix given its current state. Solutions: Java

Algorithms on Graphs (Java). Comprises of the following algorithms:

• BFS
• DFS
• Kruskal (MST)
• Prim (MST)
• Modified Dijkstra (SSSP)
• Bellman-Ford (SSSP)
• Floyd-Warshall (APSP)

You are given an M by N matrix containing only the characters 'P' and 'T'. You can flip the characters in any number of columns. I.e. 'P' becomes 'T' and 'T' becomes 'P' for all characters under that column. Your aim is to maximize the number of rows for which all the characters are the same.Solutions: Java

Implement integer division without using / or % in O(logN). Solutions: Java

You are given a binary array with N elements: d[0], d[1], ... d[N - 1]. You can perform AT MOST one move on the array: choose any two integers and flip all the elements between (and including) them. What is the maximum number of '1'-bits which you can obtain in the final bit-string? (Original question) Solutions: Java

Implement Karatsuba's multiplication algorithm. (Just a practice. No way this question will be tested) Solutions: Java

Implement Knuth shuffle. Solutions: Java

Given two strings, find the Longest Common Subsequence between them. Solutions: Java

Given two strings, find the Longest Common Substring between them. Solutions: Java

Given an array of integers, find the Longest Increasing Subsequence of its items. Solutions: Java

Given two strings, find the Longest Palindromic Subsequence between them. Solutions: Java

Given two strings, find the Longest Palindromic Substring between them. Solutions: Java

Implement Kadane's algorithm, returning the maximum subarray sum as well as the start and end indexes representing the maximum subarray. Solutions: Java

Implement merge sort. Solutions: Java

Implement a data structure that supports "find minimum" on top of the other stack operations "push" and "pop" in O(1). Space Complexity for finding minimum element should be O(1) Solutions: Java

Given a sorted list of numbers, write a function to return a string representing the missing numbers from 0 to 99 inclusive. (Original question) Solutions: Java

You have an array containing information regarding n people. Each person is described using a string (their name) and a number (their position along a number line). Each person has three friends, which are the three people whose number is nearest to their own. Describe an algorithm to identify each person's three friends. (Original question) Solutions: Java

Write a function strstr (char[] haystack, char[] needle) to return the first index occurrence of needle in haystack. If needle is not present in haystack, return -1. (Original question) Solutions: Java

Implement numeric addition of two numbers in both decimal as well as binary. Solutions: Java

An array is given consisting of integer numbers. Each number except one appears exactly twice. The remaining number appears only once in the array. Write a function which returns a number which appears only once in the array. What if we have a different array where every number appears thrice except one number which appear once?. Solutions: Java

Order Statistics. Comprises of the following algorithms:

• Kth smallest
• median

Implement a queue using 2 stacks. Solutions: Java

Implement quick sort. Solutions: Java

A kidnaper wishes to write a ransom note using letters from a magazine article. You are given with the ransom note and magazine article find whether kidnaper can write a note using the article or not. (Original question) Solutions: Java

Reverse an array in-place. Solutions: Java

Reverse the order of words in a sentence, but keep words themselves unchanged. Words in a sentence are divided by blanks. For instance, the reversed output should be "student. a am I" when the input is "I am a student.". (Original question) Solutions: Java

Given a matrix, rotate it clockwise by 90 degrees. Solutions: Java

Algorithms for set operations. Comprises of the following operations:

• Intersection of two lists
• Union of two lists
• n-way intersection of n lists

Given two sorted arrays and a number k, find the kth largest number in the union of the two arrays. Do it in place. Solutions: Java

Implement square-root method wihtout using the Math library. Solutions: Java Python

One steps through integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous step. What is the minimum number of steps in order to get from x to y? The length of the first and the last step must be 1. (Original question) Solutions: Java

Given a string "aaabbbcc", compress it into "a3b3c2" in-place. (Original question) Solutions: Java

Given a string, print out all its permutations. Solutions: Java

Write a function that parses a string into integer. Solutions: Java

Given an array of integers, return all possible subsets of length n. Solutions: Java

Given an n*m matrix, for each cell, calculate the sum of values in its implicit sub-matrix where the top-left coordinate is (0, 0) and bottom right corner is the cell itself. Can you do it in-place? (Original question) Solutions: Java

Given an array and a number n, can you obtain n using a 2 numbers in the array? What about 3 numbers? Solutions: Java

Implement a deep-copy method for the class Thing which has a list of Thing objects. Solutions: Java

Given a string, write a function which prints all the subsets of the string. Now make the function to return only unique solutions. Solutions: Java

Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible. For example, if the input string is "applepie" and dictionary contains a standard set of English words, then we would return the string "apple pie" as output. (Original question) Solutions: Java