CodeSpace
BAN USER- 0of 0 votes
AnswerDesign a chess game. Basics of a chess game was explained and a player could be human or AI.
- CodeSpace in United States
Follow-up questions:
* What are the main objects?
* How do the main objects interact with each other?
* Which object or objects own the current game state information?
* Implement the method to move a piece to another position on the board. method must communicate if the move is legal or not.
* How do you test the move piece method?| Report Duplicate | Flag | PURGE
Apple Software Engineer / Developer Object Oriented Design
Solution uses a slow and fast runner approach. The slow and fast runners will meet if the linked list is looped. Depending on if the loop start at a odd or even point in the list the list count will be the number of steps the slow runner took up minus 1 to the point it is equal to the fast runner or step behind the fast runner.
class Node {
Node next;
int data;
}
int findLength(Node head) {
if(loopedList == null)
return -1;
if(head.next == null)
return 1;
if(head.next.next == null)
return 2;
Node slow = head;
Node fast = head.next.next;
int count = 1;
while(slow != null) {
if(slow.equals(fast)){
count--;
break;
}
if(slow.next.equal(fast))
break;
slow = slow.next;
fast = fast.next.next;
count++;
}
return(count)
}
Solution loops through the array once keeping track of the minimum index for 0,1,2. If the number at the previous index if greater than the current index number, then we swap the current index number with the minimum index of the number at previous index.
static void sort(int[] array) {
if (array == null || array.length < 1)
return;
int[] lastIndex = new int[3];
lastIndex[0] = -1;
lastIndex[1] = -1;
lastIndex[2] = -1;
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
for (int i = 0; i < array.length; i++) {
if (lastIndex[array[i]] == -1)
lastIndex[array[i]] = i;
if (i != 0) {
int current = array[i];
int prev = array[i - 1];
if ((prev - current) > 0) {
if ((prev - current) == 1 || lastIndex[1] == -1) {
swap(i, lastIndex[prev], array);
updateLastIndex(current, prev, i, lastIndex, array);
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
} else {
// swap 1 and 0
swap(i, lastIndex[1], array);
updateLastIndex(0, 1, i, lastIndex, array);
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
// swap 2 and 1
swap(i, lastIndex[prev], array);
updateLastIndex(current, prev, i, lastIndex, array);
System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
}
}
}
}
}
static void updateLastIndex(int current, int previous, int index, int[] lastIndex, int[] array) {
if (lastIndex[current] > lastIndex[previous])
lastIndex[current] = lastIndex[previous];
if (array[lastIndex[previous] + 1] == previous)
lastIndex[previous]++;
else
lastIndex[previous] = index;
}
static void swap(int i, int j, int[] array) {
array[j] ^= array[i];
array[i] ^= array[j];
array[j] ^= array[i];
}
public class CircularQueue{
private Integer[] queue = null;
private int head;
private int size;
private int tail;
public synchronized boolean initialize(int size){
if(size<1)
return(false);
this.size = size;
queue = new Integer[size];
head = 0;
tail = 0;
return(true);
}
public synchronized boolean enqueue(Integer data){
if(queue==null)
return(false);
int index = (head<size) ? head : (head%size);
tail += ((head-tail)==size)?1:0;
queue[index] = data;
head++;
return(true);
}
public synchronized Integer dequeue(){
if(queue==null || (head - tail)==0)
return(null);
int index = (tail<size) ? tail : (tail%size);
Integer value = queue[index];
tail++;
return(value);
}
}
Using a modified binary search to find the index of a number within a sorted array. Will return -1 if the index was not found
Edge cases:
* circular array null or empty
* circular array with 1 element
* circular array not rotated. e.g {1,2,3,4,5,6,7,8,9}
* circular array is inverted. e.g {9,8,7,6,5,4,3,2,1}
* circular array half rotated e.g {5,6,7,8,9,1,2,3,4}
* number is not in circular array
int findIndex(int[] array, int num){
if(array != null && array.length > 0)
return(search(array, num, 0, array.length - 1));
return(-1);
}
int search(int[] array, int num, int start, int end){
int mid = (start + end) / 2;
if(array[start] == num)
return(start);
if(array[end] == num)
return(end);
if(array[mid] == num)
return(mid);
if(end - start <= 1)
return(-1);
if(array[mid] > array[start] && array[start] < num && array[mid] > num)
return(search(array, num, start, mid));
if(array[mid] < array[start] && (array[start] > num || array[mid] < num))
return(search(array, num, start, mid));
if(array[mid] < array[end] && array[mid] < num && array[end] > num)
return(search(array, num, mid, end));
if(array[mid] > array[end] && (array[mid] > num || array[end] < num))
return(search(array, num, mid, end));
return(-1);
}
static final char[][] keyPad = {
{}, {}, { 'A', 'B', 'C' }, { 'D', 'E', 'F' }, { 'G', 'H', 'I' }, { 'J', 'K', 'L' },
{ 'M', 'N', 'O' }, { 'P', 'Q', 'R', 'S' }, { 'T', 'U', 'V' }, { 'W', 'X', 'Y', 'Z' }
};
static void printCombinations(int[] number) {
if (number != null && number.length > 0)
printer(number, 0, "");
}
static void printer(int[] number, int index, String current) {
if (index >= number.length) {
System.out.println(current);
return;
}
if (number[index] >= keyPad.length || keyPad[number[index]].length == 0) {
printer(number, index + 1, current);
return;
}
for (char c : keyPad[number[index]])
printer(number, index + 1, current + String.valueOf(c));
}
class Node{
Node left;
Node right;
int data;
};
class BarNode(
Node max;
int depth;
};
Node foo(Node root){
if(root==null)
return(null);
BarNode maxNode = bar(root, 1);
if(maxNode==null)
return(null);
else
return(maxNode.max);
}
BarNode bar(Node root, int depth){
if(root==null)
return(null);
if(root.left==null && root.right==null){
BarNode bNode = new BarNode();
bNode.depth = depth;
bNode.max = root;
return(bNode);
}
lBNode = bar(root.left, depth+1);
rBNode = bar(root.right, depth+1);
if(lBNode==null)
return(rBNode);
if(rBNode==null)
return(rBNode);
if(rBNode.depth>=lBNode.depth) // Prefers right node to left if they are at the same depth
return(rBNode);
return(lBNode);
}
Posting implementation for feedback.
void foo(int[] a){
int length = a.length;
if(length < 3){
System.out.printf("Error: Array needs to have at least 3 entries");
reutrn;
}
int k = length-1;
int j = k-1;
int i = j-1;
int temp = i-1;
while(temp>0){
if(a[i]>=a[temp])
i = temp;
temp--;
}
temp = j-1;
while(temp>i){
if(a[temp]>=a[i])
j = temp;
temp--;
}
temp = k-1;
while(temp>j){
if(a[temp]>=a[j])
k = temp;
temp--;
}
if(a[i]<a[j] && a[j]<a[k])
System.out.printf("%d, %d, %d", i, j, k);
else
System.out.printf("No entries in array where i<j<k and a[i]<a[j]<a[k]");
}
The questions states "...leftmost node is placed at point (0,0)..." So, this means that 4 (the left most node) will be at (0,0) and 1's y-axis will be 2 since it is 2 cardinal points on top of our reference point (0,0). 8 y-axis will be -1 since it is 1 cardinal point below the (0,0) reference point.
With the output you are expecting you can not have 4 at (0, 0) which is a requirement from the question.
Does this make sense?
I also tested the code and it does work for me using the data set in the question.
What data set are you using for testing?
How did you construct you binary tree?
Did you verify that the contents of your binary tree is correct?
Is there any additional information you can provide to help me reproduce what you might be seeing?
Posting implementation for feedback
class Node{
Node left;
Node right;
char data;
};
static int x, y;
void printTree(Node root){
x = -1;
y = -1;
printTreeRecursive(root);
}
void printTreeRecursive(Node root){
if(root == null)
return null;
if(root.left == null && x == -1){
x = 0;
y = 0;
}
if(root.left != null){
if(x != -1){
y--;
}
printTreeRecursive(root.left);
y++;
}
System.out.println("%c,%d,%d", root.data, x, y);
x++;
if(root.right != null){
y--;
printTreeRecursive(root.right);
y++;
}
}
void countChars(char * inString){
if(inString == NULL)
return;
int start = 0;
int index = 0;
int insert = 0;
int count = 0;
while(inString[index] != NULL){
while(inString[index] == inString[start]){
index++;
}
inString[insert] = inString[start];
insert++;
count = index - start;
if(count > 1){
insert += sprintf(inString[insert], "%d", count);
}
index++;
start = index;
}
if(insert != 0 && insert < strlen(inString))
inString[insert] = NULL;
}
Posting for feedback on implementation.
final int MAX_SIZE = 10; // Can set to whatever you want.
final int cube[][][] = new int[MAX_SIZE][MAX_SIZE][MAX_SIZE];
void printPathToSurface(int x, int y, int z){ // input can be the center location
printPaths(x, y, z, "");
}
void printPaths(int x, int y, int z, String prevPath){
if(x < 0 || y < 0 || z < 0 || x >= (MAX_SIZE) || y >= (MAX_SIZE) || z >= (MAX_SIZE))
return;
if(x == 0 || x == (MAX_SIZE - 1) || y == 0 || y == (MAX_SIZE - 1) ||
z == 0 || z== (MAX_SIZE - 1)){
System.out.println(prevPath);
return;
String path = new String(prevPath);
path += "(" + String.valueof(cube[x]) + "," + String.valueof(cube[y]) + "," +
String.valueof(cube[z]) + ")"
for(int i=x-1; i<=x+1;i++){
for(int j=y-1; j<=y+1;j++){
for(int k=z-1; k<=z+1;k++){
printPaths(i, j, k, path);
}
}
}
}
Solution prints all possible paths allowed and returns the path with the max sum.
final int MAX_SIZE = 10;
int matrix[MAX_SIZE][MAX_SIZE];
class Foo{
String sting;
int data;
}
String printPaths(int row, int col){
Foo foo = printPathsRecursive(int row, int col, "");
return(foo.string);
}
Foo printPathsRecursive(int row, int col, Sting prevPath){
if(row < 0 || col < 0 || row >= MAX_SIZE || col >= MAX_SIZE)
return(null);
if(row == MAX_SIZE){
Foo foo= new Foo();
foo.string = prePath + matrix[row][col];
foo.data = matrix[row][col];
System.out.println(foo.string);
return(foo);
}
String path = new String(prevPath);
path += matrix[row][col] + "-";
Foo path1 = printPaths(row+1, col, path);
Foo path2 = printPaths(row+1, col+1, path);
Foo path3 = printPaths(row+1, col-1, path);
if(path1 != null && (path2 == null || path1.data >= path2.data) && (path3 == null || path1.data >= path3.data)){
path1.data += matrix[row][col];
return(path1);
}
if(path2 != null && (path1 == null || path2.data >= path1.data) && (path3 == null || path2.data >= path3.data)){
path2.data += matrix[row][col];
return(path2);
}
if(path3 != null && (path2 == null || path3.data >= path2.data) && (path1 == null || path3.data >= path1.data)){
path3.data += matrix[row][col];
return(path3);
}
}
Solution does an initial inorder traversal of the tree and populating the queue with the nodes inorder.
class Node{
public int data;
public Node left;
public Node right;
}
public class InorderTreeIterator implements Iterator {
LinkedList<Node> nodeQueue;
Node currentNode;
public InorderTreeIterator(Node root){
nodeQueue = new LinkedList<Node>
initializeQueue(root);
}
public boolean hasNext(){
return(!nodeQueue.empty());
}
public Node next(){
if(hasNext())
return(nodeQueue.removeFirst());
return(null);
}
private initializeQueue(Node root){
if(root = null)
return;
initializeQueue(root.left);
nodeQueue.addLast(root);
initializeQueue(root.right);
}
}
class Node{
int data;
Node children; // Linked list of children
}
Node DFS(int data, Node root){
if(root == null)
return(null);
if(root.data == data);
return(root);
Node child = root.children;
while(child != null){
if(child.data == data)
return(child);
Node returnVal = DFS(data, child);
if(returnVal != null)
return(returnVal);
child = child.next();
}
return(null);
}
Node BFS(int data, Node root){
LinkedList<Node> queue = new LinkedList<Node>();
queue.addLast(root);
return(BFSRecursive(data, queue));
}
Node BFSRecursive(data, queue){
Node node = queue.getFirst();
if(node != null)
return(null);
if(node.data == data)
return(Node);
Node child = node.children;
while(child != null){
if(child.data == data)
return(child);
queue.addLast(child);
child = child.next();
}
return(BFSRecursive(data,queue));
}
int findElement(int value, int array[]){
return(modifiedBinarySearch(value, array, 0, array.length);
}
// Modified binary search function that detects rotation in array
// and compensates accordingly.
int modifiedBinarySearch(int value, int array[], int start, int end){
// Base case for recursive method
if(end - start <= 1){
if(array[start] == value)
return(start);
else if(array[end] == value)
return(end);
else
return(-1);
}
int mid = (start + end) / 2;
// Another exit base case
if(array[mid] == value)
return(mid);
if (array[start] < array[mid]) &&
array[start] < value && array[mid] > value)
// First half of array is not rotated and value is within its range
return(value, array, start, mid);
if (array[start] > array[mid]) &&
(array[start] < value || array[mid] > value))
// First half of array is rotated and value is within its range
return(value, array, start, mid);
if (array[mid] < array[end]) &&
array[mid] < value && array[end] > value)
// Second half of array is not rotated and value is within its range
return(value, array, mid, end);
if (array[mid] > array[end]) &&
(array[mid] < value || array[end] > value))
// Second half of array is rotated and value is within its range
return(value, array, mid, end);
// Value is not is array
return(-1);
}
Posting a possible solution to the problem to get comment and feedback. Solution uses an Hashmap to store the real URL and the tiny URL where the tiny URL is the key and the real URL is the value. The tiny URL is generated by counting through characters the same way you count through numbers. A single character can give you 256 entries.
static final String fixedURLPart = "fixedURLPart";
static Hashmap<String,String> urlMap = new Hashmap<String, String>;
// Generates the Tiny URL
String generateTinyURL(String inURL){
String tinyURL = fixedURLPart + getNextString();
urlMap.put( tinyURL, inURL );
return(tinyURL);
}
// Returns the URL
String getRealURL(String tinyURL){
return(urlMap.get(tinyURL));
}
// Should be able to generate 2,560,000,000 tiny URLs with this.
// This will take up 9.54MB. Can increase number to increase scale.
static char[] charList = new char[10000000];
static int i = 0;
// Generates the unique string for each tiny URL
String getNextString(){
if(charList = null){
charList = new char[1];
charList[0] = (char)0;
} else {
int savedi = i;
while(i < charList.length){
if(charList[i] < 255)
charList[i] = (char)((int)charList[i] + 1);
break;
else{
charList[i] = (char)0;
i++;
}
}
i = savedi;
}
return(new String(charList));
}
- CodeSpace October 02, 2012Java implementation. I see there are already several solutions posted for this problem.
I just wanted to put my solution out there for feedback.
Implementation takes in the head node of 2 linked lists as input and returns the node head of the linked list that contains their sum. The first portion of the addList method iterates through the 2 input list and adds each node until the end of the shortest input list is reached. If both list are the same length we are done. Assuming the number in a node ranges from 0 to 9 (going off the example), then the carry over to the next significant node will always be 1 and the data left in the current node will be (currentSum - 10). E.g. if you add 9 + 9 = 1(carry over to next node)8(current node sum). The second part of the adds the remaining nodes to the output node if we happened to have list of different lengths (i.e. one of the input list reaches null before the other). In this case the short list node entries are treated as 0 entries, which is equivalent to just copying the longer list node entries over.
public class Node{
public Node next;
public int data;
}
static Node addList(Node listOne, Node listTwo){
int carryOver = 0;
int dataSum = 0
Node sum = new Node();
Node currentNode = sum;
while(listOne != null || listTwo != null){
dataSum = ((listOne != null) ? listOne.data : 0) + ((listTwo != null) ? listTwo.data : 0)
dataSum += carryOver;
carryOver = 0;
if(dataSum > 10 ){
carryOver = 1;
dataSum -=10;
}
currentNode.data = dataSum;
currentNode.next = new Node();
currentNode = currentNode.next;
listOne = (listOne != null) ? listOne.next : null;
listTwo = (listTwo != null) ? listTwo.next : null;
}
if(carryOver){
currentNode.data = 1;
}
currentNode.next = null;
return(sum);
}
I am making some assumption on being able to call on resources within a single method.
public Class Resourcethread extends Thread{
// thread safe resource processing function.
void synchronized run(){
A1();
B1();
A2();
B2();
}
}
// Thread calls. Can be in any order.
Resourcethread T1 = new Resourcethread()
T1.start();
Resourcethread T2 = new Resourcethread();
T2.start();
- CodeSpace December 31, 2012