Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

//Re-submitting with small change in main (). Main should call findHops() 
package com.home.careercup;

/**
 * High performance chess apps use bit operations for determining knight attacks.
 * Below is sample code snipped from some chess programming material. It demonstrates
 * a flood fill algo for determining knight attacks ( and the distance between source
 * and destination ). This is similar to bfs (but very fast with bit operations)
 * It is possible to find the shortest paths for knights from source to dest by using
 * lookup tables.
 * There are 64 values of source. For each source the shortest path to each of the
 * other target values (64) cam be precomputed offline and fed into code.
 */

public class KnightDistance {

    public static void main(String[] args) {

        // 0, left bottom corner of chess board
        // 35, D5
        KnightDistance kd = new KnightDistance();
        int d= kd.findHops(0, 35);
        System.out.println(d); // prints 3
    }

    // flood fill all attack position for all knights on board
    // some bit magic
    long attacks(long bb) {
        long l1 = (bb >> 1) & 0x7f7f7f7f7f7f7f7fL;
        long l2 = (bb >> 2) & 0x3f3f3f3f3f3f3f3fL;
        long r1 = (bb << 1) & 0xfefefefefefefefeL;
        long r2 = (bb << 2) & 0xfcfcfcfcfcfcfcfcL;
        long h1 = l1 | r1;
        long h2 = l2 | r2;
        return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
    }


    int distance(long b1 /* source */, long b2 /* target */) {
        int d = 0;
        while ((b1 & b2) == 0) {
            b1 = attacks(b1);
            d++; // hop count increment
        }
        return d;
    }

    // utility method to translate from human readable board position
    // to bit position on chess board
    int findHops(int a, int b) {
        return distance(1L << a, 1L << b);
    }


}

- Makarand August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

May be some one has better idea, just thinking out loud,
This can be done using dynamic programming, set totalMinSteps to In32.maxValue
a) a knight has 8 directions to go from any position,
b) we try out 8 ways till we hit destination point,
c) once we get there we can totalMinSteps = k, at any point if we hit more than steps, we can simply to In32.MaxValue from the initial location to terminate the search
Space complexity is O( 8 * 8), where each location will have total number of steps to reach destination, Most locations will have Int32.MaxValue indicating that some path already found a minimum possible way to get to destination

- tryingtolearn August 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.home.careercup;

/**
 * High performance chess apps use bit operations for determining knight attacks.
 * Below is sample code snipped from some chess programming material. It demonstrates
 * a flood fill algo for determining knight attacks ( and the distance between source
 * and destination ). This is similar to bfs (but very fast with bit operations)
 * It is possible to find the shortest paths for knights from source to dest by using 
 * lookup tables.
 * There are 64 values of source. For each source the shortest path to each of the
 * other target values (64) cam be precomputed offline and fed into code. 
 */

public class KnightDistance {

    public static void main(String[] args) {

        // 0, left bottom corner of chess board
        // 35, D5
        KnightDistance kd = new KnightDistance();
        int d= kd.distance(0, 35);
        System.out.println(d); // prints 3
    }

    // flood fill all attack position for all knights on board
    // some bit magic
    long attacks(long bb) {
        long l1 = (bb >> 1) & 0x7f7f7f7f7f7f7f7fL;
        long l2 = (bb >> 2) & 0x3f3f3f3f3f3f3f3fL;
        long r1 = (bb << 1) & 0xfefefefefefefefeL;
        long r2 = (bb << 2) & 0xfcfcfcfcfcfcfcfcL;
        long h1 = l1 | r1;
        long h2 = l2 | r2;
        return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
    }


    int distance(long b1 /* source */, long b2 /* target */) {
        int d = 0;
        while ((b1 & b2) == 0) {
            b1 = attacks(b1);
            d++; // hop count increment
        }
        return d;
    }

    // utility method to translate from human readable board position
    // to bit position on chess board
    int findHops(int a, int b) {
        return distance(1L << a, 1L << b);
    }


}

- Makarand August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@makarand beautiful answer, thanks for sharing

- tryingtolearn September 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS (bidirectional BFS for efficiency) should work.

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Cell {
	public:
		Cell(int r, int c)
		{
			r_ = r;
			c_ = c;
		}
		bool operator==(Cell const &other) const
		{
			return  r_ == other.r_ &&
					c_ == other.c_;
		}
		bool Valid() const
		{
			return 	r_ >= 0 &&
					c_ >= 0 &&
					r_ < 8 &&
					c_ < 8;
		}
		int r_, c_;
};

int MinMovesCount(Cell source, Cell target)
{
	vector<vector<bool>> m = vector<vector<bool>>(8, vector<bool>(8, false));
	vector<pair<int, int>> moves = {{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
	queue<Cell> q1, q2;
	queue<Cell> *parents = &q1;
	queue<Cell> *children = &q2;
	parents->push(source);
	int moves_count = 0;
	while(!parents->empty()) {
		while(!parents->empty()) {
			Cell c = parents->front();
			parents->pop();
			if (c.Valid() &&
				!m[c.r_][c.c_])
			{
				m[c.r_][c.c_] = true;
				if (c == target) {
					return moves_count;
				}
				for (auto move : moves) {
					children->push(Cell(c.r_ + move.first, c.c_ + move.second));
				}
			}
		}
		swap(parents, children);
		++moves_count;
	}
	return -1;
}

int main()
{
	for (int r = 0; r < 8; ++r) {
		for (int c = 0; c < 8; ++c) {
			for (int r2 = 0; r2 < 8; ++r2) {
				for (int c2 = 0; c2 < 8; ++c2) {
					cout << r << ", " << c << ", " << r2 << ", " << c2 << ", " << MinMovesCount(Cell(r, c), Cell(r2, c2)) << "\n";
				}
			}
		}
	}
	return 0;
}

- Alex November 17, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More