Archive

Archive for December, 2011

Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing.

December 16, 2011 Comments off

Problem : Given an array of 998 distinct integers ranging from 1 to 1000 including. Find which 2 numbers are missing.Restrictions: loop over the array only once, can’t allocate an additional array.

Solution :

Find the sum of numbers from 1 to 1000 = 1000*1001/2 = 500500 = S
Find sum of squares of numbers from 1 to 1000 = n*(n+1)*(2n+1)/6 = 333 833 500 = SS
Find sum of 998 distinct numbers as N
Find sum of squares of 998 distinct numbers as NS
Let a and b be 2 missing numbers
S-N=a+b
SS-NS=a^2+b^2
Solve for a and b.

Categories: Algorithms

Given an array of 999 distinct integers ranging from 1 to 1000 including. Find which number is missing

December 16, 2011 Comments off

Problem : Given an array of 999 distinct integers ranging from 1 to 1000 including. Find which number is missing. Restrictions: loop over the array only once, can’t allocate an additional array.

Solution :

Find sum of numbers from 1 to 1000 = 1000*1001/2 =500500
Add the current array sum of 999 numbers = S
The missing number = 500500-S
 

 

Categories: Algorithms

Find the first unrepeated character in a string

December 16, 2011 Comments off
public class FirstUnRepeatedChar
{
public char findFirstUnrepeatedCharacter(String string)
{
int repeatCount[] = new int[256];
for(int i=0;i
char c = string.charAt(i);
repeatCount[c]+=1;
}
for(int i=0;i<string.length();i++){
char c = string.charAt(i);
if(repeatCount[c]==1)
return c;
}
return 0;
}

public static void main(String[] args)
{
System.out.println(new FirstUnRepeatedChar().findFirstUnrepeatedCharacter("vidya"));
}
}
Categories: Algorithms

Remove duplicate characters in a string and display in the same order

December 16, 2011 Comments off
public class RemoveDuplicateChars
{
private String remove(String string)
{
int a[] = new int[256];
int length = string.length();
String removedString = new String();
for (int i = 0; i < length; i++)
{
char c = string.charAt(i);

if (a[c] == 0)
{
removedString = removedString + c;
a[c] = 1;
}
}
return removedString;

}

public static void main(String[] args)
{
System.out.println(new RemoveDuplicateChars().remove("vidyasagar"));
}
}

The above problem can be solved in many number of ways.This is my approach.pleases let me know if you
have any other better approach

Categories: Algorithms

Factorial of a given number

December 16, 2011 Comments off
Categories: Algorithms

Spanish Chars in XML File

December 15, 2011 Comments off
Categories: General

Amazon Interview Questions

December 12, 2011 Comments off

Written Test

  1. Given a linked list A->M->A->Z->O->N,move all vowels up front without disturbing the order.Output should be A->A->O->M->Z->N.
  2. Given a string like AAAbbbCDDD, encode the string in such a way that output should be 3A3c1b3D.
  3. Given a sorted rotated array.Find the rotation point where the array is sorted.Given 30,40,50,60,10,20.Output should be index 4.Time complexity should be less than O(n).

1st Round

  1. Given k sorted arrays.Count of number of elemenst in k sorted arrays are n.Construct the final sorted array of n elements say array[n].
  2. Given an n-ary tree.Serialize the tree int osome file system or some array and deserialize back to the original n-ary tree.

2nd Round

  1. Given a binary tree,find the max element out of all leaf nodes of a tree.When you found max element,after that that node will be deleted from the tree.Again you will have to find max element out of leaf nodes.
  2. Given a file , which have insert and delete operations enabled.You have to find first k most frequency words in taht file.
  3. You have given character set from a to z mapped from 1 to 26, A to Z mapped from 27 to 52.Given a string with possible characters are from a to z and A to Z like asF,encode the string by replacing with numbers.After encoding , decode it back to original string.

3rd Round

  1. Difference between Thread and Process.
  2. Inter process communication
  3. Semaphores and Mutex implementation.
  4. Synchronization
  5. Virtual memory
  6. Computer Architecture fundamentals like Physical Address Space and Virtual address space.
  7. Difference between Abstract Class and Interface in java
  8. When you say www.google.com, how does it works.
  9. Some things related to NAT card
Categories: Interview Questions
%d bloggers like this: