CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Expedia Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person
More Questions from This Interview



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

package conway.game.of.life;

public class Cell {

	private final int row;
	private final int column;
	private Boolean state;

	public Cell(int row, int column) {
		this.row = row;
		this.column = column;
		this.state = Boolean.FALSE;
	}

	public int getRow() {
		return row;
	}

	public int getColumn() {
		return column;
	}

	public Boolean getState() {
		return state;
	}

	public void setState(Boolean value) {
		this.state = value;

	}

	@Override
	public boolean equals(Object cell) {
		return (cell instanceof Cell) && ((Cell) cell).getRow() == this.row
				&& ((Cell) cell).getColumn() == this.column;
	}

	@Override
	public int hashCode() {
		return 31 * row << 8 * column << 9;
	}
}

package conway.game.of.life;

public class CellGrid {
	
	private Cell[][] currentGrid;
	private int rows;
	private int columns;
	private static int generation; //TODO:

	public CellGrid(int rows, int columns) {
		this.currentGrid = createClearCellGrid(rows, columns); // Cellular Pattern
		this.rows = rows;
		this.columns = columns;
	}

	private Cell[][] createClearCellGrid(int rows, int columns) {
		currentGrid = new Cell[rows][columns];
		for (int i = 0; i < rows; i++)
			for (int j = 0; j < columns; j++) {
				currentGrid[i][j] = new Cell(i, j);
				currentGrid[i][j].setState(false);
			}
		return currentGrid;
	}


	public Cell[][] getCells() {
		return currentGrid;
	}

	public void setCells(Cell[][] cells) {
		currentGrid=cells;
	}

	public int getRows() {
		return rows;
	}

	public int getColumns() {
		return columns;
	}
}

package conway.game.of.life;

public class CellGrid {
	
	private Cell[][] currentGrid;
	private int rows;
	private int columns;
	private static int generation; //TODO:

	public CellGrid(int rows, int columns) {
		this.currentGrid = createClearCellGrid(rows, columns); // Cellular Pattern
		this.rows = rows;
		this.columns = columns;
	}

	private Cell[][] createClearCellGrid(int rows, int columns) {
		currentGrid = new Cell[rows][columns];
		for (int i = 0; i < rows; i++)
			for (int j = 0; j < columns; j++) {
				currentGrid[i][j] = new Cell(i, j);
				currentGrid[i][j].setState(false);
			}
		return currentGrid;
	}


	public Cell[][] getCells() {
		return currentGrid;
	}

	public void setCells(Cell[][] cells) {
		currentGrid=cells;
	}

	public int getRows() {
		return rows;
	}

	public int getColumns() {
		return columns;
	}
}

package conway.game.of.life;

public final class ShapeChooser {

	//TODO: To create separate Shape Beans and to Inject throgh Spring
	private static Cell[][] cells;
	private static final Boolean LIVE = Boolean.TRUE;
	private static final Boolean DEAD = Boolean.FALSE;

	
	private ShapeChooser() {
		// Does Nothing
	}

	public static Cell[][] createOscillator(CellGrid grid) {
		return Oscillator.createPattern(grid);
	}

	public static Cell[][] createTenLiveCellLine(CellGrid grid) {
		return TenLiveCellLine.createPattern(grid);
	}

	public static Cell[][] createRectangle(CellGrid grid) {
		return Rectangle.createPattern(grid);
	}

	private static class Oscillator {
		private static Cell[][] drawOscillatorCellPattern(CellGrid grid) {
			int oscillatorRowPosition = grid.getRows() / 2;
			int oscillatorColumnPosition = grid.getColumns() / 2;
			cells = grid.getCells();
			cells[oscillatorRowPosition][oscillatorColumnPosition - 1]
					.setState(LIVE);
			cells[oscillatorRowPosition][oscillatorColumnPosition]
					.setState(LIVE);
			cells[oscillatorRowPosition][oscillatorColumnPosition + 1]
					.setState(LIVE);
			return cells;
		}

		public static Cell[][] createPattern(CellGrid grid) {
			return drawOscillatorCellPattern(grid);
		}
	}

	private static class TenLiveCellLine {

		private static Cell[][] drawTenLiveCellLinePattern(CellGrid grid) {
			int tenLiveLineRowPosition = grid.getRows() / 2;
			int tenLiveLineColumnPosition = grid.getColumns() / 2;
			cells = grid.getCells();
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition - 2]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition - 1]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition + 1]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition + 2]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition + 3]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition + 4]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition + 5]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition + 6]
					.setState(LIVE);
			cells[tenLiveLineRowPosition][tenLiveLineColumnPosition + 7]
					.setState(LIVE);
			return cells;
		}

		public static Cell[][] createPattern(CellGrid grid) {
			return drawTenLiveCellLinePattern(grid);
		}
	}

	private static class Rectangle {
		private static Cell[][] drawRectangle(CellGrid grid) {
			int rectangleRowPosition = grid.getRows() / 2;
			int rectangleColumnPosition = grid.getColumns() / 2;
			cells = grid.getCells();
			cells[rectangleRowPosition][rectangleColumnPosition]
					.setState(LIVE);
			cells[rectangleRowPosition][rectangleColumnPosition + 1]
					.setState(LIVE);
			cells[rectangleRowPosition - 1][rectangleColumnPosition]
					.setState(LIVE);
			cells[rectangleRowPosition - 1][rectangleColumnPosition + 1]
					.setState(LIVE);
			return cells;
		}

		public static Cell[][] createPattern(CellGrid grid) {
			return drawRectangle(grid);
		}
	}

}

