ethioer
BAN USERpublic void drawing(int n) {
int middler = n/2;
for (int i=0 ; i < n ; i++) {
int nonPaint = Math.abs(middler-i);
for (int j=0; j < n ; j++) {
if (j < nonPaint || n-j-1 < nonPaint) {
System.out.print(" ");
} else {
System.out.print("*");
}
}
System.out.println("");
}
}
I am approaching it with file sort. This is a storage expensive in that it would create another file of the same type. The idea is to get a sorted list and and find the numbers afterwards. it has complexity of n^2.
There are ways to make it better with usage of the chunk hint given... at least it would be a quick and dirty solution :)
Another approach could be using linux to sort the file and utilize that, in that case the complexity would reduce to nlogn assuming the internal sort by linux would be nlogn
package algorithm;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
/**
* Assumption: the numbers are read from file and they are sequential
*
*
*/
public class MissingNumbers {
//source file
private static String FILE_PATH = "/tmp/random-thousands.txt";
//final sorted file
private static String FILE_SORTED_PATH = "/tmp/sorted-thousands.txt";
public static void main(String str[]) {
PrintWriter writer = null;
try {
MissingNumbers missingNumbers = new MissingNumbers();
writer = new PrintWriter(FILE_SORTED_PATH);
writer.write("");
writer.close();
writer = new PrintWriter(FILE_PATH);
writer.write("");
missingNumbers.createRecords();
missingNumbers.createSortedFileList();
List<Integer> numbersLost = missingNumbers.findMissing();
for (Integer numbers:numbersLost) {
System.out.println(numbers);
}
} catch (Exception ex) {
System.out.println(ex.getMessage());
}
writer.close();
}
/**
* find the missing numbers from the billion numbers.
*
* The file would be provided as random populated file. First the file would be
* sorted on the file basis and then it would be read from top to bottom and checked for
* missing number.
* @return
*/
public void createSortedFileList() {
try {
FileReader randomReader = new FileReader(FILE_PATH);
BufferedReader bufferedRandomReader = new BufferedReader(randomReader);
RandomAccessFile sortedAccess = new RandomAccessFile(FILE_SORTED_PATH, "rw");
String currentRandom = null;
String currentSorted = null;
Long lastPointer = null;
while ((currentRandom = bufferedRandomReader.readLine()) != null) {
int currentSortedInt = 0;
//set the file pointer
lastPointer = sortedAccess.length();
sortedAccess.seek(lastPointer);
/*
* Write the numbers in such a way that the length of the written numbers
* is in equal size to make the calculation much easier since we are readin
* by size of the numbers.
*/
sortedAccess.writeBytes(String.format("%04d\n", Integer.parseInt(currentRandom))); //append it at the end
lastPointer = sortedAccess.length()-("0000\n".length());
sortedAccess.seek(lastPointer);
while ((currentSorted = sortedAccess.readLine()) != null && lastPointer >= 5) {
currentSortedInt = Integer.parseInt(currentSorted);
lastPointer -= "0000\n".length();
sortedAccess.seek(lastPointer);
String rawUpper = sortedAccess.readLine();
int upperSorted = Integer.parseInt(rawUpper);
if (currentSortedInt < upperSorted) {
sortedAccess.seek(lastPointer);
sortedAccess.writeBytes(currentSorted+"\n");
lastPointer += "0000\n".length();
sortedAccess.seek(lastPointer);
sortedAccess.writeBytes(rawUpper+"\n");
lastPointer -= "0000\n".length();
sortedAccess.seek(lastPointer);
} else {
break;
}
}
}
//release the resource
bufferedRandomReader.close();
sortedAccess.close();
} catch (FileNotFoundException foe) {
System.out.println(foe.getMessage());
} catch (IOException io) {
System.out.println(io.getMessage());
} catch (Exception ex) {
System.out.println(ex.getMessage());
}
}
/**
* At this level there is a file on FILE_SORTED_PATH which is sorted in ascending.
* go through the file and search for the missing ones. The missing ones can be
* found when the continuity is broken
* @return
*/
public List<Integer> findMissing() {
List<Integer> missingNumbers = null;
try {
FileReader fileReader = new FileReader(FILE_SORTED_PATH);
BufferedReader bufferedReader = new BufferedReader(fileReader);
missingNumbers = new ArrayList<Integer>();
String line = null;
int prevNumber = Integer.parseInt(bufferedReader.readLine());
while ((line = bufferedReader.readLine()) != null) {
int currentNumber = Integer.parseInt(line);
if (currentNumber - prevNumber != 1) {
missingNumbers.add(currentNumber-1);//the missing number is less by 1
}
prevNumber = currentNumber;
}
fileReader.close();
} catch (IOException ioe) {
//log it
}
return missingNumbers;
}
/**
* Creates 1000 that are random and put those in /tmp/random-thousands.txt
*/
public void createRecords() {
//get 20 random numbers that would be considered as missing
Map<Integer, Integer> randomHolder = new HashMap<Integer, Integer>();
Random random = new Random();
while (randomHolder.size() <= 20) {
int rand = random.nextInt(1000)+1;
if (!randomHolder.containsKey(rand)) {
randomHolder.put(rand, rand);
}
}
//now we have random numbers get all the numbers
int[] temp = new int[980];//make it to hold 980 elements, assume 20 is missing
//fill the numbers
int size = 1;
int index = 0;
while (index < 980) {
if (!randomHolder.containsKey(size)) {
temp[index++] = size;
}
size++;
}
//finally shuffle the numbers.
for (int i=0; i<980 ; i++) {
int rand = random.nextInt(980);
int holder = temp[i];
temp[i] = temp[rand];
temp[rand] = holder;
}
//finally write those to the file
try (FileWriter fileWriter = new FileWriter(FILE_PATH, true);) {
for (int i=0;i<980;i++) {
fileWriter.append(String.format("%s\n", temp[i]));
}
} catch (IOException io) {
System.out.println(io.getMessage());
}
}
}
public class LongestPalindrom {
public static void main(String[] args) {
LongestPalindrom longest = new LongestPalindrom();
System.out.println(longest.longest("aabcbcbdcc"));
}
public String longest(String string) {
if (string.length() == 0 || string == null) {
return "";
}
StringBuffer palindrom = new StringBuffer();
Map<Character, Integer> charBag = new HashMap<Character, Integer>();
for (Character c : string.toCharArray()) {
int totalChar = charBag.get(c) != null ? charBag.get(c) : 0;
if ((totalChar + 1) % 2 == 0) {
palindrom.append(c);
palindrom = palindrom.insert(0, c);
charBag.remove(c);
continue;
}
charBag.put(c, ++totalChar);
}
if (charBag.size() > 0) {
Iterator it = charBag.entrySet().iterator();
Map.Entry pair = (Map.Entry<Character, Integer>)it.next();
String c = pair.getKey().toString();
palindrom.insert(palindrom.length()/2, c);
}
return palindrom.toString();
}
}
package algorithm;
public class Algos {
public static void main(String args[]) {
Algos algos = new Algos();
System.out.println(algos.toHour("00:00"));
}
public String toHour(String hrs24)
{
if (hrs24 == null) {
return "";
}
String[] time = hrs24.split(":");
Integer hour = Integer.parseInt(time[0]);
if (hour < 0 || hour > 24) return "Invalid hour provided";
Integer formatted = hour <= 12 ? hour : hour-12;
String meridian = hour < 12 ? "AM" : "PM";
return formatted + ":" + time[1] + meridian;
}
}
My approach would be to create three trees of height 7. Lets say the number is 800-123-4567 and 1=> a,b,c 2=>d,e,f ...
so tree one will be with root a and children def. tree two will be with root b and children d,e,f.. and each d, e, and f will have their own .. then it will be direct tree traversal from root to leaf will represent one phone number..
I don't see any restriction on the usage of specific approach.. so here is the best approach.
Have a hash table of size 26 or 52 assuming i will contain only alphabet..
hash['H']=1;
hash['a']=1;
hash['l']=1;..
this will be done in o(n)
then do in o(m) for destination and increment the number when the hash contains the value only..
public static void main(String[] args){
String source = "Hello World";
String dest = "llldk";
Hashtable<Character, Character> hash = new Hashtable<Character, Character>();
for(Character a : source.toCharArray()){
hash.put(a, a);
}
int total=0;
for(Character b : dest.toCharArray()){
if (hash.contains(b)){
total++;
}
}
System.out.println(total);
}
Here is the code with complexity log(n)
#include <stdio.h>
/*
* Find the first occurence of the given number in index.
*/
void main()
{
int nums[] = {1,1,3,5,8,8,8,10,12,23,23,55};
int len = sizeof(nums)/sizeof(int);
int start = 0, end = len-1, search = 8;
int found_right = -1;
while ((end - start) > 1)
{
if (found_right != -1)
{
if (nums[end] != search)
{
break;
}
found_right = end;
end -= 1;
continue;
}
int mid = (end + start)/2;
int val = nums[mid];
if (val == search)
{
end = mid-1;
found_right = mid;
}
else if(val < search)
{
start = mid;
}
else
{
end = mid;
}
}
if (found_right != -1)
{
printf("found at %d", found_right);
}
else
{
printf("Sorry!");
}
}
Making object mutable/nonmutable should not depend on what interface you implement or what class you extend.
There are basic differences on ArrayList and Vector or some other collections in java in regard to sycronization, allowing null values, keeping their order and the like - not with modifiebility as far as I know.
For immutability, you can consider using final keyword not change its values
I am not sure how you would implement trie on this case without sorting each word first alphabetically, like bag as abg and ball as abll.. in this case you would have single trie. now you would sort the input alphabetically and search it in the trie as the expense of space though.
- ethioer July 23, 2012Here is the step that I would follow:
1. I would have exactly the same configuration, hardware and OS wise as the customers.
2. I will be on the previous build that was before the update
3. I will work on the particular area that the users are complaining.
4. If I could not reproduce it on the previous build, I will update the build to the one with the users
5. I will try to repro the bug and see on what scenario it is creating the bug.
6. Will check if there is simple fix for it like from the configuration side. and if I can update to the prev build I will do that and see the impact of upgrade
7. I will notify the dev team what I have found, the steps that I user to repro.. so that it is easy for them to fix it
8. The feedback I would give to the developers is:
before rolling out a new code:
1. Make sure all the previous features are intact, or if there is a feature change make a brief note about it and let the users know that
2. Run the integration tests, unit tests and feature tests
3. After the update rollout, keep an eye on the users..
#include <stdio.h>
#include <string.h>
void main()
{
char * string = "darks. knoght, rises";
int size = strlen(string);
int i=0, word_counter=0;
while (i < size)
{
if (string[i] == ' ')
{
printf("%i ", word_counter);
word_counter = 0;
i++;
continue;
}
word_counter++;
i++;
}
if (word_counter)
{
printf("%i ", word_counter);
}
}
Here is a solution to the question in C.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node
{
char * value;
struct Node *next;
};
struct Node *head = NULL;
struct Node *tail = NULL;
char* substr(char*str, int start, int length)
{
const char* from = str;
char *to = (char*) malloc(sizeof(str)/sizeof(char));
strncpy(to, from+start, length);
return to;
}
void addToLinkedList(char* value)
{
struct Node *curr_node = malloc(sizeof(struct Node));
char * newtemp = malloc(strlen(value));
strncpy(newtemp, value, strlen(value));
curr_node->value = newtemp;
curr_node->next = NULL;
if (head == NULL)
{
head = curr_node;
tail = head;
}
else
{
last->next = curr_node;
tail = curr_node;
}
}
void printLinkedList()
{
struct Node * curr_node = head;
while (curr_node !=NULL)
{
printf("%s\n", curr_node->value);
curr_node = curr_node->next;
}
}
void main()
{
int delimiter_size = 3, i=0, j=0;
char* delimit = "abc";
char* text = "someabccodingabctoabcparseab";
int length = strlen(text);
char* temp = (char*)malloc(length);
while(i < length)
{
//is the delimiter starts or is this one?
if (text[i] == delimit[0]) //check if the begin
{
if (strcmp(substr(text, i, delimiter_size), delimit) == 0)
{
addToLinkedList(temp);
i+=delimiter_size;
j=0;
memset(temp, '', strlen(temp));
continue;
}
}
temp[j] = text[i];
i++;
j++;
}
if (strlen(temp))
{
addToLinkedList(temp);
}
printLinkedList();
}
here is the solution with o(n^2) since it involves rows and columns, I am not sure if it can be done with less complexity.
#include <stdio.h>
/*
* Print List as columns
*/
void main()
{
char vals[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
int length = sizeof(vals)/sizeof(char);
int rows = length/3;
int remainder = length%3;
if (remainder > 0)
{
rows++;
}
int i=0, j;
for (i=0; i<rows ; i++)
{
for (j=i ; j<=length ; j+=rows)
{
printf("%c", vals[j]);
}
printf("\n");
}
}
An interface has a number of usages.
1. We will adopt the great principle of P2I - program to interface. By which we will not adhere to the concrete implementation of rather to the interface, which will give a room for change later on
2. They act as contract for management. Any class which claims that it is implementing the interface shall adhere to the contract so that we are sure whenever we are using that class, the contract is satisfied - even without looking into the actual code
Real time examples - collection classes of Java -
RepMarryJohan, Consultant at ASAPInfosystemsPvtLtd
I am successfully manage and coordinate graphic design projects from concept through completion. Create and conduct highly persuasive sales and ...
- ethioer January 24, 2018