gopi.komanduri
 0of 0 votes
AnswersThe following is the design question I was asked.
 gopi.komanduri in India
Design a dash board.
Should be very realistic.
Should be scalabe .
Should have very less latency .
Can expect millions of updates per second.
Dash board should show :
for each day :
1. city name ,
2.total trips in that city for that day ,
3.total fare it could collect in that city on that day,
4. fare collected from old clients
5. fare collected from new clients (new client is the client who is having his first ride in Uber after registration)
Input : we get two strings s1 , s2.
the format of s1 : trip_id , client_id , city , datetime
the format of s2 : trip_id , fare.
Could you please suggest how to proceed for this kind of question? Report Duplicate  Flag
StartUp Analyst Algorithm Business Question Cache Computer Architecture & Low Level Data Structures Distributed Computing Hash Table Ideas System Design  0of 0 votes
AnswersHow to sort an array of integers using two priority queues ?
 gopi.komanduri in United States Report Duplicate  Flag
Analyst Algorithm  0of 0 votes
Answershow to design a relation functionality. similar to facebook , how to hold friends objects for a user profile , so that that is easily searchable . how to use cache for this?
 gopi.komanduri in India Report Duplicate  Flag
Adobe Computer Scientist Algorithm Coding Data Structures  0of 0 votes
Answersif an application hung in customer box , how to whether that is due to dead lock?
 gopi.komanduri in United States
i suggested to take .dmp file and use windbg etc , but he said , he dont have that much time to take dump file etc. I suggested process explorer tool and if application hang , the top call in more than one thread will be like wait call. but he said he is looking for some other tool.
so any thoughts?? Report Duplicate  Flag
Adap.tv Software Architect Debugging Experience unix system programmin unix system programming  0of 0 votes
AnswersA parent array P is given where P[i] denotes the parent of the ith node in the tree(the tree is generic). Parent of root is indicated with 1. I need to find the height/depth of tree. (Best sol in O(n))
 gopi.komanduri in India Report Duplicate  Flag
ADP Analyst Algorithm Arrays C# Data Structures Trees and Graphs  1of 1 vote
AnswersDesign a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .
 gopi.komanduri in United States Report Duplicate  Flag
Computer Scientist Algorithm Android Application / UI Design Arrays Bit Manipulation C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Database Distributed Computing Dynamic Programming Hash Table Java Large Scale Computing Linked Lists Math & Computation Object Oriented Design Problem Solving Sorting SQL Stacks System Design Trees and Graphs XML  0of 0 votes
AnswersDesign a phone book such that fields are searchable with name , with number. Later enhanced teh question asking searchable with address as well.
 gopi.komanduri in India Report Duplicate  Flag
Analyst Algorithm Arrays Bit Manipulation Brain Teasers C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures  0of 0 votes
AnswersGiven data of set of persons {data contains his name , number , address} , and also , each person has 4 ranks. One is global rank , one is region rank , one is centre rank and one is family rank. each rank is independent of other. Design algorithm n ds , to accomodate this requirement. operations that can be done are , change of ranks , insert new person , . searching on rank wise {can be any rank}.
 gopi.komanduri in India
suggestions on this please. Report Duplicate  Flag
Software Architect Algorithm  0of 2 votes
AnswersHow to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.
 gopi.komanduri in India Report Duplicate  Flag
Analyst Algorithm Arrays C# C++ Coding Data Structures Dynamic Programming Experience Hash Table Large Scale Computing Linked Lists Problem Solving Sorting Trees and Graphs  1of 3 votes
AnswersDesign a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll.
 gopi.komanduri in India
later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations. Report Duplicate  Flag
Analyst Algorithm Arrays C C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming Hash Table Ideas Large Scale Computing Linked Lists Object Oriented Design Problem Solving Trees and Graphs  0of 0 votes
AnswersGiven an unsorted array (of unknown length .. can be infinite even ).. at any point of time , how to find a number which is repeated for maximum times , followed questions is how to find a number which is repeated for n times.
 gopi.komanduri in India
