Yev
BAN USERFinancial Software Engineer
- 0of 0 votes
AnswersProblem:
- Yev in United States for Anti-money laundering
8 balls, where 7 have equal weight, one does not. Find minimum times to use a scale to find ball that is not equal weight.
Interviewer answer: weight 6 balls. Choose balls from lighter side. Total two attempts. This is the average case but not the best case.
This is not true in all cases and the interviewer did not see this...
Best case:
Pick two balls. One may weight less, so the lighter ball is found with one attempt. This is the best case.
Worst case: If first two balls are equal, weight 6 balls. Choose balls from lighter side. Weight again. Total three attempts.| Report Duplicate | Flag | PURGE
BMO Harris Bank Software Developer Algorithm - 0of 0 votes
AnswersGiven a 2-dimensional square matrix, rotate the matrix clockwise. Imagine concentric circles. Input from stdin: first line is length, subsequent lines are rows of the matrix. Output the matrix to stdout. This was one of the questions. You have 2 hrs to complete it.
- Yev in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Java - 0of 0 votes
AnswersSuppose you have strings read in from a stream, e.g., '()(,)(())'. Detect if the parenthesis pair up correctly.
- Yev in United States
Part 1: How would you use threads to solve the problem?
Part 2: He then gave me an iterative solution and asked how the problem can be done distributively across multiple components.| Report Duplicate | Flag | PURGE
Here Software Developer Algorithm - 1of 1 vote
AnswersGiven a hashmap, HashMap<String,List<String>> with the following data:
- Yev in United States
A: B,C
B: X Y
X: Z
Y: Z
Expected output is an array of the dependencies. I initially started with Breadh-first search for simplicy, which had running O(|V|+'E') and space O(|V|). The interviewer said depth-first search is better; I don't see how DFS is better, because it requires recursion.
Part2: He then said my solution is functionally correct and then introduced a circular dependency and asked how to resolve it. I said using a visited hashset will detect a circular dep. He said it's not quite right and there a few approaches.| Report Duplicate | Flag | PURGE
Here Software Developer Java - 0of 0 votes
AnswersGiven a string of english characters. Find the character that appears only once. I used arr[256] to store a count of each character. Then, iterate over the array to find the first non-dup, a[iter+'a']==1. The interviewer thought that storing a[iter]='x' (dup) and a[iter]=<index> was a better solution to avoid running a second pass over the string. In my mind, I disagreed using the array index, one can find the character that appears only once. The interviewer persisted, and told me to think about it.
- Yev in United States| Report Duplicate | Flag | PURGE
Here Software Developer Java - 0of 0 votes
AnswersSuppose you have a 2 stream of integers. How would you randomly select a sample of size N, with equal probability?
- Yev in United States| Report Duplicate | Flag | PURGE
Spins Software Engineer Algorithm - 0of 0 votes
AnswersImplement a bowling game. First person took 40 mins to make sure I understood the scoring of bowling. Got stuck on coding an open-frame/strike/open-frame and time ran out with the second interviewer.
- Yev in United States
class Frame
def initialize
@rolls=[]
end
def roll(pins_down)
end
def score
end
end
class Game
attr_reader :frames
def initialize
@frames=[]
end
def score
end
end| Report Duplicate | Flag | PURGE
Centro Software Developer Ruby - 0of 0 votes
AnswersDescribe the different ways to determine if an integer is a power of 2.
- Yev in United States
He was looking for a solution other than dividing by 2.
I suggested initially log2X. They said it has some rounding issues in certain environments. I continued to doing bitwise arithmetic.| Report Duplicate | Flag | PURGE
Vail Systems Software Engineer / Developer Coding - 0of 0 votes
AnswersInput: String array. The output of the method should be the String value out of the array passed in that contains the least number of numeric characters. If two Strings have the same number of numeric characters, return the longest String. If two Strings have the same number of numeric characters and are the same length, return the String that appears first in the input array. If the array is empty, return null.
- Yev in United States for Products| Report Duplicate | Flag | PURGE
GrubHub Software Engineer / Developer Java - 0of 0 votes
AnswersWrite a function that takes 2 arguments: a binary tree and an integer N, it should return the N-th element in the inorder traversal of the binary tree. I asked the interviewer if I could use a 3rd argument to store the result; he said okay.
- Yev in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a node in a BST, find the next biggest node. Node can be left child, right, root, etc. Code this.
- Yev in United States| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Algorithm - 0of 0 votes
AnswersWrite Preorder traversal of a BST, iteratively using a Stack?
- Yev in United States| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Algorithm - 0of 0 votes
AnswersWhat is Serial ID corresponding to serialization?
- Yev in United States| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Java - 0of 0 votes
AnswersWhen/why would you not use the final keyword?
- Yev in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Java - 0of 0 votes
AnswersWhat is volatile?
- Yev in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Java - 0of 0 votes
AnswersWhat lock does the thread acquire if you call a synchronized object/static method?
- Yev in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Java - 0of 0 votes
AnswersIf you had to make a List immutable, would you extend List or ArrayList?
- Yev in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Application / UI Design - 0of 0 votes
AnswersWhat are the cons of making every object Serializable?
- Yev in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Java - 0of 0 votes
AnswersWhere/when would you use final?
- Yev in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Java - 0of 0 votes
AnswersWhat's the difference between a Hash Table & Hash Map? How would you handle a collision where key/hash are different, and visa-versa?
- Yev in United States for Risk Metrics| Report Duplicate | Flag | PURGE
Highbridge Capital Java Developer Data Structures
Best-case: O(n)
public static void pair(final int[] array) {
int max1st = array[0];
int max2nd = array[0];
int min1st = array[0];
int min2nd = array[0];
boolean isAllNeg = true;
boolean isAllNatural = true;
for (int iter = 1; iter < array.length; iter++) {
final int currValue = array[iter];
if (currValue < 0) {
isAllNatural = false;
} else {
isAllNeg = false;
}
if (currValue < min1st) {
min2nd = min1st;
min1st = currValue;
} else if ((min2nd == min1st) && (currValue < min2nd)) {
min2nd = currValue;
}
if (currValue >= max1st) {
max2nd = max1st;
max1st = currValue;
} else if ((max2nd == max1st) && (currValue > max2nd)) {
max2nd = currValue;
}
}
if (isAllNatural) {
System.out.println(min1st + " " + min2nd);
return;
} else if (isAllNeg) {
System.out.println(max1st + " " + max2nd);
return;
} else {
// Java's randomized quicksort, avg nlogn
Arrays.sort(array);
int leftIter = 0;
int rightIter = array.length - 1;
boolean modified = true;
while ((leftIter < rightIter) && modified) {
modified = false;
if ((array[leftIter] + array[rightIter]) == 0) {
System.out.println(array[leftIter] + " " +
array[rightIter]);
break;
} else if (((array[leftIter] + array[rightIter]) > 0) &&
(Math.abs((array[leftIter] + array[rightIter - 1])) < Math.abs((array[leftIter] +
array[rightIter])))) {
rightIter--;
modified = true;
} else if (((array[leftIter] + array[rightIter]) < 0) &&
(Math.abs((array[leftIter + 1] + array[rightIter])) > Math.abs((array[leftIter] +
array[rightIter])))) {
leftIter++;
modified = true;
}
}
System.out.println(array[leftIter] + " " + array[rightIter]);
}
}
First, counting sort may be optimized using a hashtable instead of an array, thereby reducing memory overhead and eliminating the concern of the input range.
For this problem, counting sort will not be good because some of the integers may be negative, thereby forcing you to create a hashcode for negative ints, which is not a simple task to do since the hashcode could collide with other values in the 32-bit integer range.
public static void insert(Node head,Node newNode)
{
if(head==null)return;
else if(head.next==null || head.next==head)
{
head.next=newNode;
newNode.next=head;
return;
}
final Node[] pair={head,head.next};
do
{
if(pair[0].value <= newNode.value && newNode.value<= pair[1].value)
{
pair[0].next=newNode;
newNode.next=pair[1];
return;
}
else
{
pair[0]=pair[0].next;
pair[1]=pair[1].next;
}
}while(pair[0]!=head);
}
// move all odd elements into 1st half, even elements into 2nd half
public static int[] sort(final int[] array) {
int iter = 1;
for (iter = 1; iter < (array.length / 2); iter++) {
if ((iter % 2) > 0) {
swap(array, iter, (array.length / 2) - 1 + iter);
}
}
// Quicksort(in-place), avg nlogn performance provided by Java
Arrays.sort(array, 0, (array.length / 2));
Arrays.sort(array, array.length / 2, array.length);
return array;
}
Total running time: O(n + nlogn)
public static int sum(final String str) {
int sum = 0;
int base = 1;
for (int startIter = str.length() - 1; startIter >= 0; startIter--) {
if ((str.charAt(startIter) >= '0') &&
(str.charAt(startIter) <= '9')) {
sum += ((str.charAt(startIter) - '0') * base);
base *= 10;
} else {
base = 1;
}
}
return sum;
}
Use depth-first search because it's not a BST. BT simplifies the problem, since each node is part of a sub-linked list:
Two possibilities:
X->...->Y...->...Z or Z->...-> Y -> ... -> X
1. Find X or Z first and mark as visited. If Y found first, return false.
2. Find Y and mark as visited; if X/Z found instead, return false.
3. Find X/Z as end of path, and mark as visited. If found, return true.
public static boolean isBST(Node root) {
if (root == null) {
return false;
}
boolean isLeftBST = false;
boolean isRightBST = false;
if (root.left == null) {
isLeftBST = true;
}
else if (root.left.value <= root.value) {
isLeftBST = isBST(root.left);
}
if (root.right == null) {
isRightBST = true;
} else if (root.value <= root.right.value) {
isRightBST = isBST(root.right);
}
return isLeftBST && isRightBST;
}
Need to merge the biggest element first(relative to end of arrayA to preserve in-place sorting:
public static int[] merge(final int[] arrayA, final int[] arrayB) {
for (int iterB = arrayB.length - 1, iterASelect = arrayB.length - 1, iterAInsert =
arrayA.length - 1; iterB >= 0;) {
if ((iterASelect >= 0) && (arrayB[iterB] >= arrayA[iterASelect])) {
arrayA[iterAInsert] = arrayB[iterB];
iterB--;
iterAInsert--;
}
else if ((iterASelect >= 0) &&
(arrayB[iterB] < arrayA[iterASelect])) {
arrayA[iterAInsert] = arrayA[iterASelect];
iterAInsert--;
iterASelect--;
}
else {
arrayA[iterAInsert] = arrayB[iterB];
iterB--;
iterAInsert--;
}
}
return arrayA;
}
Assuming the array is unique(if not, extend the TreeSet to support dups):
Need two TreeSets to avoid ConcurrentModificationException in Java:
public void permutate(String head, final SortedSet<Integer> subset) {
if (subset.size() == 1) {
String newPerm = head + subset.first();
perms.add(newPerm);
return;
}
final TreeSet<Integer> headSortedDigits = new TreeSet<Integer>(subset);
final TreeSet<Integer> remainingSortedDigits = new TreeSet<Integer>(headSortedDigits);
final Iterator<Integer> descIter = headSortedDigits.descendingIterator();
while (descIter.hasNext()) {
final Integer headInt = descIter.next();
remainingSortedDigits.remove(headInt);
permutate(head + headInt, remainingSortedDigits);
remainingSortedDigits.add(headInt);
}
}
How to call the method:
Permutations obj = new Permutations();
final SortedSet<Integer> sortedSet = new TreeSet<Integer>();
int[] array = <an integer array>;
for (int i = 0; i < array.length; i++) {
sortedSet.add(array[i]);
}
obj.permutate("", sortedSet);
obj.print();
Running time:
O(logn*n!)
Head recursion:
public void populateAncestorMatrixHeadRecursion(final Node root) {
if (root == null) {
return;
}
if ((root.left != null) && (root.right != null)) {
if (!ancestorMatrix.containsKey(root.left)) {
ancestorMatrix.put(root.left, new HashMap<Node, Node>());
}
ancestorMatrix.get(root.left).put(root.right, root);
} else if ((root.left != null) && (root.right == null)) {
if (!ancestorMatrix.containsKey(root.left)) {
ancestorMatrix.put(root.left, new HashMap<Node, Node>());
}
ancestorMatrix.get(root.left).put(new Node(-1), root);
} else if ((root.left == null) && (root.right != null)) {
Node nullNode = new Node(-1);
if (!ancestorMatrix.containsKey(nullNode)) {
ancestorMatrix.put(nullNode, new HashMap<Node, Node>());
}
ancestorMatrix.get(nullNode).put(root.right, root);
}
if (root.left != null) {
populateAncestorMatrixHeadRecursion(root.left);
}
if (root.right != null) {
populateAncestorMatrixHeadRecursion(root.right);
}
}
}
- Jack September 02, 2012Matrix[leftNode][rightNode]=rootNode...
Tail recursion:
public static Node populateAncestorMatrix(final Node root, final int level) {
if (root == null) {
return null;
}
Node nodeLeft = new Node(-1);
Node nodeRight = new Node(-1);
if (root.left != null) {
nodeLeft = populateAncestorMatrix(root.left, level + 1);
}
if (root.right != null) {
nodeRight = populateAncestorMatrix(root.right, level + 1);
}
if (!ancestorMatrix.containsKey(nodeLeft)) {
ancestorMatrix.put(nodeLeft, new HashMap<Node, Node>());
}
ancestorMatrix.get(nodeLeft).put(nodeRight, root);
return root;
}
Modified version of merge:
public static List<Integer> firstListExclusive(final List<Integer> listA,
final List<Integer> listB) {
final List<Integer> newList = new LinkedList<Integer>();
for (int iterA = 0, iterB = 0; (iterA < listA.size());) {
Integer valueA = listA.get(iterA);
Integer valueB = null;
if (iterB < listB.size()) {
valueB = listB.get(iterB);
}
if ((valueB != null) && (valueA < valueB)) {
newList.add(valueA);
iterA++;
} else if (valueA == valueB) {
iterA++;
iterB++;
} else if ((valueB != null) && (valueA > valueB)) {
iterB++;
} else {
newList.add(valueA);
iterA++;
}
}
return newList;
}
Iterative approach using BFS:
public static int findLevelQueue(Node root) {
final LinkedList<Info> queue = new LinkedList<Info>();
if (root == null) {
return -1;
} else if ((root.left == null) && (root.right == null)) {
return 0;
}
queue.add(new Info(root, 0));
Info info=null;
while (!queue.isEmpty()) {
info = queue.removeLast();
if ((info.node.left != null) && (info.node.right != null)) {
queue.add(0, new Info(info.node.left, info.level+1));
queue.add(0, new Info(info.node.right, info.level+1));
}
else if ((info.node.left == null) || (info.node.right == null)) {
return info.level;
}
}
return info.level;
}
public static int checkLevel(final Node root, int level) {
int leftLevel = -1;
int rightLevel = -1;
if (root.left != null) {
leftLevel = checkLevel(root.left, level + 1);
}
if (root.right != null) {
rightLevel = checkLevel(root.right, level + 1);
}
if ((leftLevel == -1) && (rightLevel == -1)) {
return level;
}
if ((leftLevel >= 0) && (rightLevel == -1)) {
return level;
} else if ((leftLevel == -1) && (rightLevel >= 0)) {
return level;
} else {
return (leftLevel <= rightLevel) ? leftLevel : rightLevel;
}
}
If binary tree is mutable, then call topDoubleLinkedList(rootNode):
static class Node {
Node left;
Node right;
Object value;
Node(Object value) {
this.value = value;
}
}
public static Node topDoubleLinkedList(Node root)
{
Node headNode = doubleLinkedList(root);
while(headNode.left!=null)
{
headNode=headNode.left;
}
return headNode;
}
public static Node doubleLinkedList(Node root) {
if (root.right != null) {
Node newNode = doubleLinkedList(root.right);
Node tmpNode = newNode;
while (tmpNode.left != null) {
tmpNode = tmpNode.left;
}
tmpNode.left = root;
root.right = tmpNode;
}
if (root.left != null) {
Node newNode = doubleLinkedList(root.left);
Node tmpNode = newNode;
while (tmpNode.right != null) {
tmpNode = tmpNode.right;
}
tmpNode.right = root;
root.left = tmpNode;
root = tmpNode;
}
return root;
}
If the binary tree is immutable, then
static class Node {
Node left;
Node right;
Object value;
Node(Object value) {
this.value = value;
}
}
static class ListNode<ValueType> {
ListNode<ValueType> prev;
ListNode<ValueType> next;
ValueType value;
ListNode(ValueType value) {
this.value = value;
}
}
public static ListNode<Node> doubleLinkedList(final Node root) {
ListNode<Node> headNode = null;
if (root.right != null) {
headNode = doubleLinkedList(root.right);
}
if (headNode == null) {
headNode = new ListNode<Node>(root);
} else {
headNode.prev = new ListNode<Node>(root);
headNode.prev.next = headNode;
headNode = headNode.prev;
}
if (root.left != null) {
ListNode<Node> tmpListNode = doubleLinkedList(root.left);
ListNode<Node> newHead = tmpListNode;
while (tmpListNode.next != null) {
tmpListNode = tmpListNode.next;
}
tmpListNode.next = headNode;
headNode = newHead;
}
return headNode;
}
code submitted:
public class Result {
Node foundNode;
int iteration;
}
public class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
public void findNth(final Node node, int N, final Result result) {
if (node.left != null && result.foundNode == null) {
findNth(node.left, N, result);
}
// handle root
result.iteration++;
if (result.iteration == N) {
result.foundNode = node;
return;
}
if (node.right != null && result.foundNode == null) {
findNth(node.right, N, result);
}
Suppose you have two Characters C and C. What is the key and hashcode for these? Keys and hashcodes will be equal by Java convention. Hence, a Set in Java won't work. If you create your own Character class, such that hashcode returns an a logical memory address, that would work.
- Yev August 30, 2012Okay. Let me correct myself; it's okay to do d[c]<0, but not d[c]==0; in any case, it's inefficient. It's better to store A's elements in d[c], so that there will be O(A.length) space overhead, where B.length could be very large; if you do this, then d[c]>0 will be the condition for falseness.
- Yev August 29, 2012public static int nextBiggest(final int[] array, int srcIndex)
{
int nextBiggest=-1;
for(int iter=0;iter<array.length;iter++)
{
if(srcIndex!=iter && nextBiggest==-1 && array[srcIndex]<array[iter])
{
nextBiggest=array[iter];
}
else if(srcIndex!=iter && array[srcIndex]<array[iter] && array[iter] < nextBiggest)
{
nextBiggest=array[iter];
}
}
return nextBiggest;
}
First, the interleave preserves relative order of the inputs; this greatly simplifies the problem:
public static boolean isInterleaved(final String A, final String B,
final String C) {
if ((A.length() + B.length()) != C.length()) {
return false;
}
int Aiter = 0;
int Biter = 0;
for (int Citer = 0; Citer < C.length(); Citer++) {
if (C.charAt(Citer) == A.charAt(Aiter)) {
Aiter++;
} else if (C.charAt(Citer) == B.charAt(Biter)) {
Biter++;
}
}
if ((Aiter != A.length()) || (Biter != B.length())) {
return false;
}
return true;
}
Partition the data into subsets(i.e. buckets of reasonable size in RAM), and do parallel processing on each node(bucket). Each node will return the 10 most-frequent strings and their counts, as a sorted array where the index is the rank. This is essentially mergesort, done in parallel.
- Yev August 28, 2012Dynamic Programming because this problem is a recurrence relation:
Let m[h,w] represent the max slabs which you can stack, including the base slab:
m[0,0]=0
m[1,1]=1
m[1,2]=1
m[2,1]=1
m[2,2]= 1 + m[1,1] = 1+1=2
m[3,2] =1 + m[2,1] + m[1,1] = 1 + 1 + 1 = 3
m[2,3] = 1 + m[1,2] + m[1,1] = 1 + 1 + 1 = 3
m[3,3] = 1 + m[2,2] +m[2,1] + m[1,2] = 1 + 2 + 1 + 1 = 5
m[h,w] = 1 + Sum(m[h-k,w-n]) where 1<=k<=h-1, and 1<=n<=w-1
Here's a solution which works for Nodes<ValueType>
static <ValueType> Node<?> remove(Node<?> head, final ValueType targetValue) {
Node<?> start = head;
//System.out.println("Target value: " + targetValue);
// handle base cases
if (head == null) {
return null;
} else if ((head != null) && (head.next == null) &&
targetValue.equals(head.value)) {
return null;
} else if ((head != null) && (head.next != null) &&
(head.next.next == null) && targetValue.equals(head.value)) {
return start = head.next;
}
//System.out.println("Start b4 loop: " + start);
//System.out.println("Head b4 loop: " + head);
while (head != null) {
//printList(start);
if (targetValue.equals(head.value)) {
head = head.next;
start = head;
} else if (head.next!=null && targetValue.equals(head.next.value)) {
head.next = head.next.next;
} else {
head = head.next;
}
//System.out.println("Start post loop: " + start);
//System.out.println("Head post loop: " + head);
}
return start;
}
Test output:
Original list: 3 1 2 3 3 5 3
Modified list: 1 2 5
225/1000 => 2250/1000 => 1000+1000 => 2250 - 2000 => 2*1000 + 250/1000 => 2*1000 (quotient is 2).
250/1000 => 2500/1000 => 2*1000 + 500/1000
500/1000 => 5000/1000 => 5*1000
=> 0.2 + 0.02 + 0.005 = 0.225
22/7 => 7*3 + 1/7 => 7*3 + (10/7)/10 =>
3 + (1+3/7)/10 =>
3 + (1+(30/7)/10)/10 =>
3 + (1+(4+2/7)/10)/10 =>
3 + (1+(4+(2+6/7)/10)/10)/10 =>
=> 3 + 0.1 + 0.04 + 0.002 + ... =>
=> 3.142...
Have the func input a max depth, from which to round up or down.
Given two iters A,B, such that A is always ahead of B. If both A,B are in a circle, then going forward from A, it should be possible to reach B. Since we don't know ahead of time how many steps it will take to reach B, let's accelerate after each iteration, i.e. step++; otherwise, if step is constant, it may take many more iterations before A overtakes B...
static Node findStart(final Node[] list) {
int step = 1;
if (list.length <= 2) {
return list[0];
}
Node headconstant = list[0];
Node headaccel = list[2];
boolean isLoop = false;
while ((headaccel != null) && !isLoop) {
for (int i = 1; i <= step; i++) {
headaccel = headaccel.next;
if (headaccel==headconstant) {
isLoop = true;
break;
} else if (headaccel == null) {
break;
}
}
headconstant = headconstant.next;
step++;
}
return headaccel;
}
One problem with the above code, though it finds a loop, it doesn't always specify where the cycle starts. In this case, you'd need additional info. Add a visitors integer K such that, if headaccel visits a node N, it sets K to 1. headaccel is only needed with a step of 1 . If headaccel visits N again, increment K to 2. If K=2, then you've detected a loop, and the start of the cycle.
- Yev August 16, 20121) Start with an array m of size k
2) m[0]=first element
3) merge each additional element in O(n) running time after each push
4) Find smallest element in O(1) time, m[0]
If the smallest element K is popped, m[0] == K, pop m[0] from m. Then, the next smallest element will be m[0]=m[1], and so on.
1) Run insertion sort on the first k elements on array m of size k
2) For next element K, if K= > m[k-1], then discard
3) Else find first element m[i] such that K<m[i]. Move all elements m[i...k-1] to the right and m[i]=K; if any elements fall beyond the array, discard them.
0000022222
- Jack September 09, 20120000023223
0000000000
0000033333
000013333