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 mipmaps 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
@Cyber Phenix almost correct
@avikodak you cannot check by comparing only first two numbers... the second number could be itself missing or part of a bigger number...
The problem can be divided into 2 parts... finding the number sequence and then finding the missing number in that sequence
Guess the number of digits for the first number by reading numbers from the string one by one. If the previous number you have read is x, the next number must be either x + 1 or x + 2. If it is x + 2, remember x + 1 as the missed number, continue until the end of the string anyway to verify that the initial guess was correct. If you read something else than x + 1 or x + 2, the initial guess was wrong and you need to restart with (next) guess.
For example:
9899100101103104105
First guess length 1
read 9
the next number should be either 10 or 11. Read the next two digits, you get 89.
That is incorrect, so the initial guess was wrong.
Second guess length 2
read 98
the next number should be either 99 or 100. Read the next two digits for 99
the next number should be either 100 or 101. Read the next three digits for 100
... 101
... 103 (remember 102 as the missed number)
... 104
... 105
end of input
Guess of length 2 was verified as correct guess and 102 reported as missing number.
stackoverflow.com/questions/19245137/findthemissingnumberinagivenstring
LOGIC:
1. Traverse the array forwards, wrapping around when you hit the end (code below)
2. Count the total number of inflection points you find, if num_inflection_points==2 then your array is bitonic.
3. The runtime of this should be O(n).

Here's a working example in c++:
bool is_bitonic(const vector<int>& v) {
bool was_decreasing = v.back() > v.front();
int num_inflections = 0;
for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
bool is_decreasing = v[i] > v[(i+1)%v.size()];
// Check if this element and next one are an inflection.
if (was_decreasing != is_decreasing) {
num_inflections++;
was_decreasing = is_decreasing;
}
}
return 2 == num_inflections;
}
Notes, depending on your implementation:
Note 1: Here's the basic idea for traversing an array circularly:
for (int i = ip_index; i < array_length; i++) {
int index = (i + 1) % array_length; // wraps around to beginning
// Retrieve the value with
DoSomethingWithValue(array[index];)
}
Note 2: It might simplify the code to circularly loop length + 1 elemnts, which will guarantee you find both inflection points.
Note 3: Or, it might simplify the code if you always look for the first inflection point that goes increasing to decreasing (before searching for other inflection points). That way, your scan only has to take worry about finding exactly one other inflection point with the opposite flip.
source : stackoverflow.com/a/3029129/1923790
On the basis of 1 and 3 data we can put a default floor(the floor to which lift returns automatically when no service requests are pending) for that specific time... For instance having the default floor of all the lift to the ground floor (concourse) will be helpful in reducing the average wait time of the employees. Ans similarly in the evening the topmost floor can be set as default floor.
 vik October 15, 2013Yup, that's the Moore voting algorithm
When we move the pointer forward over an element e:
If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.

vik
October 14, 2013 Yes, and to reduce the complexity of finding is a number is prime or not use sieve of Eratosthenes( check out en.wikipedia.org/wiki/Sieve_of_Eratosthenes) to generate all prime numbers upto n/2
Then you can use two for loops { i (0 to len(primes)1) and j (i to len(primes 1))} to print only those pairs where i*j<=n
the loop > j (i to len(primes 1)) ensures no repetition and reduces time to check redundant solutions
Python implementation for the same:
def generatePrimes(n):
sqrtn = int(n**0.5)
sieve = [True] * (n+1)
sieve[0] = sieve[1] = False
for i in range(2, sqrtn+1):
if sieve[i]:
m = n/i  i
sieve[i*i:n+1:i] = [False] * (m+1)
sieve = [i for i in range(n+1) if sieve[i]]
return sieve
def printPairs(n):
primes = generatePrimes(n/2)
for i in range(0, len(primes)):
for j in range(i+1, len(primes)):
if (i*j)<=n:
print primes [i], primes[j]
#Call from the driver function
printPairs(100)