Answer I proposed is using combination of binary st as ell as heap.
ex: this binary search tree will have structure which even has pointer to its correponding healelement's pointer.
while inserting an element into tree , will check whether it is repeated , if yes , will increase the priority of this element , and adjust heap accordingly.
Please comment on this solution Report Duplicate  Flag
Analyst Algorithm  5of 7 votes
Answersneed to implement a weather report functionality. user will provide the city name , need to return the weather report.
 gopi.komanduri in India
if weather station exists n functioning properly , will return the weather report of that station .
else ,
will return the nearest available weather station report.
interviewer looking for optimized manner.
looking for datastructures to stores the cities n algo to return the report. Report Duplicate  Flag
Mentor Graphics Analyst Algorithm Arrays Bit Manipulation Brain Teasers C C# C++ Cache Coding Computer Architecture & Low Level Data Mining Data Structures Dynamic Programming General Questions and Comments Graphics Hash Table Ideas Linked Lists Math & Computation Object Oriented Design Problem Solving Sets Sorting Stacks String Manipulation Terminology & Trivia Threads Trees and Graphs XML  0of 0 votes
AnswersGiven two sorted arrays of sizes N,M (N > M).
 gopi.komanduri in India
N has M gaps even though it is sorted. (gaps can be in between . Not required to be at the end).
Best algorithm to merge these two arrays , with out using any extra space. Report Duplicate  Flag
Algorithm  0of 0 votes
Answersgiven N people. one person can like one or more than one persons. But not mandatory to like any one. Find leader in that N people. Leader is a person , who is being liked by all , but he should not like any one else.
 gopi.komanduri in India
Idea I have is:
ex: lets assume set is A,B,C. A likes B,C. B likes C,A. C don't like any one.
Create an array of N and initialize to zero.
Now for every like to other person , decrement the corresponding value , and increment the liked person value.Now at the end , the index whose value is N1 , will be leader.
In now example
step 1 arr[3] = 0,0,0
step 2 (a likes b , c) = 2,1,1
step 3: (b likes a and c) = 1 (2 + 1 (because being liked by b),1 (1 2 (likes two people) , 2 (1 + 1 (being liked by b))
1,1,2.
So here C is the leader.
Please discuss if there are any flaws or abt better ideas. Report Duplicate  Flag
Algorithm  0of 0 votes
AnswersHow to find duplicate element (only one element is repeated) from an array of unsorted positive integers..
 gopi.komanduri
time complexity .. O(n)
space .. o(1). Report Duplicate  Flag
Amazon Analyst Algorithm  0of 0 votes
AnswersSort an array of n positive integers containing n/2 sorted integers in first and secondhalf?
 gopi.komanduri
in O(n) time complexity ..
and space complexity should be constant Report Duplicate  Flag
Amazon Algorithm
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
78.
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
 gopi.komanduri August 05, 2014but the complexity os o(nlogn) ..
 gopi.komanduri August 03, 2014Hi,
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???
 gopi.komanduri August 03, 2014take 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
 gopi.komanduri July 31, 2014@ Kiran : space complexity shoould be 1. but in the solution provide by you , you are using o(n) space.
 gopi.komanduri July 31, 2014Hmm , 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..
 gopi.komanduri July 31, 2014with 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 .
 gopi.komanduri July 31, 2014how 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
 gopi.komanduri July 22, 2014AFAIK , 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
 gopi.komanduri July 20, 2014Now , 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?
 gopi.komanduri July 20, 2014This 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.
 gopi.komanduri July 06, 2014Hi 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[i1].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;
}

gopi.komanduri
May 31, 2013 {
// 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[i1].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;
}
}
 gopi.komanduri May 31, 2013In between the elements!
 gopi.komanduri December 28, 2011Hi,
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
 gopi.komanduri August 17, 2011take 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 xarr[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 ?
 gopi.komanduri August 15, 2011Hi,
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.
Open Chat in New Window
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 ..
 gopi.komanduri July 27, 2016we can use pub/sub patterns while pushing to servers etc.