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
There's no need to check the values at the Node-reference level. Instead, use the array offset, and look for symmetry:
static public boolean isPalin(String str)
{
for(int i=0;i<str.length()/2;i++)
{
if(str.charAt(i) != str.charAt(str.length()-1-i))
{
return false;
}
}
return true;
}
No additional memory allocation besides linked list, and O(n) running time. There's no need here to swap the references, only the values, since the Nodes hold only an int(value exchange is cheap in this circumstance)...
static class Node {
Node left;
int bit;
public Node(int bit, Node left) {
this.bit = bit;
this.left = left;
}
public Node(int bit) {
this.bit = bit;
}
public String toString() {
return bit + "";
}
}
static void swap(Node a, Node b) {
a.bit = a.bit ^ b.bit;
b.bit = a.bit ^ b.bit;
a.bit = a.bit ^ b.bit;
}
static LinkedList<Node> sort(LinkedList<Node> list) {
Node tail = list.get(list.size() - 1);
Iterator<Node> headIter = list.iterator();
Node head = null;
while (headIter.hasNext() && (head != tail)) {
System.out.println("Current list: " + list);
head = headIter.next();
if (head.bit == 1) {
while ((tail.bit == 1) && (head != tail)) {
tail = tail.left;
}
if (head != tail) {
swap(head, tail);
tail = tail.left;
}
}
}
return list;
}
Dynamic Programming:
m[i,j]="" where i>j
m[i,j]=str(i) where i=j
m[i,j]="" where j-i+1=2 and str(i) != str(j)
m[i,j]=m[i+1,j-1] where j-i+1=3 and str(i) != str(j)
m[i,j]=string[i,j] where j-i+1=2 and str(i) = str(j)
m[i,j]=string[i,j] where j-i+1=3 and str(i)=str(j) and str(i+1)=str(j-1)
m[i,j]=string[i,j] where m[i,(j-i)/2-1] = m[(j-1)/2,j] and j-i+1>=4
m[i,j]=max_palindrome( m[i, i+k], m[i+k+1, j] ) where j-i+1>=4 and 1<=k<=j-i-1 and m[i,(j-i)/2-1] != m[(j-1)/2,j]
Longest palindrome is then in m[0,string.length()-1];
Another solution, somewhat more intuitive:
public static void myinorder(Node root) {
Node node = root;
final Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!stack.isEmpty()) {
if (node == null) {
System.out.print(stack.peek().value + " ");
node = stack.pop().right;
if (node != null) {
stack.push(node);
}
} else if (node.left != null) {
stack.push(node.left);
node = node.left;
} else if (node.left == null) {
System.out.print(stack.peek().value + " ");
node = stack.pop().right;
}
}
}
Alternate solution:
public static void myinorder2(Node root) {
Node node = root;
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || node!=null) {
//System.out.println("Stack: " + stack);
if (node!=null) {
stack.push(node);
node = node.left;
}
else {
//System.out.println("\nStack: " + stack);
if(node!=null)
{
System.out.print(node.value+" ");
}
Node tmp = stack.pop();
//System.out.println("\nStack: " + stack);
if(tmp !=null && tmp != node)
{
System.out.print(tmp.value+" ");
}
//System.out.println("\nStack: " + stack);
if(tmp != null && tmp==node)
{
tmp=stack.pop();
System.out.print(tmp.value+" ");
}
node = tmp.right;
//System.out.println("\nNew right: " + node);
//System.out.println("Stack: " + stack);
}
}
}
Another solution, albeit lengthier:
public static void myinorder(Node root) {
Node node = root;
Stack<Node> stack = new Stack<Node>();
stack.push(node);
while (!stack.isEmpty()) {
while ((node != null) && (node.left != null)) {
stack.push(node.left);
node = node.left;
}
System.out.print(stack.peek().value + " ");
if ((stack.peek().right == null) && (node != null) &&
(stack.peek() == node)) {
stack.pop();
node = null;
} else if ((stack.peek().right != null) && (node != null) &&
(stack.peek() != node)) {
node = stack.pop();
node = stack.peek();
}
else if ((stack.peek().right != null) && (node != null)) {
node = stack.pop().right;
stack.push(node);
}
else if ((stack.peek().right != null) && (node == null)) {
stack.push(stack.pop().right);
node = stack.peek();
}
}
}
import java.util.Arrays;
import java.util.List;
import java.util.Vector;
public class Test
{
public static void main(String[] args)
{
Vector<Integer> array = new Vector<Integer>(Arrays.asList(1, 1));
System.out.println("Input: " + array);
System.out.println("Array result: " +
increment(array, array.size() - 1, true));
printArray(array);
System.out.println();
array = new Vector<Integer>(Arrays.asList(9, 9));
System.out.println("Input: " + array);
System.out.println("Array result: " +
increment(array, array.size() - 1, true));
printArray(array);
}
static void printArray(final Vector<Integer> array)
{
System.out.print("Result: ");
for(int digit: array)
{
System.out.print(digit);
}
System.out.println();
}
static List<Integer> increment(final Vector<Integer> array, int start,
boolean carry)
{
if (start < 0)
{
array.insertElementAt(0, 0);
start = 0;
}
for (int i = start; i >= 0; i--)
{
if ((array.get(i) == 9) && carry)
{
array.set(i, 0);
increment(array, i - 1, true);
}
else if ((array.get(i) < 9) && carry)
{
array.set(i, array.get(i) + 1);
carry = false;
}
}
return array;
}
}
Output:
Input: [1, 1]
Array result: [1, 2]
Result: 12
Input: [9, 9]
Array result: [2, 0, 0]
Result: 200
import java.util.Arrays;
import java.util.List;
public class Test
{
public static void main(String[] args)
{
List<Integer> arrayList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
int k = 12;
System.out.println("Original list: " + arrayList);
arrayList = rotateLeft(arrayList, k);
System.out.println("Result: " +arrayList);
}
static void swap(final List<Integer> arrayList, final int a, final int b)
{
System.out.println("Swap: list(" + a + ") and list(" + b + ")");
arrayList.set(a, arrayList.get(a) ^ arrayList.get(b));
arrayList.set(b, arrayList.get(a) ^ arrayList.get(b));
arrayList.set(a, arrayList.get(a) ^ arrayList.get(b));
System.out.println("New list: " + arrayList + '\n');
}
static List<Integer> rotateLeft(final List<Integer> arrayList, final int k)
{
final int actualShifts = k % arrayList.size(); // reduce unnecessary swapping
System.out.println("Actual shifts: " + actualShifts);
for (int i = 1; i <= actualShifts; i++)
{
// for optimization alternative
//int tmp = arrayList.get(iter);
for (int iter = 0; iter < (arrayList.size() - 1); iter++)
{
swap(arrayList, iter, iter + 1);
/* alternate copying strategy for optimization
arrayList.set(iter,arrayList.get(iter+1));
*/
}
/* possible optimization
arrayList.set(iter,tmp);
*/
}
return arrayList;
}
}
Output:
Original list: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Actual shifts: 3
Swap: list(0) and list(1)
New list: [2, 1, 3, 4, 5, 6, 7, 8, 9]
Swap: list(1) and list(2)
New list: [2, 3, 1, 4, 5, 6, 7, 8, 9]
Swap: list(2) and list(3)
New list: [2, 3, 4, 1, 5, 6, 7, 8, 9]
Swap: list(3) and list(4)
New list: [2, 3, 4, 5, 1, 6, 7, 8, 9]
Swap: list(4) and list(5)
New list: [2, 3, 4, 5, 6, 1, 7, 8, 9]
Swap: list(5) and list(6)
New list: [2, 3, 4, 5, 6, 7, 1, 8, 9]
Swap: list(6) and list(7)
New list: [2, 3, 4, 5, 6, 7, 8, 1, 9]
Swap: list(7) and list(8)
New list: [2, 3, 4, 5, 6, 7, 8, 9, 1]
Swap: list(0) and list(1)
New list: [3, 2, 4, 5, 6, 7, 8, 9, 1]
Swap: list(1) and list(2)
New list: [3, 4, 2, 5, 6, 7, 8, 9, 1]
Swap: list(2) and list(3)
New list: [3, 4, 5, 2, 6, 7, 8, 9, 1]
Swap: list(3) and list(4)
New list: [3, 4, 5, 6, 2, 7, 8, 9, 1]
Swap: list(4) and list(5)
New list: [3, 4, 5, 6, 7, 2, 8, 9, 1]
Swap: list(5) and list(6)
New list: [3, 4, 5, 6, 7, 8, 2, 9, 1]
Swap: list(6) and list(7)
New list: [3, 4, 5, 6, 7, 8, 9, 2, 1]
Swap: list(7) and list(8)
New list: [3, 4, 5, 6, 7, 8, 9, 1, 2]
Swap: list(0) and list(1)
New list: [4, 3, 5, 6, 7, 8, 9, 1, 2]
Swap: list(1) and list(2)
New list: [4, 5, 3, 6, 7, 8, 9, 1, 2]
Swap: list(2) and list(3)
New list: [4, 5, 6, 3, 7, 8, 9, 1, 2]
Swap: list(3) and list(4)
New list: [4, 5, 6, 7, 3, 8, 9, 1, 2]
Swap: list(4) and list(5)
New list: [4, 5, 6, 7, 8, 3, 9, 1, 2]
Swap: list(5) and list(6)
New list: [4, 5, 6, 7, 8, 9, 3, 1, 2]
Swap: list(6) and list(7)
New list: [4, 5, 6, 7, 8, 9, 1, 3, 2]
Swap: list(7) and list(8)
New list: [4, 5, 6, 7, 8, 9, 1, 2, 3]
Result: [4, 5, 6, 7, 8, 9, 1, 2, 3]
It can be done; you'd need to have prior knowledge of the addresses, so you can find the last node in O(1) time. The question is asking how to find the last node in O(1) time and deallocate it, given the head of the singly-linked list. Assuming you know how many elements there are total(running count), in Java, if you were to implement malloc, you could find the block of heap memory assigned(using hashcode), then use base+offset to find the last allocated object, and dellocate it.
- Yev August 05, 2012The general idea is buy high, seller higher, or buy low, sell high. On one day you buy. On a later day, you sell. The positive delta is your profit, which you want to maximize. Otherwise, don't trade at all:
int[] maxProfit(int[] prices)
{
int maxProfit=0;
int[] buyselldays=new int[]{0,0};
for(int b=0;i=b<prices.length;b++)
{
for(int s=b+1; s<prices.length && b<s; s++)
{
int delta = prices[s]-prices[b];
if(delta > maxProfit)
{
maxProfit = delta;
buyselldays[0]=b;
buyselldays[1]=s;
}
}
}
return buyselldays;
}
Test Cases:
1)20, 5,10
b = 5, s=10 => max profit = 5
2) 20 15 10 => don't trade
3) 5 10 35 => max profit = 30
4) 5 40 100 25 => 100 -5 = max profit 95
Assuming the binary tree does not need to be a BST, simplest approach is to flatten out the tree first into an array, using depth-first search. The array will tell you how many elements exist, and which should be the root of a subtree; advantage of an array, is that you can pivot on any element(this is how quicksort does balancing internally!). The level input into the function merely tells you when to stop processing.
- Yev August 05, 2012This is a dynamic programming question. Here's the approach I would take:
S={12,4,7,1,6,3,3}
1) Single element is itself
2) Two elements is two sets of each
3) Three elements
(12,4,7) => (12,{4,7}) or ({12,4},7) or ({12,4,7})
=> (12,11) or (16,7) or (23)
=> (12,{4,7})
And so on until the table is built up.
Assuming unique names, simplest solution which works well is
- Yev August 15, 2012