vik
October 13, 2013 Logic: the right parentheses can appear in an output string only when there are
already more left parentheses present in the output string. Extending the solution from Gayle's solved problems
c++ code for the problem ... explanation is mostly inline and a brief summary at the end
/*
Since
n1 pairs of “{} ” brackets
n2 pairs of “[] ” brackets
n3 pairs of “() ” brackets
let
l1= r1 =(n1)/2
l2= r2 =(n2)/2
l3= r3 =(n3)/2
*/
/*call from driver function */
char str[13];
str[12]=’\0’;
printAllCombinations(2,2,2,2,2,2,str,0);
//count is the index where we have to put the character currently
void printAllCombinations(int l1, int r1, int l2, int r2, int l3, int r3, char *str, int count) {
if (l1 < 0  r1 < l1  l2 < 0  r2 < l2  l3 < 0  r3 < l1 ) return; // invalid state
if (l == 0 && r == 0) {
printf(“%s\n”, str); // found one combination, so print it
return;
}
if (l1 > 0) { // try a left curly brace, if there are some available
str[count] = ‘{‘;
printAllCombinations(l1  1, r1, l2, r2, l3, r3, str, count + 1);
}
if (l2 > 0) { // try a left bracket, if there are some available
str[count] = ‘[‘;
printAllCombinations(l1, r1, l21, r2, l3, r3, str, count + 1);
}
if (l3 > 0) { // try a left paren, if there are some available
str[count] = ‘(‘;
printAllCombinations(l1, r1, l2, r2, l31, r3, str, count + 1);
}
//Now put the matching braces at all possible combinations
if (r1 > l1) { // try a right curly brace, if there’s a matching left
str[count] = ‘)’;
printAllCombinations(l1, r11, l2, r2, l31, r3, str, count + 1);
}
if (r2 > l2) { // try a right bracket, if there’s a matching left
str[count] = ‘)’;
printAllCombinations(l1, r1, l2, r21, l3, r3, str, count + 1);
}
if (r3 > l3) { // try a right parenthesis, if there’s a matching left
str[count] = ‘)’;
printAllCombinations(l1, r1, l2, r2, l3, r31, str, count + 1);
}
}
}
Basically at any current index of the result we have 3 options
1. Fill current index using any of the 3 types of left brackets (this can be done only when the left count of that type >0 )
2. Fill current index using any of the 3 type of right bracket (this can be done only when the left count of that type >right count of that type)
3. print the result if all type of brackets has been consumed
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#define MAXELT 10001
void main() //overhead  read the numbers, print the results.
{
int i=1,n=0,L[MAXELT],m,s;
char t[10];
void largest_and_second_largest(int a[],int n,int *m,int *s);
do {
if (i!=1)
L[i++]=n;
else
i++;
printf("\nEnter a number>");
gets(t);
if (sscanf(t,"%d",&n)<1)
break;
} while (1);
largest_and_second_largest(L,i,&m,&s);
printf("\nThe maximum is %d and the secondlargest is %d.",m,s);
}
//The action lies here
void largest_and_second_largest(int a[],int n,int *m,int *s)
{
int *I, //stores the losers
size, //stores the current level in the tree
i,j, //indexed
lu, //stores the last compared element in the
//current level
max, //stores the largest number
slarge, //stores the second largest number
sindex; //stores the index of the second largest number
void swap(int *a,int *b);
size=1; lu=1; //initialize  level one and no number used
I=(int *)malloc(sizeof(int)*n);
for (i=0;i<n;i++) //initialize  no loser yet
I[i]=1;
for (;;) { //loop until size1 becomes more than n
i=size1;
if (i>=n)
break; //loop exit
j=size+i;
if (j>=n && i!=n1) //if the last element of the array has
j=n1; //not been considered, use it
if (j>=n)
if (lu<0)
break; //loop exit
else {
j=lu; //store the used number in lu
lu=1;
}
for (;;) { //another seemingly infinite loop
if (a[i]>a[j]) //swap if out of order
swap(&a[i],&a[j]);
else
I[i]=I[j]; //otherwise, just store in the loser list
I[j]=i;
i=j+size; //next number
if (i>=n)
break; //inner loop exit
else {
j=i+size; //next
if (j>=n && i!=n1) //if the last element of the array has
j=n1; //not been considered, use it
if (j>=n)
if (lu>0) {
j=lu; //take in last used
lu=1; //empty last used
}
else {
lu=i; //if there is no earlier last used, store the
//current number as last used
break;
}
}
}
size=2*size; //move to the next level
}
max=a[n1]; //largest is found
sindex=I[n1]; //find the second largest by simple comparison
slarge=a[sindex]; //in the loser list for the maximum
while (sindex!=1) {
sindex=I[sindex];
if (sindex!=1 && a[sindex]>slarge)
slarge=a[sindex];
}
*m=max;
*s=slarge;
free(I); //free and return
}
void swap(int *a,int *b) //swap two elements
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
Source :seeingwithc.org/topic3html.html
 vik October 07, 2013It can be done in n+log n2 comparisons. This question is also in CLRS.
