CareerCup

Roy that solution does not work. See the above post by "Anonymous" (it was me). It will fail that tree.

@aimHigh

good catch - you are correct. my code did not match my logic. i didn't test out my above code but the expected behavior should be:

no key exists for 6144/4096->1, so lookup in chunk 0.

it seems like you have a grasp of the algorithm I was intending to portray. do you need any further clarification?

@searching, yes that is correct.

I have drawn out different possible combinations of how memory could be allocated. Here is an image depicting those cases:

img577.imageshack.us/img577/4985/q41y.jpg

Most notably, please take a look at the table I drew at the bottom of the page.

I also conducted a few (not thorough) traces of code that should help with understanding my logic in the above code. The traces for tests cases A, B, C, B+C can be found here:

img851.imageshack.us/img851/3765/q42.jpg

I am not sure how to clarify further but I hope that this helps. You can see that Case A requires only one lookup, but cases B, C, and B+C require 2 lookups to get an answer. Take the examples and traces with a grain of salt - they are meant to get the general idea across.

Hope this helps.

you're welcome! :)

here is the actual code for now...did not check for syntax, minor errors, etc. I will post reasoning for the if-statement conditions later today if I can. It would just be illustrations of what I explained above.

/* Assume HashMap hash has key-value pairs of type <Integer, Integer> */
/* auto/unboxing in java means I don't care about Integer<->int conversions */

public int lookup(int lookup) {
  Integer input_address = lookup;
  int address_return, new_return_value;
  if (hash.containsKey(input_address/4096)) {
    address_return = hash.get(input_address/4096);
    if (input_address >= address_return)
      return address_return;
    if (input_address < address_return) {
      if (hash.containsKey(input_address/4096 - 1)) {
        new_return_value = hash.get(input_address/4096 - 1);
        if (new_return_value + 4096 > input_address)
           return new_return_value
        else
           return -1;
      } else {
        return -1;
      }
    }
  } else {
    return -1;
  }
  return -1; /* shouldn't get here, ever */
}

what does that have to do with the question?

XYZ is correct...Anonymous, how else are you supposed to work with the data if not with pointers or integers identifying indices??

No extra memory simply means don't try to copy the string into a new string..do everything in-place is all.

Hey, good idea! I would clarify this with the interviewer (I did during the interview) - the data shouldn't be collected in real time. It will be given as the following (though you were supposed to derive this struct in some form or another for the first part of the interview):

Also, just to make life easier, you can assume that all of the data being fed to you is already constrained to one customer of interest. Work with the following structure (assume you are given a list of the following structure):

typedef struct phone_call {
unsigned user_id; /* arbitrary since all data being fed is for one customer */
unsigned int start_time;
unsigned int call_length;
} phone_call;

you should not have that constraint as 0-4095 are valid input and output values

First sorry - a reasonable approach to return false would be to return a negative number. I did not word the question correctly.

I did not get into conserving space or breaking down the problem into bits. I don't think the interviewer was looking for that given his nudges during my interview. You can use either an array or a hashtable. The interviewer preferred that I use a hashtable (the logic is almost identical).

The logic behind my solution was as follows (with pseudocode):

Since memory is allocated 4k at a time, break the memory addresses into 4k chunks. These chunks will serve as the hashtable keys.

Now we need to determine what the hashtable will store. Before we get to that, let's consider various allocation scenarios (using memory address 4096 as an example):

1. No objects were allocated in 4096
2. One allocation was done, before 4096, but which proceeds past 4096
3. One allocation was done, at/after 4096, which proceeds until/past 8192
4. There were two allocations, one before 4096 and one after first_allocation + 4096;

I decided to store the following:
IF an allocation begins in a certain chunk [chunk# * 4096, (chunk#+1)*4096), store the address of where the allocation begins. The hashtable mapping would be chunk#->allocated memory address.

My logic would then be:

1. Calculate the hash code (input_address/4096).
2. Check if the hashtable has the key from (1).
   - if no key exists, return -1 ("false").
3. If it has the key, compare the value returned to your input_address:
   - if input_address >= address_return, 
     - return address_return
   - if input_address < address_return,
     - lookup the key (input_address/4096 - 1) --> new_return_value
       - if key does not exist,
         - return -1 ("false").
       - if new_return_value > input_address - 4096,
         - return new_return_value
       - else, return -1 ("false").

If it is unclear, let me know.

I had about 30 minutes for the problem. I only had to define the structure and write the verify() method. I did not have to code building & inserting.

FWIW, I said trie during the interview and justified it with all of the repetition of letters in words. my structure had the following fields:

1. char data
2. int is_legitimate_ending (e.g. can a word end at this node)
3. node **children (dynamically allocated array of node pointers)

I debated using a double pointer for children or an array of pointers (e.g. size 256 if assuming ASCII) but went with the double ptr because you can (1) save space and (2) include more than 256 characters. array would have had a more constant time lookup than iterating through the dynamically allocated array though.

congrats!! i just got an offer today as well :) thanks largely in part to gayle's book and the community here. mine was for an internship in seattle, wa as an SDE. what was yours?

