ATuring
BAN USERJust practicing
- 0of 0 votes
Answers// You are given a rectangular grid of binary pixels that can be black or white.
- ATuring in United States
// Some of the pixels may be black, but you don't initially know how many or
// where.
//
// Given a starting point (x,y), fill (i.e. make black) the region the pixel is
// in.
. . . . . . . . . . . . . . . . . . . .
. X X X . . X X X . . X X X . . X X X .
. X * X X X X . X . . X X X X X X X X .
. X . . . . . . X . -- > . X X X X X X X X .
. X . . . . . . X . . X X X X X X X X .
. X X X X X X X X . . X X X X X X X X .
. . . . . . . . . . . . . . . . . . . .
* . . . . . . . . . X X X X X X X X X X
. X X X . . X X X . X X X X X X X X X X
. X . X X X X . X . X X . X X X X . X X
. X . . . . . . X . --> X X . . . . . . X X
. X . . . . . . X . X X . . . . . . X X
. X X X X X X X X . X X X X X X X X X X
. . . . . . . . . . X X X X X X X X X X
See the correct drawing here: https://stackoverflow.com/questions/26079328/given-a-starting-point-x-y-fill-the-region-in-a-grid-the-pixel-is-located| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer
public static int[] relSort3(int[] arr){
int[] res=new int[arr.length];
int lastExch=0;
//sort negatives
for(int i=0; i<res.length; i++){
for(int j=lastExch; j<arr.length; j++ )
if(arr[j]<0){
res[i]=arr[j];
lastExch=j+1;
break;
}
}
int lastExch2=arr.length-1;
//sort positives
for(int i=res.length-1; i>0; i--){
for(int j=lastExch2; j>-1; j-- )
if(arr[j]>0){
res[i]=arr[j];
lastExch2=j-1;
break;
}
}
return res;
}
private static void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
See following,
import java.util.ArrayList;
import java.util.Arrays;
public class AnagramsInDict {
public static void main(String[] args){
String s="abc";
String[] anag={"bca", "cab", "xxx", "acb"};
int i=findAnagrams(s, anag);
System.out.println(i);
}
public static int findAnagrams(String s, String[] arr){
ArrayList<String> anagramList=new ArrayList<>();
char[] inString=s.toCharArray();
Arrays.sort(inString);
for(String ss: arr){
boolean isAnagram=true;
char[] elem=ss.toCharArray();
Arrays.sort(elem);
if(elem.length!=inString.length){
isAnagram=false;
}
else
{
for(int o=0; o<elem.length; o++){
if(elem[o]!=inString[o])
{isAnagram=false;}
}
}
if(isAnagram){
anagramList.add(ss);
}
}
return anagramList.size();
}
}
My elegant java solution:
public class MouseHole {
public static void main(String[] args){
int[] m={2, 0, -4};
int[] h={3, 1, 2, -1 };
int x=MouseHole.assignHoles(m, h);
System.out.println(x);
}
public static int assignHoles(int[] mouseP, int[] holes){
HashMap<Integer, Integer> hm=new HashMap<>();
for(int i : holes){
hm.put(i, 0);
}
int MaxTime=0;
for(int i: mouseP){
int minDis=Integer.MAX_VALUE;
int selectedHole=0;
for(int j: holes){
int dis=Math.abs(i-j);
if(minDis>dis && hm.get(j)==0){
minDis=dis;
selectedHole=j;
}
}
hm.put(selectedHole, 1);
MaxTime=Math.max(MaxTime, minDis);
}
return MaxTime;
}
}
How about this, it is java.
public static void main(String[] args){
char[] cc={'N','o','r','t','h','e','r','n',' ','C', 'a', 'l', 'i','f', 'o','r','n','i','a',' ','U','S','A'};
int start=cc.length-1;
for(int i=cc.length-1; i>=0; i--){
if(cc[i]==' ' || i==0)
{
for(int j=i; j<=start; j++){
System.out.print(cc[j]);
}
start=i;
}
}
}
public class PrimesTillN {
public static void main(String[] args){
PrimesTillN ptn=new PrimesTillN();
int input=30;
for(int i=2; i<input; i++){
if(ptn.IsPrime(i)){
System.out.println(i);
}
}
}
public boolean IsPrime(int n){
double sqrt=Math.sqrt(n);
for(int i=2; i<=sqrt; i++)
{
if (n%i==0){
return false;
}
}
return true;
}
}
My recursive java solution
import java.util.HashMap;
import java.util.Map;
public class ContigentOrder {
/*returns length of contigent orders starting from "start" order*/
public int getLength(int[] start, HashMap<Integer, Integer> map, int length)
{
if(!map.containsKey(start[1])){
return length;
}
int[] s=new int[2];
//end time of input, is start time of next order
s[0]=start[1];
//returns end time of next order
s[1]=map.get(start[1]);
int len=start[1]-start[0];
return length=length+getLength(s , map, s[1]-s[0]);
}
public static void main(String[] args){
int[] o1={1,5};
int[] o2={5,10};
int[] o3={10,15};
int[] o4={15,20};
int[] o5={25,28};
int[] o6={28,32};
HashMap<Integer, Integer> hm=new HashMap<>();
hm.put(o1[0], o1[1]);
hm.put(o2[0], o2[1]);
hm.put(o3[0], o3[1]);
hm.put(o4[0], o4[1]);
hm.put(o5[0], o5[1]);
hm.put(o6[0], o6[1]);
ContigentOrder co=new ContigentOrder();
int maxLength=0;
for(Map.Entry<Integer, Integer> m: hm.entrySet()){
int[] in={m.getKey(), m.getValue()};
int len=co.getLength(in, hm, in[1]-in[0]);
if(len>maxLength){
maxLength=len;
}
}
System.out.println(maxLength);
}
}
Following code has no limitation in terms duplicates. Also it can find common elements in any number of arrays, not only five. However, its time complexity is not very good because of retainAll method. It is very clean solution though. If there is no time constraints this could be a good solution.
import java.util.HashSet;
import java.util.ArrayList;
public class FindCommonElements {
public HashSet<Integer> findCommons(ArrayList<int[]> listOfElemens){
HashSet<Integer> set=new HashSet<Integer>();
int[] firstList=listOfElemens.get(0);
for(int i: firstList)
set.add(i);
for(int[] list: listOfElemens){
HashSet<Integer> tempSet=new HashSet<>();
for(int i: list)
tempSet.add(i);
//finds intersection of two sets
set.retainAll(tempSet);
}
return set;
}
public static void main(String[] args){
int arr1[] = {7,10,12,5,5};
int arr2[] = {8,7,10,5,5};
int arr3[] = {7,10,9,5,5};
int arr4[] = {13,10,7,5,5};
int arr5[] = {6,7,7,5,5,10};
ArrayList<int[]> listOrArrs=new ArrayList<>();
listOrArrs.add(arr1);
listOrArrs.add(arr2);
listOrArrs.add(arr3);
listOrArrs.add(arr4);
listOrArrs.add(arr5);
FindCommonElements fce=new FindCommonElements();
HashSet<Integer> set=fce.findCommons(listOrArrs);
System.out.print(set);
}
}
public static void main(String[] args){
Scanner in= new Scanner(System.in);
String s= in.next();
ArrayList<Character> currentLogest=new ArrayList<>();
ArrayList<Character> current=new ArrayList<>();
char prev = s.toCharArray()[0];
for(char c : s.toCharArray()){
if(prev==c)
{
current.add(c);
prev=c;
if(current.size()>currentLogest.size())
{
currentLogest=new ArrayList<>();
currentLogest=current;
}
}
else
{
current=new ArrayList<>();
current.add(c);
prev=c;
System.out.println(current);
if(current.size()>currentLogest.size()){
currentLogest=new ArrayList<>();
currentLogest=current;
}
}
}
System.out.println("Size: " + currentLogest.size() + " longest run: " + currentLogest );
}
My java like solution, it assumes there is a function "Parent" which returns parent node:
Node commonParent(Node n1, Node n2){
int deptN1, deptN2;
Node current=n1;
//find dept of node1
while(current!=root){
current=Parent(current);
deptN1++
}
current=n2;
//finde dept of node 2
while(current!=root){
current=Parent(current);
deptN2++
}
Node fromN1=n1, fromN2=n2;
//n1 was in lower level
if(deptN1>deptN2)
{
for(int i=0; i<(deptN1-deptN2); i++){
fromN1=Parent(fromN1);
}
Node x1=Parent(fromN1);
Node x2=Parent(n2);
if(x1==x2){
return x1;
}
else {
commonParent(x1,x2);
}
//n2 is in lower level
} else if(deptN1<deptN2){
for(int i=0; i<(deptN2-deptN1); i++){
fromN1=Parent(fromN1);
}
Node x1=Parent(n1);
Node x2=Parent(fromN2);
if(x1==x2){
return x1;
}
else {
commonParent(x1,x2);
}
// both node are in same level
else
{
Node x1=Parent(n1);
Node x2=Parent(n2);
if(x1==x2){
return x1;
}
else {
commonParent(x1,x2);
}
}
}
}
Java solution:
public static void main(String args[]){
Scanner in=new Scanner(System.in);
String input=in.next();
char currentVal=' ';
for(int i=0; i<input.length(); i++){
if(input.charAt(i)!=currentVal && input.charAt(i)==input.charAt(i+1) )
{
System.out.println(i);
currentVal=input.charAt(i);
}
else
{
currentVal=input.charAt(i);
}
}
}
I solved problem in java,
public static void main(String[] args){
Scanner in= new Scanner(System.in);
String s= in.next();
ArrayList<Character> currentLogest=new ArrayList<>();
ArrayList<Character> current=new ArrayList<>();
int lengtOfcurrentLongest=0, currentLength=0;
char prev = s.toCharArray()[0];
for(char c : s.toCharArray()){
if(prev==c)
{
current.add(c);
prev=c;
if(current.size()>currentLogest.size())
{
currentLogest=new ArrayList<>();
currentLogest=current;
}
}
else
{
current=new ArrayList<>();
current.add(c);
prev=c;
System.out.println(current);
if(current.size()>currentLogest.size()){
currentLogest=new ArrayList<>();
currentLogest=current;
}
}
}
System.out.println("Size: " + currentLogest.size() + " longest run: " + currentLogest );
}
Iterative Java Solution O(N), recursive one will take exponential time O(2^n)
public int fibIter(int n){
int fn=0, fnMinus1=1, fnMinus2=0;
for(int i=2; i<=n; i++){
fn=fnMinus1+fnMinus2;
fnMinus2=fnMinus1;
fnMinus1=fn;
System.out.print(fn);
}
System.out.print(fn);
return fn;
}
Java Solution:
public void HexToInt(String s)
{
char[] cArr=s.toCharArray();
HashMap<Character, Integer> hexVal=new HashMap<Character,Integer>();
hexVal.put('A', 10);
hexVal.put('B', 11);
hexVal.put('C', 12);
hexVal.put('D', 13);
hexVal.put('E', 14);
hexVal.put('F', 15);
int intVer=0;
int counter=0;
for(int i=cArr.length-1; i>=0; i--)
{
if(hexVal.containsKey(cArr[i]))
{
intVer=intVer+ (int) Math.pow(16, counter)*hexVal.get(cArr[i]);
}
else
{
intVer=intVer+((int) Math.pow(16, counter))*Character.getNumericValue(cArr[i]);
}
counter++;
}
System.out.println("\nhexToInt:" + intVer);
}
Java solution with Set intersection
public Set FindCommonElements(Integer[] first, Integer[] second)
{
Set<Integer> set1=new HashSet<Integer>(Arrays.asList(first));
Set<Integer> set2=new HashSet<Integer>(Arrays.asList(second));
// finds intersecting elements in two sets
set1.retainAll(set2);
return set1;
}
Java solution, returns the number which occurs even number of times.
public Integer findItemWEvenOcc(int[] in)
{
Map<Integer, Integer> myMap=new HashMap<Integer,Integer>();
for(int i : in)
{
if(!myMap.containsKey(i))
{
myMap.put(i, 1);
}
else
{
int numberOfOccurance=myMap.get(i);
numberOfOccurance++;
myMap.put(i, numberOfOccurance);
}
}
for(Map.Entry<Integer, Integer> kv : myMap.entrySet())
{
if(kv.getValue()%2==0)
{
return kv.getKey();
}
}
return null;
}
- ATuring October 22, 2014