Next power of 2

2013-05-24T23:04:00.004-07:00

Write a function that, for a given no n, finds a number p which is greater than or equal to n and is a power of 2.

import java.util.*;
import java.lang.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int a=8;
    int flag=0;
    do
    {
        if(a%2==0)
        {
            if(( a & (a-1))==0)
            {
                System.out.println("Next Number:-"+a);
                flag=1;
            }
            a=a+2;
        }
        else {
            a=a+1;
            if((a&(a-1))==0 )
            {
                System.out.println("Next NUmber :-"+a);
                flag=1;
            }
        }
        
    }while(flag==0);
        }
}

Google Interview Question with Solution

2013-05-18T11:57:00.001-07:00

1. Given a source array of integers with possible duplicates and a target integer, write algorithm to find out 2 numbers in source array whose sum is equal to target integer.

Ans :- Using Sorting :-

Algorithm:

hasArrayTwoCandidates (A[], ar_size, sum)

1) Sort the array in non-decreasing order.

2) Initialize two index variables to find the candidate

elements in the sorted array.

(a) Initialize first to the leftmost index: l = 0

(b) Initialize second the rightmost index: r = ar_size-1

3) Loop while l < r.

(a) If (A[l] + A[r] == sum) then return 1

(b) Else if( A[l] + A[r] < sum ) then l++

4) No candidates in whole array - return 0

Program :-

import java.util.*;

import java.lang.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int a[]={4,1,2,7,9,3};

int length=a.length;

length--;

mergesort(a,0,length);

SumToTarget(a,0,length,2);

}

/* Function to check whether the duplicates whose sum equal to target num exist or not */

public static void SumToTarget(int a[],int start,int last , int num)

{

int i=start;

int j=last;

while(i<j)

{

if((a[i]+a[j])==num )

{

System.out.println("Two numbers are"+a[i]+" "+a[j]);

return ;

}

else if((a[i]+a[j])>num)

{

j--;

}

else if((a[i]+a[j])<num)

{

i++;

}

System.out.println("Duplicates whose sum equal to target doesnot exist");

}

public static void mergesort(int a[],int start,int last)

{

if(start<last)

{

int mid=(start+last)/2;

mergesort(a,start,mid);

mergesort(a,mid+1,last);

merge(a,start,last,mid);

}

public static void merge(int a[],int start ,int last,int mid )

{

int j,k,l;

int c[]=new int[a.length];

j=start;

k=start;

l=mid+1;

while(j<=mid && l<=last )

{

if(a[j]<a[l])

{

c[k]=a[j];

k++;

j++;

}

else

{

c[k]=a[l];

k++;

l++;

}

while(j<=mid)

{

c[k]=a[j];

k++;

j++;

}

while(l<=last)

{

c[k]=a[l];

k++;

l++;

}

for(int i=start;i<=k-1;i++)

{

a[i]=c[i];

}

In my algorithm I have used merge sort hence time complexity will be

O(nlogn)+o(n)=O(nlogn)

And space complexity o(n) because of merge sort .

2. Say you have three tables WORK, USERS, MANAGERS

WORK- work_id- user_id- how_muchUSERS

- user_id
- teamMANAGERS

- manager_id
- team

If I am a manager, write a select statement to retrieve the work of all users who belong to my team. The mapping of user to team and team to manager are defined in the USERS and MANAGERS table.

Ans:- Select how_much from WORK, USERS,MANAGER where

WORK.user_id = USERS.user_id and USERS.team= MANAGERS.team

3. In a Chrome extension, which file contains the most important information of the extension like version, pattern matches, etc.

Ans:- The manifest file, called manifest.json, gives information about the extension, such as the most important files and the capabilities that the extension might use. Here's a typical manifest file for a browser action that uses information from google.com:

{

"name": "My Extension",

"version": "2.1",

"description": "Gets information from Google.",

"icons": { "128": "icon_128.png" },

"background": {

"persistent": false,

"scripts": ["bg.js"]

"permissions": ["http://*.google.com/", "https://*.google.com/"],

"browser_action": {

"default_title": "",

"default_icon": "icon_19.png",

"default_popup": "popup.html"

}

For more information of the answer of this question see the link:- http://developer.chrome.com/extensions/overview.html

4. There are three rooms, and there are Princess, Flowers and Snake in those rooms. The doors of all the rooms have incorrect nameplates. i.e., the nameplate for the princess’ room is not Princess. Similarly, the nameplate for the Flowers’ room is not Flowers. You need to find the room of the Princess without going to the room of Snake. How do you find?

Ans;- Go to the room which has the nameplate Snake. That will not have Snake. If the room has princess, you are done. If the room has flowers, then go to the room which has nameplate flowers. Princess would be there in that room. [Since, Princess cannot be there in the room which has nameplate Princess.

5. Which is faster: finding an item in a hashtable or in a sorted list? And Why?

Ans;- The fastest way to find an element in a sorted indexable collection is by N-ary search, O(logN), while a hashtable without collissions has a find complexity of O(1).

It also depends on the amount of the data as well . because if we have a small amount of data then sorted list will be almost as much efficient as the hastable would be but if the data storage is very large then definitely hastable would be efficient.

6. How do you find out if a number is a power of 2? And how do you know if it is an odd number? Write code in the language of your choice.

Ans:- To check whether a number is a power of 2 we apply the and operation between number and number-1 if we get 0 then it is otherwise it is not .

for eg:-

Hence 8 is an power of 2 .

To check whethera numbers is odd we didvide it by 2 if leaves remainder then it is odd otherwise it is even.

7.Number of users in 2010 for adwords, chrome, gmail, android and picassa are in the ratio of 6:9:14:13:8, and in 2011 we add 3 lakh more users. New ratio is 8:12:13:11:6. Number of picassa users in 2011= 1,44,000. Calculate number of adwords users in 2010.

Everybrickmatter

Next power of 2

Google Interview Question with Solution