Given two sorted linked lists. Find the path of maximum sum.

Given two sorted linked lists. You start with a one of the two lists and then move till the end. You may switch to the other list only at the point of intersection (which mean the two node with the same value in different lists.) You have to find the path of maximum sum.

Eg
  1->3->30->90->120->240->511
  0->3->12->32->90->125->240->249
  You can switch at 3 90 or 240 so the max sum paths is
  1->3->12->32->90->125->240->511 

Sol:

This can be solved in O(m+n).

Take two pointers p1 and p2 for both lists. 

Maintain two sums curr1 and curr2 for each list init to 0.

1. If p1 == p2: 
• if curr1 > curr2: Choose LL1 as path upto this point.
• else: Choose LL2 as path.
2. If p1 < p2:
• curr1 += p1
• increment p1 to next node.
3. else if p2 < p1:
• curr2 += p2
• increment p2 to next node
4. if p1 == null:
• traverse all of p2 and keep incrementing curr2.
• Take the path with greater sum
5. if p2 == null: // do as above for p1

https://www.geeksforgeeks.org/flipkart-interview-set-7-sde-ii/

Find all the Nodes at the distance K from a given node in a Binary tree. Print them in any order.

Sol:

This can be divided into two cases:

1. It is easy to print the nodes at distance K from node which are under the subtree of the given node. Pass an integer 'dist' to its children and increment it each time. When 'dist' == K, print those nodes.
2. Nodes at distance K from the given node with its parent node in the path. For this we can return 'dist' in our recursive function. And increment it at each step before returning. When returned value at any point is K we print those nodes. Special case: If we are doing inorder traversal, we need to handle a special case when the given node is the right child of its parent. In this case we will have to traverse the left child of its parent again.

https://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/

Given 4 lists of numbers (including -ve no.s) of length n, find all combinations of numbers (a, b, c, d) from respective lists which sum to zero.

We need to find 4 numbers, one from each list which sum up to zero.

Solving for 2 lists:
We can solve for 2 lists in O(n) as follows,

• Put the first list in a hashmap.
• Iterate the second list
• for each element s(i) in second list, lookup "0-s(i)" in the map
• If found we got one pair

Solving for 4 lists:

• Combine first and second list as follows,
• For each combination of f(i) and s(j), create an element f(i)+s(j)
• This gives us n^2 elements
• Combine 3rd and 4th lists in a similar manner and get another n^2 list.
• Now we can solve for these two lists of size n^2 in O(n^2).

Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed

Given an array, only rotation operation is allowed on array. We can rotate the array as many times as we want. Return the maximum possbile of summation of i*arr[i].

Example:

Input: arr[] = {1, 20, 2, 10}
Output: 72
We can 72 by rotating array twice.
{2, 10, 1, 20}
20*3 + 1*2 + 10*1 + 2*0 = 72

Input: arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9};
Output: 330
We can 330 by rotating array 9 times.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
0*1 + 1*2 + 2*3 ... 9*10 = 330

Solution:

Maintain the sum (lets say, B) of the full array except the last and first element for the current rotation.

After each clockwise rotation, the new sum to calculated(lets say, A) increases by this B & the current first element, and reduces by the (n-1) * last element.

http://www.geeksforgeeks.org/find-maximum-value-of-sum-iarri-with-only-rotations-on-given-array-allowed/

Find smallest +ve no. missing from the array

Original link:http://www.careercup.com/question?id=12708671

You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. 
Eg: 
Input = {2, 3, 7, 6, 8, -1, -10, 15} 
Output = 1 

Input = { 2, 3, -7, 6, 8, 1, -10, 15 } 
Output = 4

Solution:

1.) Partition the array into the values smaller than zero and +ve integers using the Quicksort partition method. This can be done in O(n) time and in the same array.

2.) Now you the index of element '0' or first +ve number, say this is idxZ.

3.) Traverse starting from idxZ and set the sign bit of the value at position (idxZ + A[idxZ]) to 1. You do this only in case the value of position lies in the bounds of array.

4.) Now starting at 'idxZ' find the first position where the sign bit is UNSET. This gives you the number you are looking for.

Building a search engine based on Inverted indexes

http://en.wikipedia.org/wiki/Inverted_index

SPOJ problem ID [4]: Transform the Expression

