Google Interview Round 2 Question

February 9, 2018 at 4:11 pm | Posted in C++, Hacking, Programming | 1 Comment

I was just searching for C and C++ related topics and came across Google interview question.:

/**
*
* Google OnSite Round 2
*
* Input is an integer array A
* Return an array B such that B[i] = product of all elements of A except A[i]
*
*/

Original Question was on CareerCup. I wrote an algorithm on paper in 7 min and took me another 10 min to type it in computer. Do it without using division.

Continue Reading Google Interview Round 2 Question…

Advertisements

Literate Programming

January 10, 2018 at 10:43 am | Posted in Hacking, Programming | Leave a comment
Tags: , , , , ,

I was reading Knuth’s The Art of Computer Programming, the seminal in algorithms. I was unable to understand some parts of section 1.2.10 (analysis of an algorithm), so I asked on IRC channels (like ##programming, ##c, #haskell etc.) and I came across More Shell, Less Egg. Go read that article and come back here.

I hope you have finished reading that article. A few years back I came to know about Literate Programming. I was curious about it, I read some articles on it and really loved the concept. Fast forward to 2018, I am a full-time computer programmer with several years of experience now and my thinking has changed. So how does literate programming look now ?

I read full article and was quite impressed by the cleverness and experience of both Mcllroy and Knuth. Now Mcllroy is a UNIX guy (he wrote UNIX pipes). UNIX gurus are very practical and wise when it comes to solving problems. But I found myself little bit wrong in comparing a shell script with a full fledged programming language available on a variety of systems. Then I came across this comment by Charles Wolfe:

most comments tend to become useless rather rapidly and having the documents wholly separated from the code make the cross referencing or consultation of docs to understand code difficult most of the time.

I have to agree with that as per my own experience (it may not be valid all the time and this is how most of the industrial code is written). We combine that with another very practical blog post by Franklin Chen. He used 2 pieces of codes to prove his point, first one, normal Haskell code and 2nd, Haskell code written with documentation (something like Haskell’s own WEB system). If you look carefully you can see that one with documentation is not much readable (at least I felt horrible when I tried to read it).

So, What Do I think now in 2018 after working in software industry ?

Let me make it very clear that Knuth is a brilliant guy, I respect him a lot. I even someday want to learn from him by sitting next to him teaching me 🙂 . We are talking here about Software Industry, the commercial interests. I think Literate Programming will not spread into the software industry. First of all, industrial software developers (at least here in India) do not care much about comments. I do write hell lot of comments but that is because I was learned my skills on USENET whereas most industrial programmers in India learned from usual engineering colleges where commenting your code well, is not part of the picture. There is no paradigm of “you will write it once and it will be read 10000 times, so help your fellow programmers by telling them what are you doing” (I just industrialized the quote from Knuth: “Programs are meant to be read by humans and only incidentally for computers to execute.”).  2nd, there is lot of job-shifting happens in industry. By the time  a project comes to its completion, there is a possibility that  1000 different people have worked  on it who never communicated with each other, hence,  lot of code changes and many times, comments, sooner or later, become irrelevant. Some comments stay same, many don’t. 3rd, managers in industry want solutions fast and even though, most of the time, such attitude hurts the software and hence the company in long term but then I do not think it is their fault because they have pressure on them to deliver. So, if a project takes a month to design, code and test and deliver then you have to get it done by next week. In such cases, all things not related to “fast delivery” are generally ruled out. If it is not a whole project and there is problem you have to solve then  because of “fast delivery” requirements, UNIX tools win. I have experienced both. You can’t beat UNIX tools there with a general purpose language.  So, I think Literate Programming  will never catch up in industry.

Copyright © 2017 Arnuld Uttre, Hyderabd, Telangana – 500017 (INDIA)
Licensed Under Attribution-NoDerivs 3.0 United States (CC BY-ND 3.0 US)

C quiz

January 4, 2018 at 3:30 pm | Posted in Programming | Leave a comment

I was looking at an online C language quiz and came across this:

#include <stdio.h>

int main(void) {
 struct myStruct
  {
    int num = 10;
  }var;

  printf("%d\n", var.num
);

  return 0;
}

This will never compile. Guess why. Because You can’t initialize struct members in declaration. Here is what gcc 7.2.1 will throw:

[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra t.c
t.c: In function ‘main’:
t.c:6:13: error: expected ‘:’, ‘,’, ‘;’, ‘}’ or ‘__attribute__’ before ‘=’ token
int num = 10;
^
t.c:4:9: warning: struct has no members [-Wpedantic]
struct myStruct
^~~~~~~~
t.c:9:21: error: ‘struct myStruct’ has no member named ‘num’
printf(“%d\n”, var.num
^
t.c:7:4: warning: variable ‘var’ set but not used [-Wunused-but-set-variable]
}var;
^~~
[arnuld@arch64 programs]$

You can do this instead:

#include <stdio.h>

int main(void) {
 struct myStruct
  {
    int num;
  }var;

  var.num = 10;
  printf("%d\n", var.num);

  return 0;
}

Then you get this:

[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra t.c
[arnuld@arch64 programs]$ ./a.out
10
[arnuld@arch64 programs]$

But this will not work:

#include <stdio.h>

struct myStruct
{
  int num;
}var;

int main(void)
{
  var x;
  x.num = -1;
  printf("%d\n", x.num);

  return 0;
}

[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra struct.c
struct.c: In function ‘main’:
struct.c:11:3: warning: statement with no effect [-Wunused-value]
var x;
^~~
struct.c:11:7: error: expected ‘;’ before ‘x’
var x;
^
struct.c:12:3: error: ‘x’ undeclared (first use in this function)
x.num = -1;
^
struct.c:12:3: note: each undeclared identifier is reported only once for each function it appears in
[arnuld@arch64 programs]$

Can you guess why ?

Because /var/ is a myStruct variable, not a type. If you want it to be accessible inside main() then you have to make it a type using typedef, like this:

#include <stdio.h>

typedef struct myStruct
{
  int num;
}var;

int main(void)
{
  var x;
  x.num = -1;
  printf("%d\n", x.num);

  return 0;
}

[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra struct.c
[arnuld@arch64 programs]$ ./a.out
-1
[arnuld@arch64 programs]$

C is a very small language. You can put entire C language in your head if you do few years of serious coding in C. For the standard libraries, you have have H&S5.

Copyright © 2018 Arnuld Uttre, Hyderabd, Telangana – 500017 (INDIA)
Licensed Under Attribution-NoDerivs 3.0 United States (CC BY-ND 3.0 US)

Interview Question — Printing a Palindrome

May 9, 2017 at 4:35 pm | Posted in Programming | Leave a comment

This was asked recently to me in an interview. Problem is explained in the comments:

/* GlobalEdx interview Question, Real Life Practicial Code
*
* If a user enters D then write a program to print like this:
*  A B C D C B A
* If user Enters J or Z then it should print till J or Z
* like above. Program should work for every letter of English
*
*/

#include <stdio.h>

void printPalindrome(char c) ;
int getFirstLetter(char* p, char* pc);

int main(int argc, char* argv[]){
char c;
if(2 != argc) {
printf("Please provide 1 argument\n");
}
else
{
if(!getFirstLetter(argv[1], &c)) printPalindrome(c);
else printf("You did not enter a character. Enter uppercase character \n");
}
return 0;
}

/* If you get more than letter. Just pick up the first letter
*
*/
int getFirstLetter(char* p, char* pc) {
char temp = *p;

/* What if user puts an int or double, here we handle that ? */
if( ((temp >= 'A') && (temp <= 'Z')) ) {
*pc = temp;
return 0;
}
else return 1;
}

void printPalindrome(char c) {
char t;

for(t='A'; t != c; ++t) printf("%c, ", t);
for(; 'A' != t; --t)     printf("%c, ", t);
printf("%c\n", t);
}

OUTPUT:
[arnuld@arch64 programs]$ gcc -ansi -pedantic -Wall -Wextra palindrome.c
[arnuld@arch64 programs]$

[arnuld@arch64 programs]$ ./a.out BA
A, B, A
[arnuld@arch64 programs]$ ./a.out D
A, B, C, D, C, B, A

[arnuld@arch64 programs]$ ./a.out 0
You did not enter a character. Enter uppercase character

[arnuld@arch64 programs]$ ./a.out 0*
You did not enter a character. Enter uppercase character

[arnuld@arch64 programs]$ ./a.out {
You did not enter a character. Enter uppercase character
[arnuld@arch64 programs]$

Copyright © 2017 Arnuld Uttre, Hyderabd, Telangana – 500017 (INDIA)
Licensed Under Attribution-NoDerivs 3.0 United States (CC BY-ND 3.0 US)

HCL Interview

March 28, 2017 at 11:16 am | Posted in Patterns, Programming | Leave a comment

Earlier I wrote about my interview experience with NetCloud Systems Bangalore. Recently I appeared for an interview with HCL Technologies. (HCL Technologies is on the Forbes Global 2000 list.[13] It is among the top 20 largest publicly traded companies in India with a market capitalisation of $22.1 billion as of May 2015.[14] As of August 2015, the company, along with its subsidiaries, had a consolidated revenue of $6.0 billion.[5]  — Source: Wikipedia )

Interviewer was quite younger than me. He asked me to write a program using a singly linked list where he wants to remove Nth element counting from last node you added. e.g if you added 10 elements in the list then 7th element from end is 4th element you added in beginning, hence 4th should be removed. If 1,2,3,4,5,6,7,8,9,10 are the elements you added then “./a.out 7” should remove 4 not 7.

I told him I can use singly list as stack where elements are always added in reverse order. From his looks I could make out he could not understand what I just said. So I asked him if can I use any method,he replied that I should use pointers and gave  a paper and pen to write. This is the full-fledged code with all the checks and added command-line input and string conversion etc. but algorithm/logic/data is exactly same I wrote there and he said this code will not remove 7th from end but 5th from end.   This is wrong code. I was shocked to hear that. Loot at it yourself and see the output:

/* HCL Interview Question (2017)
 *
 * A singly-linked-list (SLL) program to add nodes to SLL and remove Nth node
 * from the end
 *
 * e.g Add 10 nodes to a SLL & remove the 7th node starting from the end
 * 7th node from end is 4th node you added while building SLL
 *
 * I am using a Stack (LIFO). Last node (the end) is always the latest. So, we can
 * go down from there easily. The interviewer said it will not work.
 * Worked fine for me 🙂
 *
 ***/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include 				<limits.h>

struct node {
  long nn;
  struct node* next;
};

struct StPtr {
  struct node* head;
  long tn; /* totoal number of nodes */
};

struct StPtr* st;

void print_diagnostics(void);
void printStack(void);
void convert_to_long(long*, long*, const char*, const char*);
void addNodes(long, long);
void removeNode(long, long);

int main(int argc, char* argv[]) {
  if(3 != argc) {
    print_diagnostics();
    return EXIT_FAILURE;
  }

  st = malloc(sizeof*st);
  if(NULL == st) {
    printf("Out of Memory\n");
    return EXIT_FAILURE;
  }

  st->head = NULL;
st->tn = 0;
  long t = 0, r = 0;
  convert_to_long(&t, &r, argv[1], argv[2]);
  addNodes(t,r);
  printStack();
  removeNode(t, r);
  printStack();  

  return EXIT_SUCCESS;
}

void removeNode(long num, long rem) {
  if((0 >= num) || (0 >= rem) || (rem > num)){
    printf("Nothing to remove\n");
  }
  else {
    struct node* t = st->head;
    struct node* prev = st->head;
    long i = (t->nn - rem) + 1;
    /* IF we ar eremoving the head */
    if(i == st->head->nn) {
      st->head = st->head->next;
      st->tn--;
      printf("Removing node#: %ld \n", i);
      free(t);
    }
    else {
      while(i != t->nn) {
	prev = t;
	t = t->next;
      }
      prev->next = t->next;
      printf("Removing node#: %ld \n", i);
      st->tn--;
      free(t);
    }
  }
}

void addNodes(long num, long rem) {
  if((0 >= num) || (0 >= rem) || (rem > num)){
    printf("Nothing to add\n");
  }
  else {
    for(long i = 1; num >= i; ++i) {

      struct node* p = malloc(1 * (sizeof *p));
      if(NULL == p) {
	printf("Out of memory, will not add node\n");
      }
      else if(NULL == st->head) {
	printf("Adding 1st node\n");
	p->nn = i;
	p->next = NULL;
	st->head = p;
	st->tn++;
      }
      else {
	p->nn = i;
	p->next = st->head;
	st->head = p;
	st->tn++;
      }

    }
  }
}

void convert_to_long(long* num, long* rem, const char* numptr, const char* remptr) {
  errno = 0;  /* To distinguish success/failure after call */
  char* endptr;
  long temp = strtol(numptr, &endptr, 0);
  if( ((0 == temp) && (0 == strcmp(numptr, endptr)) && (errno == ERANGE))
      || ((LONG_MAX == temp) && (ERANGE == errno)) ) {
    *num = 0;
    *rem = 0;
  }
  else {
    *num = temp;
    temp = strtol(remptr, NULL, 0);
    if( ((0 == temp) || (LONG_MAX == temp)) && (ERANGE == errno) ) {
    *num = 0;
    *rem = 0;
    }
    else { *rem = temp; }
  }
}

void print_diagnostics(void) {
  printf("Invalid Number of Args\n");
  printf("Provide 2 arguments:\n");
  printf("\t1st arg is number of nodes\n\t2nd arg is nuber of node to be removed\n");
}

void printStack(){
  struct node* t = st->head;
  for(t = st->head; t; t = t->next) {
    printf("%ld, ", t->nn);
  }
  printf("\n\t---> Total %ld nodes\n", st->tn);
  printf("\n======================================\n\n\n");
}

OUTPUT:
[arnuld@arch64 programs]$ gcc -std=c99 -pedantic -Wall -Wextra ll.c
[arnuld@arch64 programs]$ ./a.out 10 7
Adding 1st node
10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
—> Total 10 nodes

======================================

Removing node#: 4
10, 9, 8, 7, 6, 5, 3, 2, 1,
—> Total 9 nodes

======================================

[arnuld@arch64 programs]$ ./a.out 10 5
Adding 1st node
10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
—> Total 10 nodes

======================================

Removing node#: 6
10, 9, 8, 7, 5, 4, 3, 2, 1,
—> Total 9 nodes

======================================

[arnuld@arch64 programs]$ ./a.out 10 1
Adding 1st node
10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
—> Total 10 nodes

======================================

Removing node#: 10
9, 8, 7, 6, 5, 4, 3, 2, 1,
—> Total 9 nodes

======================================

[arnuld@arch64 programs]$ ./a.out 1 10
Nothing to add

—> Total 0 nodes

======================================

Nothing to remove

—> Total 0 nodes

======================================

[arnuld@arch64 programs]$

I don’t understand how could he say this code will not remove the Nth node from end , code behaves fine. May be he never wrote a Stack in his life. I did another mistake by trying to explain him that Stack is an implementation of a linked list and he shrugged it off. He asked me to write it using some other method (he meant another algorithm) but explain to him first and I did and he said same words again that this new method will not work either. Then I told him, there are several ways you can approach the problem that is why so many algorithms (methods 😉 ) exist and is there any specific method he is thinking of ?   He told me that he is done with me and I can leave for the day  🙂

After coming out I saw on the doors in capital letters, “ODC” was written. That means Offshore Development Center. Most of the ODCs in Indian companies are service based, there is not much development/coding involved. Companies in India, get freshers in a mass based campaigns from colleges and put them on work because they are dirt cheap to get when it comes to economy. These freshers have never worked before and most of engineering colleges here have non-ISO conforming compilers and code in their CS textbooks too does not conform to any ISO/ANSI standard. They have learned C and C++ using such resources, so it is expected that they wont know what is the definition of C language and how do ISO conforming compilers and non-forming compilers behave and what it costs in terms of bugs and maintenance.

Now lets get back to HCL, the company. What did they lose ?  I am just one programmer and what about others. There were 100 people for interview and I am sure at least 10 of them must be very good programmers. Will they get hired ?  I have been to interviews where I had to choose one answer out of 4 options given to me for   “int i = 0; prinf(“%d\n”, i++ + ++i)” and none of the options said “UB”. You were forced to choose an integer as an answer. What did I do ? I wrote “option5: UB” just below tho option 4 and of course I was not hired 🙂 . Can you imagine the quality of code in such a company, quality of hires ?   and what a nightmare it will be to fix bugs and add new features ?  HCL did not do much different from them in my interview. Whom to blame ?  Their hiring process which lets a person with low knowledge of Data-Structures interview a person with medium level of knowledge of Data-Structures. Who created such process. I know I am not that intelligent  because I have never written an AVL Tree and I can’t understand more than half of Maths Knuth writes in his Art of Computer Programming books. I just try to improve everyday and like to read definition of language, reference manuals and man pages and do what they advise. And I am still working on Knuth. In book Programming Interviews Exposed authors wrote that the more you stay away from coding and move towards business side, the more money you make and more secure your career will be (I did not know at that time that google’s machine learning department is working on making coding obsolete).  You make more money if you move from being programmer to business analyst and to software architect (A glassdoor search will tell you that it is really true). Now, how does a person who loves to program, who loves  to write code day and night, who loves to learn more languages, algorithms, more UNIX, Linux, DragonFlyBSD, NetBSD and more UNIX way of solving problems, data-structures, gcc libraries and learn more about programming paradigms,  loves Lisp and the idea behind its macros, loves to read why Eiffel was created and what problems it solves and why and how does it do it and wants to inculcate these as a part of his thinking, plus the shell he works in, and then mastering his text-editor etc. All that  just for the interest and liking. What that person can do to show his skill and get to work with MNC ? Not much if company is not even interested in having a skilled person and improving their software, tools and methodologies.  I think that challenge comes down to the programmer himself. Few companies want to improve, most don’t and you go and find those few companies.

Copyright © 2017 Arnuld Uttre, Hyderabd, Telangana – 500017 (INDIA)
Licensed Under Attribution-NoDerivs 3.0 United States (CC BY-ND 3.0 US)

Next Page »

Blog at WordPress.com.
Entries and comments feeds.