Think of elements as competitors, and a tournament is going to rank them.
First, compare the elements, as in the tree

/ \
 
/ \ / \
x x x x
this takes n1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.
The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n  1 comparisons.
from stackoverflow.com/questions/3628718/findthe2ndlargestelementinanarraywithminimumofcomparisom
your third approach will always not result into correct result.. Assuming you are picking 2 elements at a time which is resulting into your 1.5N complexity.. consider following test case
arr = [3,4,1,2,5,6]
min1 = 3
min2 =4
you pick 1 and 2
then compare 1 (as 1<2) with 3 (as 3<4) and update min1 (as 1<4)
and you move to next pair(5,6) and you will be done in next iteration
however the min2 was not updates to 2 which is the correct ans.
According to your approach... 4 is the 2nd smallest element which is currently in min2 which is incorrect!
Yeah but then since you have N threads now merging the answer into a single global variable will need some kind of locking mechanism on that global variable. Now consider this if the number of threads is huge the step of merging the result into a single variable becomes bottleneck and all threads are waiting to take a lock on a single variable so that they can update the total sum...
 vik October 04, 2013@kkr.ashish : the solution is correct however you can do it in two iterations rather than 3n
C++ code below for O(2n)
int * prodExceptCurrElem (int * arr, int len){
if (!arr  len<0) return NULL;
int * newArr = new int [len];
int i=0, prodSoFar =1;
for(;i<len;i++){
newArr[i] = prodSoFar;
prodSoFar *= arr[i];
}
prodSoFar = 1;
for (i=len1; i>=0; i){
newArr[i] *= prodSoFar;
prodSoFar *= arr[i];
}
return newArr;
}

vik
October 04, 2013 @Itanium as the people have already mentioned that the Q is for subarray not subset which needs to be contiguous.
@algos However there is a cost in this solution of space O(n).
geeksforgeeks.org/findsubarraywithgivensum/
This above article explains an O(n) solution which requires no extra space and can be used for any target sum and not only 0.
@nice algos
Implementation in python of the same:
def subArraySumZero(intList):
sumHash= { }
sumSoFar = 0
index = 0
for index in range(0,len(intList)1):
sumSoFar += intList[index]
if sumSoFar in sumHash.keys():
print intList[ sumHash[sumSoFar] +1 : index+1]
return
else:
sumHash[sumSoFar] = index
print "NO SUCH RESULT"
testList = [2, 3, 4, 9, 1, 7, 5, 6, 5 ]
subArraySumZero(testList)

vik
October 03, 2013 The approach is correct ... the only issue being that the solution will not scale and for a large number of machines the network traffic may be gargantuan. Consider an example with top ten counts in range of 1million and the number of servers in 10k range (which is not a big number considering the scale of amazon or google scale) so eventually you will ask for all URL which have count >= T/S which is 100 in this case. So you will end up sending a lot more data than is actually needed (as you will be sending URL for counts between 100 and 1 million). Also the bottleneck in such a solution would be central node processing this algorithm which wont scale but as I said earlier the solution is correct but not scalable.
 vik October 01, 2013Assumption: While a pairwise intersection of corresponding pixels in the two images....Intersection is white iff both pixels of the pair are white.
Then you can do the recursive intersection as follows:
let A and B be to corresponding nodes in the two trees (or their subtrees)
if rootA.color == "black":
return A
if rootA.color == "white":
return B
if rootA.color == "gray" and rootB.color == "gray".
##Pairwise intersect the subtrees of A and B.
##If all four of the returned subtrees have a black root, return a single node tree with a black root.
Otherwise return a tree with a gray root and the four returned subtrees as its subtrees.
Complexity is O(min{A, B}).
 vik September 30, 2013A quad tree can have only 3 color of nodes .. black white and gray
The crux is that at each level(depth) if the pixel color is not gray then it represents 4^(kd) pixels of color same as itself. where k represents the overall size of image of size (2^k X 2^k) and d represents the current depth of node in the tree
Assuming each node has color field: "black"/"white"/"gray"
and 4 field for the 4 child nodes of type node: ne , nw, se, sw
Code in Python:
def quadTreeCountBlackPixels(root, depth, size):
if (None == root):
return 0
if (root.color == “white”):
return 0
elif (root.color == “black”):
return pow(4, sizedepth)
else:
seCount = quadTreeCountBlackPixels(root.se, depth+1, size)
swCount = quadTreeCountBlackPixels(root.sw, depth+1, size)
neCount = quadTreeCountBlackPixels(root.ne, depth+1, size)
nwCount = quadTreeCountBlackPixels(root.nw, depth+1, size)
return seCount + swCount + neCount +nwCount
#initial call to function
totalBlackPixels = quadTreeCountBlackPixels(root, 0 , k):
#where the image is of size 2^k X 2^k

