Motorola Interview Question for SDE1s


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

take two pointers p1 - 0th position p2 on 2nd position..swap both
now change the position of pointers - p1 - next to 2nd pointer..p2 - position of p1+2..swap again.. if there is no 3rd element break the loop.

- shah November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Single linked list reversal by interval N

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>

typedef struct _ll
{
	int val;
	struct _ll *nxt;
}ll_t;

ll_t *head=NULL;

int addElm2ll(int count, int *vals)
{
	int i=0;
	ll_t *llp;	
	for( ; i<count; i++){
		llp = (ll_t *) malloc( sizeof(ll_t));
		if( llp<=0 ) printf("Memory allocation for node failed\n");
		llp->nxt = head;
		head = llp;
		llp->val = vals[count-i-1];
	}
	return i;
}

void dispElm4ll(ll_t *tmp)
{
	int i=0;	
	printf("\n");
	while(tmp){
		printf("%d ", tmp->val);
		tmp = tmp->nxt;
		i++; 
	}
	printf("\n");
}

int revbyorderN(int N, ll_t *tmp, int count)
{
	int i, j;
	ll_t *tmp1;
	int *vals = (int*)malloc(sizeof(int)*N);
	if(vals <= 0) return -1;
	for(j=0; j < (count/N); j++){
		tmp1=tmp;
		for(i=0; i<N; i++){
			vals[i] = tmp->val;
			tmp = tmp->nxt;
		}
		for(i=N-1; i>=0; i--){
			tmp1->val = vals[i];
			tmp1 = tmp1 -> nxt;
		}
	}
	free(vals);
	return 0;
}

void delEle4ll(ll_t *tmp)
{
	ll_t *tmpnxt;
	while(tmp){
	 	tmpnxt = tmp->nxt;
		free(tmp);
		tmp = tmpnxt;
	}
}

int char2int( int count, char **argvs, int vals[])
{
	int i;
	for( i=0; i<count; i++){
		vals[i] = strtol(argvs[i+2], NULL, 10);
	}
	return i;
}

int main(int argc, char **argv)
{
	int *vals = (int *)malloc( sizeof(int)*(argc-2));
	if(argc < 3) {
		printf("%s reverse_by_order numbers_seprated_space\n", argv[0]);
		printf("ex: %s 3 12 43 56 34 56 34\n", argv[0]);
		return -1;
	}
	char2int(argc-2, argv, vals);
	addElm2ll( argc-2, vals);
	dispElm4ll(head);
	revbyorderN(atoi(argv[1]), head, argc-2);
	dispElm4ll(head);
	delEle4ll(head);
	return 0;
}

- sizins November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

That's a good one but very very Long... we can do the same using just two pointers and the entire list we can reverse after interval of K..

public Link<Integer> recursiveRecurse(Link<Integer> node, int k){
		Link<Integer> q = node;
		Link<Integer> r = null;
		Link<Integer> s = null;
		int count = 0;
		
		while(q!=null && count < k) {
			s = r;
			r = q;
			q = q.next;
			r.next = s;
			count++;
		}
		
		if(q != null) {
			node.next = recursiveRecurse(q, k);		// for joining the reversed part and the first node of the sublist.
		}
		return r;
	}

- vrajendra.singh.mandloi November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

well explained solution found on Internet:

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL.

Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5
Output: 5->4->3->2->1->8->7->6->NULL.

Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev. See this post for reversing a linked list.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list */

#include<stdio.h>
#include<stdlib.h>
 
/* Link list node */
struct node
{
    int data;
    struct node* next;
};
 
/* Reverses the linked list in groups of size k and returns the
   pointer to the new head node. */
struct node *reverse (struct node *head, int k)
{
    struct node* current = head;
    struct node* next = NULL;
    struct node* prev = NULL;
    int count = 0;  
     
    /*reverse first k nodes of the linked list */
    while (current != NULL && count < k)
    {
       next  = current->next;
       current->next = prev;
       prev = current;
       current = next;
       count++;
    }
     
    /* next is now a pointer to (k+1)th node
       Recursively call for the list starting from current.
       And make rest of the list as next of first node */
    if(next !=  NULL)
    {  head->next = reverse(next, k); }
 
    /* prev is new head of the input list */
    return prev;
}
 
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node =
            (struct node*) malloc(sizeof(struct node));
 
    /* put in the data  */
    new_node->data  = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);   
 
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
 
/* Function to print linked list */
void printList(struct node *node)
{
    while(node != NULL)
    {
        printf("%d  ", node->data);
        node = node->next;
    }
}   
 
/* Drier program to test above function*/
int main(void)
{
    /* Start with the empty list */
    struct node* head = NULL;
  
     /* Created Linked list is 1->2->3->4->5->6->7->8 */
     push(&head, 8);
     push(&head, 7);
     push(&head, 6);
     push(&head, 5);
     push(&head, 4);
     push(&head, 3);
     push(&head, 2);
     push(&head, 1);          
 
     printf("\n Given linked list \n");
     printList(head);
     head = reverse(head, 3);
 
     printf("\n Reversed Linked list \n");
     printList(head);
 
     getchar();
     return(0);
}

Time Complexity: O(n) where n is the number of nodes in the given list.

- Algorithmy November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

java version --

/**
      *  Reverses the list - iterative
      *  reverse the list at kth element
      *  Complexity: O(n)
      */
      public Node<AnyType> reverseKthElement(int k)
      {
    	  return head=reverseKthElement(this.head, k);
      }
      
     /**
      *  Reverses the list - iterative
      *  reverse the list at kth element
      *  Complexity: O(n)
      */
      private Node<AnyType> reverseKthElement(Node<AnyType> head, int k)
      {
         Node<AnyType> prev, current, next;
         prev = null;
         next = null;
         current = head;
         int count = 0;
         
         while(current != null && count < k)
         {
      	   next = current.next;
      	   current.next = prev;
      	   prev = current;
      	   current = next;
      	   count++;
         }
         
         if( next != null ){
        	 head.next = reverseKthElement(next, k);
         }
         
         return prev;
      }

- Algorithmy November 11, 2014 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More