Co-joined Linked lists

You have two linked lists: A and B. A and B are co-joined at some node 'c'.

(A)--------
           (c) |------- (common part of both linked lists)
(B)--------

Find the the node (c) at which both the linked lists meet / collide.

Solution:

1. Traverse both the lists and find their lengths 'a' and 'b' respectively.
2. calculate the difference between both lengths: d = |a-b|
3. Make two pointers PA and PB for each list.
4. Move the pointer of the longer list 'd' steps.
5. Then move both the pointers simultaneously until both the pointers become equal, which happens at the node 'c'.

Find similarity between two arrays

There are two arrays.

int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

The arrays will be called similar if they contain same number of elements equally.

Write the pseudo code to check this ?

I was not allowed to use sorting and hashtable.

Solution:

I.
Pick a random number from the array and partition it using the quick sort partition function.

Then partition the second array using the same number. O(n) time.

Now recursively, do this until the counts on either side mis-matches.

II.
Make two min heaps in O(n) time.
Extract the mins from both and compare till either both heaps are empty or there is a mismatch.

Reference: http://www.careercup.com/question?id=11685824

Using GDB to debug in linux

To debug a process: "./a.out arg1 arg2", run:

$ gdb ./a.out
(gdb) run arg1 arg2


Reading: http://cs.baylor.edu/~donahoo/tools/gdb/tutorial.html

Understanding the I/O redirection in linux

STDIN is FD 0, while STDOUT is FD 1, and STDERR is FD 2.

To redirect the errors to the output stream use this: 2>&1

Here '&' tells that it is a FD(file descriptor) and not an ordinary file named '1'.

There are lots of redirection symbols that you can use, and here are some of them:

< file	means open a file for reading and associate with STDIN.
<< token	Means use the current input stream as STDIN for the program until token is seen. We will ignore this one until we get to scripting.
> file	means open a file for writing and truncate it and associate it with STDOUT.
>> file	means open a file for writing and seek to the end and associate it with STDOUT. This is how you append to a file using a redirect.
n>&m	means redirect FD n to the same places as FD m. Eg, 2>&1 means send STDERR to the same place that STDOUT is going to.

Reading: http://www.linuxsa.org.au/tips/io-redirection.html

Find if number is a power of two, and returns it power

Solution:

'a' is power of two iff:  (a & (a-1) == 0).


To calculate the highest power 'a',

• iteratively shift the bits of a number to right
• increment a counter each time you shift right
• repeat above 2 steps until number > 0.
• 'counter' gives the value if the highest power.
• No. of loops = 32 ( width of the number)

Better solution:

To find more optimally one can make a lookup table, of say size 4, which stores the power of 2/(number of set bits) and then run the loop 32/4 = 8 times. 

Optimal Solution:

To optimize this even further we can use divide and conquer, at each step find the half of the 32 bit number which contains the set bit. And do this recursively. We need just 5 (= log 32) iterations in this method.

Reading: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog

Swap two numbers using bit operations

Two numbers a,b.

XOR based solution:
a = a^b
// now a contains the  'a xor b'

b = b^a
// now b contains 'a'

a = a^b
// now a contains 'b'

Print all interleavings of given two strings

Given two strings str1 and str2, write a function that prints all interleavings of the given two strings. You may assume that all characters in both strings are different

Example:

Input: str1 = "AB",  str2 = "CD"
Output:
    ABCD
    ACBD
    ACDB
    CABD
    CADB
    CDAB

Solution:

public static void interleavings(String x, String y, String r){
  if(x.length() >0){
   if(y.length() >0){
    interleavings(x.substring(1),y,r+x.charAt(0));
    interleavings(x,y.substring(1),r+y.charAt(0));
   }
   else{
    System.out.println(r+x);
   }
  }
  else{
   System.out.println(r+y);
  }
 }

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

A Program to check if strings are rotations of each other or not

Solution:

If the two given strings are A,B;
concatenate A+A => S.
Now if S contains B, then A is a rotation of B, else not.

Using KMP this can be done in O(n).

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

Check whether two strings are anagram of each other

Solution:

I.) Sort both the strings O(m log m) and then compare each of the sorted strings O(m) => O(m log m).

II.) Create an array of size 26,  in which store the counts of each alphabet in A. As you process B, decrement the count. If any of the counts are not equal to 0, then it is NOT an anagram pair. => O(m)

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

The celebrity problem

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.



In a group of N people, find out if there is a celebrity (who knows no one, but evry one knows him).
Use the func. doesAknowB(A,B) returns true if A knows B.


Solution:


Maintain a stack of celebrities(possibly). Take two ppl A,B out from the stack and check if they know each other.
If doesAknowB(A,B) returns true, then A is discarded as he cant be the celeb. If it returns false, B is discarded as B cant be celeb bcoz evryone knows a celeb.


Keep discarding all the ppl till one last person remains. now validate if this person is celeb or not.


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

Reasoning: This solution uses the the fact that each comparison/question allows us to discard one of the person, who is not a celebrity for sure. So, after N comparisons we have 1 prospective celeb remaining, which we can confirm by asking another n-1 questions.

Find the two numbers with odd occurrences in an unsorted array

Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.


Solution:


XOR of all no.s which occur even no. of times is zero, so XOR of two odd numbers will be the output. Choose a bit at which they differ, and then XOR all elements which have that bit set to '1' gives one no. 
similarly find the other number.


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

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

Solution:

Since all numbers are positive so the sum, we can do this without needing a DP array/table.

Maintain a running sum, which adds all elements from start_pos to curr_pos, until the sum becomes greater than the given number. When sum > given number remove the starting elements until the sum becomes <= the given number.

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

Find the minimum of two numbers without using relational operators

Solution:

1.) Run a loop in which u decrement each number till either of them becomes a zero, and keep incrementing a counter. Return this counter value.
int min(int x, int y){
  int ctr = 0;
  while(x & y){
    x--;y--;ctr++;
  }
  return ctr;
}

2.)
Minimum of x and y will be

y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))

This method shifts the subtraction of x and y by 31 (if size of integer is 32). If (x-y) is smaller than 0, then (x -y)>>31 will be 1. If (x-y) is greater than or equal to 0, then (x -y)>>31 will be 0.
So if x >= y, we get minimum as y + (x-y)&0 which is y.
If x < y, we get minimum as y + (x-y)&1 which is x.

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