Following is my first solution to the SPOJ problem 4: http://www.spoj.com/problems/ONP/

Python solution:


import sys
import string

operators = ['+', '-', '*', '/', '^']

n = int(raw_input())

def isoperator(char):
        if char in operators:
                return True
        else:
                return False

def process_line(line):
        stck = []
        output = ""
        for i in range(0,len(line)):
                if line[i].isalpha():
                        output += line[i]
                else:
                        if isoperator(line[i]):
                                while len(stck) >0 and stck[-1] in operators and operators.index(line[i]) < operators.index(stck[-1]): #lower precendence of new operator, so pop the higher precendence from stck
                                        output+=stck.pop()
                                stck.append(line[i])
                        elif line[i] == ')': #is a closing brace
                                while stck[-1] != '(' :
                                        output+=stck.pop()
                                stck.pop()
                        else : # opening brace, and put it to stck
                                stck.append(line[i])
                #print "stck     :" + str(stck)
                #print "output   :" + output
        while len(stck) > 0:
                output+=stck.pop()
        print output

while n > 0:
        line = raw_input()
        n-=1
        process_line(line)

String searching problem

Given a TEXT string say "abcmanmfaxyzabcn" and a search string "man". Find the number of occurrences of the SEARCH string "man" in the given text string. The alphabets of the search string can be separated by other characters in between them in the text string e.g. "man" occurs twice in "mabcayzn" with 'a' occurring at two different positions.

Solution:

1. First build a boolean array of 26 chars and store the chars which occur in the SEARCH string.
2. Next remove all characters from the TEXT string which don't occur in the SEARCH string using the above array. This allows us to reduce the problem size by removing unwanted characters from TEXT string.
3. The first approach i gave to the interviewer was to use a recursive function, which passes 2 arguments to the function findSubstring(String text, String search) and this searches search[0] in all the places in text and then calls the function on the remaining subproblem. However the time complexity of this solution is exponential.
4. Next i came up with a dynamic programming solution. In this we create a matrix res[m][n] with TEXT string chars as the columns and the SEARCH string chars as the rows. Now we calculate  res[i][j] as:

res[i][j] =   0  if SEARCH[i] != TEXT[j]

                          Sum of all res[i-1][k] for all  0<k<j

The time complexity of this solution is O(mn) and is a lot faster than the recursive solution.

Design a timer class

Design a timer class. The users of your class should be able to register to your class with the time in secs and their callbacks. These callbacks are called as the time expires.

