Google Interview Question
SDETsCountry: United States
Interview Type: Phone Interview
import java.util.*;
public class HelloWorld{
public static void main(String []args){
generate(6);
}
public static void generate(int number){
HashMap<Integer, HashMap<String, Integer>> cache = new HashMap<Integer, HashMap<String, Integer>>();
cache.put(0, new HashMap<String, Integer>());
cache.get(0).put("x", 3);
cache.get(0).put("y", 2);
cache.put(1, new HashMap<String, Integer>());
cache.get(1).put("x", 2);
cache.get(1).put("y", 1);
cache.put(2, new HashMap<String, Integer>());
cache.get(2).put("x", 2);
cache.get(2).put("y", 2);
cache.put(3, new HashMap<String, Integer>());
cache.get(3).put("x", 2);
cache.get(3).put("y", 3);
cache.put(4, new HashMap<String, Integer>());
cache.get(4).put("x", 1);
cache.get(4).put("y", 1);
cache.put(5, new HashMap<String, Integer>());
cache.get(5).put("x", 1);
cache.get(5).put("y", 2);
cache.put(6, new HashMap<String, Integer>());
cache.get(6).put("x", 1);
cache.get(6).put("y", 3);
cache.put(7, new HashMap<String, Integer>());
cache.get(7).put("x", 0);
cache.get(7).put("y", 1);
cache.put(8, new HashMap<String, Integer>());
cache.get(8).put("x", 0);
cache.get(8).put("y", 2);
cache.put(9, new HashMap<String, Integer>());
cache.get(9).put("x", 0);
cache.get(9).put("y", 3);
int[][] LMove= {{-1,-2},
{-1,2},
{1,2},
{1,-2},
{-2,-1},
{-2,1},
{2,-1},
{2,1}};
int currentX = cache.get(number).get("x");
int currentY = cache.get(number).get("y");
for (int[] move : LMove) {
int destX = currentX + move[0];
int destY = currentY + move[1];
HashMap<String, Integer> point= new HashMap<String, Integer>();
point.put("x", destX);
point.put("y", destY);
int destNum = getKeyFromValue(cache, point);
if(destNum !=10){
System.out.println(destNum);
}
}
}
public static int getKeyFromValue(HashMap hm, Object value) {
for (Object o : hm.keySet()) {
if (hm.get(o).equals(value)) {
int i = (int) o;
return i;
}
}
return 10;
}
}
Its a simple co-ordinate geometry problem. You can use mod 3 and solve it easily
/**
* |1,2,3|
* |4,5,6|
* |7,8,9|
* |0|
*/
public class KnightMoveInCalc{
private static void find(int num) {
if(num<0) return;
int x = num%3-1;
int y = num/3;
if(num == 0) {
x = 4;
y = 0;
}
int[] dxs = {1,2,-1,-2};
int[] dys = {1,2,-1,-2};
for(int dx:dxs) {
for(int dy:dys) {
if(Math.abs(dx)!=Math.abs(dy)) {
if((x+dx)>=0 && (x+dx)<3 &&
(y+dy)>=0 && (y+dy)<3) {
System.out.println((y+dy)*3+(x+dx)+1);
} else if((y+dy)==3 && (x+dx)==0) {
System.out.println("0");
}
}
}
}
}
public static void main(String[] args) {
find(5);
}
}
Its a simple geometry problem, use mod3 and solve it.
/**
* |1,2,3|
* |4,5,6|
* |7,8,9|
* |0|
*/
public class KnightMoveInCalc{
private static void find(int num) {
if(num<0) return;
int x = num%3-1;
int y = num/3;
if(num == 0) {
x = 4;
y = 0;
}
int[] dxs = {1,2,-1,-2};
int[] dys = {1,2,-1,-2};
for(int dx:dxs) {
for(int dy:dys) {
if(Math.abs(dx)!=Math.abs(dy)) {
if((x+dx)>=0 && (x+dx)<3 &&
(y+dy)>=0 && (y+dy)<3) {
System.out.println((y+dy)*3+(x+dx)+1);
} else if((y+dy)==3 && (x+dx)==0) {
System.out.println("0");
}
}
}
}
}
public static void main(String[] args) {
find(5);
}
}
package sk.radobenc.exercises;
import java.util.HashMap;
import java.util.Map;
/*
1 2 3
4 5 6
7 8 9
0
To adjust 0 position, fix the respective element in map m below.
*/
public class NumberPad {
static class Pos {
private final int row;
private final int column;
Pos(int row, int column) {
this.row = row;
this.column = column;
}
@Override
public boolean equals(Object obj) {
Pos p = (Pos) obj;
return column == p.column && row == p.row;
}
@Override
public int hashCode() {
return 31 * (31 + column) + row;
}
@Override
public String toString() {
return new StringBuilder().append('[').append(row).append(',').append(column).append(']').toString();
}
}
public static void main(String[] args) {
Map<Pos, Integer> m = new HashMap<Pos, Integer>();
m.put(new Pos(0, 0), 1);
m.put(new Pos(0, 1), 2);
m.put(new Pos(0, 2), 3);
m.put(new Pos(1, 0), 4);
m.put(new Pos(1, 1), 5);
m.put(new Pos(1, 2), 6);
m.put(new Pos(2, 0), 7);
m.put(new Pos(2, 1), 8);
m.put(new Pos(2, 2), 9);
m.put(new Pos(3, 0), 0);
Map<Integer, Pos> revM = new HashMap<Integer, Pos>();
for (Map.Entry<Pos, Integer> e : m.entrySet()) {
revM.put(e.getValue(), e.getKey());
}
int[][] moves = { { 2, 1 }, { 2, -1 }, { 1, -2 }, { 1, 2 }, { -1, -2 }, { -1, 2 }, { -2, -1 }, { -2, 1 } };
for (int i = 0; i < 10; i++) {
for (int j = 0; j < moves.length; j++) {
Pos source = revM.get(i);
Pos target = new Pos(source.row + moves[j][0], source.column + moves[j][1]);
if (null == m.get(target)) {
continue;
}
System.out.println("input=" + i + " target=" + target + " targetSign=" + m.get(target));
}
}
}
}
output:
input=0 target=[2,2] targetSign=9
input=0 target=[1,1] targetSign=5
input=1 target=[2,1] targetSign=8
input=1 target=[1,2] targetSign=6
input=2 target=[2,2] targetSign=9
input=2 target=[2,0] targetSign=7
input=3 target=[2,1] targetSign=8
input=3 target=[1,0] targetSign=4
input=4 target=[2,2] targetSign=9
input=4 target=[0,2] targetSign=3
input=5 target=[3,0] targetSign=0
input=6 target=[2,0] targetSign=7
input=6 target=[0,0] targetSign=1
input=7 target=[1,2] targetSign=6
input=7 target=[0,1] targetSign=2
input=8 target=[0,0] targetSign=1
input=8 target=[0,2] targetSign=3
input=9 target=[3,0] targetSign=0
input=9 target=[1,0] targetSign=4
input=9 target=[0,1] targetSign=2
public class NavigateCalculator {
/**
* Write all possible numbers returned from a calculator pad where a start number
* move in a L direction in any direction (1-2 moves)
* ie
* From calculator pad - start 8 --> go in L shape - 2 up and 1 right and t ends in 3
* From 2 it will be 7
* from 2 it will be 9
* From 7 it will be 2
* from 7 it will be 6
*
* What data structure can we use
* Array
* HashMap
*/
public static void main(String[] args) {
int[][] calculatorPad = {{0},{1,2,3},{4,5,6},{7,8,9}};
int[][] moves = {{1,2},
{1,-2},
{2,1},
{2,-1},
{-2,1},
{-2,-1},
{-1,2},
{-1,-2}};
for (int i=0;i<moves.length;i++) {
for (int j=0;j<moves[i].length;j++) {
System.out.print(moves[i][j] + " ");
}
System.out.println();
}
for (int i=0;i<calculatorPad.length;i++) {
for (int j=0;j<calculatorPad[i].length;j++) {
System.out.print(calculatorPad[i][j] + " ");
}
System.out.println();
}
for(int k=0; k<=9;k++) {
int[] location = locateN(k, calculatorPad);
System.out.print(k +" is located: ");
System.out.print(location[0] + " " + location[1]);
System.out.println();
for (int i=0;i<moves.length;i++) {
if(isMovePossible(location, moves[i], calculatorPad)) {
System.out.println("From location [" + location[0] +" " +location[1] + "], the following move is possible [" + moves[i][0] +" "+moves[i][1]+"] final number: "+move(location,moves[i],calculatorPad) );
}
}
}
}
//findLocation of n (indexOf?)
public static int[] locateN(int n, int[][] calculatorPad) {
int[] location = new int[2];
for (int i=0;i<calculatorPad.length;i++) {
for (int j=0;j <calculatorPad[i].length; j++){
if (calculatorPad[i][j] == n) {
location[0]=i;
location[1]=j;
break;
}
}
}
return location;
}
// is it possible to make move
public static boolean isMovePossible(int[] locationOfN, int[] move, int[][] calculatorPad) {
int y= locationOfN[0];
int x = locationOfN[1];
if ((y + move[0] > calculatorPad.length-1) || (y + move[0] < 0)) {
return false;
}
if ((x + move[1] > calculatorPad[y+move[0]].length-1) || (x + move[1] < 0)) {
return false;
}
return true;
}
//if possible then make move and store number
public static int move(int[]currentLocation, int[] moves, int[][] calculatorPad) {
int y = currentLocation[0] + moves[0];
int x = currentLocation[1] + moves[1];
return calculatorPad[y][x];
}
}
public class NavigateCalculator {
/**
* Write all possible numbers returned from a calculator pad where a start number
* move in a L direction in any direction (1-2 moves)
* ie
* From calculator pad - start 8 --> go in L shape - 2 up and 1 right and t ends in 3
* From 2 it will be 7
* from 2 it will be 9
* From 7 it will be 2
* from 7 it will be 6
*
* What data structure can we use
* Array
* HashMap
*/
public static void main(String[] args) {
int[][] calculatorPad = {{0},{1,2,3},{4,5,6},{7,8,9}};
int[][] moves = {{1,2},
{1,-2},
{2,1},
{2,-1},
{-2,1},
{-2,-1},
{-1,2},
{-1,-2}};
for (int i=0;i<moves.length;i++) {
for (int j=0;j<moves[i].length;j++) {
System.out.print(moves[i][j] + " ");
}
System.out.println();
}
for (int i=0;i<calculatorPad.length;i++) {
for (int j=0;j<calculatorPad[i].length;j++) {
System.out.print(calculatorPad[i][j] + " ");
}
System.out.println();
}
for(int k=0; k<=9;k++) {
int[] location = locateN(k, calculatorPad);
System.out.print(k +" is located: ");
System.out.print(location[0] + " " + location[1]);
System.out.println();
for (int i=0;i<moves.length;i++) {
if(isMovePossible(location, moves[i], calculatorPad)) {
System.out.println("From location [" + location[0] +" " +location[1] + "], the following move is possible [" + moves[i][0] +" "+moves[i][1]+"] final number: "+move(location,moves[i],calculatorPad) );
}
}
}
}
//findLocation of n (indexOf?)
public static int[] locateN(int n, int[][] calculatorPad) {
int[] location = new int[2];
for (int i=0;i<calculatorPad.length;i++) {
for (int j=0;j <calculatorPad[i].length; j++){
if (calculatorPad[i][j] == n) {
location[0]=i;
location[1]=j;
break;
}
}
}
return location;
}
// is it possible to make move
public static boolean isMovePossible(int[] locationOfN, int[] move, int[][] calculatorPad) {
int y= locationOfN[0];
int x = locationOfN[1];
if ((y + move[0] > calculatorPad.length-1) || (y + move[0] < 0)) {
return false;
}
if ((x + move[1] > calculatorPad[y+move[0]].length-1) || (x + move[1] < 0)) {
return false;
}
return true;
}
//if possible then make move and store number
public static int move(int[]currentLocation, int[] moves, int[][] calculatorPad) {
int y = currentLocation[0] + moves[0];
int x = currentLocation[1] + moves[1];
return calculatorPad[y][x];
}
}
- wingchuihk November 08, 2017