vik
September 30, 2013 @ankit thanks for pointing that out... I can do away with curr2 by using prev or viceversa
node* appendLastNtoBegin(node* head,int n){
if ((!head)  (!head>next)  n<=0)
return head;
node * curr(head), *prev(head);
int i(1);
while(curr>next){
if (i<n) i++;
else prev = prev>next;
curr=curr>next;
}
if (i<n){
cout<<"invalid input for N"<<endl;
return head;
}
prev>next=NULL;
curr>next=head;
head=prev;
return head;
}

vik
September 15, 2013 With this question they just want to know if you know about any scripting languages.. any scripting language will do bash/python/perl. c++/java code in this Q may reduce your chances of getting selected unless its an astonishing solution
If its just for one time then following grep command like:
grep lr '[19]\{3\}[09]\{4\}[09]\{3\}' "*.html" > results.txt
This was an open ended question and he was quite impressed with my answer and I got the offer so it worked. we discussed the test cases for around more than 1.5 hours while include 15 min of categorizing test cases and he said there is no end to it we could discuss it for whole week... basically they wanna see how broad you can think and never say thats it ... as there will be so so many more test cases
 vik February 25, 2013yes.. if the tree is not balanced it will result into O(n) search times. one can use AVL or Red black tree for this purpose.
Stl::map itself used red black tree since its balanced and red black tree has advantage over AVL here is that the rotation operation to balance the tree is O(1) whereas in AVL it could be O(logn)
here is an example
1
/ \
2 3
/ \ / \
4 5 6 7
The tree has 5 vertical lines
VerticalLine1 has only one node 4 => vertical sum is 4
VerticalLine2: has only one node 2=> vertical sum is 2
VerticalLine3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
VerticalLine4: has only one node 3 => vertical sum is 3
VerticalLine5: has only one node 7 => vertical sum is 7
So the resultant array would be
4, 2, 12, 3, 7
The logic being we will have at max number of 2*h1 elements in the resultant list where h is the height of the tree
Imagine tree as umbrella and now the columns sum start only at the nodes who are on top arc of the tree ...rest internal nodes are part of sum of some node above it .
I have used
resArr of 2h1 elements in which i will store results
bool initLeft and bool initRight to determine in which direction i need to initiate a new sum and if its false i just sum to the given position and dont initiate sum for new position in resultant array
pos to determine which column i am adding sum (which will be initially mid pos for root node)
initially only root will have both initLeft and initRight as true rest nodes will have either one of them as true(if the lie on arc of umbrella) or none
void getVerticalSum(node * root, int*arr, int pos, bool initLeft, bool initRight){
if (!root  !arr)
return;
arr[pos]+=root>data;
if (root>left)
getVerticalSum(root>left>right, arr,pos, false, false);
if (root>right)
getVerticalSum(root>right>left, arr,pos, false , false);
if (initLeft)
getVerticalSum(root>left, arr, pos1, true, false);
if (initRight)
getVerticalSum(root>right, arr, pos+1, false, true);
}
Driver function or main:
int *resArr = new int[2*h1];
getVerticalSum(root, resArr, h1, true , true);
cout<< "\n Vertical sum list is ";
for (int i=0; i<2*h1;i++) cout<<resArr[i]<<"\t";
delete []resArr;

