CareerCup

@Shashi... Well I didn't got why U are doing the last if check
if(S[i]=='?'){
S[i]='A';
}

This makes logic highly vulnerable..
Example..:-
You are always replacing last character with alphabet 'A' if its '?' why ??

Its Not a Binary tree

Corner case missing .. Question hasn't mentioned it is a binary tree.. Infact the question Says its an UNORDERED tree. So a Child may hv 5 children and another hv only 1... your code fails here

My Algo may be the kinda bit Complicated but I guess the implementation will have its advantage.

1> I will use Trie to Store the words (Not Letters). Coz search string will have words like "the ", "what" etc more frequent.
2> Now For every query .i.e. in trie end node , I will put the frequency count.

Now I even can have the Time complexity to be as minimal as possible coz we are searching word graph (DWAG) and the space of Trie being the minimal, the optimisation will be the best one...


Anymore or better algo is highly appreciated.

No this Lack Memory Compromise.. not a good algo.. coz search site hits million of record in 24 long hour.. Also, during searching the Time Complexity drastically increases........ Not at all the Sol I would like to have

-1 for your Algo.. Coz.. You are assuming the search String is ONE WORD Sentence which is not the case..

The question is query String.. not query word..

Also, the algo sound fishy.. I mean for words like "Britney Spears".. What if the "Britney" and "Spears" individually way less than top 100 but combined String is on the top. coz the way you are framing definitely will have the common words like "the" frequency way above.

See buddy I am having 4+ expr in C/C++ and now I am using C# for cloud project. Code and logic remains the same but C/C++ is much more complex than C# and .net. I mean the transition for me was easy coz the reverse transition will take it own toll..
So be Sure.. thats not a piece of cake as .Net (My View)

This is Duplicate Question .. Please find the proper discussion thread here

http : / / w w w . careercup.com/question?id=15024669

Whats This Eugene ??
-1 for this to you.. :)

I think probably the hash is one option here.

1> I will hash the elements of one array into the hash table.
2> For Every element in the second array try to find the collision and for each collision print value.
Time Complexity = O(m)
Space Complexity = Hash Table Creation.

Clearing Ambiguity and responding to this question here.

Certainly we need to assume that the tree Has to be Binary Tree to be possible. So the algo goes here.

We need to create a Binary Tree on the basis of edge weight value as node and do the following operation.

1> For Unorder Binary Tree, we need to traverse the full tree to get the following values
a> Smallest Edge Node Value and Second Smallest Edge Node Value. As node is now edge.
b> Total Weight of the Tree
So the Max value will be Total minus the two smallest Node value and there will be three sub tree.
Time Complexity will be O(n) and Space O(1).
2> For Ordered Binary Tree like BST the algo remain the same only the Time Complexity goes to O(log n) as searching for the two smallest edge will be easier.

@All.. but still it need some node to store the data.. I guess no extra space rules out the possibility of using any extra space .. Specially for Data Storage .. including O(1) space..

Had Answer this Algo long time Back .. Responding again.

1> Read each word and put into the stack. use recursion for efficiency.
2> Read the Stack till get empty.

@Martin.. Well I believe... thats was a Amazon First Round.. I too humped my First round last year becoz of similar reason.. I wasn't actually prepared for the kind of question they will ask in First round and went with big algo's and all.. but finally the time went like anything..

From my experience what I can tell U.. is leave the rest on them. Even if you try to contact them they won't be able to help you. Coz its online and who know who is going to check it.

And probably U gonna get a next chance after 6 months time as well.. But hope U'll get better than me.. coz now I got call for ASE after I screwed last year call for SDE 2..

Well... I guess this is the Caller dependency...

For Normal Cases we can Say if Thread A only executes then the min value will be there.
and For both thread executes the max value will get generated, But Still there are more complexity involved if we keep discussing.

But i n Laymen Term.

Min=3 ,
Max =8

@Eugene... Who Said C++ Does not Support nested Class ? Search google.. Anyways.. For your information about language.. if your are experienced programmer .. tell me one question.. if you have the language limitation or language operatibility limitation.. will you use or promote language ?? But than how come Java /C++ stand out ?? So what you are claiming here now DOES NOT MAKE SENSE..
There is not benefit of doubt .. in fact for programmer like me there should not be and if there it is U need to clear it out.
So For your info.. here it is.. the only diff with Java from C++ is Memory management.. How java Does MM is BYREFERENCE (no pointer in laymen term).. so even there is one java type version of C++ .. most people called it as C#.. it does the exact same kinda MM what Java Does..
So from my previous expr with Microsoft where I was working on Windows Phone 7 Logger .. I can tell you that the MM layout does follow up almost everything what C++ MM does.. however there is some advance concepts being taken care.. but for question like this no doubt it does.
And I do apologize for my explanation coz I am not a management guy to explain bit and pieces in tech forum and I expect that people reading / commenting have atleast the gap filling knowledge to understand what I meant. :)

