vik
BAN USER- 2of 2 votes
AnswersGiven an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b) over all choices of indexes such that both c > a and d > b.
- vik in United States
Required complexity: O(n^2)| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Arrays Data Structures Ideas Matrix - 0of 0 votes
AnswersGiven set of N threads generate sum of all numbers in an array of known size M
- vik in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Trees and Graphs - 0of 2 votes
AnswerWhat is high dynamic range rendering and why is it important for realistic rendering?
- vik in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Graphics - 1of 1 vote
AnswersWrite a function to generate a second array of numbers containing running average of N elements from the original array
- vik in United States
So for instance if the original array is,
2,6,4,2,3 and N=3
result = 2,4,3,4,3
you can assume the corner elements can be filled with original elements where there are not enough elements to take avg of N elements| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Algorithm Arrays - 4of 4 votes
AnswersYou have written a memory manager and after using it your coworker complains that he is facing severe issues of fragmentation. What could be the reason(s) and how can you fix it
- vik in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer / Developer Computer Architecture & Low Level Debugging Operating System - 5of 5 votes
AnswersA link list contains following elements
struct node{ int data; node* next; node* random; }
Given head of such a linked list write a function who copies such a linked list and returns the head of the new list. So if in the original list first node points to fourth node in random the copy should have the same relation. The random pointer can point to any node including itself and more than two nodes can have random pointer to the same node.
- vik in United States
Required time complexity O(n) and no extra space can be used (apart from the newly allocated memory which you will need to create the new list)| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ Data Structures - -2of 4 votes
AnswersWrite a thread safe data structure such that there could be only one writer at a time but there could be n readers reading the data. You can consider that incrementing or decrementing a variable is an atomic operation. If more than one threads try to write simultaneously then just select one randomly and let others wait
- vik in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer C++ Data Structures Operating System - 0of 0 votes
AnswersDesign a web crawler to dump all the pages of a given website (URL) onto disk. So basically it saves pages which is related to the website (for instance dump all pages of aws.amazon.com) and do not crawl the links outside the website
- vik in United States
I coded it in python and then they asked what is the internal structure of dict in python and why or why not it is fast| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Coding Data Structures Python - 0of 0 votes
AnswersDesign a library shelf which can store books or digital media also like CD/DVD. It was more of a design question rather than a coding question and they wanted to know how would you design classes and have abstractions and inheritance in them.. after that they kept on adding details of what could be included on the shelves and how to manage them and routines related to them and what would info I need to have to respond to the user queries and making the design useful.
- vik in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Object Oriented Design - 0of 0 votes
AnswersYou come to office install the latest build of internet explorer and find out that instead of the expected page explorer loaded a blank screen .. before discussing with developer what test you will like to conduct so that he can pin point the problem from your observation
- vik in United States for Internet Explorer| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Testing - 0of 0 votes
AnswersWhat is mip-maps and why are they used
- vik in United States| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer Intern - 0of 0 votes
AnswersWhy we use 4X4 matrix for representing and calculations in transformation of 3D points when that can be done only with 3X3 matrix.
- vik in United States
(the concept of homogenization of matrices and how they help including translation operation)| Report Duplicate | Flag | PURGE
NVIDIA Software Engineer Intern Graphics - 2of 2 votes
AnswersThere is an machine which can process any kind of fruit and produce packaged boxes … write test cases for that
- vik in United States for Internet Explorer| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Testing - 0of 0 votes
AnswersWhat are uses of Btree, AVL and RBtree(individual applications as i explained that we use them whenever we need balanced BST and he wasnt convinced)
- vik in United States
When would you specifically use Btree over AVL tree.
Which one out of balanced BST is most efficient(for which i answered Btree for large values of n) and he asked why dont we always use Btree then?| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Data Structures - 3of 3 votes
AnswersDesign a phonebook dictionary which on input any characters gives names and phone number of all the matching names(prefix)
- vik in United States
For instance
Rihana 233222232
Ricky 134242444
Peter 224323423
Ron 988232323
If you give R as input it should list
Rihana Ricky and Ron which their contact numbers
If you give ri as input it should list
Rihana, Ricky which their contact numbers| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer Algorithm Data Structures - 0of 0 votes
AnswersYou have a sequence of data which tells about daily prices of a stock (of a company in some market). Given the sequence for N such days tell when should one buy and sell to maximize the profit. (for simplicity Assume you can buy only 1 stock). Prices of stock is same for a single day and you cannot buy and sell on the same day.
- vik in United States
Edit: You have to buy once only and sell once only. (I also misunderstood Q during interview that we have to tell sequence of buying and selling but it was not the question)| Report Duplicate | Flag | PURGE
Walmart Labs Intern Algorithm
yeah as pawan also mentioned if the tree is unbalanced then u cant even reach the node in time < height and height>=log(n). so if u have to find smallest element n=1 in a BST with 1000 nodes on left you cant even reach it in log(n).
@barcode in case of complete BST it can be done in log(n) time
@Mihail.. speedmanics is right ..it will crash so u can just check before popping out element if it has any elements... also your second and third case of if statement are same
@zyfo2... your code is definitely better ... and if there is no priority in your code it becomes even simpler and you can just remove those checks and looks something like this
if(str[i]=='[') a++;
if(str[i]==']'){ a--; if(a<0) return false;}
if(str[i]=='(') {b++;}
if(str[i]==')'){ b--; if(b<0) return false;}
if(str[i]=='{') {c++; }
if(str[i]=='}') {c--; if(c<0) return false;}
@Kamy in the if condition
if(a+b < c && b+c < a && a+c < b) return 0;
can this be ever true?
I dont think for 3 +ve real numbers a,b,c they can ever satisfy your condition
However you can fix the code by putting
if(a+b = c || b+c = a || a+c = b) return 0;
which is the case when the 3 points lie on a line
@kannan ...logic is correct but you are pushing head in q1 and q2 is empty initially so your code in main while loop
while(!q1.empty() && !q2.empty())
will never be executed as q2 will always be empty at starting. so you can just change it by changing && to ||
Following is the similar c++ code that i used
void reverseLevelOrder(node* root){
if (root==NULL) return;
else{
queue<node*> q1,q2;
stack <node*>s1;
node* currNode = NULL;
q1.push(root);//Pushing root to startwith
while((!q1.empty()) || (!q2.empty()))
{
while(!q1.empty()){
currNode= q1.front();
q1.pop();
if (currNode->left)q2.push(currNode->left);
if (currNode->right)q2.push(currNode->right);
s1.push(currNode);
}
s1.push(NULL);
while(!q2.empty()){
currNode= q2.front();
q2.pop();
while(!currNode){
currNode= q2.front();
q2.pop();
}
if (currNode->left)q1.push(currNode->left);
if (currNode->right)q1.push(currNode->right);
s1.push(currNode);
}
s1.push(NULL);
}
//now s1 has all the items to be printed
while(!s1.empty())
{
currNode = s1.top();
s1.pop();
if (!currNode) cout<<endl;
else cout<<currNode->data<<" ";
}
}
}
In case any1 needs explanation... its quite simple
Using 2 queues so that i can keep track of level..
current level's nodes are saved in one of the queues and rest are their child is saved in another and while popping from this queue to save its child on next level instead of printing it(for normal level order printing) just push into a stack so when you finally print it by popping its in reverse order.
For printing "\n" i push a NULL in the stack and when it sees a NULL in stack while printing i just print a new line for new level... hope this helps
@Anonymous ...Shashi's code will work fine in your case
@shashi ...However there is a basic flaw for which i didnt had to run the code.. which is the head of linked list is not being updated and hence
I/P 1->2->3->4->5->6->7->8->9->10->11->12 k=4 m=3;
will result into
1->5->6->7->11->10->9->8->12
so either u should return the updated head from your function or use pointer to pointer for head
@Shashi in the Q u have mentioned "Reverse the linked-list till k elements and then traverse till m elements and repeat."
can you explain what u mean by "repeat" are we supposed to alternatively reverse k elements after every m elements?
If I am understanding it right it should be
I/P 1->2->3->4->5->6->7->8->9 k=2 m=3;
O/P 2->1->3->4->5->7->6->8->9 ????
@Jim the suffix tree is helpful when there are large number of queries as it takes significant time in creation of suffix tree along with the space.... however in this case it will not be a good choice as the tree creation will take long and there are no repeated queries
@Hua in russell's example
186: x,a,b
187: a,b,x
188: x,d,e
189: d,e,x
The answer should be x but your algo will return NULL (as LCS between a,b and d,e will be NULL)
I think we can use the same algo but use it for more iteration to complete the solution .. so if we get NULL at end of first iteration we can only say that the LCS we started with doesnt have any common URL in all users....but we cant say for sure if there is no such solution...what we can do is ... take next LCS between first two strings(186 and 187 ignore the previous one)....and then do same thing for it...and we will have to do it till the LCS between the first two becomes NULL(by ignoring all previous LCS between them) ... only then we can say that there exists no solution between all users...lets assume we have p such LCS between first two strings then complexity increases to O(kmnp)
@Ravisingh .... this is fine actually the array contains the prices not profit/loss and since u can buy only once and then sell it only once the max profit in your example will also be 3 only not 4
@ducking ... this is similar what i was refering to(kandane's algo) however yours will not be consuming any extra space also so its definitely better
My solution at the end was:
Store difference from each consecutive day in an array of size n-1 (as size of original array is 1). So now we just have to find a continuous sequence of numbers(in the difference array) whose sum is maximum and that would give us max benefit
For instance lets say
original price array = [150 ,149 ,155, 157, 137, 150, 167]
difference price array = [ -1, 6, 2, -20, 13, 17]
So in difference array 1element represent the profit or loss(if -ve) if one buys stock on first day and sells on 2nd day
Now the problem reduces to maximum sum in subarray which can be easily calculated by Kandane's Algo in worst case O(n)
@Manohar you are right but can we also rotate the tree upside down(by 180degrees instead of flipping the tree) and then try to join them? If yes then in that case we will have to try to find sum of both the arrays as mentioned by you front-> end + front -> end AND front->end+end->front as they could be joined in 2 ways
..... 3
1 2
7 12
+
......... 5
43 77
11 13
Merged
3
1 2
7 12 11 13
77 43
5
OR
... 3
1 2
7 12
+
... 5
77 43
11 13
Merged
3
1 2
7 12 11 13
77 43
5
and both should be valid answers
- vik January 21, 2013@Cyrus in a way you are right but you will have to keep track of visited nodes. For instance
5
3 9
2 12 1 23
11 13 21 99
Now if you want to print nodes at a distance 2 from 23 even with the method you described you will land into issues when you revisit an already visited node in your case you might also print 23 itself... Now the issue can be easily resolved by keep a track of visited nodes on which the searchNthNodeBelow() has been called or you can do something easier in this case as the only wrong answer will be the number itself(the node from where you have to start) and that too if the distance is even... so you can eleminate the source node from result if the distance !=0
- vik January 21, 2013@Franky ... the space require will be O(N) where N is the largest number in the array.
So if the array have large numbers (1,-2 , 20000, 5, 4000,0, -3,8000000) then the amount of space which will be wasted in creating the auxiliary array will be huge as in this case the auxiliary array would comsume 8000000*int_size space when there are only few +ve numbers so it might not be a good idea to create the auxiliary array
@aztec It has to be a min heap of 3 highest ferq element so that you can compare the next element's from the top of min heap and decide if it belongs to the min heap(of highest freq elements) or not(in which case you can just move to next element)
However you can avoid all this post processing of creating heap by tracking which 3 elements has the largest count while creating the hash itself which has been show in code by Will_In_Seattle's post
@anish1 ...this will work for repetition also and yang is not processing columnwise this is how you will have to create the heap picking 1st element from each row(starting with it) and then pick next element from row whose element has been recently popped from the min heap.
@zerobyzero ... ur logic is correct however your step 3(simply increment its pointer in the repected row) will be able to avoid adding repeated element to heap only if the repeated item is being brought into heap after pop or in other words the next smallest element is being inserted in heap which is same as popped element. However if the repeated elements were brought into heap from diff rows and they were not smallest at that time then they will be inserted in heap....Anyway it will work in that case also as you can always have repetition in min heap with a tie breaker
-@SRB... if you create a MAX heap for k minimum distance elements then on root of that maxheap will be kth closest point and as he has mentioned you can use quick-select for kth closest point... and for ensuring linear time you should use median of medians algorithm
- vik January 16, 2013@RK it will work even in your test case also
3->6->9->1->2->4
once you find a element which has value lower than previous which in your case is 1 then just merge the list starting at 1 and other starting at 3(ending at 9) as 2 separate sorted listed which can now be easily done in O(n) without any extra space.
//from jagat's post below
if(p1->data < p2->data) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
I was asked same Q at microsoft 2 years back. Few imp thing to keep in mind in Q like these:
1. Make no assumptions... ask wherever u have doubt before coding
2. Enumerate all cases and handle them when u write code like in this case inp could be of length 0,1,2,3n,3n+1,3n+2
3. Remember the head will change after this reversing so either use ptr to ptr while passing head or return the new head... as i have done in example below.
node* reversePartial(node* head){
if (head==NULL || head->next==NULL){
return head; //handling len 0 or 1
}
node* newHead= NULL;
bool firstTime = true;
node * curr= head;
node * nxt1 = head->next;
node * nxt2 = nxt1->next;
node * lastLoopItem = NULL;
while (curr && nxt1 && nxt2){ //handling len = 3n
node * ptr = nxt2->next;
if (firstTime){
firstTime = false;
newHead = nxt2;
}
if (lastLoopItem){
lastLoopItem->next= nxt2;
}
lastLoopItem = curr;
nxt2->next = nxt1;
nxt1->next = curr;
curr->next = ptr;
curr = ptr;
if (curr){
nxt1 = curr->next;
}
else{
nxt1=nxt2=NULL;
break;
}
if (nxt1){
nxt2 = nxt1->next;
}
else
break;
}
if (nxt1){ //handling len=3n+2
if (firstTime){
newHead = nxt1;
firstTime = false;
}
if (lastLoopItem)
lastLoopItem->next= nxt1;
nxt1->next=curr;
curr->next=NULL;
}
if (lastLoopItem){ //handling len=3n+1
lastLoopItem->next= curr;
}
return newHead;
}
@SRB though the logic is correct but you mention "Store the Matrix in single dimensional array by removing all the elements on & above major diagonal" which means only those elements will be stored for which i>j however in the example you have taken elements above major diagonal but thats fine as the logic is correct
My Q is do we need to do so much calculations? consider if we only save lower half as u mentioned (i>j). Then in your example elements saved will be
-------------------------------------------------------------------------------
|(2,1) | (3),1 | (3,2) | (4,1) | (4,2) | (4,3) | (5,1) | (5,2) | (5,3) | (5,4)|
-------------------------------------------------------------------------------
So for calculating index in new array we can just use
new_index = (i-2)*(i-1)/2 +j
because for reaching any element in virtual 2D array we will have to skip (i-2)*(i-1)/2 elements in i-1 rows and then j elements in ith column
Chengyun Zuo is right. I have removed some unnecessary code
public class sumSmallerThanCurr{
public static int getSumofLessSum(int[] test,int begin,int end){
if(begin==end) return 0;//base case
int mid=(begin+end)/2;
int leftPart=getSumofLessSum(test,begin,mid);
int rightPart=getSumofLessSum(test,mid+1,end);
int mergeSum=mergeTwoPartGetSum(test,begin,mid,end);
return leftPart+rightPart+mergeSum;
}
public static int mergeTwoPartGetSum(int[] test,int begin,int mid,int end){
//both subarrays are sorted due to merge in previus step
int[] helpArray=new int[end-begin+1];
int begin1=begin;
int end1=mid;
int begin2=mid+1;
int end2=end;
int result=0;
int helpArrayIndex=0;
while(begin1<=end1&&begin2<=end2){
if(test[begin1]<=test[begin2]){
result+=test[begin1]*(end2-begin2+1);
helpArray[helpArrayIndex++]=test[begin1++];
}
else helpArray[helpArrayIndex++]=test[begin2++];
}
if(begin1>end1)
for(;begin2!=end2+1;) helpArray[helpArrayIndex++]=test[begin2++];
else
for(;begin1!=end1+1;) helpArray[helpArrayIndex++]=test[begin1++];
for(int i=0;i!=helpArray.length;i++) test[begin++]=helpArray[i];
return result;
}
public static void main(String[] args) {
//int[] test={1,5,3,6,4};
int[] test={3,1,2,4,6,2,7,8};
}
}
Now the logic... we require sum of all elements which are current than current element and we have to find sum of such sum.... In other words each element will contribute M times where M is the number of elements larger than current element at indices higher than current index.
So the algo is exactly the merge sort with one additional line
result+=test[begin1]*(end2-begin2+1);
and this gives us the sum of sum
So for each sorted subarrays while merging if item in left subarray is smaller than item at right subarray then that element in left subarray will contribute K times (end2-begin2+1 i.e. elements still left in right subarray to merge)
So this is almost merge sort and we calculate sum at logN levels for N elements while merging subarrays so complexity becomes O(NlogN)
NAME is correct.. here is what it looks like:
int maxSumOfLeafpaths(node* root, int * maxSum){
if (root==NULL)
return -1;
if (root->right==NULL && root->left ==NULL)
return root->data;
int leftSum = maxSumOfLeafpaths(root->left, maxSum);
int rightSum = maxSumOfLeafpaths(root->right, maxSum);
int maxSumAtCurrLevel = MAX(leftSum,rightSum)+ root->data;
if (leftSum+rightSum+ root->data > *maxSum){
*maxSum = leftSum+rightSum+ root->data;
}
return maxSumAtCurrLevel;
}
We can keep do a recursive inorder traversal and keep flag to indicate f we have found the value whose successor to be find. Once the value has been found print the next value and return
void findSuccessor(struct node* head, struct node* key, bool & found)
{
if (head == NULL)
return;
findSuccessor(head->left, key, NULL);
if (*found !=False)
{
print( "found it: %d",head->info;
return;
}
if (head==key)
*found = True
findSuccessor(head->right, key, found);
}
you are converting the whole tree into array which will take O(n) time and O(n) ... how is it a Ologn solution??
- vik January 29, 2013