vik
February 14, 2013 Almost correct but you missed one case in your 3.ii when you couldnt find a parent whose data is greater then it is the next node then stop at the node whose parent is NULL and now the successor is in right subtree(if it exists) so from root of tree(whose parent is NULL) traverse to the smallest in the right subtree and return that node. and there is changes to the psuedocode also
if ( node.right !=null )
return node.right
else if ( node.parent.data > node.data )
return node.parent
else if ( node.parent.data < node.data ) {
temp = node.parent
while(temp !=null &&temp.data < node.data){
node=temp
temp = node.parent
}
if(temp > node.data)
return temp
else if(temp==null){
if(node>right)
while (node>left){
node=node>left
}
return node
else
return null
}

vik
February 14, 2013 @JerryC ... yes if the number of fraud patterns are small then its certainly a nice idea(which one should ask the interviewer and in this case most probably it will be). however if the the fraud pattern are large in number then it will be O(n) in searching in linked list. So we can use a balanced BST(AVL, RB) instead of linked list and hence time will be O(1)+O(logn) =>logn
 vik February 14, 2013I think it will work but there is a small issue ...you are swapping the data(or its pointer) instead of changing a pointer itself...And in almost all the cases the answer is not acceptable
For example
Assume that the node consists of object or data pointers to more than one data... in that case you are supposed to rearrange the nodes using the pointers rather than swapping the data(or its ptrs) [this is what my interviewer said to me at interview at MS and which seems fair enough]
So similar thing can be achieved by just rearranging next pointers leaving data untouched (obviously i will have to save the pointers to the elements prev to the elements to be swapped)
Following is the c++ code
node* swapkthFirstAndLast(node* head,int k){
if (head==NULLk<=0 )return head;
int i(k);
node * curr(head), *startPrev(NULL), *startEle(NULL),*tmp(NULL),*prev(NULL), *currBack(head);
while ((i1)>0 && curr>next){
prev = curr;
curr = curr>next;
i;
}
if ((i1)>0){
cout<<"Invalid value of K"<<endl;
return head;
}
startEle = curr;
startPrev = prev;
while(curr>next){
prev = currBack;
currBack = currBack>next;
curr = curr>next;
}
//same elements
if (currBack == startEle)
return head;
//end elements
if (k==1){
currBack>next = head>next;
prev>next = head;
head>next = NULL;
head = currBack;
return head;
}
//adjacent
if (currBack>next==startEle){
tmp = startEle>next;
startEle>next=currBack;
currBack>next=tmp;
prev>next= startEle;
return head;
}
//lying elsewhere
prev>next = startEle;
tmp= startEle>next;
startEle>next=currBack>next;
currBack>next = tmp;
startPrev>next = currBack;
return head;
}
i had tested on k = ve, 0,1,2,3...,>len(list) on both even and odd lengths and hence covering all four cases mentioned by @Shondik ...but if i still missed any corner case let me know
 vik February 10, 2013@Anand... LinkedHashMap can be only used here as it will iterate in the order in which the entries were put into the map whereas HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.
Does anybody know equivalent of LinkedHashMap in C++?
yes he has explained properly under bottomup approach while comparing to other approaches
So the logic is... while going bottom up(stack unwinding) you pass min and max at current node to the caller node(parent) and return the total number of nodes if its BST else 1. Nodes who does not satisfy the BST properties, all subtrees above them (which includes this node as well) must also not satisfy the BST requirements. Time complexity O(n) with no extra space
This c++ code is from the same page
int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
int &maxNodes, BinaryTree *& largestBST) {
if (!p) return 0;
bool isBST = true;
int leftNodes = findLargestBSTSubtree(p>left, min, max, maxNodes, largestBST);
int currMin = (leftNodes == 0) ? p>data : min;
if (leftNodes == 1 
(leftNodes != 0 && p>data <= max))
isBST = false;
int rightNodes = findLargestBSTSubtree(p>right, min, max, maxNodes, largestBST);
int currMax = (rightNodes == 0) ? p>data : max;
if (rightNodes == 1 
(rightNodes != 0 && p>data >= min))
isBST = false;
if (isBST) {
min = currMin;
max = currMax;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = p;
}
return totalNodes;
} else {
return 1; // This subtree is not a BST
}
}

vik
February 10, 2013 yes... this is standard Knuth shuffle algo
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
And here is the c++ code for the same
void knuthShuffle(int n){
int *ar = new int[n];
int i(0),temp(0);
for (;i<n;i++) ar[i]=i+1; //initialize array
while(i>0){
int r = Random(i1);//which is similar to >rand()%i;
temp = ar[i1];
ar[i1] = ar[r];
ar[r] = temp;
i=1;
}
for(i=0;i<n;i++) cout<<ar[i] <<" ";cout<<endl;
delete ar;
}
Time complexity: O(n)
Space complexity: O(n)
yes you are right...here is the same implemented in c++
node* appendLastNtoBegin(node* head,int n){
if ((!head)  (!head>next)  n<=0)
return head;
node * curr(head),*curr2(head), *prev(NULL);
int i(1);
while(curr>next){
if (i<n) i++;
else{
prev= curr2;
curr2= curr2>next;
}
curr=curr>next;
}
if (i<n){
cout<<"invalid input for N"<<endl;
return head;
}
prev>next=NULL;
curr>next=head;
head=curr2;
return head;
}