@eugene.. Thanks for your insight .. but I would rather like to tell you that in C++ the memory Layout happens EXACTLY what I said.. I am Device Driver Programmer.. and most of the time.. I use this memory management layout to coordinate different process accessing the same memory location..

Well if U know what I meant to say that U understood it.. :D

Well I do Seriously Doubt on what @alex has told up.. People having Java Env Can check with changing the variable name as mentioned by him.

However, being more of the C++ coder, I have a firm idea about what is happening but need to get it verified as Java Don't support pointer.

IMHO, when stack object of Y is being created in the memory stack, the member variable Z will have its address to the offset of 0 bytes from the object of Y.. But as object Y is constructing another object W on the top of its stack, it MAY have this object being created to the offset of 0 bytes to the memory address of the static class Y.

As a Consequence , When we put X.Y.Z.. Compiler goes to the base address of Y and then tries to find the variable Z which after the W's object created lies in the offset of 0 bytes to the base object.

Now the beauti lies in assigning the variable Z which itself is static here.. So as the object W is being created after the Z assignment inside Y, it will get overridden to new value of Z as mentioned in class W.

Well I am not much of the Java Code but looking at the code it should print Apple.

Since its a Static Class so no need to make an Object of class and X.Y.Z refer to the static string Z of the Static Class Y.

U Got that.. So as I mentioned clearly the Collision cases would be cumbersome.

People may throw better ideas around.. I guess for me.. this itself is bit complex to implement.

@anish.. Check the Adjustment Part AGAIN where I am recalculating the stackbase of third stack and shifting elements and lemme know if you fail to understand again.. :)

Well, I guess the way I would like to Achieve this is by something like this.
1> Grow First Stack from the array[0].
2> Grow Second Stack from array[n-1].
3> Here Comes the Challenge. For which I may go for something like this.
Initially I assume array[n/2] and the third array and start growing it accordingly. but when I hit the stacktop of third Stack to the stacktop of any of the other stack, I would recalculate the stackbase of the third array and shift all of its allocated value accordinly.

To recalculate the stackbase of third array probably I may use, the stacktop of the array which does not collide to the stackbase of the third array to find the spacing still available in an array and then divide by 2 to make sure I have spaces left for all the three stack to grow again.
Similarly I would think of stackbase of third array to the stacktop of either array and make again adjustments accordingly.
Ofcourse the collision case would create the time complexity JUMP hugely.. coz I need all stack operation working on together again right from the beginning.

Run BFS and Store the value with its level in a hashmap.

Read the value which is right next to the given value.

Buddy... Pls ReCalculate the Complexity..
Its hell not O(B+N).

FYI.. U missed to calculate the gotoStep 3 part.. which may run for again O(B) or O(N)..

Making it total of O(B2) or O(N2)

Tree.. Tree ... Make a Heap........ Very Easy..

Pretty Old Question,

Use Trie.. for best reference.. Code would be bit complex though

Actually this question seems less puzzling when we say 10GB and 4 GB memories... What if we say 100 GB of data and 2 GB of RAM??

Well, the Answer is less puzzling for all of this.. Its all External Sorting...

Using the Same Idea, we can achieve it ..

Java !!! Well M not a very much of JAVA Coder unlike C++ but My Answer would be like.

Abstract Class in More flexible than interface . means, i will put some logic which later on I can change easily in the derived classes.. Well that says the saying " In interface by Default all methods are abstract". So only Definition in Interface.


However coming to this question. here both the implementation are more or less same. Except the fact that if I want a method Say get1() to have some bydefault logic, I can't do in interface, i need to have Abstact Class.
but along side I am okei with your rest of the responses !!!

M Not Sure.. Why U think there is the limitation.

For Instance, if U find it difficult to implement generics in C. U should use void pointers.. all that template or generics can do is use an Abstract layer to make things easy.. but Finally U can do in C the same thing wat C++ or java Can Do..

I can write a Code of Stack / Queue or rather even a Vector in C using void pointer..

This is obvious question.
1> We need to use template class.
2> API's are very general API's like push /pop/top /size.
3> I would rather like to use Vector as it has the flexibility of resizing.
4> Yes, template class generates place holder's according to datatype and so it won't be an issue.

