CareerCup

@saurabh - I thought of same idea...here is the implementation in C#

var expression = "(a(b))(c(d(f))g)(y(h))".ToCharArray();

            int parenthesisCounter = 0, maxParenthesis = 0;

            for (int idx = 0; idx < expression.Length; idx++)
            {
                if (expression[idx] == '(')
                {
                    parenthesisCounter++;
                }
                else if (expression[idx] == ')')
                {
                    parenthesisCounter--;
                }

                if (parenthesisCounter > maxParenthesis)
                {
                    maxParenthesis = parenthesisCounter;
                }
            }

@Rajesh - always test your code before posting. Your code will through index out of range error when i reaches length-1

it might be...

As per my understanding I'm providing the below example for others to try out

Input:

singly linked list
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20

and k = 5

Output:

1->2->3->4->5->10->9->8->7->6->15->14->13->12->11->20->19->18->17->16

Note: Take care of corner cases like n%k != 0 (n - number of nodes in LL) when you work out.

Sort both the arrays A1 and A2 separately using any sorting which guarantees nlogn time
Create an output array A3 of size A1.length+A2.length
Have 2 pointers at the end of each array, compare them (may be using ASCII) and copy the elements to the new array A3, decrement the pointer based on the comparison

sample comparison part:

if (A1[end1] > A2[end2])
{
A3[end3] = A1[end1];
end1--;
}
else
{
A3[end3] = A2[end2];
end2--;
}
end3--;

I can think of one option without involving sorting - space O(n) and time O(n log n)

Create a BST from the input array
Loop through the input array and find the next largest number in BST (n * log n) for search and update the input array

The question says the same for me too..

I agree with you comment, balanced BST is a better choice than array when input size is unknown.

Thanks

forgot to say, the time complexity is O(log n) for both push and pop.

The only problem I can think of using heap data structure (tree representation of an array) is the size. Array allocation is purely assumption as the input is a stream of numbers and we don't know the size. Array is not expandable, once it reaches full the only way to make room is allocating a bigger array and copying all the elements which adds up time and space complexity.

Did interviewer ask this question? and what is the answer?

good one, in other words use "min heap"

Assuming you referred to Sieve of Eratosthenes (en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

It helps finding prime numbers and prints them in sorted order and not in lexicographic order (treating numbers as strings, for example 11 comes before 2)

Please let me know if you intended to describe some thing else.

@Rakesh - The data structure used for storing character occurrence counts depends on the range the characters in the input string.

If the input contains only alpha-numeric then an array of constant size would suffice.
If the input contains wide range of characters then the hash table would save lot of memory.

It all depends on the assumptions which you take during the interview.

Mocking is a good way to test, but the interface should allow us to mock the concrete class.

After lot of math and paper work here is the code in C# with inline comments

O(n) time and O(1) space complexity

public void PrintNumbersInDictionaryOrder(int N)
{
    // straight forward
    if (N < 9)
    {
        for (int i = 1; i <= N; i++)
        {
            Console.WriteLine(i);
        }

        return;
    }

    int startingDigit, multiplyingFactor, loopCount, max;

    // dangerous code with lot of math :-)
    for (int index = 1; index <= 9; index++)
    {
        // prints single digit numbers
        startingDigit = index;
        Console.WriteLine(startingDigit);

        // reset variables
        multiplyingFactor = 1;
        loopCount = 1;

        while (startingDigit * 10 < N)
        {
            // 10, 100, 1000 and so on
            // 20, 200, 2000 and so on
            startingDigit = startingDigit * (int)Math.Pow(10, 1);

            // 9, 99, 999, 9999 and so on
            max = 9 * multiplyingFactor;

            // max value depends on N
            // for example, if N is 25 then max will become 5 instead of 9
            // another example, if N is 256 then max will become 56 instead of 99
            if (N - startingDigit < Math.Pow(10, loopCount))
            {
                max = N - startingDigit;
            }

            // prints 10 - 19, 100 - 199 and so on
            for (int j = 0; j <= max; j++)
            {
                Console.WriteLine(startingDigit + j);
            }

            // 1, 11, 111, 1111 and so on
            multiplyingFactor = (multiplyingFactor * 10) + 1;

            loopCount++;
        }

        // corner case to print
        // for example, if N = 10/100/1000 while loop fails to print the number
        if (startingDigit * 10 == N)
        {
            Console.WriteLine(N);
        }
    }
}

The above code gives you just the idea and it can be refactored more to reduce some Math.

* As per my understanding

As my understanding the lexicographic order / dictionary order of numbers for the range 0 to 20 is

0 1 10 11 12 13 14 15 16 17 18 19 2 20 3 4 5 6 7 8 9

Correct me if I'm wrong...

Thanks URIK :-) I would love too ...