vik
February 09, 2013 @suresh ... coolguy's solution is better as u need to modify the original data neither u can use extra space and since the arrays are sorted then
Time taken = n(to find max start element)+
n(elements of that array) * n (number of arrays)* logn(binary search for each element)
=n+n2logn = n2logn
However your's would be O(n3) ... if the arrays would have been unsorted then your solution would be the valid one but here we can take advantage of sorted arrays
Let A and B be two ranges which are limited by [Alow,Ahigh] [Blow,Bhigh]
Now there can be total 7 cases
1. both ranges matches
2. A is contained in B
3. B is contained in A
4. they intersect but A is on right of B
5. they intersect but B is on right of A
6. they dont intersect and B is on right of A
7. they dont intersect and A is on right of B
which have been handled in python code as following
def findDiffAB(Alow,Ahigh,Blow,Bhigh):
#negetive test case
if (Alow>Ahigh or Blow>Bhigh):
return list()
if(Alow==Blow and Ahigh==Bhigh):
return list()
if (Alow>Blow and Ahigh<Bhigh):
return list()
if (Alow<Blow and Ahigh>Bhigh):
return range(Alow,Blow)+range(Bhigh,Ahigh)
if (Alow>Blow and Ahigh>Bhigh and Alow<Bhigh):
return range(Bhigh,Ahigh)
if (Alow<Blow and Ahigh<Bhigh and Blow<Ahigh):
return range(Alow,Blow)
if (Ahigh<=Blow):
return range(Alow,Ahigh)
if (Alow>=Bhigh):
return range(Alow,Ahigh)
Obviously 4 cases can be merged two 2 here but i didnt for sake of clarity
Few test cases:
print findDiffAB(2,5,2,5)
print findDiffAB(3,5,2,7)
print findDiffAB(2,15,7,9)
print findDiffAB(12,25,2,5)
print findDiffAB(2,5,12,25)
print findDiffAB(2,5,13,15)
print findDiffAB(12,25,2,5)
@Cerberuz i think i will work with but there is something missing
in the following statement
if dp[j] == true:
dp[ j+a[i] ] = true
you set true in dp when there was some other element in dp was already true..... but you never set any element of dp to true(before the main for loop)
I think it can be easily fixed by initializing dp[a[i]] = true (and rest as false) . so that you have elements to start with in dp who are true so that dp can grow on top of them (as you already have 1 element who has a sum equal to index of j)
//before main for loop
for i = 1 to n:
dp[a[i]] = true

vik
February 09, 2013 Yeah i also explained him the trie solution but he was concerned about high amount of space that would be consumed (as each node will contain an array of 26 nodes for next character).. i could have have suggested him compressed trie but we were out of time so we couldnt discuss further
 vik February 09, 2013Here is a working code.. in case anyone wanna have a look
node* reverseList(node* head){
if (!head) return NULL;
node *curr(head), *prev(NULL), *tmp(NULL),*newHead(NULL);
while (curr){
tmp = curr>next;
curr>next = prev;
prev = curr;
curr = tmp;
}
newHead = prev;
return newHead;
}
node* mergeLastAndFirst(node* head){
if (head==NULL )return NULL;
if (head>next==NULL )return head;
node * curr(NULL), *slow(head), *fast(head);
node *newHead(NULL), *tail(NULL),*tmp(NULL),*prev(NULL);
while (fast && fast>next && fast>next>next){
slow = slow>next;
fast = fast>next>next;
}
tail = reverseList(slow>next); //slow will always have next
printList(tail);
slow>next = NULL;
newHead = curr = tail;
while(head && tail){
tmp = tail>next;
curr>next = head;
tail = tmp;
head = head>next;
prev = curr>next;
curr>next>next = tail;//>next;
curr = curr>next>next;
}
if (!curr) curr=prev;
if (head) curr>next = head;
if (tail) curr>next = tail;
return newHead;
}

vik
February 08, 2013 No extra space/stack/queue required.
Total time 2n=> O(n)
Simple non recursive solution
1. Use small and fast pointer to find middle of linked list (no need to calculate length and waste n operations) Time = n/2
2. Reverse the part of list which is following the middle(slow after 1st step) pointer (i have used it as tail in my code) Time = n/2
3. Merge the two half lists (head and tail lists) Time = n
Total time= n/2+n/2+n=2n
Open Chat in New Window
best time is n +logn 2 using tournament trees
 vik October 21, 2013