How does coding improve with time?

Answer by Phillip Oldham from Quora:

• You write code that’s easier to read. Better variable/function/class names, inline comments, better layout, more logical flow.
• You learn that documentation is a GoodThing™ and, while boring to produce, is something you start to add without being prompted.
• You find naming things (arguably the hardest part of programming) gets easier.
• You learn how to structure your code better. Grouping functionality into classes, modules, packages becomes second nature.
• You stop copy-pasting code around your codebase to duplicate functionality, and start following “Don’t Repeat Yourself” practices.
• You learn to log properly, and how useful that is for debugging.
• You stop to think more. When you start out you tend to just keep writing code until something works. As you progress, you start to think more about the problem and stop piling on the code to attempt to fix things.
• You write less code overall; experience teaches you better approaches to the basics you start with.
• You learn what Technical Debt is. And you learn to hate it.
• You learn to refactor. You’d be surprised how often you fix a problem by refactoring and simplifying your code.
• You learn that premature optimisation is a “sin”, but you also learn to use optimal constructs by default.
• You learn to manage your code properly. Version control. Code reviews. Versioning. Releases.
• You stop relying on things. Networks, APIs, protocols, libraries, databases, data, people, even your own code… what can go wrong will go wrong, so you learn to be defensive about everything. While this sounds pessimistic, you realise it’s simply practical.

How does coding improve with time?

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

Since 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
}

Implement a stack having findMiddle operation as well, which returns middle element of stack on O(1) time.

[gist https://gist.github.com/vishnujayvel/6098074]

assert in C

In computer programming, an assertion is a predicate (a true–false statement) placed in a program to indicate that the developer thinks that the predicate is always true at that place.

Assert is a macro which is used to check a condition during runtime and it is very much helpful in debugging #include <stdio.h> #include <assert.h>  int main() { int a, b; printf(“Input two integers to divide\n”); scanf(“%d%d”, &a, &b) assert(b != 0); …………. ……… ….. } assert takes an expression and if the expression is true it continues the program otherwise throws an arrow indicating line no. and condition which does not hold true.

 

SPOJ SBANK problem

This spoj problem may seem difficult in the beginning, but all that is required is a good knowledge of STL in C++. It simply required obtaining the account number from the user and storing it in a map. After this, just iterate through the map and print the values.

[gist https://gist.github.com/niviusha/5944486]

How to sort a stack?

Given a stack S, write a C program to sort the stack (in ascending order).
You are not allowed to make any assumptions about how the stack is implemented; the only
functions allowed to be used are: Push, Pop, Top, IsEmpty, IsFull.

time complexity O(n^2)
Assuming that the only data structure allowed here is the Stack,
then you could use 2 Stacks.

Iterate until the original stack is empty and in each iteration,
pop an element from the original stack, while the top element
in the second stack is smaller than the removed element,
pop the second stack and push it to the original stack.
Now you can push the element you originally popped off the
original stack to the second stack.
if the top element in the 2nd stack is greater than the removed element
just push the removed element from the stack1 to stack2

Ex:
initially
s1:100,2,76,3
s2:null

s1:2,76,3
s2:100

s1:76,3
s2:2,100

s1:2,3
s2:76,100

s1:3
s2:2,76,100

s1:2
s2:3,76,100

s1:null
s2:2,3,76,100

This is actually a modified insertion sort

	#include<iostream>
	#include<stack>
	using namespace std;
	int main(){
	stack<int> s1,s2;
	s1.push(3);
	s1.push(76);
	s1.push(2);
	s1.push(100);
	s2.push(s1.top());
	s1.pop();
	int value;
	while(!s1.empty()){
	value=s1.top();
	s1.pop();
	while(value>s2.top()){
	s1.push(s2.top());
	s2.pop();
	}
	s2.push(value);
	}
	while(!s2.empty()){
	cout<<s2.top()<<' ';
	s2.pop();
	}
	}

view raw sortstack.cpp hosted with ❤ by GitHub

Count set bits in an integer

Subtraction of 1 from a number toggles all the bits (from right to left) till the rightmost set bit(including the righmost set bit). So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the righmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.
Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer.

source: geeksforgeeks

time: O(k) where k is the number of set bits 0<=k<=n

	#include<iostream>
	using namespace std;
	int countSetBits(int n){
	int count=0;
	while(n){
	n=n&n-1;
	count++;
	}
	return count;
	}
	int main(){
	cout<<countSetBits(15);
	}

view raw countbits.cpp hosted with ❤ by GitHub

output:2

Two nodes of a binary search tree have been incorrectly swapped. How will you efficiently restore the tree to its correct state?

An 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 ]

Checking Anagram

Here is a simple code to check if given 2 strings are anagram are not

Just sort the 2 strings and compare if both strings are same

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int main(){

char str1[]=”adamm”;
char str2[]=”madam”;
sort(str1,str1+strlen(str1));
sort(str2,str2+strlen(str2));
if(strcmp(str1,str2)==0)
cout<<“YES”;
else
cout<<“NO”;

}

This is not efficient since you are using sort function twice

An efficient way to check is to create array of 256 characters(includes all ASCII characters)

initialize all array elements as zero and then increment the array element whose index value is the ASCII equivalent of the character encountered in the string

Rest is self explanatory in the given code

#include<iostream>
#include<string.h>
using namespace std;
bool checkAnagrams(char *s,char *t){
int num_unique,num_counted;
num_unique=num_counted=0;
int CharCount[256]={0};
if(strlen(s)!=strlen(t))
return false;
for(int i=0;i<strlen(s);i++){
if(CharCount[s[i]]==0)
num_unique++;
CharCount[s[i]]++;
}
for(int i=0;i<strlen(t);i++){
if(CharCount[t[i]]==0)
return false;
CharCount[t[i]]–;
if(CharCount[t[i]]==0){
num_counted++;

}

}
if(num_counted==num_unique)
return true;
return false;
}
int main(){
char s[]=”helloa”;
char t[]=”oheall”;
if(checkAnagrams(s,t))
cout<<“YES”;
else
cout<<“NO”;
return 0;
}

 

Merge sort using recursion

#include<iostream>
using namespace std;

void merge(int A[],int temp[],int left,int mid,int right ){
int left_end=mid-1;
int temp_pos=left;
int size=right-left+1;
while((left<=left_end)&&(mid<=right)){
if(A[left]<=A[mid]){
temp[temp_pos++]=A[left++];
}
else{
temp[temp_pos++]=A[mid++];
}
}
while(left<=left_end)
temp[temp_pos++]=A[left++];

while(mid<=right)
temp[temp_pos++]=A[mid++];

for(int i=0;i<size;i++){
A[right–]=temp[right];
}
}
void mergesort(int A[],int temp[],int left,int right){
int mid=(left+right)/2;
if(left<right){
mergesort(A,temp,left,mid);
mergesort(A,temp,mid+1,right);
merge(A,temp,left,mid+1,right);

}

}
int main(){
int arr[]={0,45,67,988,99,100,111,1233,0};
int temp[9];
mergesort(arr,temp,0,8);
for(int i=0;i<9;i++)
cout<<arr[i]<<‘ ‘;
}