CareerCup

is this not more like given a BST and one integer k, finding sum of the nodes which can make to that k ?

use geohash, and tries on that . we can find the nearest cabs which are following under same parent.

Got it. Using dfs we don't need to visit all cells if we can find a single path where water can flow, the worst case complexity will be O(n^2), And in my solution, I need to all cells and avg complexity will be O(n^2). Apart from that any other comments on the solution provided by me ?

Answer I suggested:
Represented the wall as 2x2 matrix. All opaque bricks are 1s and all Porus bricks are 0s.
algorithm:
we do using bottom up approach. from right most, bottom cell to top most left cell.

step 1: For any cell A[I][j], if that is 1, go to step 4. If that is 0, proceed to step 2
step 2: A[I][j] = product of (all elements around this cell from where water can pass.
A[I][j] = product (A[I-1][j] , A[I][j-1], A[I][j+1], A[I-1][j+1], A[I-1][j-1])
if value of A[I][j] == 1 go to step 4, else proceed to step 3.
step 3: A[I][j] = product (A[I+1,j-1], A[I+1,J],A[I+1,J+1].
step 4: repeat same to next cell,

Finally, loop through first row of the matrix, if there is any 0 , means there is a way water can travel till ground.

But the question is mostly for real time .. so where we cannot have a dashboard to work as observer pattern. we can choose mvvp / mvc for UI . and at back end , we have use loadbalancers and servers use some hashmaps to get the required details ..
we can use pub/sub patterns while pushing to servers etc.

hey got in one more way.
have taken one more array . in that array I am incrementing heights like explained below :
-1,0,1,6,6,0,0,2,7
filling lengths in the corresponding parent indexes and placing the negative parent index in that child index. why we need this is , to maintain lengths , by accessing parent index length .
a[0] = 1
a[1]= 2
a[2]= -1
a[3]=-6
a[4]=-6
a[5]=-0
a[6] = 3
a[7]=3
a[8]=4 .. the maximum val is the length of the tree

Hi,
My reply is like this. take one hash map , keep on adding parents as key's and corresponding children as values.
ex: let us assume -1,0,1,6,6,0,0,2,7 is the array.

now the hash map will be {excluding -1 , as -1 represents that index as root. so in this case , 0 is root}
0 - 1,5,6
1 - 2
6 - 3,4
2- 7
7-8.
Now take the root element. here it is 0 .
so take one queue and insert values as mentioned in followoing manner

queue.push(1,5,6) length = 1;
pop 1,5,6 .. queue.push(2,3,4) = length ++; // length = 2 // here we have pop'd the queue .. and considered those as keys , and inserted , the values of those keys.

again pop 2,3,4 .. push , 7 = length++; // length = 3;

again pop 7 , push 8 ; length ++ // length = 4.
pop 8 .. now as we dont have any node which acts as parent , length is 4..

time complexity is 0(n) , and space is 0(n) ..

can any one plz correct my understanding ?

My algo works even in taht case.. check the below comment for my approach

but the complexity os o(nlogn) ..

Hi,
even two sum , we need to loop through entire array. but as per the question , they allow only 2 steps itseems

oh misread the question ..sorry .. when u mean two steps , u mean using any 2 operations???

take two pointers , point one at first and one at third. keep on moving one step each till those two point to same value. .
ex: 1a2a3a4a5a .. these two meet at a's which are after 1 , and after 2 .. (in one move)
12aa3a4a5a .. these two meet a's which are before 3 and after 3 ..(3 steps)
123aaa4a5a .. two meet which are after 4 and seond a after 3 ...
1234aaaa5a .. 12345aaaaa .. straight

sure , will share

@ Kiran : space complexity shoould be 1. but in the solution provide by you , you are using o(n) space.

Hmm , how abt like this??
1.scan entire array , take the max positive value , max negative values , count of negative , total count.
2.Now the challange is to maintain order. so for every number , lets say x is the positive number , max positive is mp , max negative is mn.
scan array .. , take two pointers , , positiveP , negativeP.
now for each value in the array , change the value as value follows ..
if(number is positive , use positiveP) else , use negativeP ....
value as value + (positiveP or negativeP)*(mp+1 or mn+1)
mp if we use positiveP , mn if we uuse negativeP .
increment whichever is used (is positiveP is used , incr positiveP else ince negativeP)
so now each value is modified as value + its finalposition*(maxValue+1)..
then arrange array as mentioned in my above proposal.
now in final array,
take two pointers , val , pos .
for each array element , if taht is positive , % taht with maxP if negative % taht with maxN , to get position , and divide with maxP or maxN to get val ...
and arrange accordingly.
time complexity is o(n)
space is (1)

can anyone plz clarify the problem? not clear to me..

with latest technologies , we cna use nodejs for event driven , async functionality (ideally nodejs enables us to use javascript at server end , its a google pet) . and sip for session initiation , and using observer pattern for change listening , we can code multi chat even .

how abt this??? first scan entire array , and get total count of positives and negatives. now in that array , lets take 2 pointers , one starts at start and other at the start + count of positives. now seperate positives and negatives in following manner. keep on incrementing first index , till u get negative value. once u get , swap with that the value of second index and increment second index.
now we have both posittives and negatives seperated.
now again take 2 pointers and swap alternative numbers .
total time ocmplexity is similar to o(n) , space is o(1)

hash table wont work , as memory contraint will be there ...
using trie how can we search with name and with number as well?? I mean using single ntri

One condition the interviewer mentioned is should not use any predefined datastructures like lists

AFAIK , when any number is compared to 0 , it will be OR'd with 0xfffffff , .. so 1 and 0 in first case which is 1 it will skip .. but in 2 | 0 , it will check 0th bit and first bit as well. hence there is one more instruction check in this case... plz correct me if i m wrng

Now , if I want to retrieve top 10 ranked ppl in gkey , ckey , how can I do tat?? we have rank list ...but this ranklist is based on which rank?

This is not my requirement , the interviewer asked this. However initially he said he is open to use any datastructure,. after later narrowed down to hashmap.

Hi saurabh.
I hope i didnt explain the question properly. this is more like for a huge data (lets say for a org like tcs where ppl count is too huge) , and while inserting data , we will have name , id , contact , designation. etc . this record should be searchable using name / id / designation.. whenever multiple records are possible (like name designation) , need to print them all.

Hi,
as mentioned , it is not a fixed array. The size is unknown , like streams in network etc.

// CoinDenomination.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<Windows.h>
#include<atlstr.h>
typedef struct _deno
{
	CString individualDeno;
	CString denominations;
	int cnt;
	_deno()
	{
		individualDeno = _T("");
		denominations = _T("");
		cnt = -1;
	}
}Deno;
int getMin(int n,int *denom,int denomcnt,int currentNum,Deno *denomidations)
{
	
	int min = n + 1;
	int cnt = -1;
	for(int i=0;i<denomcnt;i++)
	{
		if(denom[i] <= currentNum)
		{
			int x = currentNum % denom[i];
			int y = currentNum/denom[i];
			if(!x)
			{
				cnt = denomidations[denom[i]].cnt * y;
				if(cnt < min)
				{
					min = cnt;
				}
			}
			else
			{
				if((denomidations[x].cnt != -1) || (denomidations[x].cnt != -2))
				{
					cnt = denomidations[denom[i]].cnt * y + denomidations[x].cnt;
					if(cnt < min)
					{
						min = cnt;
					}
				}
			}
		}
	}
	denomidations[currentNum].cnt = min;

	return min;

}
int FunmindenomCnt(int n,int *denom,int denomcnt)
{
	Deno *denominations = new Deno[n];
	int minDenom;
	for(int i=0;i<denomcnt;i++)
	{
		denominations[denom[i]].cnt = 1;
	}
	for(int i=0;i<=n;i++)
	{
		if(i >= denom[0])
		{
			if(denominations[i].cnt != 1)
			{
				minDenom = getMin(denominations[i-1].cnt,denom,denomcnt,i,denominations);
				denominations[i].cnt = minDenom;
			}
		}
		else
		{
			denominations[i].cnt = -2;
		}
			
	}
	return minDenom;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[3]={1,2,4};
	int mindenomCnt = FunmindenomCnt(7,arr,3);
	return 0;
}

{
// CoinDenomination.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<Windows.h>
#include<atlstr.h>
typedef struct _deno
{
	CString individualDeno;
	CString denominations;
	int cnt;
	_deno()
	{
		individualDeno = _T("");
		denominations = _T("");
		cnt = -1;
	}
}Deno;
int getMin(int n,int *denom,int denomcnt,int currentNum,Deno *denomidations)
{
	
	int min = n + 1;
	int cnt = -1;
	for(int i=0;i<denomcnt;i++)
	{
		if(denom[i] <= currentNum)
		{
			int x = currentNum % denom[i];
			int y = currentNum/denom[i];
			if(!x)
			{
				cnt = denomidations[denom[i]].cnt * y;
				if(cnt < min)
				{
					min = cnt;
				}
			}
			else
			{
				if((denomidations[x].cnt != -1) || (denomidations[x].cnt != -2))
				{
					cnt = denomidations[denom[i]].cnt * y + denomidations[x].cnt;
					if(cnt < min)
					{
						min = cnt;
					}
				}
			}
		}
	}
	denomidations[currentNum].cnt = min;

	return min;

}
int FunmindenomCnt(int n,int *denom,int denomcnt)
{
	Deno *denominations = new Deno[n];
	int minDenom;
	for(int i=0;i<denomcnt;i++)
	{
		denominations[denom[i]].cnt = 1;
	}
	for(int i=0;i<=n;i++)
	{
		if(i >= denom[0])
		{
			if(denominations[i].cnt != 1)
			{
				minDenom = getMin(denominations[i-1].cnt,denom,denomcnt,i,denominations);
				denominations[i].cnt = minDenom;
			}
		}
		else
		{
			denominations[i].cnt = -2;
		}
			
	}
	return minDenom;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[3]={1,2,4};
	int mindenomCnt = FunmindenomCnt(7,arr,3);
	return 0;
}

}

In between the elements!

Hi,
How about the following approach.

lets take stack is stack1.
lets take 2 pointers , p1 and p2
for every pop , keep increment p1 , so that p1 will point to latest pop'ed out element.
increment p2 for every odd count of pop's...

increment p2 , for 1 , 3 , 5 , pop'ings etc..
so at the end , p2 will point to middle element of the stack.

yes

take an array of linked list structure.
struct mylist *ptr[5] // assumed 5 sorted lists r provided...

for(i=0;i<5;i++)
ptr[i]= // assign the lists heads;

now get the minimum value of all nodes assigned in that array ... one find , increment that corresponding array node.. till all nodes of array are pointing to NULL.

complexity .. O(countof(all nodes in the provided sorted lists)

lets assume for k=2 initially ..
now the problem will be turned into , finding 2 numbers from a given arraay , whose sum will be x
sort the array , then
for(int i= 0;arr[i]<x;i++)
for each and every arr[i] , use binary search to find x-arr[i] ...


for each binary search , order is o(logn) .. as we repeat for n times . (generic ) .. order is o(nlogn)

now if k = 3 , o(n^2logn)

sort the array .. now for consider two elements and find the required third element using binaary sserach ..

please correct me if I am wrong.

sort the array in desc order. Then iterate through the same. keep counting for entire array ... with this appproacl , we can get repeated elementss for n/2 times , then n/4 , n/8 , etc.
complexity .. O(nlogn) // for sorting o(nlogn)+ one scan o(n)

spaace -- o(n) ..

are we assuming that all repeated elements are adjacent ?

Hi,
Seems to be good solution , but in the problem sstaatement , it is mentioned as "iterating through a sequence is not provided to you as part of this test question" .. but I believe your algo requires to iterate through the arrays.

Hi Ashish,
Thanks for the explanation.. but still that is not pretty much clear to me..
n = 2 3 4 5 3 (repeat! set bit in B)
A = 1 110 1110 11110 11110
B = 0 000 0000 00000 00100

as we have taken 2 bit arrays...
lets take one bit array to scan for first time.
bit myarray[10] // given 10 in random
Input : 23453
for first time , we get 2
so we set myarray[2] bit (assumed array starts with 0 .. and will set corresponding bit in array..
next we set 3 .. now our array contains .. 0011 ( first zero as number didnt start with zero .. next 0 as no 1 .. next 1 as we have 2 .. next 1 as we have 3)
next we set myarray[4] .. next 5 ...
now next 3.. as bit 3 is already set .. we are declaring as duplicate..
is this what you are trying to say?
if so ,
lets assume we have array like 142,100,98,1500,12,150,142,1500 ..
could you please explain how to apply the above concept and fetch the dup in o(n)

Hi Ashish Kaila,
Please correct me if I am wrong.
lets assume I have numbers like 1,2,3 and given one bit array..
so to represent 1 , we need to set 0th bit ... (001) , to set 2 , we need to set 1st bit (010) .. for 3 , we need to set 0th and 1st bits (0011) ..so now if we look at the bit array , we will see it as 0011... so we cannot make it out which numbers are set ...
so could you please explain how to use bit array in this case.