public class Count { public static void main (String [] args){ for (int i=0; i<100;i++){ System.out.println(i); } } }
1 1 2 3 5 8 13Write a function which takes as input an integer x an returns an array of integers filled with fibonacci numbers in order.
public class Fibonacci { public static int[] getSeries(int x){ int[] result = new int[x]; result[0]= 1; result[1]= 1; for (int i=2; i < x; i++){ result[i] = result[i-1] + result[i-2]; } return result; } public static void main (String [] args){ int[] fib = Fibonacci.getSeries(20); for (int i : fib){ System.out.println(i); } } }
public class Smallest{ public static void main(String[] args){ } }
Robot?toString()? why? can you override it?public
int foo(String x). What is (explain what each one's role is
using proper teminology):
m be an instance of some class.
m.x do?m.x fail?m.f(3) do?m.f(3) fail?m?m as an argument to some other function? That is, do x.f(m)?m++?System.out.println(m)?int x = m;?String x = m;?(m = n)?(m == n)?(m < n)?if (m) ...?(String) m?(Robot) m work?Strings into one?String is immutable?Problem Statement | |||||||||||||
A new device is being designed for all the post offices in Byteland. This device will make mail classification and delivery more efficient by automatically recognizing the addresses written on envelopes. You are responsible for the software component that determines if two addresses match. Given two Strings address1 and address2, determine if they match using the following procedure. First, remove all spaces from both addresses. Then, perform a case-insensitive string comparison. If the two strings are equal, return -1. Otherwise, return the leftmost 0-based position at which they differ (the index after removing the spaces). | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
| - | address1 and address2 will each contain between 0 and 50 characters, inclusive. | ||||||||||||
| - | address1 and address2 will contain only letters ('a'-'z', 'A'-'Z'), digits ('0'-'9'), and spaces. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. (c)2006, TopCoder, Inc. All rights reserved.
//Solution by tomekkulczynski //translated to Java by JM Vidal. public class PostOffice { public static int matchAddress(String a, String b) { String a2 = ""; String b2 = ""; int i; for(i=0; i<a.length(); i++){ if(a.charAt(i) != ' ') a2 += a.substring(i,i+1).toLowerCase(); } for(i=0; i<b.length(); i++){ if(b.charAt(i) != ' ') b2 += b.substring(i,i+1).toLowerCase(); } if(a2.equals(b2)) return -1; //The commented-out line is tomekkulczynski's solution, but it is //broken. It fails (IndexOutOfBounds) when comparing, say "Wall" //and "WallStreet" It is interesting to study why his solution //works (in C++) most of the time. //for(i=0; a2.charAt(i)==b2.charAt(i); i++); for(i=0; i< a2.length() && i < b2.length() && a2.charAt(i)==b2.charAt(i); i++); return i; } public static void main (String [] args){ System.out.println(PostOffice.matchAddress("145 West 44th Street", "145 west 44 th street")); System.out.println(PostOffice.matchAddress(" wall street ", "WallStreet")); System.out.println(PostOffice.matchAddress(" Wall Street", " Waal Street")); System.out.println(PostOffice.matchAddress(" A", "a ")); System.out.println(PostOffice.matchAddress("Wall", "WallStreet")); } }
Problem Statement | |||||||||||||
| A sequence of characters is called a fence if it consists of alternating '|' and '-' characters, like "|-|-|-|" or "-|-|" (quotes for clarity only). Notice that "|-||-|" or "--" are not fences, because each contains two equal characters adjacent to each other. Given a string s, find the longest consecutive substring of it that is a fence, and return its length. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
| - | s will contain between 1 and 50 characters, inclusive. | ||||||||||||
| - | Each character of s will be either '|' or '-'. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||
| 5) | |||||||||||||
| |||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. (c)2006, TopCoder, Inc. All rights reserved.
/** From topcoder.com: FunnyFence is a simple problem, which asks you to find the largest fence in a string. Coming up with an algorithm to solve the problem isn't too difficult, but while implementing it you must pay careful attention to avoid fencepost errors. Typically, to avoid bugs creeping into your implementation, you should code up the simplest algorithm you can think of that won't timeout. If you are afraid that the simple solution will timeout, you can then make small optimizations until your algorithm is fast enough. For example, the simple algorithm for FunnyFence is to go through every substring and test it to see if it is a fence. To do each test you can loop through each character in the substring and make sure that it is different from the one right before it. This will end up looking something like: smallest=infinity; for(start=0 ; start < s.length ; start++) for(end=start+1 ; end<= s.length ; end++) sub = s.subString(start,end) if( isFence(sub) ) smallest = max( smallest, sub.length) isFence() returns true if the substring is indeed a fence. Since there are O(n2) substrings we will call isFence() a total of O(n2) times. Each call to isFence() could take up to O(n) time, since it examines each character in the substring, so overall this algorithm is O(n3). Since n is at most 50, we have plenty of time to do the O(n3) operations. Code translated to Java by jmvidal*/ public class FunnyFence { //by jmvidal public static boolean isFence(String s){ if (s.length() == 1) return true; for (int i=1; i < s.length(); i++){ if (s.charAt(i) == s.charAt(i-1)) return false; if (s.charAt(i) != '-' && s.charAt(i) != '|') return false; } return true; } /** Top coder solution */ public static int getLength(String s){ int smallest = -99999999; for(int start=0; start < s.length(); start++){ for(int end = start+1; end <= s.length(); end++) { String sub = s.substring(start,end); if( FunnyFence.isFence(sub) ) smallest = Math.max(smallest, sub.length()); } } return smallest; } /** Their solution (above) seems extremely inefficient and overly complicated. Below is my solution to the problem which is much faster and seems to solve the problem. This solution assumes that s contains only the - and | characters, as their examples seem to imply.*/ public static int myGetLength(String s){ if (s.length() == 1) return 1; int maxLength = 1; int currentLength = 1; for (int i = 1; i<s.length(); i++){ if (s.charAt(i) != s.charAt(i-1)) currentLength++; else currentLength = 1; if (currentLength > maxLength) maxLength = currentLength; } return maxLength; } public static void main (String [] args){ System.out.println(FunnyFence.getLength("|-|-|")); System.out.println(FunnyFence.getLength("-|-|-|-")); System.out.println(FunnyFence.getLength("||||||")); System.out.println(FunnyFence.getLength("|-||-|-")); System.out.println(FunnyFence.getLength("|-|---|-|---|-|")); System.out.println(FunnyFence.getLength("|||-||--|--|---|-||-|-|-|--||---||-||-||-|--||")); System.out.println("---"); System.out.println(FunnyFence.myGetLength("|-|-|")); System.out.println(FunnyFence.myGetLength("-|-|-|-")); System.out.println(FunnyFence.myGetLength("||||||")); System.out.println(FunnyFence.myGetLength("|-||-|-")); System.out.println(FunnyFence.myGetLength("|-|---|-|---|-|")); System.out.println(FunnyFence.myGetLength("|||-||--|--|---|-||-|-|-|--||---||-||-||-|--||")); } }
Integer.toString(int x).
Problem Statement | |||||||||||||
| The town John lives in consists of a large number of streets numbered 1 to streets, inclusive. He insists on parking his car only on street numbers that are palindromic (i.e., they read the same forward and backward). He is currently located at street number now. Return the closest street where he can park his car. If there are multiple solutions, return the smallest among them. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | Leading zeroes shouldn't be considered. So you can't interpret "10" as "010" and consider it palindromic. | ||||||||||||
Constraints | |||||||||||||
| - | streets will be between 1 and 2147483647, inclusive. | ||||||||||||
| - | now will be between 1 and streets, inclusive. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. (c)2006, TopCoder, Inc. All rights reserved.
/** Solution by jmvidal */ public class CarParking{ public static boolean isPalindrome(int i){ String s = Integer.toString(i); for (int j=0; j< s.length() / 2; j++){ if (s.charAt(j) != s.charAt(s.length() - j - 1)) return false; } return true; } /** Solve it by simply searching in the order: now, now-1, now+1, now-2, now+2... But, make sure to stop if now+i > streets */ public static int closestShed(int now, int streets){ for (int i=0; ; i++){ //yest, its an infinite loop, theoretically if ((now - i) >=0 && CarParking.isPalindrome(now - i)) return now - i; if ((now + i) <= streets && CarParking.isPalindrome(now + i)) return now + i; } } public static void main (String[] args){ System.out.println(CarParking.closestShed(19,22)); System.out.println(CarParking.closestShed(19,21)); System.out.println(CarParking.closestShed(9999,99999999)); System.out.println(CarParking.closestShed(9991,99999999)); System.out.println(CarParking.closestShed(123456,99999999)); } }
DNAString which stores
as its member variable one such string, can turn itself into
a string, and implements a function called
positionOf which takes as input a string and
returns the starting position of that substring in the DNA
string. That is, the following code: public class DNAString {should produce the following output:/** The gene. I choose to represent it as an array since its is then more natural to access random positions and I can change it in place without copying the whole thing (Remember: Strings are immutable). */ protected char[] strand; public DNAString(int length){ strand= new char[length]; } public void set(String g){ for (int i=0; i < g.length(); i++){ strand[i] = g.charAt(i); } } public String toString(){ String result = ""; for (char g : strand){ result += g; } return result; } /** @param s the substring we are looking for. Returns the starting position of s in this DNAString or -1 if s is not found anywhere in this strand */ public int positionOf(String s){ for (int i=0; i < strand.length - s.length(); i++){ boolean match = true; for (int j =0; j< s.length(); j++){ if (strand[i+j] != s.charAt(j)) { match = false; break; } } if (match) { return i; } } return -1; }public static void main (String [] args){ String joeDNA = "AGCTGAAAAAGTCCCCACGATCATCAAGACTTGACTACGCTAGC"; DNAString joe = new DNAString(joeDNA.length()); joe.set(joeDNA); System.out.println(joe); System.out.println("AAGT is first found at position " + joe.positionOf("AAGT")); } }
AGCTGAAAAAGTCCCCACGATCATCAAGACTTGACTACGCTAGC AAGT is first found at position 8
DNAString and overrides the positionOf
to take as input Strings that might also contain the '*'
character, which is allowed to match any letter. Thus the following code:
produces the following outputpublic class DNAString2 extends DNAString { public DNAString2(int l){ super(l); } /** @param s the substring we are looking for. The '*' character means that we don't care which letter is in that position. Returns the starting position of s in this DNAString or -1 if s is not found anywhere in this strand */ public int positionOf(String s){ for (int i=0; i < strand.length - s.length(); i++){ boolean match = true; for (int j =0; j< s.length(); j++){ if (s.charAt(j) != '*' && strand[i+j] != s.charAt(j)) { match = false; break; } } if (match) { return i; } } return -1; }public static void main (String [] args){ String joeDNA = "AGAACTGAAAAAGTCCCCACGATCATCAAGACTTGACTACGCTAGC"; DNAString2 joe = new DNAString2(joeDNA.length()); joe.set(joeDNA); System.out.println(joe); System.out.println("AA*T is first found at position " + joe.positionOf("AA*T")); }}
AGAACTGAAAAAGTCCCCACGATCATCAAGACTTGACTACGCTAGC AA*T is first found at position 2
//Recording.java import java.util.Scanner; public abstract class Recording{ /** The total time of this recording, in seconds.*/ private double duration; /** The title */ private String title; public Recording(String title, double duration){ this.title = title; this.duration = duration;}/** Create me by reading a string (which can contain spaces) folloed by a double */ public Recording(Scanner in){ title = ""; while (!in.hasNextDouble()){ title += in.next() + " "; } title = title.trim(); //gets rid of the extra space at the end. duration = in.nextDouble(); } public String toString(){ return title + " " + duration; }}
//AudioRecording.java import java.util.Scanner; public class AudioRecording extends Recording { /** Bit rate (Sampling rate) in kpbs */ private double sample; /** Artist's name */ private String artist; public AudioRecording(String title, double duration, String artist, double sample){ super(title, duration); this.artist = artist; this.sample = sample; }/** Create me by reading from a file */ public AudioRecording(Scanner in){ super(in); artist = ""; while (!in.hasNextDouble()){ artist += in.next() + " "; } artist = artist.trim(); sample = in.nextDouble(); } public String toString(){ return "audio " + super.toString() + " " + artist + " " + sample; }}
//VideoRecording.java import java.util.Scanner; public class VideoRecording extends Recording { /** x resolution */ private int xResolution; /** y resolution */ private int yResolution; public VideoRecording(String title, double duration, int x, int y){ super(title,duration); this.xResolution = x; this.yResolution = y;}/** Create me by reading from a file */ public VideoRecording(Scanner in){ super(in); this.xResolution = in.nextInt(); this.yResolution = in.nextInt(); in.nextLine(); } public String toString(){ return "video " + super.toString() + " " + xResolution + " " + yResolution; }}
//MyTunes.java import java.io.*; import java.util.*; public class MyTunes { private Recording[] m;If you can't write the function for one of these questions and you need it for a following question, don't worry. Simply write in English what the function should do and assume that it has been correctly implemented./** Create an instance of the database by reading every Recording from a file */ public MyTunes (String filename){ try { Scanner in = new Scanner(new File(filename)); m = new Recording[in.nextInt()]; in.nextLine(); int i = 0; while (in.hasNext()){ String type = in.next(); if (type.equals("audio")){ m[i] = new AudioRecording(in); } else { //it must be video m[i] = new VideoRecording(in); } i++; } } } /** Writes the whole array to a string. The first number is the number of items in the array. */ public String toString(){ String result = ""; result += m.length + "\n"; for (Recording r : m){ result += r + "\n"; } return result;} /** @param filname is the name of the file Write m to filename. */ public void writeToFile(String filename){ try { PrintWriter out = new PrintWriter(filename); out.print(this); out.close(); } catch (FileNotFoundException ex) { System.out.println(ex.getMessage()); } }public static void main(String[] a){ //Read it all from a file MyTunes mine = new MyTunes("recs.txt"); //Print it to screen System.out.println(mine); //Write it to a file mine.writeToFile("recs2.txt"); //recs.txt and recs2.txt should now be identical. } }
toString() functions for
AudioRecording, VideoRecording and
Recording. These return a string with all the
values for the instance variables. Make sure that the data is
returned in a format that is easy to parse as you will be
writting functions to read that data in the next questions.toString() function for
MyTunes. It should return a string with the values
for all the elements in its instance variable m. It
should use the functions from the previous question. toString() functions you
defined above, write the code to write the m array
from MyTunes into a file. That is, implement the
writeToFile function that is called from the
main in the code above.AudioRecording, VideoRecording and
Recording which take as input a
Scanner and read their instance variable values
from it. Assume that the data is in the format (order)
implemented by your toString() methods. Note that
to do this you might need to make minor changes to your
toString() methods. MyTunes constructor which
takes as input a filename and populates his instance variable
m by reading all the recodings in that file. Use
the constructors from the previous question and assume the file
was written using the MyTunes toString()
function.