package conway.game.of.life.controller;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import conway.game.of.life.Cell;
import conway.game.of.life.CellGrid;

public class CellGridController implements Controller {

	private CellGrid gridUnderControl;
	private Cell[][] nextGenerationCells;

	public CellGridController(CellGrid grid) {
		this.gridUnderControl = grid;
	}

	@Override
	public void execute() {
		nextGenerationCells = next(gridUnderControl);
	}

	@Override
	public Cell[][] nextGen() {
		return nextGenerationCells;
	}

	private Cell[][] next(CellGrid grid) {
		final Cell[][] previousCells = grid.getCells();
		final int rows = grid.getRows();
		final int columns = grid.getColumns();
		Cell[][] nextGenCells = new Cell[rows][columns];
		final Map<Cell, Integer> neighboursMap = getNeighbourMap(previousCells,
				rows, columns);
		Set<Cell> cellSet = neighboursMap.keySet();
		for (Cell cell : cellSet) {
			int neighbourCount = neighboursMap.get(cell);
			// TODO:transaction
			nextGenCells = killCells(nextGenCells, cell, neighbourCount);
			nextGenCells = preserveCells(nextGenCells, cell, neighbourCount);
			nextGenCells = bornTheCell(nextGenCells, cell, neighbourCount);
		}
		cellSet = null;
		return nextGenCells;
	}

	private Cell[][] bornTheCell(Cell[][] nextGenCells, Cell cell,
			int neighbourCount) {
		if (neighbourCount == 3) {
			nextGenCells[cell.getRow()][cell.getColumn()] = cell;
			nextGenCells[cell.getRow()][cell.getColumn()]
					.setState(Boolean.TRUE);
		}
		return nextGenCells;
	}

	private Cell[][] preserveCells(Cell[][] nextGenCells, Cell cell,
			int neighbourCount) {
		if (neighbourCount == 2) {
			nextGenCells[cell.getRow()][cell.getColumn()] = cell;
			if (cell.getState().booleanValue()) {
				nextGenCells[cell.getRow()][cell.getColumn()]
						.setState(Boolean.TRUE);
			} else {
				nextGenCells[cell.getRow()][cell.getColumn()]
						.setState(Boolean.FALSE);
			}
		}
		return nextGenCells;
	}

	private Cell[][] killCells(final Cell[][] nextGenCells, Cell cell,
			int neighbourCount) {
		if (neighbourCount <= 1 || neighbourCount >= 4) {
			nextGenCells[cell.getRow()][cell.getColumn()] = cell;
			nextGenCells[cell.getRow()][cell.getColumn()]
					.setState(Boolean.FALSE);
		}
		return nextGenCells;
	}

	private Map<Cell, Integer> getNeighbourMap(final Cell[][] previousCells,
			final int rows, final int columns) {
		final Map<Cell, Integer> neighboursMap = new HashMap<Cell, Integer>();
		for (int i = 0; i < rows; i++)
			for (int j = 0; j < columns; j++) {
				neighboursMap.put(previousCells[i][j], calculateLiveNeighbours(
						previousCells[i][j], previousCells));
			}
		return neighboursMap;
	}

	public int calculateLiveNeighbours(Cell currentCell, Cell[][] cells) {
		return getLiveClosure(currentCell, cells);
	}

	private int getLiveClosure(Cell currentCell, Cell[][] cells) {
		int closureCount = 0;
		int m = currentCell.getRow();
		int n = currentCell.getColumn();
		// TODO: Bind them in one loop staing from m-1,n-1 to m+1,n+1 excluding
		// m,n
		if (isBoundaryConditionPassed(m, n)) {
			if (isLiveNeighbour(cells[m][n - 1])) {
				closureCount++;
			}
			if (isLiveNeighbour(cells[m][n + 1])) {
				closureCount++;
			}
			if (isLiveNeighbour(cells[m - 1][n - 1])) {
				closureCount++;
			}
			if (isLiveNeighbour(cells[m - 1][n])) {
				closureCount++;
			}
			if (isLiveNeighbour(cells[m - 1][n + 1])) {
				closureCount++;
			}
			if (isLiveNeighbour(cells[m + 1][n - 1])) {
				closureCount++;
			}
			if (isLiveNeighbour(cells[m + 1][n])) {
				closureCount++;
			}
			if (isLiveNeighbour(cells[m + 1][n + 1])) {
				closureCount++;
			}
		}
		return closureCount;
	}