• The timer runs in its own thread, and it sleeps for 1 sec (since, the interviewer had asked for 1 second as the granularity)
• It maintains a list of  'Task/Runnable' along with the remaining time to expire.
• Every time the timer wakes up after a sec, it reduces the expiry time for each task by 1 sec.
• And for all those tasks for which the expiry reaches zero, their callbacks are called.
• I suggested a faster way (where one doesn't need to iterate the list of tasks) if the timer was limited to a fixed number of seconds using an circular array of seconds.

http://www.java2s.com/Code/Java/Development-Class/AsimpleimplementationoftheJava13javautilTimerAPI.htm

http://www.artima.com/intv/blochP.html

Linked list Duplication

Given a linked list which has the node structure as shown below:

class Node{
  Node val; // note that the value also randomly points to some other node in the LL
  Node next;
}

How would you duplicate this linked list ?

Hint: I used an external hashmap DS in my solution.

Better solution:
http://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/

Microsoft Interview Question

Given two numbers as a linked list of digits, write a program to add the numbers and return the result in the new linked list.

Microsoft Interview Questions

1. Make the mirror image of the given binary tree.
2. Design the data structure and algorithm to help in spell correction of words. The correct words are given in alphabetical order in the dictionary file.
3. Write a function which tests whether the given binary tree is a binary search tree or not?
4. Merge two given BSTs in linear time.
5. Using getchar() take user input until user presses Enter key. And then print the user input in the reverse order.

Adobe Interview Questions

1. A rectangle is cut from another rectangle (any orientation). Find the line which divides both rectangles into 2 equal halves.
2. Do the tree traversal level by level. After each level print the new line i.e. ‘\n’.
3. Solve the 12 coin problem to find the different coin in 3 weightings.
4. A king has 1000 barrels of wine, out of which one is poisoned. Use min. no of prisoners to identify the poisoned bottle.
5. Modified tower of Hanoi. Every disk move is through an intermediate bar.
6. Find the no. of ways in which the sum of coins can be obtained using the coins x,y,z.
7. Sorting of very large file, which does not fit in memory.

Google Interview Questions

1. You are given a sorted array (a[]) and a value sum. Find the pairs a[i] and a[j] in the sorted array s.t. a[i] + a[j] = sum. Your algorithm should be linear in time and space.
2. In the tennis tournament find the second best player.

Find all contiguous sub-arrays whose sum is zero.

For example:

i/p: 1,2,3,-3,-2,-1
o/p: [2,3], [1,4], [0,5]

You can do a running sum of all the array elements to get the tmp[]:
=> 1 3 6 3 1 0

Now in this array you need to find all duplicates,triplets etc.. All such pairs represent indices of numbers between which the sum of sub-array is zero.

Now to find the duplicates, we can store the tmp[] values as the key in the hashmap with the array index as the values. So, all indices which fall to same key gives us the solution.

Design data structure for merging meeting schedules

http://stackoverflow.com/questions/8346689/design-data-structure-for-merging-meeting-schedules

Add two numbers without using arithmetic operators

http://www.geeksforgeeks.org/archives/18324

Store an N-ary tree structure in Relational database table

I was asked this question during my tower research interview for the position of Senior script developer.
I came up with the solution to store it in a self referring table which has two columns (parent,child). So, in this kind of table he said that finding the depth of any particular node, i would have to write/call queries equaling the depth of the node under consideration. He asked how can you improve the data structure to store this kind of structure in tables ??

http://iamcam.wordpress.com/2006/03/24/storing-hierarchical-data-in-a-database-part-2a-modified-preorder-tree-traversal/
http://www.sitepoint.com/hierarchical-data-database-2/

Other questions:

Linux:

Find all files open under a process -> ls -l /proc/{PID}/fd

How to setup a password-less SSH

Remove the soft-links in a directory and replace them with the copy of the original file.

List all files in a directory recursively which are not owned by a particular user.

Array Based:

Given 2K+1 numbers out of which K numbers occur twice each and one number occurs just once, find this one time occurring number. -> used XOR

Given numbers from 1 to K with 2 numbers missing, find the 2 missing numbers. -> used XOR based partitions.

Java:

When is finally called. What if you return from inside try and have a return inside finally as well ? What if finally throws an exception ?

About the synchronized() keyword.

Database:

How would you store a tree in the relational tables?

Interviewer: Manikant K.

How to design a web forum

This was asked to me as a design question in amazon telephonic round. The interviewer wanted to know the DB design and the web-app design for a forum which supports around 100K users with the following use-cases:


 -Sign up
- Posting
- Replying
- Searching [keywords + dates based]

I told him we could have following DB schemas:


Thread [tid, subject, date]
Post [pid, tid, uid, msg, datetime ]
User [uid, role, emailid, password_hash ...]
Role [rid, list flags(for permisssion etc.)...]

The plain DB solves the use cases for Sign-up, posting and replying but could become a bottle neck for search if we run a search query based on query in the Post table (with a where clause as 'like "%keyword%"). So, for improving the performance of this, i suggested running an independent background process which parses the msgs in the post table and stores the important keywords from this messsage in the  independent datastore/B-Tree structure to be able to index the keywords for faster searches. The corresponding value for the keywords is the 'pid' (post id) in the table. This should improve the performance of the query. the interviewer seemed to have liked the proposal. Let me know if you guys can think of a better strategy for faster searches.

After this he wanted me to move to the Java side and explain the design there. I told that we would make similar classes/objects like the tables above, define relationship between those classes and then define the operations on these classes.
For components, I told him i would use the MVC architecture, where the views would be JSPs and Controller would be the interacting servlets which would extract data from the views, call the business logic from the Model and then fill the results in a new view which is returned to the user. He asked me to delve a little deeper into the Model components. I told this would basically have two main layers one is DAO (which interacts with the DB) and other is the service layer (which is called by the controller and internally calls the DAO classes for DB interaction). The service classes would be using the above set of objects.
PS: I wasn't very comfortable with the component design part, so any comments are welcome.

Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Amazing solution in the link below, based on a stack for O(n) time. I just loved it :P

Reading:http://www.geeksforgeeks.org/archives/8405