amirtar
BAN USER- 3of 5 votes
AnswersLook at the sequence below:
- amirtar in United States
1, 11, 21, 1211, 111221, 312211, ...
Write a code that receives n and returns the nth element of the sequence. If it gets 4 as input of the method it should return 1211.| Report Duplicate | Flag | PURGE
Google Software Engineer - 0of 2 votes
AnswersThe text of question below is exactly given by Google interviewer. So they are owner of the text and I am just quoting them. I am not the author of the text below:
- amirtar in United States
"
Imagine a museum floor that looks like this:
.#.G.
..#..
G....
..#..
G == Museum Guard
# == obstruction/impassable obstacle
. == empty space
Write a piece of code that will find the nearest guard for each open floor space. Diagonal moves are not allowed. The output should convey this information:
2#1G1
12#12
G1223
12#34
You may choose how you want to receive the input and output. For example, you may use a 2-d array, as depicted here, or you may use a list of points with features, if you deem that easier to work with, as long as the same information is conveyed.
"| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm Ideas Math & Computation - 1of 3 votes
AnswersWe know a string is Palindrome if it is the same reading from both sides. Now we define the following string also Palindrome:
- amirtar in United States
A man, a plan, a canal, Panama!
Write a code that returns if an string is palindrome and it should return true for above input. (Without directly saying, I should conclude that I have to only consider alphanumerical characters in a string). In addition, we assume the string is very long and we can not keep a copy of this string or even a copy of preprocessed version of this string. Therefore the result should be returned with the first sweep of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm String Manipulation
Hello Madhur, your code does not seem to have the error I thought. I tested a couple of cases I thought may produce bug, but it didn't. Unfortunately, I could not read your code. I think you need to use data structures rather than passing i and j as string and then parsing them back to integer. This does not seem like a good policy if you are doing job interview and makes the code harder to read.
- amirtar May 09, 2015This is the answer I wrote in my interview. This algorithm works for many cases but it is wrong. It can produce wrong results. The logic to explain why it is wrong is very complex and unfortunately I don't have time to explain it. One of my Googler friends told me why it was wrong. Even the interviewer told me I solved it right and he did not realize the logic error while I was writing the code.
Anyways I write the code I gave in my interview here. FYI, I didn't get the offer. So this code is not good enough eventhough it works for many cases.
class Pairs {
int MAXCOL = 1000;
private int row;
private int col;
pubic Pairs(int r, int c) {
row = r;
col = c;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public boolean isEqual(Pairs p) {
return (this.row == p.row && this.col == p.row);
}
public int hashCode() {
return row * MAXCOL + col;
}
}
class Museum {
List<Pairs> obstacles;
List<Pairs> guards;
int rowSize;
int colSize;
public Museum(List<Pairs> o, List<Pairs> g, int row, int col) {
obstacles = o;
guards = g;
rowSize = row;
colSize = col;
//There should be checking that all the pairs inside o and g are within map
//...
}
public Map<Pairs, Integer> getGuardDistance() {
//First create a queue of all the empty spaces
Queue<Pairs> notFilinzed = new LinkedList<>();
Map<Pairs, Integer> distances = new HashMap<>();
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize; j++) {
Pairs p = new Pairs(i, j);
if ((!obstacles.contains(p)) && (!guards.contains(p))) {
notFilinzed.add(p);
distances.put(p, Integer.MAX_VALUE);
}
if (guards.contains(p)) {
distances.put(p, 0);
}
if (obstacles.contains(p)) {
distances.put(p, Integer.MAX_VALUE);
}
}
}
//as long as I have something in the que
while (!notFilinzed.isEmpty()) {
Pair p = notFilinzed.poll();
int min = Integer.MAX_VALUE;
boolean foundDistance = false;
//top:
if (p.row - 1 >= 0) {
Pairs top = new Pairs(p.row - 1, p.col);
if (!notFilinzed.contains(top) && !obstacles.contains(top) && distances.get(top) < min) {
min = distances.get(top);
foundDistance = true;
}
}
//right
if (p.col + 1 < colSize) {
Pairs right = new Pairs(p.row, p.col + 1);
if (!notFilinzed.contains(right) && !obstacles.contains(right) && distances.get(right) < min) {
min = distances.get(right);
foundDistance = true;
}
}
//bottom
if (p.row < rowSize) {
Pairs bottom = new Pairs(p.row + 1, p.col);
if (!notFilinzed.contains(bottom) && !obstacles.contains(bottom) && distances.get(bottom) < min) {
min = distances.get(bottom);
foundDistance = true;
}
}
//left
if (p.col - 1 >= 0) {
Pairs left = new Pairs(p.row, p.col - 1);
if (!notFilinzed.contains(left) && !obstacles.contains(left) && distances.get(left) < min) {
min = distances.get(left);
foundDistance = true;
}
}
if (!foundDistance) {
notFilinzed.add(p);
}
distances.put(p, min + 1);
}
//Create output format
return distances;
}
}
I was looking at this question for long time waiting for a good answer to come! (I posted this question). The best algorithm for this problem is of O(nlogn). it gets implemented using shortest path algorithm (Dijkstra). The famous algorithm should be modified slightly as follows:
1. in the beginning, all of the guard locations can be starting point. Therefore, instead of just adding one point to the main heap in the code, we add all of the guard locations to that heap with distance of 0.
2. Instead of ending the algorithm when destination is met, the algorithm ends when the main heap is empty, meaning all of the locations are met.
With these modifications, Dijkstra algorithm with O(nlogn) can solve it.
Good answer. Just one point. You should compare a and b with equals not "==" since a and b are Character pointers not char variables. or you could just use valA and valB also since you are comparing in the begining you could simplify the if statment by use chain if else-if statements like below:
if(valA < 0 || valA >= 26) {
i++;
}else if(valB < 0 || valB >= 26) {
j--;
}else if( valA != valB) {
return false;
} else{
i++;
j--;
}
The problem is not clear. But if your issue is to create a unique hashCode when the first name and last name change you can do like this:
class Employee{
int age;
String fname;
String lname;
public int hasCode(){
if(fname.hashCode()<lname.hashCode())
return (fname+lname).hashCode();
return (lname+fname).hashCode();
}
}
As the last comments recommended using pascal triangle would help. I use different way fo calculating the coefficients. I used the literal mathematical formula but the C implementation by @DattaP is more efficient. Here is my Java Code:
class Problem{
public int solution(int N){
int carry=0;
int counter=0;
for(int i=0;i<N;i++){
int term= choose(N,i)+carry;
if((term%10)==1)
counter++;
carry=term/10;
}
return counter;
}
int choose(int n, int k){
return (factorial(n))/(factorial(k)*factorial(n-k));
}
int factorial(int n){
int result=1;
for(int i=1;i<=n;i++)
result*=i;
return result;
}
}
}
- amirtar April 20, 2015I realized the method isAdditive had some issue with two gigitbase additive numbers. I fixed it. Please replace isAdditive with this code:
public boolean isAdditive(int number) {
int len = getLength(number);
for (int i = len; i > 2; i--) {
for (int j = i - 1; j > 1; j--) {
int num1 = getNumber(number, len, i);
int num2 = getNumber(number, i - 1, j);
int num3 = getNumber(number, j - 1, 1);
if (startsWith(num3, num1 + num2)) {
int number2 = getNumber(number, j - 1 - getLength(num1 + num2), 1);
if (number2 == -1) {
return true;
}else{
if(isAdditive(number2))
return true;
}
}
}
}
return false;
}
This is my code. for each number with N digit, it takes O(N^2) to check if it is additive number.
class AdditiveNumber {
public List<Integer> getAdditiveNumber(int rangeBegin, int rangeEnd) {
List<Integer> list = new LinkedList<>();
for (Integer i = rangeBegin; i <= rangeEnd; i++) {
if (isAdditive(i)) {
list.add(i);
}
}
return list;
}
//returns the number of digits in an integer
private int getLength(int number) {
return (int) (Math.floor(Math.log(number) / Math.log(10)) + 1);
}
//MSD: Most Significant Digit
//returns a number insise "number"
//starting from MSD and end at LSD both inclusive
private int getNumber(int number, int MSD, int LSD) {
if (LSD < 1 || MSD < 1 || MSD < LSD) {
return -1;
}
number %= (int) (Math.pow(10, MSD));
number /= (int) (Math.pow(10, LSD - 1));
return number;
}
//Checked if num1 starts with num2 meaning
//num1 MSDs are equal to num2
private boolean startsWith(int num1, int num2) {
int len1 = getLength(num1);
int startNumber = getNumber(num1, len1, len1 - getLength(num2));
return startNumber == num2;
}
public boolean isAdditive(int number) {
int len = getLength(number);
for (int i = len; i > 2; i--) {
for (int j = i - 1; j > 1; j--) {
int num1 = getNumber(number, len, i);
int num2 = getNumber(number, i - 1, j);
int num3 = getNumber(number, j - 1, 1);
if (startsWith(num3, num1 + num2)) {
number = getNumber(number, j - 1 - getLength(num1 + num2), 1);
if (number == -1) {
return true;
}
} else {
return false;
}
}
}
return false;
}
}
Thanks,
I used your hints and wrote my code. With some modifications like used regular boolean array rather than hash map.
class Question {
public boolean does2Add12(int[] input) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < input.length; i++) {
if (input[i] > max) {
max = input[i];
}
if (input[i] < min) {
min = input[i];
}
}
int offset = min;
int length = max - min + 1;
//If the range of number are too wide use simple sort
//I used 4 times of input length as too wide. You can change it.
if (length > 4 * input.length) {
return does2Add12ScatteredNumbers(input);
}
boolean[] matches = new boolean[length];
for (int i = 0; i < input.length; i++) {
if (matches[(12 - input[i]) - offset]) {
return true;
} else {
matches[input[i] - offset] = true;
}
}
return false;
}
private boolean does2Add12ScatteredNumbers(int[] input) {
Arrays.sort(input);
int large = input.length - 1;
int small = 0;
while (small < large) {
if (input[small] + input[large] == 12) {
return true;
}
if (input[small] + input[large] > 12) {
large--;
}
if (input[small] + input[large] < 12) {
small++;
}
}
return false;
}
}
I realized my code missed one condition, if the series ends with positive series and that is the longest series then my code does not catch it. To fix the below code should be added before the last two lines before storing output results:
if(posEdge){
if(count>lastCount){
lastBegin=begin+1;
lastCount=count;
}
}
I think the first comment wanted to give the same logic as my code but his code is not right. I tried to use better variable naming.
class Sequence {
public void getLongestSequence(int[] input, int[] output) {
if (input.length == 0) {
output[0] = 0;//count of longest series
output[1] = 0;//starting point: 1 is the first so 0 means N/A
return;
}
int lastBegin = 0;
int lastCount = 0;
int count = 0;
int begin = 0;
boolean posEdge = input[0] > 0;
for (int i = 0; i < input.length; i++) {
if (posEdge) {
if (input[i] > 0) {
count++;
} else {
posEdge = false;
if (count > lastCount) {
lastBegin = begin + 1;
lastCount = count;
}
}
} else {
if (input[i] > 0) {
posEdge = true;
count = 1;
begin = i;
}
}
}
output[0] = lastCount;
output[1] = lastBegin;
}
}
Many people wrote the answer. I thought I share mine as well. I got the idea from your answer BTW.
public int getMinDiceToWin(int size, Map<Integer, Integer> ladders, Map<Integer, Integer> snakes) {
int[] minDice = new int[size + 1];
for (int i = 2; i <= size; i++) {//i==1 needs zero move which already is filled
//if this location is a snake mouth then put it infinity dice for not being used later
if (snakes.values().contains(i)) {
minDice[i] = Integer.MAX_VALUE;
continue;
}
int min = Integer.MAX_VALUE;
//checking all 6 locations before current location
for (int j = 1; j <= 6; j++) {
if (i - j > 0 && i - j <= size) {
if (min > minDice[i - j] + 1) {
min = minDice[i - j] + 1;
}
}
}
//Checking for ladder in current location
Integer ladderBottom = ladders.get(i);
if (ladderBottom != null) {
if (min > minDice[ladderBottom]) {
min = minDice[ladderBottom];
}
}
minDice[i] = min;
}
return minDice[size];
}
You are right @Alex. For 10 there is an answer. I was not patient enough to try it. But for N=10 there is 4 answers not 1. Two of them are the vertical mirror of the other two (i.e. 2 unique answers).
This is the output of my program for N=10:
10x10: Total Solutions with knight move: 4
--*-------
-----*----
--------*-
*---------
---*------
------*---
---------*
-*--------
----*-----
-------*--
---*------
-------*--
*---------
----*-----
--------*-
-*--------
-----*----
---------*
--*-------
------*---
------*---
--*-------
---------*
-----*----
-*--------
--------*-
----*-----
*---------
-------*--
---*------
-------*--
----*-----
-*--------
---------*
------*---
---*------
*---------
--------*-
-----*----
--*-------
My version (Corrected for the root count)
public Map<String, Integer> getEmployees(Map<String, String> employeeManager){
Map<String,Integer> employeeCounts= new HashMap<>();
for(Map.Entry<String, String> pair:employeeManager.entrySet()){
String employee= pair.getKey();
String manager= pair.getValue();
if(!employee.equals(manager)){
Integer count= employeeCounts.get(manager);
if(count==null)
employeeCounts.put(manager, 1);
else
employeeCounts.put(manager, count+1);
}
}
return employeeCounts;
}
Same logic as above code. But different looping.
public Map<String, Integer> getEmployees(Map<String, String> employeeManager){
Map<String,Integer> employeeCounts= new HashMap<>();
for(Map.Entry<String, String> pair:employeeManager.entrySet()){
String employee= pair.getKey();
String manager= pair.getValue();
Integer count= employeeCounts.get(manager);
if(count==null)
employeeCounts.put(manager, 1);
else
employeeCounts.put(manager, count+1);
}
return employeeCounts;
}
The question does not have answer. I did not know it before I wrote the code. After I run it and saw it has no answer, I found the logic. If we consider the 3rd move for knights then there is no answer. If we do not consider the knight move (i.e. only cosider diagonal, vertical, and horizontal moves) then there is an answer.
I wrote it in a way that both can be shown.
Below is the two classes for Chess and SolveQueen in java:
Chess class:
class Chess{
boolean[][] table;
boolean[][] queens;
int N;
private int[] knightRow= {-2,-1,1,2, 2, 1,-1,-2};
private int[] knightCol= { 1, 2,2,1,-1,-2,-2,-1};
private int knight=8;
int lastCompleted;
boolean includeKnight;
public Chess(int size){
N=size;
table= new boolean[N][N];
queens=new boolean[N][N];
lastCompleted=-1;
}
public Chess(Chess chess){
this(chess.N);
includeKnight=chess.includeKnight;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
table[i][j]=chess.table[i][j];
queens[i][j]=chess.queens[i][j];
}
}
public boolean isAvailable(int row, int col){
return !table[row][col];
}
public void put(int row, int col){
//for vertical, horizontal, and diagonal
lastCompleted=row;
queens[row][col]=true;
for(int i=0;i<N;i++){
table[row][i]=true;
table[i][col]=true;
if(col-i>=0){
if(row-i>=0)
table[row-i][col-i]=true;
if(row+i<N)
table[row+i][col-i]=true;
}
if(col+i<N){
if(row-i>=0)
table[row-i][col+i]=true;
if(row+i<N)
table[row+i][col+i]=true;
}
}
//knight move check
if (includeKnight) {
for (int i = 0; i < knight; i++) {
int nRow = row + knightRow[i];
int nCol = col + knightCol[i];
if (nRow >= 0 && nRow < N && nCol >= 0 && nCol < N) {
table[nRow][nCol] = true;
}
}
}
}
public String toString(){
StringBuilder buffer= new StringBuilder();
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(queens[i][j])
buffer.append("*");
else
buffer.append("-");
}
buffer.append("\n");
}
return buffer.toString();
}
}
It is the SolveQueen class:
class SolveQueen{
int N;
boolean includeKnight;
public SolveQueen(int size){
N=size;
includeKnight=false;
}
public List<Chess> solveIt(){
Chess emptyChess= new Chess(N);
emptyChess.includeKnight=includeKnight;
List<Chess> chessesCompleted= new LinkedList<>();
Queue<Chess> fifo = new LinkedList<>();
fifo.offer(emptyChess);
while(!fifo.isEmpty()){
Chess currentChess=fifo.poll();
if(currentChess.lastCompleted==N-1)
chessesCompleted.add(currentChess);
else{
int row=currentChess.lastCompleted+1;
for(int col=0;col<N;col++){
if(currentChess.isAvailable(row,col)){
Chess newChess= new Chess(currentChess);
newChess.put(row,col);
fifo.offer(newChess);
}
}
}
}
return chessesCompleted;
}
}
Here it is the main method to solve it the with and without knight move:
public static void main(String[] args) {
//Create the problem
SolveQueen solve= new SolveQueen(4);
//Solve it without knight moves
List<Chess> solutions=solve.solveIt();
System.out.println("4x4: Total Solutions without knight move: "+ solutions.size());
for(Chess chess:solutions){
System.out.println(chess);
}
//Solve it with knight moves
solve.includeKnight=true;
solutions=solve.solveIt();
System.out.println("4x4: Total Solutions with knight move: "+ solutions.size());
for(Chess chess:solutions){
System.out.println(chess);
}
}
And here is the output of above code:
4x4: Total Solutions without knight move: 2
-*--
---*
*---
--*-
--*-
*---
---*
-*--
4x4: Total Solutions with knight move: 0
Same solution, I just implemented the mergesort differently. It takes less space.
public static void mergeSort(int[] input, int[] inversions, int begin, int end){
if(begin==end)
return;
if(begin+1==end)
return;
int mid=(begin+end)/2;
mergeSort(input, inversions, begin, mid);
mergeSort(input, inversions, mid, end);
merge(input, inversions, begin, mid, end);
}
public static void merge(int[] input, int[] inversions, int begin, int mid, int end){
if(mid==end)
return;
if(mid==begin)
return;
int[] inputFirst= Arrays.copyOfRange(input, begin,mid);
int[] inversionsFirst=Arrays.copyOfRange(inversions, begin, mid);
int leftIndex=0;
int rightIndex=mid;
int index=begin;
for(;index<end;index++){
if(rightIndex==end){
input[index]=inputFirst[leftIndex];
inversions[index]=inversionsFirst[leftIndex++]+end-mid;
continue;
}
if(leftIndex==mid-begin){
input[index]=input[rightIndex];
inversions[index]=inversions[rightIndex++];
continue;
}
if(inputFirst[leftIndex]<=input[rightIndex]){
input[index]=inputFirst[leftIndex];
inversions[index]=inversionsFirst[leftIndex++]+rightIndex-mid;
}else{
input[index]=input[rightIndex];
inversions[index]=inversions[rightIndex++];
}
}
}
This is how I write it in Java which would be very simple'
public static Integer[] unique(Integer[] input){
Set<Integer> mySet= new HashSet<>(input.length);
for(Integer i:input)
mySet.add(i);
return mySet.toArray(new Integer[1]);
}
The trick of question is for C for not using hashtable:
int* unique(int* input, int length){
int max=0x7FFFFFFF+1;//minimum integer
int min=0x7FFFFFFF;//maximum integer
int i;
//find the max and min of the array O(n)
for(i=0;i<length;i++){
if(max<input[i])
max=input[i];
if(min>input[i])
min=input[i];
}
char* countArr = calloc(max-min+1,sizeof(char));
int count=0;
for(i=0;i<length;i++){
countArr[input[i]-min]=1;
count++;
}
int* output= calloc(count, sizeof(input[0]));
int index;
index=0;
for(i=min;i<=max;i++)
if(countArr[i-min]){
output[index++]=i;
}
return output;
}
I have to return the size of return array somehow that I did not do here.
- amirtar April 08, 2015public static boolean isMatch(String str, String pattern){
String[] miniPatterns= pattern.split("[*]");
first=true;
for(String miniPattern:miniPatterns){
str=isMiniMatch(str,miniPattern);
if(str==null)
return false;
}
if(pattern.charAt(pattern.length()-1)=='*')
return true;
return str.length()==0;
}
static boolean first=true;
public static String isMiniMatch(String str, String miniPattern){
if(str.length()<miniPattern.length())
return null;
int offset=0;
if (!first)
offset=str.indexOf(miniPattern.charAt(0));
first=false;
for(int i=0;i<miniPattern.length();i++){
if(miniPattern.charAt(i)!='.'){
if(miniPattern.charAt(i)!=(str.charAt(i+offset)))
return null;
}
}
return str.substring(miniPattern.length()+offset);
}
First sort it then from beginging look for ranges.
public String getRanges(Integer[] numbers){
Arrays.sort(numbers);
Integers begin= numbers[0];
StringBuilder buffer= new StringBuilder();
for(int i=1;i<number.length;i++){
if(numbers[i]!=numbers[i-1]+1){
if(begin==numbers[i-1]){
buffer.append(begin).append(“,”);
}else{
buffer.appebd(begin).append(“-”).append(number[i-1]).append(“,”);
}
begin=numbers[i];
}
}
int len=buffer.length();
buffer.delete(len-1,len);
return buffer.toStrong();
}
I realized there is away to make the code shorter and combine the two loops. This time I wrote it in C++ for my own practice:
int minSteps(int m, int n){
int x,y;
bool downDirection=true;
int steps=0;
for(x=y=1;(x<m||y<n)&&(x<n||y<m);steps++){
if (downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
return steps;
}
The shortest path comes when you move diagonally. But depending on m and n you should either start with right or down. This is my Java method:
public static int minSteps(int m, int n){
int x,y;
int stepsDownFirst=0;
boolean downDirection=true;
for(x=1, y=1;x<m || y<n;stepsDownFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
int stepsRightFirst=0;
downDirection=false;
for(x=1, y=1;x<m || y<n;stepsRightFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
if(stepsDownFirst<stepsRightFirst)
return stepsDownFirst;
else
return stepsRightFirst;
}
All of the solutions I see here are great. But based on the discussion I had with my interviewer, she was looking for a double recursive solution. Obviously I failed to answer it in the interview, but I have the answer now. The code becomes very small with double recursive solution:
- amirtar May 09, 2015