sameer
BAN USER- 1of 1 vote
Answersdesign question:
- sameer in India for azure
I will request you to first read only upto Solution-2 only and try to think about your solution and then read other lines. If we read whole post(without thinking about your solution) then your brain will get polluted with my idea and you may not be able to think naturally.
----------------------------------------------------------------------------
One machine daily taking backup of its datatstore on some server machine, MINIMIZE network data transferred.
Solution -1 : Compress storage and then send over network
Solution - 2 : Take diff and send only diff(and not whole data daily)
Interviewer asked for better ideas as above two are well known ideas but I was stuck.
---------------------------------------------------------------------------------
So he gave me hint(no 1) and depending upon hint I devise following solution
Solution - 3: Divide storage into sequence of 1K bits so total number of possible patters are 2^1000. Now Using hashTable just store existing 1000bits-length pattern and all their sequence numbers. And, then transfer this hashTable to server. So for example datastore consists of "file1, file2, file3=file1+file2" then we can reduce network data by 50%
So interviewer asked why 1000bits and why not 100bits or 10000bits. Also, as we increase length of bit-pattern, probability of getting duplicate patterns reduces and if we decrease length of pattern we may not be able to effectively reduce network data transferred
Solution-4: Don't divided storage bits into equal length pattern but in variable length pattern so client tells server "Pattern-X(bit string) of length L exists at offsets 5, 10003, 363738, 42311, 43433.
Interviewer said how can check for variable length patterns on client machine as this will be computaionally inefficient. I suggested Trie, Huffman coding, file-by-file comparison but he straightway discarded those ideas :)
He gave final important hint that
somehow client should give indication to server that next bytes are going to be like this without tranferring those bytes and
then server should tell client that "OK don't send next 1000bits as I already have them from previously send/stored data at different section(like different file) in storage"
and asked me how to do it and how will be the handshake/protocol between server-client
Since, throughout interview I was stuck to my hashTable solution and not able to think beyond hashTable, as per HR I got negative feedback in this interview :(
Overall interviewer was helping lot and was really helpful. He gave lot of hints and time(never said "Ok thats enough let us move on"...Finally I myself gave up :) )| Report Duplicate | Flag | PURGE
Microsoft Network - 3of 3 votes
AnswersI had two interviews with Google
- sameer in India
first) one with US person...he asked decent question with lot of hints...experience : positive
and
then second) interview with person from India...I prepared for one month but he asked me very tough one graph/tree question...never gave single hint and based on that one question he judged my seven years of experience in Software Development (I never experienced what they say...Google looks for approach and not final answer)
Q.1 : Arrange array in wave form A1 > a2 < a3 > a4 ...
O(n.log-n) (Note: its not A1 >= A2)
Q.2 : Given Graph with Tree characteristics, find one node as root so that height of tree will be minimum| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm
import java.util.HashMap;
import java.util.Scanner;
/**
* Created by sameer on 30/11/17.
*/
public class Merge {
public static void main(String args[])
{
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = scanner.nextInt();
}
HashMap<Integer, Integer> startsWith = new HashMap<>();
HashMap<Integer, Integer> endsWith = new HashMap<>();
for (int i = 0; i < n; ++i) {
if (endsWith.containsKey(a[i] - 1) && startsWith.containsKey(a[i] + 1)) {
// Merge
int startsWithItem = endsWith.get(a[i] - 1);
int endsWithItem = startsWith.get(a[i] + 1);
startsWith.remove(a[i] + 1);
endsWith.remove(a[i] - 1);
startsWith.put(startsWithItem, endsWithItem);
endsWith.put(endsWithItem, startsWithItem);
} else if (startsWith.containsKey(a[i] + 1)) {
int endsWithItem = startsWith.get(a[i] + 1);
startsWith.remove(a[i] + 1);
startsWith.put(a[i], endsWithItem);
} else if (endsWith.containsKey(a[i] - 1)) {
int startsWithItem = endsWith.get(a[i] - 1);
endsWith.remove(a[i] - 1);
endsWith.put(a[i], startsWithItem);
} else {
startsWith.put(a[i], a[i]);
endsWith.put(a[i], a[i]);
}
}
int max = Integer.MIN_VALUE;
for (HashMap.Entry<Integer, Integer> entry: startsWith.entrySet()) {
int startsWithItem = entry.getKey();
int endsWithItem = entry.getValue();
if (max < endsWithItem - startsWithItem + 1) {
max = endsWithItem - startsWithItem + 1;
}
}
System.out.println(max);
}
}
import java.util.HashMap;
import java.util.Scanner;
/**
* Created by sameer on 30/11/17.
*/
public class Merge {
public static void main(String args[])
{
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = scanner.nextInt();
}
HashMap<Integer, Integer> startsWith = new HashMap<>();
HashMap<Integer, Integer> endsWith = new HashMap<>();
for (int i = 0; i < n; ++i) {
if (endsWith.containsKey(a[i] - 1) && startsWith.containsKey(a[i] + 1)) {
// Merge
int startsWithItem = endsWith.get(a[i] - 1);
int endsWithItem = startsWith.get(a[i] + 1);
startsWith.remove(a[i] + 1);
endsWith.remove(a[i] - 1);
startsWith.put(startsWithItem, endsWithItem);
endsWith.put(endsWithItem, startsWithItem);
} else if (startsWith.containsKey(a[i] + 1)) {
int endsWithItem = startsWith.get(a[i] + 1);
startsWith.remove(a[i] + 1);
startsWith.put(a[i], endsWithItem);
} else if (endsWith.containsKey(a[i] - 1)) {
int startsWithItem = endsWith.get(a[i] - 1);
endsWith.remove(a[i] - 1);
endsWith.put(a[i], startsWithItem);
} else {
startsWith.put(a[i], a[i]);
endsWith.put(a[i], a[i]);
}
}
int max = Integer.MIN_VALUE;
for (HashMap.Entry<Integer, Integer> entry: startsWith.entrySet()) {
int startsWithItem = entry.getKey();
int endsWithItem = entry.getValue();
if (max < endsWithItem - startsWithItem + 1) {
max = endsWithItem - startsWithItem + 1;
}
}
System.out.println(max);
}
}
I think idea is to use state diagram ... Assume k =3 then If state is 110 and then two possible states are 1. State-4/100 if you append 0 to 110 and 2. State -101 if you append 1 to 110
Now shortest string is shortest path in state diagram that covers all states or nodes
Calulcate Array sum[n] where for example sum[8] = input[8] + input[7] + input[6] for k = 3
Calculate Array maxFromLeft[n] where for example maxFromLeft[8] = max (sum[0], sum[1], ..., sum[8])
Calculate Array maxFromRight[n] where for example maxFromLeft[8] = max(sum[8], sum[9], ..., sum[n])
Now iterate over sum[n] and at each iteration consider intermediateSum[i] = maxFromLeft[i] + sum[i] + maxFromRight[i]
Answer: Max( intermediateSum[i] ) where i -> 0 to n - 1
Complexity: O(n)
You can convert this problem to DP using array DP[n][n];
#include <stdio.h>
int max(int* arr, int i, int j)
{
if (i == j) {
return 1;
}
if (i > j) {
return 0;
}
int x = max(arr, i + 1, j);
int itr = 0;
for (itr = j; itr >= (i + 1); --itr) {
if (arr[itr] != arr[i]) continue;
int y = max(arr, i + 1, itr - 1) + 2;
if (y > x) {
x = y;
}
break;
}
return x;
}
int main()
{
int arr[100];
int n = 5;
int i = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &arr[i]);//populate(arr, &n);
}
printf("%d\n", max(arr, 0, n - 1));
return 0;
}
Use MinHeap of size "m" where m -> size of set:
Initially, insert all elements in a set in minheap
For i = 1 to n:
top = remove top element from minheap
Multiply top element with 2 and adjust that element in heap
there is special case of duplicate elements that can be handled easily
- sameer December 28, 2015Palindrome normally solved using stack...so maybe we can solve it using recursive function if allowed though stack frame would still consume space :)
1. Cal total length of string
2. Recursively move to next node till we encounter node that has center char of palindome
3. Process current node for palindrome substring and return remaining part of string of current node or next pointer to calling function
I am just simulating stack using recursive call though coding look little hard
Removing leftmost ti is equivalent to moving window to right so that window does not contain all t-i s and now search for next window that contains all t-i s....so in.next iterations condition
if (sliding_window[0] != 0 && sliding_window[1] != 0 && sliding_window[2] != 0)
Becomes false
Hi zr.zoman,
Thanks showing interest in my solution. Its simply sliding window algo...
1) (pos_t1[i] = 1) => string t1 starts at pos-i in original string
2) sliding_window[0] => Latest starting position of t1 in original string when scanning from left to right
sliding_window[1] => Latest starting position of t2 in original string when scanning from left to right
sliding_window[2] => Latest starting position of t3 in original string when scanning from left to right
3) cal_width(sliding_window):
Example:
sliding_window = { 12, 17, 19} and len(t1) = 3, len(t2) = 9 and len(t3) = 7;
then width of current window = 12 to max (12 + 3, 17 + 9, 19 + 7}
4) sliding_window[lesser_position_of_3(sliding_window)] = 0;
Remove leftmost substring from window
Its SLIDING WINDOW algorithm => Hope it clears
step-1 : Use some pattern matching alogo like KMP
output of step-1:
short position_t1[strlen(str)];
short position_t2[strlen(str)];
short position_t3[strlen(str)];
step-2:
short sliding_window[3];
int final_answer = INT_MAX;
for (i = 0 ; i < strlen(str); ++i) {
if (pos_t1[i]) {
sliding_window[0] = i;
}
if (pos_t2[i]) {
sliding_window[1] = i;
}
if (pos_t3[i]) {
sliding_window[2] = i;
}
if (sliding_window[0] != 0 && sliding_window[1] != 0 && sliding_window[2] != 0) {
possible_answer = cal_width(sliding_window);
if (possible_answer < final_answer) {
final_answer = possible_answer;
}
sliding_window[lesser_position_of_3(sliding_window)] = 0;
}
}
printf("%d\n", final_answer);
Assumption: Each employee has one interval (Start-i, End-i)
Define strucrure :
struct node_t {
time_t time;
int type; // START, END
}
Convert given input into following heterogenous SORTED(by time) list/array with each node of "node_t".
Now scan this list/array with counter = 0, whenever u encounter START_type "++counter" and whenever u encounter START_type "--counter".
Moment when u get counter = 0, that's free time for all employees so just check next START_type to find interval length
Sort three arrays...initialize three iterators on three arrays to position 0, cal diff of three and now keep on advancing iterator to curr min of three values ...and ans is smallest diff...time comlexity is onlogn.
.have u given interview in Pine...how many rounds ...how was your experience ?
F(i, j, k) = max { 10 * Array1[i] * F(i + 1, j , k - 1), F(i + 1, j + 1, k) } if Array1[i] > Array2[j]
max { 10 * Array2[j] * F(i, j + 1, k - 1), F(i + 1, j + 1, k) } else
So this can be solved using Dynamic Programming with time and space complexity of O(m * n * k) [Not sure if this can be solved without using DP in more efficiently]
int function(int* Array1, int i, int* Array2, int j, int k)
{
// Check for i & j moving out of bound
if (k <= 0) {
return 0;
}
if (DP[i][j][k]) {
return DP[i][j][k];
}
if (Array1[i] > Array2[j]) {
return DP[i][j][k] = max( 10 * Array1[i] * function(i + 1, j, k - 1), function(i + 1, j + 1, k) )
} else {
return DP[i][j][k] = max( 10 * Array[j] * function(i, j + 1, k - 1), function(i + 1, j + 1, k) );
}
}
ANS : DP[0, 0, k];
2nd Q... finding largest path and middle of that path...this is what I suggested but how to find that path ?
1) I suggested separate dfs from each node -> O(n^2)
interviewer expecting O(n)
2) iteratively delete all current leaf nodes (using queue-reverse level order traversal) till u get single node and thats root node
For each element find closest index to left and right and then take closest of two.
// Calculate element closest to the left
for (i = 0; i < n; ++i) {
while (stack.top() < a[i]) {
stack.pop();
stack_pos.pop();
}
left[i] = stack.top();
left_pos[i] = stack_pos.top();
left_pos = stack_pos.top();
stack.push(a[i]);
stack_pos.push(i);
}
// Similarly populate right
// Take closest of left and right
for (i = 0; i < n; ++i)
{
closest[i] = closest(left[i], right[i], left_post[i], right_pos[i]);
}
- sameer May 29, 2019