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;
}
Tag Archives: computer programming
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
}
Reverse a doubly linklist
2
[gist https://gist.github.com/vishnujayvel/6098657]
Find a sorted subsequence of size 3 in linear time
0Given an array of n integers, find the 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time. If there are multiple such triplets, then print any one of them.
Examples:
Input: arr[] = {12, 11, 10, 5, 6, 2, 30}
Output: 5, 6, 30
Input: arr[] = {1, 2, 3, 4}
Output: 1, 2, 3 OR 1, 2, 4 OR 2, 3, 4
Input: arr[] = {4, 3, 2, 1}
Output: No such triplet
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream>
using namespace std;
void findSubsequence(int arr[],int n){
int max=n-1;
int min=0;
int *larger=new int[n];
int *smaller=new int[n];
//store the index of the element smaller than arr[i] (on its left side)
//in smaller[i] or -1 if there is no such element
smaller[0]=-1;//its obvious since theres no element in the left of arr[0]
for(int i=1;i<n;i++ ){
if(arr[i]>arr[min]){
smaller[i]=min;
}
else{
smaller[i]=-1;
min=i;
}
}
//store the index of the element larger than arr[i] (on its right)
//in larger[i] or -1 if there is no such element
larger[n-1]=-1;//since theres no element in the right of arr[n-1]
for(int i=n-2;i>=0;i--){
if(arr[i]<arr[max]){
larger[i]=max;
}
else{
larger[i]=-1;
max=i;
}
}
//find the first number which has smaller element on its left and larger element
//on its right
for(int i=0;i<n;i++){
if(smaller[i]!=-1&&larger[i]!=-1){
cout<<endl<<arr[smaller[i]]<<' '<<arr[i]<<' '<<arr[larger[i]];
return;
}
}
cout<<"NO such triplet";
return;
}
int main(){
int arr[]={34,56,45,51,69,70};
findSubsequence(arr,6);
}
Two nodes of a binary search tree have been incorrectly swapped. How will you efficiently restore the tree to its correct state?
2An inorder traversal of BST will be in sorted order.
In the incorrect BST Â 2 of the nodes are swapped .
use this to your advantage and find these 2 elements in inorder traversal which violate the sorted order.This 2 elements need to  be swapped.Thats it!!
Just modify inorder traversal function as follows
[gist https://gist.github.com/vishnujayvel/5879942 ]
Randomized select- Finding Kth minimum element in O(n)
0Yet another application of quicksort.Searching Kth minimum element in O(n)…
[gist https://gist.github.com/vishnujayvel/5879818]
Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
0Algorithm
1)This approach is similar to the problem “checking whether a pair exists in an array
with specific sum S”.
This is what we are going to do.Have a start and end pointer which intially points to
arr[0] and a variable currentSum=arr[0]
2)Now increase end pointer such that currentSum>S .Now we can try finding a subarray having
sum=S within this subarray ending with end pointer.
3)Now to adjust currentSum to S we need to increase the start pointer which in turn reduces
currentSum’s value.If currentSum becomes smaller than S you have to go back to step 2.
4)At one point of time currentSum might become S.if theres no subarray with such sum then
start will be eventually equal to end.
5)Now start your quest from new starting point start+1 and ending point end+1
Time complexity- O(n)
Â
Inorder traversal of BST without recursion
0We all know how easy it is to print bst in inorder traversal using recursion.
What if we want to do this without recursion?
Its not difficult.Recursion uses stacks implicitly while executing.So lets use stacks itself.
algorithm:
1) keep on traversing the root left pushing each node into the stack.
2)if stack is empty exit the function
3)When reaching end pop an element and print it and make root=root->right .Goto step1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void nonRecursiveInorderTraversal(node *root){ | |
| stack<node*> s; | |
| cout<<endl; | |
| while(1){ | |
| while(root){ | |
| s.push(root); | |
| root=root->left; | |
| } | |
| if(s.empty()) | |
| break; | |
| root=s.top(); | |
| s.pop(); | |
| cout<<root->data<<" "; | |
| root=root->right; | |
| } | |
| } |
Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?
1#include<iostream>
#include<string.h>
using namespace std;
int main(){
char str1[]=”hello worlda”;
char str2[]=”lets all woraak”;
int s1[256]={0},s2[256]={0};
int flag=1;
int i=0,j=0;
while(str1[i]!=”){
s1[str1[i]]++;
i++;
}
while(str2[j]!=”){
s2[str2[j]]++;
j++;
}
j=0;
while(str2[j]!=”){
if(s2[str2[j]]>1){
if(s1[str2[j]]!=0){
j++;
continue;
}
else{
flag=0;
break;
}
}
j++;
}
if(flag==1)
cout<<“yes”;
else
cout<<“no”;
}
searching an element in a sorted matrix in O(n)
0#include<iostream>
using namespace std;
bool searchElement(int mat[][4],int n,int x){
int i=0;//1st row
int j=n-1;//last column
//we are starting to search from the right most top element in the sorted matrix
while(i<n&&j>=0){
if(mat[i][j]==x){
cout<<“found in [“<<i<<“,”<<j<<“]”;
return 1;
}
else
{
if(mat[i][j]<x)
i++;//if x is greater check in the next row since rows and columns are sorted
else
j–;//if x is smaller check in the previous column since rows and columns are sorted
}
}
return 0;//if i reaches n and j reaches -1
}
int main(){
int mat[][4]={ {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50},
};
int x=50;
if(searchElement(mat,4,x))
cout<<” “<<x<<” is present”;
else
cout<<“not present”;
}
coding hangover 