DJ
BAN USER- 0of 0 votes
AnswersYou are given a set of 8 balls, all of them identical in appearance and weight, except for one which is slightly heavier than the rest. You are also given a scale with no units, which can only tell you if one load is heavier than the other (think a scale-of-justice type scale). How can you find the heavy ball with only two comparisons? You may place as many balls as you wish on either side of the scale for each comparison.
- DJ in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Brain Teasers - 0of 0 votes
AnswersGiven an integer N, populate an array of size N with the first N sum-of-squares. In other words, if you were given N=3, your array would be [1, 5, 14] (1^2, 1^2 + 2^2, 1^2 + 2^2 + 3^2).
- DJ in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm - 4of 4 votes
AnswersImplement a simple regex parser which, given a string and a pattern, returns a boolean indicating whether the input matches the pattern. By simple, we mean that the regex can only contain one special character: * (star). The star means what you'd expect, that there will be zero or more of any character in that place in the pattern. However, multiple consecutive stars are allowed. Some examples of valid input (and expected output):
- DJ in United States
f(a*b, acb) => true
f(abc*, abbc) => false
f(**bc, bc) => true| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Coding - 0of 0 votes
AnswersDesign a class structure for an airport terminal, where your primary use case is allocating runway time to approaching aircraft. For example, an instance of a terminal may have only two runways of different lengths and must schedule these among five aircraft of different types requesting permission to land.
- DJ in United States| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Object Oriented Design - 0of 0 votes
AnswerWrite a service or services to support tic-tac-toe between two players, on an infinite board. Normal rules apply (i.e. three in a row to win), but the players are not limited to a 3X3 board and can choose to place an X or an O in any arbitrary, positive (i, j) position. Solution should be as space and time efficient as possible. Your service is only responsible for maintaining and updating the state of the board between two players, given their sequence of moves.
- DJ in United States| Report Duplicate | Flag | PURGE
Microsoft Senior Software Development Engineer Coding
- 4 Answers How is my reputation so low?
I've contributed several thoughtful, detailed answers and one question which I quoted verbatim from the interviewer. I've been on and conducted dozens of interviews with top employers and received several offers, so I know the average quality of my contributions is high. Admittedly, the question I posted was vague, but do I really deserve to be down-voted into the ground until I have a -20 reputation? There are plenty more questions and answers I could contribute, but now I don't want to. It seems this community is focused on beating down its members for the slightest lapse while failing to recognize their positive contributions. That's not how you foster a positive community; hell, that's why I'm looking to leave my current employer. Please think before you down-vote, and if you are the kind who only down-votes, please stop. You are turning what should be a positive community into a negative one. Thanks.
- DJ April 19, 2013| Flag | PURGE
Thanks Gayle, I appreciate that. For the benefit of the community, here are some guidelines I try to follow in an up/down voting forum like this one or SO:
1. For every incorrect/vague post there are generally 2 or more useful ones. The ratio of my votes should reflect this.
2. IMO, the sole purpose of down voting is to help curate content which I feel might be misleading to other users or otherwise detracts from the discussion. I don't use it as a means to punish or correct.
3. If I down vote, I should try to leave a comment explaining why I did it. If my point is reasonably refuted, I should rescind my down vote.
4. Generally speaking, it is unnecessary to down vote any post that already has a negative score. Usually, a score of even -1 is enough to push a post to the bottom of the heap, effectively curating it.
O(2^N), no recursion, no caching
package questions;
public class CalculateTarget {
public static void main(String[] args) {
System.out.println(waysToTarget(new int[]{2,4,6,8}, 12));
System.out.println(waysToTarget(new int[]{0,10,20}, 30));
System.out.println(waysToTarget(new int[]{-6,-4,-2,0}, -2));
}
/**
* We need to account for both positive and negative of each value.
* The intuition here is that we simply treat the negative values
* like the second half of an extended array. Then this problem
* simplifies to finding each member of the powerset such that the
* sum of the members equals the target. This we can do by iterating
* from zero to 2^N, where N is the size of the extended array.
*/
public static int waysToTarget(int[] a, int target) {
int ways = 0;
int bits = a.length*2;
int halfbits = a.length;
// treat negative values like distinct values
int[] ary = new int[bits];
// mask to help ensure we don't use both x and -x
int himask = 0;
for(int i=0;i<halfbits;++i) {
ary[i] = a[i];
himask |= 1 << i;
}
int next = halfbits;
for(int i=0;i<halfbits;++i) {
// if zero is present, don't duplicate
if(a[i] == 0) {
--bits;
}
else {
ary[next++] = -1*a[i];
}
}
// iterate powerset, discarding +/- duplicates
int ceiling = (int) Math.pow(2, bits);
for(int i=0;i<ceiling;++i) {
int hibits = i >> halfbits;
int lobits = i & himask;
// if no duplicate bits set
if((hibits & lobits) == 0) {
// calculate the sum for the set bits
int sum = 0;
for(int j=0;j<bits;++j) {
int mask = 1<<j;
if((mask&i) == mask) {
sum += ary[j];
}
}
if(sum == target) ++ways;
}
}
return ways;
}
}
package questions;
import java.util.Arrays;
public class HasPerm {
public static void main(String[] args) {
System.out.println(hasPerm("abcdefg", "ba"));
System.out.println(hasPerm("abcdefg", "gf"));
System.out.println(hasPerm("abcdefg", "dc"));
}
public static boolean hasPerm(String source, String find) {
String k = key(find);
for (int i = 0; (i + find.length()) <= source.length(); ++i) {
String sub = source.substring(i, i + find.length());
if (key(sub).equals(k))
return true;
}
return false;
}
private static String key(String s) {
char[] ary = s.toCharArray();
Arrays.sort(ary);
return new String(ary);
}
}
I almost got this, but not quite. You can see that (4, 4) throws my approach due to hits at both x=4 and y=4, neither of which are the true nearest neighbor. Basically, I'm using a balanced BST for x-coords and y-coords, with the intuition being that we always want to minimize sqrt(x-delta^2 + y-delta^2), which means we want to only compare those cities which are closest in x and y:
package question;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class Main {
public static class City {
private String label;
private int x;
private int y;
public City(String label, int x, int y) {
this.label = label;
this.y = y;
this.x = x;
}
public double distance(int x, int y) {
return Math.sqrt(Math.pow(this.x - x, 2) + Math.pow(this.y - y, 2));
}
}
public static class Node {
Node l, r;
int val;
List<City> cities = new LinkedList<City>();
public Node(int v) {
val = v;
}
}
public static class Tree {
Node root = null;
public void insert(int n, City c) {
if(root == null) {
root = new Node(n);
root.cities.add(c);
}
else {
insertHelper(root, n, c);
}
}
private void insertHelper(Node node, int n, City c)
{
if(n == node.val) {
node.cities.add(c);
}
else if (n < node.val)
{
if (node.l == null) {
node.l = new Node(n);
node.l.cities.add(c);
}
else
insertHelper(node.l, n, c);
}
else
{
if (node.r == null) {
node.r = new Node(n);
node.r.cities.add(c);
}
else
insertHelper(node.r, n, c);
}
}
public List<City> nearest(int n) {
Node prev = root, curr = root;
while(curr != null && curr.val != n) {
prev = curr;
if(n < curr.val) {
curr = curr.l;
}
else {
curr = curr.r;
}
}
return (curr == null)? prev.cities : curr.cities;
}
}
private static final City DENVER = new City("Denver", 0, 0);
private static final City SEATTLE = new City("Seattle", -4, 5);
private static final City PORTLAND = new City("Portland", -2, 4);
private static final City SANFRANCISCO = new City("San Francisco", -3, -2);
private static final City LOSANGELES = new City("Los Angeles", -5, -3);
private static final City CHICAGO = new City("Chicago", 2, 3);
private static final City ATLANTA = new City("Atlanta", 3, 0);
private static final City MIAMI = new City("Miami", 4, -5);
private static List<City> cities = Arrays.asList(DENVER, SEATTLE, PORTLAND,
SANFRANCISCO, LOSANGELES,
CHICAGO, ATLANTA, MIAMI);
// Trees balanced by insertion order, not self-balancing
private static Tree xt = new Tree();
static {
xt.insert(DENVER.x, DENVER);
xt.insert(SEATTLE.x, SEATTLE);
xt.insert(LOSANGELES.x, LOSANGELES);
xt.insert(SANFRANCISCO.x, SANFRANCISCO);
xt.insert(PORTLAND.x, PORTLAND);
xt.insert(ATLANTA.x, ATLANTA);
xt.insert(CHICAGO.x, CHICAGO);
xt.insert(MIAMI.x, MIAMI);
}
private static Tree yt = new Tree();
static {
yt.insert(DENVER.y, DENVER);
yt.insert(ATLANTA.y, ATLANTA);
yt.insert(PORTLAND.y, PORTLAND);
yt.insert(CHICAGO.y, CHICAGO);
yt.insert(SEATTLE.y, SEATTLE);
yt.insert(LOSANGELES.y, LOSANGELES);
yt.insert(SANFRANCISCO.y, SANFRANCISCO);
yt.insert(MIAMI.y, MIAMI);
}
public static void main(String[] args) {
search(0, 0);
search(0, 1);
search(0, 2);
search(2, 2);
search(4, 4);
search(0, -1);
search(0, -2);
search(-2, 2);
search(4, -4);
}
private static void search(int x, int y) {
System.out.println("Searching for city nearest (" + x + ", " + y + ")");
linearSearch(x, y);
binarySearch(x, y);
}
private static void linearSearch(int x, int y) {
double min = Double.MAX_VALUE;
City nearest = null;
for(City c : cities) {
double dist = c.distance(x, y);
if(dist < min) {
nearest = c;
min = dist;
}
}
System.out.println("Linear search determined that " + nearest.label +
" is closest with " + cities.size() + " calculations.");
}
private static void binarySearch(int x, int y) {
List<City> candidates = new LinkedList<City>();
candidates.addAll(xt.nearest(x));
candidates.addAll(yt.nearest(y));
double min = Double.MAX_VALUE;
City nearest = null;
for(City c : candidates) {
double dist = c.distance(x, y);
if(dist < min) {
nearest = c;
min = dist;
}
}
System.out.println("Binary search determined that " + nearest.label +
" is closest with " + candidates.size() + " calculations.");
}
}
This is the question from the interviewer, verbatim. I agree it is unclear and poorly worded. Presumably the interviewer was looking for clarifying questions which I, unfortunately, did not ask much of. I assumed this was simply testing for length and looking it up in a HashSet which was apparently wrong. So part of this question involves interpreting the requirements.
- DJ March 10, 2013
How would you prioritize certain aircraft? For example, one might be low on fuel.
- DJ April 24, 2013