bool findElement(int a[], int length, int expectedNum) { int i = 0; while(i < length) { if(a[i] == expectedNum) return true; else { int diff = abs(expectedNum - a[i]); i = diff + i; } } return false; }
Monthly Archives: July 2013
Maths – Problem solving shortcuts
0Here is a pdf of all must-know shortcuts for solving math puzzles/problems
https://docs.google.com/file/d/0BwBNB2MLLRV7VHlFZlcxdThRSWc/edit?usp=sharing
Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity
0Since we cannot use extra space, take advantage of the fact that the array has elements only from 1 to n
and there are n elements in the array(index ranges from 0 to n-1)
So if 1 occurs make value at 0th index negative
if 2 occurs make the value at 1st index negative
if n occurs make the value at n-1th index negative
So if the same number occurs again then the value at that number index will be found negative already and
voila !Thus we found a way finding repeating number.
Algorithm
traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
Interview Question: Data Structure for Tic-Tac-Toe
1Got this recently:
How would you design a data structure for the game Tic Tac Toe? The main objective is to provide: A method, as efficient as possible, for checking the board to see if there is a winner.
View original post 372 more words
Given a 10GB file of integers and a RAM that can hold only 4GB values, how would you sort the integers in the file.
0Divide the file in 3 parts(3.5 GB+3.5 GB+3 GB,(each part must be less than 4GB )) and sort each chunk using any O(nlogn) sorting algo(as it is less than 4GB we can apply any in-place sorting algo). once each chunk of file sorted, bring 1GB of each chunk in memory, so it’ll occupy 3GB(1+1+1), now sort this 3GB data(by 3-way merge sort).
When executing the merge function select the minimum element add that in remaining 1GB, and while selecting this number, bring the first number from remaining set from the corresponding chunk to replace it, finally write sorted 1GB to secondary storage.
Example:
let say we divide file in three chunk A,B,C and after sorting individully, content of these parts is like: A{12,18,20,25,33,35,37},B{8,13,14,40,41,45,47},C{2,15,50,70,72,75,78}.
Now suppose in memory, we have {12,18,20,25} {8,13,14,40} {2,15,50,70} respectively from A,B,C. now we’ll select 2 from C’s part as its minimum, so put this in remaining 1GB and replace 2 in memory by an element of chunk C. i.e. insert 72 in C’s part in memory.. next replace 8 by 41 and so on.. we are maintaining a min heap.
source:careercup.com
Reverse a doubly linklist
2Insert in a circular sorted linklist
0#include<iostream> | |
using namespace std; | |
struct node | |
{ | |
int data; | |
struct node *next; | |
}; | |
struct node* createNewNode(int data){ | |
struct node* nn=new struct node(); | |
nn->data=data; | |
nn->next=NULL; | |
return nn; | |
} | |
struct node* sortedInsert(node *head,int data){ | |
struct node* newNode=createNewNode(data); | |
struct node* current=head; | |
if(current==NULL){//if the circular LL is empty | |
newNode->next=newNode; | |
head=newNode; | |
} | |
else if(current->data>=newNode->data){// if newNode has to be inserted before the head | |
while(current->next!=head){ | |
current=current->next; | |
} | |
current->next=newNode; | |
newNode->next=head; | |
head=newNode; | |
} | |
else{//if the newNode has to be inserted somewhere inbetween the list | |
while(current->next!=head&¤t->next->data<newNode->data) | |
current=current->next; | |
newNode->next=current->next; | |
current->next=newNode; | |
} | |
return head; | |
} | |
void printList(struct node *start) | |
{ | |
struct node *temp; | |
if(start != NULL) | |
{ | |
temp = start; | |
cout<<endl; | |
do { | |
cout<<temp->data<<" "; | |
temp = temp->next; | |
} while(temp != start); | |
} | |
} | |
int main() | |
{ | |
struct node *head = NULL; | |
for(int i = 6; i>0; i--) | |
{ | |
head=sortedInsert(head,i); | |
} | |
printList(head); | |
return 0; | |
} | |
Implement a stack having findMiddle operation as well, which returns middle element of stack on O(1) time.
0Printing binary form of a number using stack
0void
printBinaryForm(
int
n)
{
Stack S;
// Say it creates an empty stack S
while
(n > 0)
{
// This line pushes the value of n%2 to stack S
push(&S, n%2);
n = n/2;
}
// Run while Stack S is not empty
while
(!isEmpty(&S))
printf
(
"%d "
, pop(&S));
// pop an element from S and print it
}
implement your own sizeof() operator
0Define a macro as shown in line 3 in the code
#include<iostream>
using namespace std;
#define mysizeof(data) (char*)(&data+1)-(char*)(&data)
int main(){
char arr[]={1,2,3};
int arr1[]={1,2,3};
cout<<mysizeof(arr);
cout<<endl<<mysizeof(arr1);
}
output:
3
12
suppose memory location for arr1[] starts with 2000, then arr1[]+1 will point to 2012 and not 2004.
This is because arr1[] is referring to the complete array and hence arr1[]+1 will refer to a memory location just next to the last element of the array.
So, the output with mysizeof(arr1) gives you 12
source:careercup,com