As I understand, the expected output is AABBCCCCBBAA for the input 'ABCD', but why the question talks about second and third iteration?

that will be a separate routine if 'ABC' is passed as input, the expected output is AABBBBAA

and same is with the third routine with the input as 'AB' and the expected output as AAAA

All the tests are inter-related, you cannot perform one without the other. I thought of mentioning it separately just to categorize your test cases.

As you mentioned scalability testing is a good one to add.

Thanks.

* 'm' ranges from 1 to 9

time complexity is O(n * m) where 'n' ranges from 0 to 987654321 and 'm' ranges from 0 to 9 (number of digits) considering Contains and ToString operation for every 'n'
space complexity is O(1) as the size of the pattern string is constant

correct me if I'm wrong.

Forget about my comment, it doesn't make sense to think about the number which has 32 1's in it.

Why your thinking is restricted to 4 bit? and also the binary representation of 11 is 1011 and not 1111 which is for 15

n ranges from 0 to 10^9 (10 power 9) which is a 32 bit number and the number 4294967295 has 32 1's in it.

n-2^k = 4294967295

so the problem here is to find the number 'k' for a given 'n' written on the board in order to reach 4294967295

lets think and find out...

It is easy if you follow my post in the given link, but it involves number to string conversion.

For the case you mentioned, frame a string like below and call it as pattern

"111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 99999999"

if single digit number
	digits are not repeated
else
	if pattern.contains(num.toString())
		digits are repeated
	else
		digits are not repeated

test case:

11
22
33
111
222
333
1111
2222
3333
.
.
.
.
888888888 < 987654321 which is the biggest number with repeated digits

all these numbers when converted to string is a sub string in the pattern :-)

There are lot of test scenarios listed already.

Some of them which are not listed.

1. Cross browser testing
2. User experience testing
3. Performance testing
4. Security testing - includes sql injection, XSS, etc.,

duplicate

question?id=5982716570894336

boolean overlap( Rect a, Rect b){
return( a.ul.x <= b.lr.x &&
	a.ul.y >= b.lr.y &&
	a.lr.x >= b.ul.x &&
	a.lr.y <= b.ul.y );
}

Verified. Alternatively you can do a positive check to find if the rectangles overlap. Check my comment.

Frame a string based on the input range 45 to 4578

"1111 2222 3333 4444 555 666 777 888 999"

this string contains all the possible repeated digits between 45 to 4578 starting from 55 to 4444

Convert the number to string say 45 -> "45" then check if the above string contains this string
if yes, then it has repeating digits

foreach number in the range
convert the number to string
if pattern.contains(string)
repeated digits
else
no repeated digits

@Srikanth once you implement comparable interface on the object say "Shape" the collection.sort method will take care of sorting, you don't need to explicitly write it.

contd... remember to find the node which is just before the beginning of the second half in order to remove the node from second half and insert in first half.

[assumption: if the linked list is singly linked list]

Enjoy coding!!!

good and ideal solution.

What if the input stream has a range of characters which is bigger than the memory available to hold them, in that case we cannot use in-memory hashmap.

Any solution to this follow up?

that's an ideal answer to come up with but I would like to know if Google was happy with this answer assuming this approach was presented.

this works.

But from the given sample data, I suggest to use left join between employee and department because there might be an employee with/without dept/region (Amir in this case) and for that employee region will be blank/NULL

@kmr - there are two cases.

1. To delete the node, we need n+1th node from tail
2. To delete the data, we need nth node from tail. In this case we need to get the data from next node and delete next node

thinking about you approach for all characters...

need to rethink the later part of algo for disconnected characters like "i", "j", etc.,

Queue can be implemented using two stacks, but either Enqueue or Dequeue is expensive

Steps:
1. Create stacks s1 and s2
2. Enqueue operation - push data into s1 then pop all items from s1 and push it into s2
3. Dequeue operation - pop from s2

1. Have two pointers ptr1 and ptr2 pointing to head of linked list
2. Traverse one pointer say ptr2 to distance n from head
3. Now, traverse both
4. When ptr2 reaches the tail, ptr1 is at distance "n" from the tail of linked list

Need to do validation like
1. null check,
2. n might be greater than the length of linked list,
3. loop check and etc.,

refer question?id=14991835

