#include<iostream>
using namespace std;
/* Function to swap two characters */
void swap(char& a, char& b)
{
char temp;
temp = a;
a = b;
b = temp;
}
/* Function to obtain permutations of string characters */
void permutation(string s,int i,int n)
{
int j;
if (i == n)
cout << s << "\t";
else
{
for (j = i; j < s.length(); j++)
{
swap(s[i],s[j]);
permutation(s, i + 1, n);
swap(s[i],s[j]);
}
}
}
int main()
{
string s;
cout << "Enter the string : ";
cin >> s;
cout << endl << "The permutations of the given string : " << endl;
permutation(s, 0, s.length() - 1);
cout << endl;
}
char * full_string;
void permute(char * str, int length) {
if(length == 0) {
printf(“%s\n”, full_string);
return;
} else {
for(int i = 0; i < length; ++i) {
swap(str[0], str[i]);
permute(str+1, length-1);
swap(str[0], str[i]);
}
}
}
Call like: permute(full_string, strlen(full_string));
http://courses.csail.mit.edu/iap/interview/materials.php
http://www.yu-zhang.net/blog/category/solution-to-cracking-coding-interview-150-questions/
https://gist.github.com/zy66543/c4f42d53357bbcf1c97e
http://www.sanfoundry.com/c-programming-examples-linked-list/
https://gist.github.com/zy66543/94c71816a9ada5cd1a70 remove nodes from Linked list
#include <string>
#include <iostream>
using namespace std;
/* -- check if str1 is a permutation of str2 -- */
bool permutation(string str1, string str2)
{
int len1 = str1.length();
int len2 = str2.length();
if(len1 != len2)
return false;
int letters[256] = {0};
for(int i = 0; i < len1; i++)
letters[str1[i]]++;
for(int i = 0; i < len2; i++)
{
if(--letters[str2[i]] < 0)
return false;
}
return true;
}
/*
* C Program to Reverse a Linked List
*/
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node *next;
};
void create(struct node **);
void reverse(struct node **);
void release(struct node **);
void display(struct node *);
int main()
{
struct node *p = NULL;
int n;
printf("Enter data into the list\n");
create(&p);
printf("Displaying the nodes in the list:\n");
display(p);
printf("Reversing the list...\n");
reverse(&p);
printf("Displaying the reversed list:\n");
display(p);
release(&p);
return 0;
}
void reverse(struct node **head)
{
struct node *p, *q, *r;
p = q = r = *head;
p = p->next->next;
q = q->next;
r->next = NULL;
q->next = r;
while (p != NULL)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
*head = q;
}
void create(struct node **head)
{
int c, ch;
struct node *temp, *rear;
do
{
printf("Enter number: ");
scanf("%d", &c);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = c;
temp->next = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->next = temp;
}
rear = temp;
printf("Do you wish to continue [1/0]: ");
scanf("%d", &ch);
} while (ch != 0);
printf("\n");
}
void display(struct node *p)
{
while (p != NULL)
{
printf("%d\t", p->num);
p = p->next;
}
printf("\n");
}
void release(struct node **head)
{
struct node *temp = *head;
*head = (*head)->next;
while ((*head) != NULL)
{
free(temp);
temp = *head;
(*head) = (*head)->next;
}
}
1. Write a Python function to return the sum of squares of an iterable. I'd be surprised if your function has more than six lines. A built-in self-test in the module is a good idea.
2. Write a similar function to return the sums of squares of any number of iterable arguments. Note that there is not just one argument, a list of iterables, but any number of arguments, each one an iterable. I'd be surprised if your function has more than ten lines. A built-in self-test in the module is a good idea. Would object-oriented programming help?
#!/usr/bin/env python
def sum_of_squares(items):
result = 0
for item in items:
result += item * item
return result;
def sum_of_squares_of_many_args(*args):
result = 0
for arg in args:
result += sum_of_squares(arg)
return result
if __name__ == '__main__':
a = [1, 2, 3, 4]
print sum_of_squares(a)
print sum_of_squares_of_many_args(a,a,a)
3. Write a Python program, perhaps with multiple functions, to take a filename from the command line, read the file, and print the sum of squares of the integer values in the file, one integer per line. If the value of a line is not strictly an integer (e.g. "3.14" is not an integer), print an error message to the standard error port. If the file can't be accessed for some reason, print an error message to the standard error port. If the filename is missing, print a usage message. Return a zero to the shell if the program operated normally, and non-zero values for the various error conditions. It would be nice for the program to include the magic $ variables for SVN to auto-update the version number, check-in date, and so on, but that's not required.
import sys
import os
def sum_of_int_squares(file_name):
result = 0
try:
with open(file_name) as f:
for line in iter(f):
try:
i = int(line)
result += i * i
except ValueError as e:
sys.stderr.write(line.rstrip() +' is not an integer\n')
return result
except IOError as e:
sys.stderr.write ( 'Cannot read the file: '+ file_name)
exit(3)
if __name__ == '__main__':
if len(sys.argv) != 2:
print "Usage: ", sys.argv[0], "filename"
exit(1)
print sys.argv[1]
if os.path.isfile(sys.argv[1]):
print sum_of_int_squares(sys.argv[1])
exit(0)
else:
sys.stderr.write ("File does not exist: "+ sys.argv[1])
exit(2)
4. Write a C function to return the sum of squares of a list of doubles, where the end of the list is marked with 6.0221415 × 10^23.
#include <stdio.h>
#include <math.h>
double LAST_ELEMENT = 6.0221415e23;
double EPSILON = 0.0001; // precison of comparison
double sum_of_squares(double *arr, int size){
double result=0.0;
int i;
for (i=0; i<size; i++){
if abs( fabs(arr[i] - LAST_ELEMENT) < EPSILON )
break; // comparing the doubles/floats for equality is not working, so we use approximation
result += arr[i]*arr[i];
}
return result;
}
int main(void){
double my_array[] = {1.0, 2.0, 3.0, LAST_ELEMENT};
int len=sizeof(my_array)/sizeof(double);
double res = sum_of_squares( my_array, len);
printf("res=%f \n",res);
return 0;
}
6. Write a C function to return the sum of squares of doubles, where the parameter to the function is a pointer to a list of pointers, each of which points to a single double. The end of the list is marked with a NULL pointer. Optional: For extra credit, change the parameter to a singly linked list and document the code accordingly.
#include <stdio.h>
double sum_of_squares(double **parr){
double result=0.0;
int i=0;
while ( parr[i] ){
result += (*parr[i]) * (*parr[i]);
i++;
}
return result;
}
int main(void){
double array[] = {1.0, 2.0, 3.0};
double *p_array[] = {NULL, NULL, NULL, NULL};
int len=sizeof(array)/sizeof(double);
int i;
for ( i=0; i<len; i++){
p_array[i]=&array[i];
}
double res = sum_of_squares( p_array);
printf("sum_of_squares=%f \n",res);
return 0;
}
7. Write a template function that takes a single argument of some type T and returns the result of applying class T's * operator to the argument.
8. If I asked you to write a specialization of the template function in the previous problem that handles the case of T == char *, you would have to ask me some questions in return. What would those questions be? (This tests advanced C and C++ knowledge in several areas. It's a relatively deep question. Cheating is ok but won't help.)
9. Write the SQL to return the largest timestamp in the "ts" column of the table "foo".
(This tests basic SQL knowledge.)
10. Write the SQL to return the names of students who received a grade of A, A+, or A- given the two tables shown below. Also write the command to create the first table.
(This tests basic SQL knowledge and testing strings for similarity.)
table: Student_Grades_by_ID
column 1: student_id (an integer)
column 2: grade (two characters)
table: Student_Names_by_ID
column 1: student_id: (an integer)
column 2: student_name (100 characters)
11. If every person, cat, dog, lizard, mouse, and snake on the planet enrolled in our school, the SQL you wrote in the previous problem wouldn't have to change but the system that evaluates it would. How could we change the system to handle a large problem with billions and billions of rows?
12. Pretend that we need to solve (11) above by September and the person charged with modifying the system was, just this afternoon, hit by a meteor, struck by lightening, and crushed by a dead whale. The job falls to you to find the performance bottlenecks in (10) above and fix them for (11). How would you approach that problem?