byteattack
BAN USERwhat would the time complexity be? is it O(n^3) ?
- byteattack July 16, 2014hey Kary nice approach but can you tell me how is it n^2 ? I think its n^3 since it tries every possible combination.
- byteattack July 16, 2014At Least someone understood the question.
why do people make things overly complex! the question was clearly
"Implement a stable sort algorithm" That's it. Merge sort is a good one and easy to implement.
public Node hangFromALeaf(Node start, Node leaf) {
if (null == start || null == leaf) {
return null;
}
if (null == leaf.left && start == leaf && null == leaf.right) {
return leaf;
}
Node left = hangFromALeaf(start.left, leaf);
if (null != left) {
left.left = start;
start.right = start.left;
start.left = null;
return left;
}
Node right = handFromALeaf(start.right, leaf);
if (null != right) {
right.right = start;
start.left = start.right;
start.right = null;
return right;
}
return null;
}
if leaf comes from the left
we assign its parent to its left,
its parent's right will get the parent's left node (mirroring) and parent's
if leaf comes from right
we do the opposite,
propagate this logic till the root node, at the root node, we just switch the root's left with right (or vice versa depending on the location of the leaf) and we are done.
worst case nlog(n) to go down the tree logn to come up so i guess O(n) = nLog(n)
I have the same solution! :)
- byteattack June 20, 2014a[i][j] would never be larger than a[i+1][j] or a[i][j+1]
This is a sorted matrix...
int[] result = new int[b/2];
public double pow(double a, int b, int[] result) {
if (b == 0) {
return 1;
}
if (b == 1) {
return a;
}
if (INTEGER.MAX_VALUE != result[b]) return result[b];
if (b % 2 != 0) {
result[b] = result[b - 1] * a;
return result[b];
}
else {
double _result = pow(a, b/2, result);
result[b] = _result * _result;
return result[b];
}
}
- byteattack June 11, 2014I had the same question asked....
I first gave a solution using DP (like fibonacci) with complexity N/2 = O(n)
Then I told him I can improve on this I gave another solution which was Log(n) (using memoization + recursion) something similar to top comment.
:( I guess I won't make it
Solution is:
priority queue size 'm' (m = m nearest)
For each point in points:
if priorityQueue is not full:
add to queue;
else:
if point < priorityQueue.top() {
pop the top element;
push the new element
to check distance use pythagoras theorem
Sqrt (point.x^2 + point.y ^2)
i can read this code, i just coded mine in a minute, let me know if its wrong.
def getdepth(list, depth):
sum = 0
for item in list:
if type(item) == type(list):
sum += getDepth(item, depth + 1)
else:
sum += item * depth;
return sum
looks similar to yours
- byteattack June 11, 2014amazing solution! How long did it take you to come up with this solution? Because what I would have done would be
Add B to itself A number of times..
I wonder how will I solve such a question when faced during an interview.. Thanks for the person who shared it! and the solution :)
i meant o2.end > o1.end
- byteattack June 09, 2014if (o1.start > o2.start) {
return 1;
} else if (o1.start > o2.start) {
return -1;
} else if (o1.end > o2.end){
return 1;
} else if (o1.end > o2.end) {
return -1;
} else {
return 0;
}
did you mean in the else condition o2.start > o1.start
and o2.end > o2.end ?
because in the 4 conditions in your comparator 2 of the conditions are exactly same as the previous statement.
the person failed to mention UNIQUE intervals
[(1,3), (2,5),(8,9)] should return 5
a) 1 2 3 = 2 unique intervals (1 to 2, 2 to 3)
b) 2 3 4 5 = 2 unique intervals ( 3 to 4, 4 to 5) We did not count 2 - 3 since it was already counted.
c) 8 9 = 1 unique interval
result = 2 + 2 + 1 = 5
hope this clarified the question.
Amazing I had the same answer!
- byteattack June 04, 2014O(n) solution
O(1) space
public int findShortestDistance(String[] words, String a, String b) {
Map<String, Integer> parityValueMap = new HashMap<String, Integer>();
parityValueMap.put(a, 0);
parityValueMap.put(b, 1);
Map<String, Integer> posMap = new HashMap<String, Integer>();
posMap.put(a, 0);
posMap.put(b, 0);
int[] min = new int[words.length];
int minDistance = Integer.MAX_VALUE;
Integer parityValue = Integer.MAX_VALUE;
int wordsLength = words.length;
for (int i = 0; i < wordsLength; i ++) {
if (parityValueMap.containsKey(words[i])) {
posMap.put(words[i], i);
// First time we see a required word
if (parityValue == Integer.MAX_VALUE) {
parityValue = parityValueMap.get(words[i]);
// we found the word other than the one found last time so lets calculate distance
} else if (!parityValue.equals(parityValueMap.get(words[i]))) {
parityValue = parityValueMap.get(words[i]);
int tempMin = posMap.get(words[i]) - posMap.get(words[i].equals(a)? b : a);
if (tempMin < minDistance) {
minDistance = tempMin;
}
}
}
}
return minDistance;
}
Find any word out of the two
if you find a word out of the given two , save its position
if you find the same word as you did the last time, update its position and continue
if you find the other word, update its position and calculate distance and update min distance if its lower than before
use a flip bit to mark which word did you see before.
it can test this code
public int findShortestDistance(String[] words, String a, String b) {
Map<String, Integer> parityValueMap = new HashMap<String, Integer>();
parityValueMap.put(a, 0);
parityValueMap.put(b, 1);
Map<String, Integer> posMap = new HashMap<String, Integer>();
posMap.put(a, 0);
posMap.put(b, 0);
int[] min = new int[words.length];
int minDistance = Integer.MAX_VALUE;
Integer parityValue = Integer.MAX_VALUE;
int wordsLength = words.length;
for (int i = 0; i < wordsLength; i ++) {
if (parityValueMap.containsKey(words[i])) {
posMap.put(words[i], i);
// First time we see a required word
if (parityValue == Integer.MAX_VALUE) {
parityValue = parityValueMap.get(words[i]);
// we found the word other than the one found last time so lets calculate distance
} else if (!parityValue.equals(parityValueMap.get(words[i]))) {
parityValue = parityValueMap.get(words[i]);
int tempMin = posMap.get(words[i]) - posMap.get(words[i].equals(a)? b : a);
if (tempMin < minDistance) {
minDistance = tempMin;
}
}
}
}
return minDistance;
}
Find any word out of the two
if you find a word out of the given two , save its position
if you find the same word as you did the last time, update its position and continue
if you find the other word, update its position and calculate distance and update min distance if its lower than before
it runs in O(n)
space complexity is constant O(1)
forgot this
letter = {}
number = {}
for i in range(65, 65 + 26):
letter[i - 65 + 1] = chr(i)
number[chr(i)] = i - 65 + 1
def convert_to_letters(col):
str = ''
if col in letter:
return letter[col]
else:
l = (col - 1) / 26
l2 = (col - 1) % 26
if l > 26:
str = convert_to_letters(l)
return str + letter[l2 + 1]
else:
return letter[l] + letter[l2 + 1]
def convert_to_numbers(col):
if len(col) <= 0:
return 1
if col in number:
return number[col]
else:
part_num = convert_to_numbers(col[1:])
part_num = (number[col[:1]] + 25) * part_num + 1
return part_num
Test it out, it works :)
- byteattack June 03, 2014if string is "" and regex is "abcdefgh*"
it will return true
you should do
if regex.length() == 0 || (regex.length() == 1 && regex.charAt(regex.length() - 1)
good one
- byteattack June 03, 2014Same question exists in the book Cracking Coding interview, I got same question in my Yahoo Phone screen today.
@gul did you clear it?
I thought of the same,
Build 26 trie's one of each letter store in hashmap
keep a count of each word in the leaf node.
sounds good for now,
how will we find top 1000?
this will work it will be nlog(m)
n = size of integer array
m = size of window
Looks like guys above have a O(n) approach though..
we can use Doubly or singly Linked List
keep a tail pointer and a head pointer
public class Queue<T> {
private static class Node {
Node previous;
Node next;
T value;
public Node(T value, Node next, Node previous) {
this.value = value;
this.next = next;
this.previous = previous;
}
}
private head = null;
private tail = null;
private int size = 0;
private int maxSize = 0;
public Queue(int size) {
this.maxSize = size;
}
public void insert(T value) {
if (head == null) {
head = new Node(value, null, null);
tail = head;
size += 1;
} else {
if (this.size == this.maxSize) {
throw new Exception("Queue is full");
}
Node tempNode = new Node(value, head, null);
head.previous = tempNode;
head = tempNode;
size += 1;
}
}
public T pop() {
if (this.size < 1) {
throw new Exception("Queue is empty");
} else if (size == 1) {
T value = head.value;
head = null;
tail = null;
size = 0;
return value;
}
Node tempNode = tail;
tail.previous.next = null;
tail = tempNode.previous;
size -= 1;
return tempNode.value;
}
}
I think it will look something like this, please let me know if we can save memory further
public enum StockPriceMath {
INSTANCE;
private long INTERVAL = 600000000; // microseconds since each second we get 50000 updates, we can't do it in miliseconds
private volatile HashMap<String, Queue> priceMap = new ConcurrentHashMap<String, Queue<Message>>();
private volatile HashMap<String, Long> sumMap = new ConcurrentHashMap<String, Integer>();
public void updatePrice(Message message) {
Queue<Message> tickerQueue;
// if we have seen the ticker before
if priceMap.contains(message.ticker) {
tickerQueue = priceMap.get(ticker);
}
else {
// new ticker
tickerQueue = new ConcurentLinkedQueue<Message>(600000000);
tickerQueue.insert(message);
priceMap.set(message.ticker, tickerQueue)
sumMap.set(message.ticker, 0)
}
long sum = sumMap.get(message.ticker);
while (message.timestamp - tickerQueue.peek().timestamp > INTERVAL) {
sum = sum - tickerQueue.pop().price;
}
sum += message.price;
sumMap.set(message.ticker, sum);
}
public long get10minuteAverage(String ticker) {
Queue<Message> tickerQueue = priceMap.get(ticker);
long sum = sumMap.get(message.ticker);
return sum / tickerQueue.size();
}
}
I used Enum istead of class to make it singleton since this will be used in a high frequency environment and singleton will help us to maintain concurrency.
Also I do not know if something like concurrentLinkedQueue exists, i just assumed it did.
Main program
public class YahooInterview {
public String removeAdjacentDuplicates(char[] duplicates, List<Integer> dupRemoval, int index) {
if (index == duplicates.length - 1) {
return String.format("%c", duplicates[index]);
}
if (duplicates[index] == duplicates[index + 1]) {
dupRemoval.set(0, dupRemoval.get(0) + 1);
return removeAdjacentDuplicates(duplicates, dupRemoval, index + 2);
} else {
return String.format("%c%s", duplicates[index], removeAdjacentDuplicates(duplicates, dupRemoval, index + 1));
}
}
}
Driver Method
public void testRemoveAdjacentDuplicates() throws Exception {
YahooInterview yahooInterview = new YahooInterview();
String test = "ABCCBCBA";
List<Integer> intlist = new ArrayList<Integer>(1);
intlist.add(0, 0);
String output = yahooInterview.removeAdjacentDuplicates(test.toCharArray(), intlist, 0);
while (intlist.get(0) != 0) {
intlist.set(0, 0);
output = yahooInterview.removeAdjacentDuplicates(output.toCharArray(), intlist, 0);
}
}
The approach:
Find duplicates and remove them in the remove_duplicate method
Keep a track of duplicates removed if > 0 then call the method again till duplicates removed!=0
if duplicates removed = 0 that means we have cleared all the duplicates in the string.
had similar approach. good explanation.
- byteattack May 31, 2014I just realized my find smallest is actually doing sorting... that can be replaced by quicksort.
- byteattack May 31, 2014ok i found a flaw i replace the first even number with array[0]
it should be smallest even number in the subarray
My approach is same as the top answer,
1) find the smallest non increasing subinteger (from right to left)
2) find the smallest ( but larger than most significant digit of the above subinteger) integer in the above subinteger
3) Swap
4) Find the smallest number you can achieve with the above subinteger's digits - 1 ie
if above integer is 4921 then find smallest using 921 - ie 129
so 4921 becomes 4129
5) find the first even number starting from the right and replace it with number[0]
public class NextLargestEventNumber {
public int findNextLargestEventNumber(int input) {
int len = String.toInteger(input).length();
if len == 0 {
return input;
}
int[] numarray int[len]
int next_largest = find_next_largest(input)
for (int i = len - 1; i >= 0; i--) {
numarray[i] = next_largest % 10
}
for (int i = 0; i < len; i ++) {
if numarray[i] % 2 == 0 {
swap(numarray[i], numarray[0]);
break;
}
}
return arrayToInt(numarray);
}
private int[] find_smallest(int[] input, begin_index) {
if begin_index == 0 {
return input
}
int min = input[0]
int minindex = 0
for (int i = 0; i <= begin_index; i++) {
if (min < input[i]) {
min = input[i]
minindex = i
}
}
swap(numarray[begin_index], numarray[minindex])
find_smallest(numarray, begin_index - 1)
return numarray
}
private int find_nex_largest(int input) {
int len = String.toIntege(input).length() == 0
int[] numarray = int[len]
for (int i = len - 1; i >= 0; i--) {
numarray[i] = input % 10
}
if len == 0 {
return input
}
int max = numarray[0]
for (int i = 0; i < len; i++) {
lsg = numarray[i]
if lsg > max {
max = lsg
}
if (lsg < max) {
int min_diff = 0
int swapint = 0
for (int j = 0; j < i; j++) {
if numarray[i] > numarray[j] {
int diff = numarray[j] - numarray[i]
if diff < min_diff {
min_diff = diff
swapint = j
}
}
}
swap(numarray[i], numarray[j])
find_smallest(numarray, i)
break;
}
return array_to_int(numarray)
}
}
It is a modified version of BFS. Since you have been given a starting point (node)
find its neighbors which match the value of the starting node. (top left down right) we don't need diagonal since the top left down right will cover those cases.
Save the nodes you have visited in a parent hashmap so that you don't visit them again. and just count the number of nodes in the parent hashmap in the end for the area :)
I think you may have accepted the offers till now but, as of now Groupon as a company is not doing really well. It may have more growth opportunities since the company is new. Amazon - True the working hours are long and there are talks about its culture not being as friendly as other tech companies. Engineers are "on call" for their product - what it means is that you may get a call/sms if something related to your product goes wrong in production. on-call happens in rotations so you may not be on-call all the time. (Please ask the recruiter or a engineer at the company about policy for your team).
The advantage is
1) Reputation - If you come from Amazon people will know you are hardworking
2) You will learn a LOT in a large company - how do they handle their products, scaling network and products etc etc \
3) After 1-2 years if you look to move in a mid-size company which is growing, they would love to have you on board since you would have the knowledge on how these giant companies scale. Chances are you will also get a really sweet salary and position to lure you to leave Amazon.
If you burn out within an year or so, never mind just apply for a new job :) (its easy if you are single to move). If you cleared Amazon Interview i'm sure you will do well in other companies too
Thanks for the tip
- byteattack May 23, 2014Some larger companies are not really efficient to process the offer letters since it has to make multiple rounds - hiring committee, your future manager etc.. They also might be waiting for some other candidates to accept, so as to give all of you guys a combined start date so that they can maximize the training group. Do not worry, if they verbally said they would like to proceed with the offer, it will come your way :)
- byteattack May 23, 2014the answer is this big? I doubt... it can be done in under 30 minutes.
- byteattack May 23, 2014thanks for the explanation
- byteattack May 23, 2014agreed with Samuel
map.get(key)
queue.remove(key)
queue.insert(key)
(with the if conditions in place)
null != oldestKey
a very good coding practice. instead of oldestKey != null
I like the Hash Map approach. If you complete that, and still have time, then suggest that we can improve this code by doing XYZ and then try to do it.
1) You have solved the problem
2) You have shown the interviewer that you are aware that optimizations can be carried out and you know how to do it.
even if you don't end up coding the tricky solution, you will still get the points for having a creative approach - which is crucial for companies like google, fb etc
I agree with Navid and that's why i subscribed to this question.
I would like to know:
is the tree already full?
or
we fill in values
also do we have access to the node.balance method?
We can implement BST using AVL tree
Keep counts
1) elements larger than median
2) elements smaller than median
calculate the median for first two elements
for third element onwards keep the track of the counters. If the counters differ by more than 2 then you know the tree might be out of order
then maybe we can do something at that step
to prove the point AVL BST is not a good median holder see this example
(insert into AVL BST with max diff = 1)
12 - 9 - 18 - 7- 10
This tree is still in balance ( the height differ by just 1 of left and right subtree of 12)
but the median should be 10.
12
9 18
7 10
Binary Search Tree is not AVL tree. An AVL tree can be implemented as Balanced BST.
This was a question asked to my friend 1 week ago by Google recruiter
Q) Which one of these Data Structures have Log N traverse time
Red Black Tree
Binary Search Tree
Hash Table
Array
Directed Acyclic Graphs
He included BST in his answer which was wrong.
Watch out for these differences in interviews.
I think it will work for Square 1's but not rectangle. The solution you are giving is already present on GeeksForGeeks
- byteattack May 19, 2014adding to what Soundwave said
Get a list of all the nodes which are equal to the first letter of the word.
then go through each of these instances ( refer them by their co-ord not values)
and do a BFS keeping track of the path you took. Again the key here is to use Co-Ordinates to navigate and check for cycles and not values. Just use the values at the time you want to compare against the required ones.
use a method like getAdjNodes(i,j, matrix) which returns a list if i,j as neighbors of the node you passed in.
This is not a facebook interview question, EXACT same question exists on Stackoverflow asked 2 years ago. The answer over there explains the solution in a very nice manner and it is a LENGTHY question. Unless you are super smart you can't answer this in 35 minutes ( rest of 10 - 15 minutes used for other discussions in the interview). Not a good judge of candidates ability.
- byteattack May 19, 2014stackoverflow dot com questions 10013933/conversion-to-proper-postfix-notation-in-minimum-number-of-steps
seems like facebook is looking at stackoverflow to copy exact question..my friend gave fb interview last week and he said they are all 45 minute rounds on site (may extend to 1 hr max) never more than 1 hr. In rare instances can you solve this question in 35 - 40 minutes with all the stress. (10 minutes are spent to ask about other questions) I find it hard to believe this was asked in an interview.
Remember to check for Cycles
def reach_the_end(path):
visited = {}
def start_moving(path, current_location):
if current_location >= len(path):
print "moved beyond the path"
return 0
elif current_location == len(path) - 1:
print "Reached the end"
return 0
else:
moves = path[current_location]
if current_location + moves in visited:
print "Looks like we have visited this before, path has cycle"
return 0
visited[current_location + moves] = current_location
start_moving(path, current_location + moves)
start_moving(path, 0)
return visited
letter = {}
number = {}
for i in range(65, 65 + 26):
letter[i - 65 + 1] = chr(i)
number[chr(i)] = i - 65 + 1
def convert_to_letters(col):
str = ''
if col in letter:
return letter[col]
else:
l = (col - 1) / 26
l2 = (col - 1) % 26
if l > 26:
str = convert_to_letters(l)
return str + letter[l2 + 1]
else:
return letter[l] + letter[l2 + 1]
def convert_to_numbers(col):
if len(col) <= 0:
return 1
if col in number:
return number[col]
else:
part_num = convert_to_numbers(col[1:])
part_num = (number[col[:1]] + 25) * part_num + 1
return part_num
print convert_to_letters(703)
print convert_to_numbers('AAA')
good i like your approach without recursion.
- byteattack May 18, 2014The original question is "how will you deep copy a linked list" not just copy.
- byteattack May 18, 2014
}
- byteattack November 14, 2014