dhirajb1989
BAN USER- 0 Answers Google Written Test
I am preparing for interviews for companies that will come in my campus. Recently I came to know that Google is going to come to my campus. The first round is supposed to be a 60-70 minute written test.
- dhirajb1989 July 27, 2013
Can anyone please tell how to prepare strongly for the written test??| Flag | PURGE
class RemoveNonSimultaneous {
public static void main(String[] args) {
String str = "aabcdabagtdraafgdta";
removeNonSimultaneous(str, 'a');
}
private static void removeNonSimultaneous(String str, char ch) {
// TODO Auto-generated method stub
char charArray[] = str.toCharArray();
int counter = 0;
for (int i = 0; i < charArray.length;) {
if (charArray[i] == ch) {
i++;
if (i == charArray.length) {
break;
}
if (charArray[i] != ch) {
charArray[i - 1] = '\0';
i++;
} else {
while (charArray[i] == ch)
i++;
}
} else
i++;
}
int j = 0;
System.out.println(charArray.length);
for (int i = 0; i < charArray.length; i++) {
while (i != charArray.length && charArray[i] != '\0') {
charArray[j++] = charArray[i++];
}
}
charArray[j]='\0';
String str1 = new String(charArray);
System.out.println(str);
System.out.println(str1 + " :index - " + j);
}
}
//finding the nth fibonacci number
//Time : O(logn)
//Space O(logn)
//All we need to do is multiply {1,1},{1,0} i.e {F(n+1),F(n)},{F(n),F(n-1)} 4999 times so that we get the 5000th fibonacci number
class Fibonacci{
private static void fib(int F[][],int n){
if(n==1)
return ;
//n/2 because if we multiply {1,1,1,0} with itself it becomes 2 times and that if we multiply by itself
//it becomes 4 times and if we multiply that by {1,1,1,0} it will becomes 3 times
int M[][]= {{1,1},{1,0}};
fib(F,n/2);
multiply(F,F);
if(n%2!=0)
multiply(F,M);
}
private static void multiply(int F[][],int M[][]){
int x=F[0][0]*M[0][0]+F[0][1]*M[1][0];
int y=F[0][0]*M[0][1]+F[0][1]*M[1][1];
int z=F[1][0]*M[0][0]+F[1][1]*M[1][0];
int w=F[1][0]*M[0][1]+F[1][1]*M[1][1];
F[0][0]=x;
F[0][1]=y;
F[1][0]=z;
F[1][1]=w;
}
public static void main(String args[]){
int F[][]= {{1,1},{1,0}};
int n=Integer.parseInt(args[0]);
fib(F,n-1);
System.out.println("Fib("+n+") = "+F[0][1]);
//0,1,1,2,3,5,8,13,21,34
}
}
//Input : javac career_cup.java ;java Fibonacci 9; // here 9 is the nth fibonacci number we need to find
//Output: Fib(9) = 21
The answer should be A because once a file is locked, it should be unlocked by the process that locked it.
- dhirajb1989 May 20, 2014I will use a Max heap so that at whichever time-stamp the traffic was high stays right at the root. Using this data structure we can keep those information right at the top for which you need the maximum or minimum. Suppose we need top 10 websites, then we can use a max heap to maintain that.
- dhirajb1989 May 20, 2014-Firstly we take a/b in a string called currentdirectory
-Then we split "c/../d/e/../f" with delimiter as "/"
-When there is a ".." then we take a substring of the currentdirectory
-If there is a character, then we will append "/" and the character
public class FindResultantDirectory {
private static String findResultingDirectory(String currentDirectory,
String sequenceOfOperations) {
String splitDirectories[] = sequenceOfOperations.split("/");
for (int i = 0; i < splitDirectories.length; i++) {
if (splitDirectories[i].equals("..")) {
currentDirectory = currentDirectory.substring(0,
currentDirectory.length() - 2);
} else {
currentDirectory = currentDirectory + "/" + splitDirectories[i];
}
}
return currentDirectory;
}
public static void main(String[] args) {
System.out.println(findResultingDirectory("a/b", "c/../d/e/../f"));
}
}
Data Structures to be used are : Queue for cache and hashtable for constant lookup.
We can use a queue implemented as a doubly linked list to keep the page frames in the cache. So basically any frame that we access from the memory will be put into the queue at the front.
Also use a hashtable that will have page number as the key and the address of the frame in the queue as the value for the key.
Whenever there is a frame i.e it is not in cache but in memory, we bring the frame as a new entry at the top of the queue in the cache.
Then if we need a frame that is already present in the cache or the queue, then detach that frame from the queue and put it infront of the queue.
Now if the queue is full then we take the frame that is at the rear of the queue and place the new frame at the top of the queue.
So searching of a frame and updating it can happen in constant time.
public class FindingRank {
private static int fact(int x){
int product=1;
for(int i=2;i<=x;i++){
product = product*i;
}
return product;
}
public static void main(String[] args) {
int arr[]={4,5,1};
int num = 514;
int i=0;
int sum=0;
while(num!=0){
arr[arr.length-1-i]=num%10;
num=num/10;
i++;
}
for(i=0;i<arr.length-1;i++){
int counter=0;
for(int j=i+1;j<arr.length;j++){
if(arr[i]>arr[j]){
counter++;
}
}
sum=sum+(counter*fact(arr.length-1-i));
}
System.out.println(sum+1);
}
}
Time:O(n^2)
Space: O(n)
Yes, there will be no way to look back to know where the element will be. If the input is 40 then its OK. For that the code is as belows:
void insertInAscendingOrder(Node node, int insertData) {
while (node.data < insertData && node.next != null) {
node = node.next;
}
if (node.next != null) {
int temp = node.data;
Node newNode = new Node(temp);
newNode.next = node.next;
node.data = insertData;
node.next = newNode;
} else {
if (node.data > insertData) {
int temp = node.data;
Node newNode = new Node(temp);
newNode.next = node.next;
node.data = insertData;
node.next = newNode;
} else {
Node newNode = new Node(insertData);
node.next = newNode;
}
}
}
But if the input is 20, then the code will fail and will give the output 10->30->20->50->70
- dhirajb1989 May 12, 2014class NoOfTrailingZeros{
private static int trailingZeroes(int n){
int power = 5;
int i = 1,noOfZeroes = 0;
while(power < n){
noOfZeroes = noOfZeroes + (n/power);
power = power*5;
}
return noOfZeroes;
}
public static void main(String args[]){
int n = 10;
System.out.println(trailingZeroes(n));
}
}
class FindMaxNumberAfterSwaps{
private static void findGreatestNumber(int a[],int noOfSwaps){
int max =0;
int indexOfMax = 0;
for(int i=0;noOfSwaps!=0 && i < a.length - 1 ;i++){
max =a[i];
indexOfMax=i;
for(int j=i+1;j<a.length;j++){
if(max<a[j]){
max = a[j];
indexOfMax = j;
}
}
for(int k = indexOfMax ; noOfSwaps != 0 && k != 0; ){
if(a[k] > a[k-1]){
a[k]=a[k]^a[k-1];
a[k-1]=a[k]^a[k-1];
a[k]=a[k]^a[k-1];
noOfSwaps--;
k--;
}
else
break;
}
}
}
public static void main(String args[]){
int a1[]={2,5,1,9,3,7,2,8,9,3};
int a2[]={2,1,1,1,1,1};
int a[]={5,4,3,2,1,0};
int noOfSwaps = 2;
System.out.print("Old Array: ");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
findGreatestNumber(a,noOfSwaps);
System.out.print("New Array: ");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
Time : O(n^2)
Space : O(1)
class Duplicate {
private static int getDuplicates(char arr[]){
int x = 1,y = 0,counter=0;
for (int i=0;i<arr.length;i++){
//To get the number in the range 0-26
//Assuming only capital letters are in the array, we are subtracting by 65
//65 is the ascii value of 'A'
int num = arr[i] - 65;
//Shifting the 1 to as many bits as the value of "num"
x=x<<num;
//Here the particular bt is being added to 'y' by the OR method
if((x & y) == 0 ){
y = x | y;
}
else{
//means there was a duplicate character
counter ++;
}
//because we need to again do the same thing with 'x'. So restoring to the previous state
x=1;
}
return counter;
}
public static void main(String args[]){
char arr[] = {'A','B','C','A','B'};
char arr1[] = {'A','B','A','A','A'};
char arr2[] = {'C','D','C'};
System.out.println(getDuplicates(arr));
System.out.println(getDuplicates(arr1));
System.out.println(getDuplicates(arr2));
}
}
//Just make use of bit shifting. In an integer just make those bits 1 that corresponding to the letter 'A or 'B. And check if a char is a duplicate if the bit for that in the integer is 1 already.
Time O(n)
Space O(1)
The output is :
true
true
true
The concept here is the same as String constant pool
Java maintains an integer constant pool for integers upto -128 to 127.
So if you do
{{ Integer i1 =127;
Integer i2 = 127;
System.out.println(i1 == i2);
}}
Then it will give true as it is returning the same object from the constant pool.
In the above Question
{{
Integer i1 = new Integer(1);
Integer i2 = new Integer(1);
}}
Both are different object not created in the pool but somewhere else in the heap. So they have different addresses and so hashcode generated for them is different due to which the answer will be false.
For {{System.out.println(i1 <= i2);}}, actual unboxing is happening due to which addresses are not being compared but 1<=1 is being compared.
Instead of ==, we should use equals() method as it properly matches the contents of the two objects and then makes it decisions
The output is :
true
true
true
The concept here is the same as String constant pool
Java maintains an integer constant pool for integers upto -128 to 127.
So if you do
{{ Integer i1 =127;
Integer i2 = 127;
System.out.println(i1 == i2);
}}
Then it will give true as it is returning the same object from the constant pool.
In the above Question
{{
Integer i1 = new Integer(1);
Integer i2 = new Integer(1);
}}
Both are different object not created in the pool but somewhere else in the heap. So they have different addresses and so hashcode generated for them is different due to which the answer will be false.
For {{System.out.println(i1 <= i2);}}, actual unboxing is happening due to which addresses are not being compared but 1<=1 is being compared.
Instead of ==, we should use equals() method as it properly matches the contents of the two objects and then makes it decisions
The concept here is the same as String constant pool
Java maintains an integer constant pool for integers upto -128 to 127.
So if you do
{{ Integer i1 =127;
Integer i2 = 127;
System.out.println(i1 == i2);
}}
Then it will give true as it is returning the same object from the constant pool.
In the above Question
{{
Integer i1 = new Integer(1);
Integer i2 = new Integer(1);
}}
Both are different object not created in the pool but somewhere else in the heap. So they have different addresses and so hashcode generated for them is different due to which the answer will be false.
For {{System.out.println(i1 <= i2);}}, actual unboxing is happening due to which addresses are not being compared but 1<=1 is being compared.
Instead of ==, we should use equals() method as it properly matches the contents of the two objects and then makes it decisions
I will do the following:
-Take three variables namely current_temprature,max_temperature and min_temperature
-After 5 second interval we update the current_temperature with the current temperature....
-If current temperature > max_temperature
then
update max_temperature with current temperature
else If current temperature < min_temperature
then
update min_temperature with current temperature
Do this for every 5 second interval for 24 hours
May be you would want to enclose in triple quotes to mind the formatting
- dhirajb1989 May 31, 2014