	private boolean isBoundaryConditionPassed(int m, int n) {
		return (m + 1) < gridUnderControl.getRows()
				&& (n + 1) < gridUnderControl.getColumns() && (m - 1) >= 0
				&& (n - 1) >= 0;
	}

	private boolean isLiveNeighbour(Cell cell) {
		return cell.getState() == Boolean.TRUE;
	}

}

package conway.game.of.life.controller;

import conway.game.of.life.Cell;

public interface Controller {
	public void execute();

	public Cell[][] nextGen();
}

package conway.game.of.life.datamodel;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import javax.swing.table.AbstractTableModel;

import conway.game.of.life.Cell;
import conway.game.of.life.CellGrid;
import conway.game.of.life.ShapeChooser;
import conway.game.of.life.controller.CellGridController;
import conway.game.of.life.controller.Controller;

public class GameOfLifeModel extends AbstractTableModel implements Runnable {

	private static final int DELAY = 1000;
	private static final long serialVersionUID = -8691592220317134382L;
	private static final int MAX_THREAD_POOL = 1;
	private Thread currentThread;
	private CellGrid grid;
	private Cell[][] currentCellularData;
	private Cell[][] nextCellularData;
	private Controller controller;

	// TODO :
	// TODO: Dependency only at run runtime
	// TODO:Subclassing is required for each model
	public GameOfLifeModel(int rows, int columns, String pattern) {
		this.grid = new CellGrid(rows, columns);
		controller = new CellGridController(grid);// TODO: To Inject Dependency
		if (pattern == "R") {
			this.currentCellularData = ShapeChooser.createRectangle(grid);
			grid.setCells(currentCellularData);
		} else if (pattern == "O") {
			this.currentCellularData = ShapeChooser.createOscillator(grid);
			grid.setCells(currentCellularData);
		} else if (pattern == "L") {
			this.currentCellularData = ShapeChooser.createTenLiveCellLine(grid);
		}

		currentThread = new Thread(this);
		ExecutorService service = Executors.newFixedThreadPool(MAX_THREAD_POOL);
		service.execute(currentThread);

	}


	@Override
	public int getColumnCount() {
		return currentCellularData.length;
	}

	@Override
	public int getRowCount() {
		return currentCellularData.length;
	}

	@Override
	public Object getValueAt(int rowIndex, int columnIndex) {
		return currentCellularData[rowIndex][columnIndex];
	}

	@Override
	public Class<?> getColumnClass(int columnIndex) {
		return currentCellularData[0][columnIndex].getClass();

	}

	public void run() {
		while (true) {
			controller.execute();
			nextCellularData = controller.nextGen();
			currentCellularData = nextCellularData;
			nextCellularData = null;
			fireTableDataChanged();
			try {
				Thread.sleep(DELAY);
			} catch (InterruptedException ie) {
			}
		}
	}

}

package conway.game.of.life.main;

import conway.game.of.life.ui.GameOfLifeUI;

public class LiveLineOfTenMain {
	public static void main(String args[]) {
		final GameOfLifeUI ui = new GameOfLifeUI(25, 25,"L");
		ui.setVisible(true);
	}
}

package conway.game.of.life.ui;

import java.awt.Color;
import java.awt.Component;
import javax.swing.JPanel;
import javax.swing.JTable;
import javax.swing.table.TableCellRenderer;

import conway.game.of.life.Cell;

public class CellRenderer implements TableCellRenderer {
	private JPanel panel = new JPanel();

	@Override
	public Component getTableCellRendererComponent(JTable table, Object value,
			boolean isSelected, boolean hasFocus, int row, int column) {
		if (((Cell) value).getState().equals(Boolean.TRUE)) {
			panel.setBackground(Color.RED);
		} else {
			panel.setBackground(Color.WHITE);
		}
		return panel;
	}
}

package conway.game.of.life.ui;

import java.awt.BorderLayout;
import java.awt.Dimension;

import javax.swing.JFrame;
import javax.swing.JScrollPane;
import javax.swing.JTable;

import conway.game.of.life.Cell;
import conway.game.of.life.datamodel.GameOfLifeModel;

public class GameOfLifeUI extends JFrame {
	/**
	 * 
	 */
	private static final long serialVersionUID = 6663772561171684137L;

	public GameOfLifeUI(int m, int n, String pattern) {
		setTitle("Conway's Game of Life");
		setSize(new Dimension(600, 600));
		JTable table = new JTable(m, n);
		GameOfLifeModel dataModel = new GameOfLifeModel(m, n,pattern);
		table.setModel(dataModel);
		table.setDefaultRenderer(Cell.class, new CellRenderer());
		JScrollPane jsp = new JScrollPane(table);
		getContentPane().add(jsp, BorderLayout.CENTER);
		setDefaultCloseOperation(EXIT_ON_CLOSE);
	}

}

- Muris Bandes January 28, 2014 | 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