you should consider each interview to be an evaluation..and (evidently, see below) just because you thought you did poorly doesn't mean that you did poorly.

i just had two on-campus interviews for amazon back-to-back and though i cruised through the first interview, i only got 1 out of 3 questions in the second interview, and the latter 20 minutes of my 45 minutes was me struggling to find answers to the remaining questions. but they sent me an offer today and i think the second interviewer's last question was not designed to be solvable in the given time, but they were probably rather evaluating a candidate's reactions and seeing how they attempted to tackle the problem, their persistence, etc.

@bob, instead of reversing the number at the end you can also, calculate the number of digits beforehand, and set values by decrementing a pointer.

also, be sure to take into account negative numbers if the interviewer wants.

just use XOR. numbers that show up an even number of times will cancel. the value of final will reflect the odd element.

int final = 0;
for (int i=0; i<n; i++)
  final ^= a[i];

you should also make sure you don't have duplicates. it's not clear given the question if we should have the numbers be sorted, either.

try this:

5
     3         8
   1   6     7   9

try this:

5
     3         8
   1   6     7   9

Non-Recursive function in Java (e.g. if you want to call it on another node)

public class Node<T extends Comparable<T>> {
	private Node<T> left = null;
	private Node<T> right = null;
	private T data = null;
	private boolean flagged = false;

...

	public void flag() {
		flagged = true;
	}
	
	public boolean isFlagged() {
		return (flagged);
	}

	public void unflag() {
		if (left != null)
			left.unflag();
		flagged = false;
		if (right != null)
			right.unflag();
	}
	
	public boolean isBST(Node<T> t) {
		T old = null;
		T _new = null;
		Node<T> temp = null;
		Queue<T> queue = new LinkedList<T>(); /* will store the list of sorted nodes */
		Stack<Node <T>> stack = new Stack<Node <T>>(); /* recursive stack */
		stack.push(t);
		while (!stack.isEmpty()) {
			temp = stack.pop();
			if (temp.getRight() != null) {
				stack.push(temp.getRight());
			}
			if (!temp.isFlagged())
				stack.push(temp);
			if (temp.getLeft() != null) {
				stack.push(temp.getLeft());
			}
			if (!temp.isFlagged() && (temp.getLeft() == null || temp.getLeft().isFlagged())) {
				queue.add(temp.getData());
				temp.flag();
			}
		}
		t.unflag(); /* unflags all nodes */
		if (!queue.isEmpty())
			old = queue.poll();
			System.out.println(old);
		while (!queue.isEmpty()) {
			_new = queue.poll();
			System.out.println(_new);
			if (_new.compareTo(old) < 0)
				return false;
			old = _new;
		}
		return true;		
	}
}

Code in Java:

private void InOrderQueue(Queue<T> q) {
		if (left != null)
			left.InOrderQueue(q);
		q.add(data);
		if (right != null)
			right.InOrderQueue(q);
	}
	
	public boolean isBST() {
		T old = null;
		T _new = null;
		Queue<T> queue = new LinkedList<T>();
		InOrderQueue(queue);
		if (!queue.isEmpty())
			old = queue.poll();
		while (!queue.isEmpty()) {
			_new = queue.poll();
			if (_new.compareTo(old) < 0)
				return false;
			old = _new;
		}
		return true;
	}

I can see why the other code broke, thank you.

But does this work? When you run the following code:

if(r_.value.intValue() < pivot.intValue()) 
				return false;
			else{
				pivot = r_.value;
				return true;
			}

if the latter case is true, pivot = r_.value does not do anything because it doesn't change the pivot value outside the scope of the function..once it returns the pivot will be the same as it was before calling the function on that specific node.

Tracing your code I see the following calls (on your tree):

isBSTImpl(Node 5, -1)
->isBSTImpl(Node 3, -1)
--->isBSTImpl(Node 1, -1) /* returns true */
--->set pivot to 3
--->isBSTImpl(Node 6, 3) /* returns true */
->set pivot to 5
->isBSTImpl(Node 7, 5) ...

so I think it still fails?

AFAIK that will only cause an infinite loop - it will freeze the program but won't crash the system. a forkbomb can be implemented like this..it has a similar concept to what you did except instead of calling itself again and again, it will make a new process and both will call it, then 4 processes, etc...2^n processes will be made:

#include <unistd.h>
 int main(void)
{
  for(;;)
    fork(); /* each time this is called, # processes *=2 */
  return 0;
}

When I first learned BSTs most of the time we had allowed duplicates - but that was practice and not actually storing key->value pairs using the BST. Thanks for the heads up - I better just ask the interviewer if duplicates are allowed before I get coding :).

if your snake is going zigzag and touching itself, how will you find out in which direction the tail should shorten? E.g.

v- tail
  XXXXXX
       X
       X
   XXXXX
   XXXXX
   XXXXX
   XXXXXXXX <-- head

In the blob at the end..how do you know if the snake went

.---'
   `---.
   .---'
   `------| <-- head

versus

/\/\|
   |||||
   |\/\/
   '------| <-- head

Instead...how about have 0 for empty space, -1 for apple, -2 for wall, and each part of the snake has a value that counts up? e.g. the first part of the snake is 1, then 2, 3, 4,...50,51,...99,100. to erase then just check surrounding boxes for the box with the next highest digit and erase.

