1 .What’s 2 to the power of 64? (Google)
Karatsuba multiplication algorithm.
x = x1 * B^m + x2 y = y1 * B^m + y2
xy = (x1 * B^m + x2)(y1 * B^m + y2) => a = x1 * y1 b = x1 * y2 + x2 * y1 c = x2 * y2xy = a * B^2m + b * B^m + c
#include <iostream>
using namespace std;
#include <string>
using std::string ;
//add two numbers
string addString(string number1 , string number2)
{
if(number1.length()> number2.length())
{
int i = number1.length()- number2.length();
string zeroNumber ;
for(int j = 0 ; j<i; j++)
{
zeroNumber = "0"+ zeroNumber ;
}
number2 = zeroNumber+ number2;
}
else
{
if(number2.length()> number1.length())
{
int i = number2.length()- number1.length();
string zeroNumber ;
for(int j = 0 ; j<i; j++)
{
zeroNumber = "0"+ zeroNumber ;
}
number1 = zeroNumber+ number1;
}
}
int remainder = 0;
string sum="";
for(int i = number1.length()-1; i>=0; i --)
{
int value = (number1[i] - 48) +(number2[i] - 48) +remainder ;
if(value > 9)
{
remainder = 1;
value = value - 10;
}
else
{
remainder = 0;
}
sum = "0"+sum ;
sum[0] = (value+ 48) ;
}
if(remainder ==1)
{
sum = "0"+sum ;
sum[0] = (remainder+ 48) ;
}
return sum ;
}
string power(int n)
{
string sum = "1";
for(int i = 0 ; i< n; i++)
{
sum = addString(sum,sum) ;
}
return sum ;
}
int main()
{
cout <<power(64)<<endl;
return 1;
}
2. What is the size of the C structure below on a 32-bit system? On a 64-bit?(Google)
struct foo {
char a;
char* b;
};
struct foo {
char a;
char* b;
};
char *a = NULL;
int size = (int) (a+1);
3. Using two threads you should print "Hello World Hello World Hello World Hello World Hello World Hello World ". (IBM)
In two threads one should print "Hello: and another thread "World"..
4. write a program to print a matrix
1 2 3
4 5 6
7 8 9
I need to print like following
1 2 3 6 9 8 7 4 5
4 5 6
7 8 9
I need to print like following
1 2 3 6 9 8 7 4 5
5 Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?(Google)
#include <iostream>
#include <string>
#include <stdlib.h> /* malloc, free, rand */
using std::string ;
using namespace std;
//---------------------------------------
//Return -1 Not find
//Return >-1 position for data in resourse
//----------------------------------------
int FindString(const char *Resourse ,const char *Data)
{
int iDataLength = 0;
while(*(Data+iDataLength)!= NULL)
{
iDataLength++;
}
int i = 0;
while(*(Resourse+i)!= NULL)
{
int j = 0;
if (*(Resourse+i) == *Data)
{
while(*(Data+j) != NULL)
{
if(*(Data+j) != *(Resourse+i+j))
{
break;
}
j++;
}
}
if (j ==iDataLength )
{
return i;
}
i++;
}
return -1;
}
//-------------------------------
// get length of string
//-------------------------------
int LengthString(const char *data)
{
int ilength = 0;
while(*data!= NULL)
{
ilength ++;
data++;
}
return ilength;
}
//------------------------------------------------------
//remove string in string
// "i love you" , remove "love"-> return "i you"
//------------------------------------------------------
char* RemoveString(const char *Resourse ,const char *Data)
{
int iDataLength = 0;
int iResourseLength= 0;
while(*(Data+iDataLength)!= NULL)
{
iDataLength++;
}
while(*(Resourse+iResourseLength)!= NULL)
{
iResourseLength++;
}
int i = 0;
while(*(Resourse+i)!= NULL)
{
int j = 0;
if (*(Resourse+i) == *Data)
{
while(*(Data+j) != NULL)
{
if(*(Data+j) != *(Resourse+i+j))
{
break;
}
j++;
}
}
if (j ==iDataLength )
{
char *ptr = (char*)malloc(sizeof(char)*(iResourseLength-iDataLength)+1);
if (*ptr==NULL)
{
return NULL;
}
int i1= 0;
int j1 = 0 ;
while(*(Resourse+i1)!= NULL)
{
if ( (i1 <(i+iDataLength)) && (i1>= i))
{
i1++;
continue;
}
*(ptr+j1) = *(Resourse+i1);
i1 ++;
j1 ++;
}
/*if (*ptr){
free(ptr);
}*/
*(ptr+j1) = NULL;
return ptr;
}
i++;
}
return NULL;
}
int main()
{
char a[]= "i love you";
char b[] = "love";
cout<<a<<endl;
cout<<b<<endl;
cout<<FindString(a, b)<<endl;
cout<< LengthString(b)<<endl;
char *ptr = RemoveString(a,b);
int i = 0;
while(*(ptr+i) != NULL)
{
cout<<*(ptr+i);
i++;
}
cout<<endl;
if (ptr)
{
free(ptr);
}
return 0 ;
}
6 . Implement a function to divide two integers without using the divide operator.(Google)
-
7 . Write a function to efficiently convert a floating point number to a rational number. For example, given
-
9 How would you store 1 million phone numbers?
-
google-
7 . Write a function to efficiently convert a floating point number to a rational number. For example, given
0.125 return"1/8" (Microsoft)-8 ,Write a program to reverse a singly linked list? Modify that program to reverse a doubly linked list.(facebook)-
#include <iostream>
using namespace std;
#include <stdlib.h> //malloc ,freee
typedef struct node
{
int data;
struct node *next;
}Node;
typedef struct list
{
Node *first;
Node *Last;
}List;
Node *CreateNode(bool& result , int data)
{
result = false;
Node *NewNode = (Node *)malloc (sizeof(Node ));
if(NewNode == NULL)
{
return NewNode;
}
result = true;
NewNode->data = data;
NewNode->next = NULL;
return NewNode;
}
void initLinkList(List &MyList)
{
MyList.first = NULL;
MyList.Last = NULL;
}
void AddNewNode(List &MyList ,Node *newEle)
{
if(MyList.first == NULL)
{
MyList.first = newEle;
MyList.Last = MyList.first;
}
else
{
newEle->next = MyList.first;
MyList.first = newEle;
}
}
void reverseList(List &MyList)
{
Node *prev = NULL;
Node *cur = MyList.first;
Node *next = NULL;
MyList.Last = MyList.first;
while(cur!=NULL)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
MyList.first = prev;
}
void display(List &MyList)
{
Node *current = MyList.first;
cout<<"show link list"<<endl;
while (current != NULL)
{
cout<< current->data << " ";
current = current->next;
}
cout<<endl;
}
#include <iostream>
using namespace std;
#include "linkList.h"
int main()
{
List MyList;
initLinkList(MyList) ;
bool flag = false;
Node* newNode = CreateNode( flag, 10);
cout<<"add new node "<<endl;
AddNewNode(MyList, newNode);
Node* newNode1 = CreateNode( flag, 20);
cout<<"add new node "<<endl;
AddNewNode(MyList, newNode1);
Node* newNode2= CreateNode( flag, 15);
cout<<"add new node "<<endl;
AddNewNode(MyList, newNode2);
display (MyList);
reverseList (MyList);
display(MyList);
return 0;
}
Reverse a Linked List9 How would you store 1 million phone numbers?
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
using namespace std;
//#include <Windows.h>
void swap(int& a , int& b)
{
a = a+b;
b = a -b;
a =a -b;
}
unsigned int CountSetBits( unsigned int X )
{
unsigned int cout = 0;
while(X > 0 )
{
if (X%2 == 1)
{
cout++;
}
X = X>>1;
}
return cout;
}
Count the number of 1 in binary representation
Number of 1 in a Binary int factorial(int n) { if (n== 0) { return 0; } int i = n-1; if (i ==0) { return n; } return factorial(n-1)*n; } int countfactorial(int n) { int i= factorial(n); int total = 0; while(i>0) { total = total + (i%10); i = i/10; } return total; } void RemoveDuplicates( int* Array, int Size ) { int end = Size; int position = Size-1; for (int i = 0 ; i< end;i++ ) { for (int j =0 ;j< Size;j++) { if ((Array[i]) == Array[j] && i!= j &&(end-1) != i) { swap(Array[end-1] , Array[i]); end = end -1; i = -1; position --; break; } } } cout<< "position " << position <<endl; for(int i = 0; i< Size;i++) { cout<< Array[i]<<" "; } cout<<endl; } int main() { cout<<factorial(7)<<endl; cout<<countfactorial(7)<<endl; cout<<CountSetBits(10)<<endl; int a[]= {5,5,5,5,5,5,5,5,5,5}; RemoveDuplicates(a, 10); for(int i = 0; i<9 ; i++ ) { for(int j = i+1 ; j< 10; j++) { if (a[i]>a[j]) { swap(a[i],a[j]); } } } int temp; int count = 0; for (int i = 0 ; i< 10 ;i++) { cout<< a[i]<<" "; } cout<<endl; for (int i = 0 ; i< 10 ;i++) { temp = a[i]; if (temp == a[i+1]) { count++; } else { cout<< a[i] <<" "<< count +1<<endl; count = 0; } } return 0; } |
http://www.cs.berkeley.edu/~vazirani/algorithms/
http://www.a2zinterviews.com/Interview/technical-interviews/data-structure/data-structure-interview-questions_2.php
http://www.careercup.com/page?pid=ibm-interview-questions
http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/analysis.4up.pdf
http://thereq.com/q/best-cpp-software-interview-questions/language-features
http://javarevisited.blogspot.com/2013/03/top-15-data-structures-algorithm-interview-questions-answers-java-programming.html
http://www.glassdoor.com/Interview/Microsoft-Software-Development-Engineer-II-Interview-Questions-EI_IE1651.0,9_KO10,42.htm
http://dsalgointerview.wordpress.com/tag/amazon-interview/
No comments:
Post a Comment