Mahmoud El-Maghraby
BAN USERpublic class SumSubSequence
{
public static String getSumSubSequence(int[] list, int sum)
{
for (int i = 0; i < list.length; i++)
{
int currentSum = 0;
int j = i;
for (; j < list.length; j++)
{
currentSum += list[j];
if (currentSum == sum)
return "(" + i + "," + j + ")";
else if (currentSum > sum)
break;
}
if (j == list.length)
return "Not Found";
}
return "Not Found";
}
public static void main(String[] args)
{
int[] seq = { 1, 7, 6, 3, 5, 8, 9 };
System.out.println(getSumSubSequence(seq, 9));
}
}
This one is O(n) to get the largest m numbers in an array of size n
public class AdviseredAverage
{
public static double getAdviseredAverage(int[] list, int n)
{
if (n >= list.length)
{
System.out.println(" Input Error: n must be < list.length");
return -1;
}
// Intialize elimination list
int[] eliminationList = new int[n];
// Initialize currentMin in elimination
int currentMin = list[0];
int currentMinIndex = 0;
// Initialize sum to 0
int sum = 0;
for (int i = 0; i < n; i++)
{
eliminationList[i] = list[i];
if (eliminationList[i] < currentMin)
{
// update minimum
currentMin = eliminationList[i];
currentMinIndex = i;
}
sum += list[i];
}
for (int i = n; i < list.length; i++)
{
if (list[i] > currentMin)
{
eliminationList[currentMinIndex] = list[i];
// update minimum
currentMin = eliminationList[0];
currentMinIndex = 0;
for (int j = 0; j < n; j++)
{
if (eliminationList[j] < currentMin)
{
// update minimum
currentMin = eliminationList[j];
currentMinIndex = j;
}
}
}
// add current number to sum
sum += list[i];
}
// subtract largest n numbers from sum
for (int i = 0; i < n; i++)
{
sum -= eliminationList[i];
}
return (double) (((double) sum) / ((double) (list.length - n)));
}
public static void main(String[] args)
{
int[] list = { 15,500,16,18,29,65,98,789,654,12,32,59,744,32,56,1254,12 };
System.out.println(getAdviseredAverage(list, 5));
}
}
public class LookAndSay
{
public static String[] lookAndSay(String initialNum)
{
String[] result = new String[10]; // result array
String currentSeq = initialNum; // initialize current seq
// outer loop to generate 10 sequences
for (int i = 0; i < 10; i++)
{
char currentDigit = currentSeq.charAt(0); // current digit
int cnt = 1; // number of repetitions of that digit
String newSeq = "";
for (int j = 1; j < currentSeq.length(); j++)
{
// count current digit
if (currentSeq.charAt(j) == currentDigit)
cnt++;
else
{
// append count of current digit along with the
// digit itself
newSeq += cnt + "" + currentDigit;
// reintialize current digit and count
currentDigit = currentSeq.charAt(j);
cnt = 1;
}
}
newSeq += cnt + "" + currentDigit;
result[i] = newSeq;
currentSeq = newSeq;
}
return result;
}
public static void main(String[] args)
{
String[] las = lookAndSay("1");
for (String seq : las)
System.out.println(seq);
}
}
public class PasswordChecker
{
public static boolean isValidPassword(String input, String expected)
{
String temp = "";
// remove all possible characters once at a time
for (int i = (int) '1'; i <= (int) '9'; i++)
{
// Check if current character exists in expected pw and
// doesn’t exist in input
if (!input.contains(((char) i)+"") && expected.contains(((char) i)+""))
{
// remove all occurrences of character in expected
temp = expected.replaceAll(((char) i)+"", "");
// return true if it is the same as input
if (input.equals(temp))
return true;
}
}
return false;
}
public static void main(String[] args)
{
System.out.println(isValidPassword("1698324786", "15698532547856")); // true
System.out.println(isValidPassword("16983286", "15698532547856")); // false
}
}
import java.util.ArrayList;
public class PalindromeFinder
{
public static ArrayList<String> getPalindromes(String s)
{
ArrayList<String> initialPalindromes = new ArrayList<String>();
for (int i = 0; i < s.length(); i++)
{
String currentPalindrome = s.charAt(i) + "";
int j = 1;
boolean palindromeEnded = false;
while (i - j >= 0 && i + j < s.length() && !palindromeEnded)
{
if (s.charAt(i - j) == s.charAt(i + j))
currentPalindrome = s.charAt(i - j) + currentPalindrome
+ s.charAt(i + j);
else
palindromeEnded = true;
j++;
}
if (currentPalindrome.length() >= 3)
{
initialPalindromes.add(currentPalindrome);
}
}
ArrayList<String> finalPalindromes = new ArrayList<String>();
for (String palindrome : initialPalindromes)
{
int palLingth = palindrome.length();
int maxOffset = (palindrome.length() / 2) - 1;
for (int i = 0; i <= maxOffset; i++)
finalPalindromes
.add(palindrome.substring(0 + i, palLingth - i));
}
return finalPalindromes;
}
public static void main(String args[])
{
String s = "abcdefedcba1234543454321";
ArrayList<String> palindromes = getPalindromes(s);
for (String palindrome : palindromes)
System.out.println(palindrome);
}
}
import java.util.ArrayList;
public class WellOrderedStrings
{
public static ArrayList<String> getWellOrderedStrings(int length)
{
if (length > 26 * 2) // all lower case and upper case letters
System.out.println("Error: length must be <= 52");
// String of all alphabet
String alphabet = "abcdefghijklmnobqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
// List of all found sequences till now
ArrayList<String> allSeqs = new ArrayList<String>();
for (int i = alphabet.length() - 1; i >= 0; i--)
{
// List of new generated sequences
ArrayList<String> newSeqs = new ArrayList<String>();
// Add new sequences
for (String seq : allSeqs)
{
// interested only in sequences <= length
if (seq.length() <= length - 1)
newSeqs.add(alphabet.charAt(i) + seq);
}
allSeqs.addAll(newSeqs);
allSeqs.add(alphabet.charAt(i) + "");
}
// List of final results
ArrayList<String> finalResult = new ArrayList<String>();
for (String seq : allSeqs)
{
if (seq.length() == length)
{
finalResult.add(seq);
}
}
// Print size of final list
System.out.println(finalResult.size());
return finalResult;
}
public static void main(String args[])
{
getWellOrderedStrings(4);
}
}
public class IrreducibleFraction
{
public static String getIrreducibleFraction(double num)
{
int n = (int) (num * 10000);
int d = 10000;
// get greatest common divisior
int gcd = getGCD(n, d);
return ((n / gcd) + "/" + (d / gcd));
}
private static int getGCD(int a, int b)
{
if (a == 0)
return b;
while (a != b)
{
if (a > b)
a = a - b;
else if (b > a)
b = b - a;
else
return a;
}
return a;
}
public static void main(String args[])
{
System.out.println(getIrreducibleFraction(0.1));
}
}
import java.util.ArrayList;
import java.util.HashSet;
public class CombineLists
{
public static ArrayList<String> getCombinedList(String[] l1, String[] l2)
{
HashSet<String> hashSet = new HashSet<String>();
ArrayList<String> combinedList = new ArrayList<String>();
for (int i = 0; i < l1.length; i++)
{
if (hashSet.add(l1[i].toLowerCase()))
{
combinedList.add(l1[i]);
}
}
for (int i = 0; i < l2.length; i++)
{
if (!hashSet.contains(l2[i].toLowerCase()))
{
combinedList.add(l2[i]);
}
}
return combinedList;
}
public static void main(String[] args)
{
String[] l1 = { "a", "b", "c", "d", "e" };
String[] l2 = { "f", "b", "g", "d", "h" };
ArrayList<String> combinedList = getCombinedList(l1, l2);
for (String item : combinedList)
System.out.println(item);
}
}
- Mahmoud El-Maghraby June 30, 2014