you will need to take into account the values getting too large, though, and will need to find an appropriate time to reset the values. (if you're storing ints in the array...you will be able to move ~2million spaces before this happens, though).

#include <math.h>
#define _X 1
#define _Y 0

typedef struct rectangle {
  int x1; /* bottom side of rectangle */
  int y2; /* left side of rectangle */
  int width;
  int height;
} rectangle;

int get_center(rectangle *r, int is_x) {
  if (r == NULL)
    return 0;
  if (is_x)
    return ((r->x1+r->width)/2);
  else
    return ((r->y1+r->height)/2);
}

int intersecting(rectangle *r1, rectangle *r2) {

  int r1cx, r1cy, r2cx, r2cy;

  if (r1 == NULL || r2 == NULL)
    return;

  r1cx = get_center(r1, IS_X);
  r2cx = get_center(r1, IS_X);
  r1cy = get_center(r2, IS_Y);
  r1cy = get_center(r2, IS_Y);

  if ((abs(r1cx-r2cx) <= (r1->width+r2->width)/2) && \
      (abs(r1cy-r2cy) <= (r1->height+r2->height)/2))
    return true;
  return false;
}

pardon small typos if there are any; didn't compile this.

Almost. You can't assume they intersect if one condition is fulfilled or the other. Your example would pass if two rectangles had centers at the same y value but were very far apart from each other and never intersected. You would need to verify that |y2-y1| <= (h1+h2)/2 AND |x2-x1| <= (w1+w2)/2.

this code is mostly correct.

change one of the testing conditions to include an equals sign.

e.g.: rootNodePtr->left && rootNodePtr->key <= rootNodePtr->left->key

OR

e.g.: rootNodePtr->right && rootNodePtr->key => rootNodePtr->right->key

depends on the implementation I suppose. Ask a clarifying question if equals goes on the left or the right.

In C

void swap_every_two(node **head) {
  node *current = *head;
  node *next = NULL;
  node *prev = NULL;
  if (head == NULL)
    return;
  if (*head == NULL) /* no elements */
    return;
  if ((*head)->next == NULL) /* only one element */
    return;
  *head = current->next; /* update the head pointer */
  next = current->next;
  current->next = next->next;
  next->next = current;
  prev = current;
  current = current->next;
  while (current != NULL && current->next != NULL) {
    next = current->next;
    current->next = next->next;
    next->next = current;
    prev->next = next;
    prev = current;
    current = current->next;
  }
}

a 2 dimensional array can store where flags, etc. are. you can consider a 3 dimensional array as well - the third dimension can have the bomb/no bomb information as well as store a visible/flagged/hiding state.

you could also store two 2 dimension arrays i suppose, but that would take up more space.

by the way i would guess a trie..and i use a char to store each digit because they are 1 byte whereas short=2, int=4.

doesn't your code cause inversions in the lists? e.g. +ve and -ve orders are not preserved?

e.g.: assume the list is -1 -2 -3 -4 -5 6 7 8 9
will your program output -1 6 -2 7 -3 8 -4 9 -5?

or will it's first step be to swap: -1 [6] -3 -4 -5 [-2] 7 8 9?

does the original order need to be maintained?

also @rajendra: list generally preserves order while set does not guarantee it.

you can use the sizeof function...

eg..for int: sizeof(int)
for char pointer: sizeof (char *)
for your own structure: sizeof (struct my_structure)

a forkbomb might do it

and the datatype:

typedef struct node {
 struct node *next;
 void *data;
} Node;

my solution in C:

void reverse(Node **head) {
 Node *current = *head;
 Node *next;
 Node *temp;
 if (head == NULL || *head == NULL || (*head)->next == NULL)
  return;
 temp = current->next;
 current->next = NULL;
 while (temp != NULL) {
  next = temp->next;
  temp->next = current;
  current = temp;
  temp = next;
 }
 *head = current;

}

I used 3 pointers. Not sure if you can do it with two. If anyone has any suggestions please let me know! handles even # of nodes, odd # of nodes, 0, 1, 2 nodes.

void swap_every_two(node **head) {
  node *current = *head;
  node *next = NULL;
  node *prev = NULL;
  if (head == NULL)
    return;
  if (*head == NULL) /* no elements */
    return;
  if ((*head)->next == NULL) /* only one element */
    return;
  *head = current->next; /* update the head pointer */
  next = current->next;
  current->next = next->next;
  next->next = current;
  prev = current;
  current = current->next;
  while (current != NULL && current->next != NULL) {
    next = current->next;
    current->next = next->next;
    next->next = current;
    prev->next = next;
    prev = current;
    current = current->next;
  }

}

Ah good call. Thank you for that!

You will need two stacks.

Everytime you want to enqueue, push into s1.
When you want to dequeue, push all of s1 into s2, and pop from s2.
As long as you continue to dequeue, pop from s2.
If you receive any more enqueue commands, push all of s2 into s1 before pushing into s1.
As long as you continue to enqueue, just push into s1.

That should cover all of the general cases. Check for empties, etc. of course!