Implementation Fairly Easy

<template typename T>
class MyStack {
private :
vector <T> stack;
int size;
T *top;
public ;
bool Push ( T data)
{ }

T Pop()
{}

T Top()
{}

int Size()
{}
};

Now these API's are fairly easy to implement.

Well, if M not mistaken.. this is last years Amazon question.. Unfortunately, it sounds like this is an NP problem and still the proper answer is under research !!!!!

Anyone can redirect to correct direction here ?

First of all the question need modifications.

Two trees means two each of n node.. So the Algo is pretty easy for O (n).

Steps :-

1> Visit all node of tree One and push them in queue Q. i.e. O(n) // n is the no. of node in tree 1.
2> For each value in queue Q.
dequeue the value from the queue Q.
Now put this value into the Tree 2 using the BST rule.
end of For // O(m).. // m is the no of node in tree 2

So total time complexity is O(T)=O(n)+O(m) .
if m==n the O(n)
else if m<n
O(n)
else
O(m)

Easy One :-

1> Object foo of class type MyObject is being created on the stack.
2> Pointer named bar is being created which can point to the object of the type MyObject.
3> Here object of the class MyObject is being created on the heap.

If Time Complexity Matters the Most than , you can use the KMP Algo modification for integer accordingly.Its 0(n) , else if 0(n2) is okei than just need to use to loops one for picking each integer in a series and other for checking just the immediate next if its value is greater than itself and collection accordingly.

WOW, Great insight Laxmi.. Thanks for sharing..
Yeah that's absolutely correct what she has told above lines. However adding further towards answering this question from HP , It yes a memory leak, what has actually happend here is during allocation a chunk of 10 bytes memory from heap is returned and the head is being holded by pointer p. but when I say p++ I said p to just forward its next data address (i.e. add of P + 1*datatype of p), so Now P here is just unaware of its first byte of allocation and now when I say free(p),and all but first address gets deleted. Reason free() usage of knows frm where to start releasing to till when, which in this case being array goes releasing till char 10 but avoiding first one.

Thanks for share..
Anyway, its kinda easy question i guess........ :)

Good Question..
Lemme give my view.. Every prgm either hv to compromise of Time or Space Complexity..

Algo:-
1> Space Compromise :-
a> Read a array and hash it.
b> Before putting into hash table check if that place is filled.
c> if Filled its duplicate else not keep it in there.

2> Time Compromise :-

Usual Sorting algo with little modification will work.
a> Pick an element search for its duplicity in the array with min complexity.

Good Question..
But as far as I know, return value is only the compiler check. It has nothing to do with the call stack...

Infact call stack has space reserved for :-
1> All function parameters.
2> All Variables within that scope
3> Any Variables which are used to call for another subroutine.

I feel its a tricky question,and even if you do something stupid as this.. Your code will not compile " Function should return a Value " or " Parameter Mismatched " in case of C / C++ . So call stack itself will not generate if the code is not able to compile.

Sorry for Abbreviation.. Its Time Optimization and Space Optimization .. :)

Typically assume that H=1 and T!=H=0 and set the bit accordingly and send this data using the single string.

However you gotto set the protocol on both the points for your assumption.

Oh Come On Guys ... Its they who are judging you.. Let them know what you know.. and what is correct... if I get the very basic or stupid question in any interview.. regardless of my expertise.. I would give my answer and if possible with added flavour of my experience regarding why is that so........

So, its always suggested to answer the concepts of inheritance, polymorphism and Encapsulation in Java and how is being achieved to make Java an Object Oriented for this question.

Well this statement is the violation of point rule and hence the behavior is undefined.

Different compilation provide different rules and the output cannot be determined to the accuracy.

Simple ..

Local Variables :- Stack
Global Variables :- Data Segment.

Good Question . I guess it depends on designer how do you design your class. For me..

Base class watch should have private methods like ..

int seconds () // returns seconds from 0-59
int Minutes ()
int Hours ()
// can extends to calender feature

public methods like set and get function

You can now extend this base class to derived class called

class Wrist watch extends Watch
Now putting wrist watch features accordingly..

Volatile keywords does two major Task in C Programming.

1> Tells optimizer to please avoid any kind of optimization to be done during compilation.

2> Tells Developer to be careful during its usage as its value can change abruptly.

This is what we called a Pointer implicit conversion. Here the exact way of compiler interpretation is ( Difference in address of pointer variables / Data type of the Pointer )