void LevelOrderHelper(Node root)
{
if (root == null)
return;

int height = Height(root);

for (int i = height; i >= 1; i--)
{
LevelOrderRecursive(root, i);
Console.WriteLine();
}
}

void LevelOrderRecursive(Node root, int level)
{
if (root == null)
return;

if (level == 1)
{
Console.Write(root.data);
}
else
{
LevelOrderRecursive(root.left, level - 1);
LevelOrderRecursive(root.right, level - 1);
}
}

int Height(Node root)
{
if (root == null)
{
return 0;
}

int leftHeight = Height(root.left);
int rightHeight = Height(root.right);

if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}

static void Main()
{
TreeProblems t = new TreeProblems();

Node root = new Node(1);

Node level1Child1 = new Node(2);
Node level1Child2 = new Node(3);

Node level2Child1 = new Node(4);
Node level2Child2 = new Node(5);
Node level2Child3 = new Node(6);
Node level2Child4 = new Node(7);

root.left = level1Child1;
root.right = level1Child2;

level1Child1.left = level2Child1;
level1Child1.right = level2Child2;

level1Child2.left = level2Child3;
level1Child2.right = level2Child4;

t.LevelOrderHelper(root);

Console.ReadLine();
}

Implementation in C#, in place, O(n)

void Convert(char[] input)
{
if (input == null)
return;

int zeroCount = 0;
int oneCount = 0;

for (int i = 0; i < input.Length; i++)
{
if (input[i] == '0')
{
zeroCount++;
}
else if (input[i] == '1')
{
oneCount++;
}
else
{
throw new ApplicationException("invalid string format");
}
}

for (int i = 0; i < input.Length; i++)
{
if (zeroCount != 0)
{
input[i] = '0';
zeroCount--;
}
else if (oneCount != 0)
{
input[i] = '1';
oneCount--;
}
}

Console.WriteLine(new string(input));
}

By your post, I assume that there are variables in both the equations.

As per my knowledge, only way to solve this problem is to parse and find variables

What I meant by random numbers is

if you substitute x by 2 in equation (1) do the same in equation(2), by this way you can ensure that both the expressions are same only if they evaluates to same output.

I expect a valid comment when I see down vote.

Basic idea is to use expression tree to evaluate both the strings and then return true or false based on the output of both.

If the equations are something like "2x+3(y*z)" and "3x-2y/(x^z)" think of replacing x, y and z in both the strings to some random number.

Note: validation is required before blindly replacing, because both the expressions can be completely different, one with a,b,c and other with x,y,z..

Life is easy when the expressions are just numbers and operators

@artemis - heap is also full binary tree, in other words tree representation of array

check chapter 6 in CLRS book

@vinod - can you guess what is the condition for this step
"now traverse both upwards and they reach at LCA"

before this step both n1 and n2 are at equal distance from LCA

while (n1.data != n2.data)
{
n1 = n1.parent;
n2 = n2.parent;
}

will this not take care when one node is the child of other ?

public string largestPalindrome(string input)
{
int i, j, k, len = input.Length, maxLengthTillNow = 0;
string palindromeString = string.Empty;

for (i = 1; i < len; ++i)
{
// for even length palindrome
if (input[i - 1] == input[i])
{
j = i - 2;
k = i + 1;

//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j--;
k++;
}

//compare with prev max
if (maxLengthTillNow < (k - j - 1))
{
maxLengthTillNow = k - j - 1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}

// for odd length palindrome
if ((i + 1 < len) && input[i - 1] == input[i + 1])
{

j = i - 2;
k = i + 2;

//expand the sequence
while (j >= 0 && k < len && input[j] == input[k])
{
j--; k++;
}

//compare with prev max
if (maxLengthTillNow < (k - j - 1))
{
maxLengthTillNow = k - j - 1;
palindromeString = input.Substring(j + 1, maxLengthTillNow);
}
}
}

return palindromeString;
}

easy...same as linked list intersection problem.

traverse upwards from both the nodes using parent pointer and find the distance to the root

say d1 > d2

traverse n1 upwards, d1-d2 times...by keeping n2 at same position

now traverse both upwards and they reach at LCA.

why not using min heap of size 3

parse the array, when ever the element in the array is greater than the root of min heap, replace the root with new element and run min heapify on root

at the end, root will contain the third largest number

this can also be modified to find kth largest element where k = 1 to n

How about writing extension methods for string type?

static class StringExtensions
{
public static string CustomConcat(this string s, string s2)
{
return string.Concat(s, s2).ToUpper();
}
}

static void Main(string[] args)
{
string s = "abc";

s = s.CustomConcat("def");
}