Google Interview Question for SDE1s


Team: Google Search
Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 6 vote

This question is carefully described at geeksforgeeks org

Search for an-in-place-algorithm-for-string-transformation there.

Base64 encoded url: aHR0cDovL3d3dy5nZWVrc2ZvcmdlZWtzLm9yZy9hbi1pbi1wbGFjZS1hbGdvcml0aG0tZm9yLXN0cmluZy10cmFuc2Zvcm1hdGlvbi8=

- GK March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 5 votes

Isn't it easier to just paste the URL with some spaces or something?

- Anonymous March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

There is something called cycle leader iteration which can be used for this.
The pre-requisite for this is that the size array should be in 3^k+1 format. If the input array is not of that length then the array need to be broken in multiple subarrays to get this format for all arrays.
Once that is done cycle leader iteration can be applied on each array individually and then merge them to get final output.

- struggler March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 5 vote

Who asked you this at Google? We need to notify the hiring committee of this interviewer.

- S O U N D W A V E March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

Why? Is this task bad or what?

- GK March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 6 votes

Yes it's stupid and useless interview question.
30 min. to invent something while nervous, yet the answers are pointing to published papers.......

- S O U N D W A V E March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are good enough for Google Research (or Google X) though.

Evidenced by the loads of useless non-interview questions you've posted on cc:
careercup.com/user?id=5728613638864896

- S O U N D W A V E March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 votes

Have to agree with BigK.

The question with time and space complexity requirements will be thrown out by the hiring committee.

Without the complexity requirements, it is a decent interview question (permits multiple levels of solutions).

Ayush, if you are preparing for Google interview, I think you are going about it all wrong. Please don't reduce the signal/noise ratio of this site in the process. Thanks.

- Anonymous March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There's actually a solution with the required time and space complexity. It's a tricky task, but it's not impossible or a 'research' problems. Just be careful to consider all the input constraints.

-m

- Anonymous April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The folowing solution is, possibly, the simplest and cheapest (in terms of memory and space) that can be!

The characters in odd positions must be moved to the last half and that's what the solution shown in geeksforgeeks does. However the problem also states that those characters are digits. This is not required for the geeksforgeeks solution to work but using this fact allows a much simpler solution (this one here).

Here is the function:

#include <algorithm>
#include <cassert>
#include <cctype>

void transform(char* const begin, char* const end) {
  assert(begin <= end);
  const unsigned h = (static_cast<unsigned>(end - begin) + 1) / 2;
  for (unsigned i = 1; i < h; ++i) {
    if (std::isdigit(begin[i])) {
      unsigned j = i;
      while ((j = j / 2 + (j % 2) * h) != i)
        std::swap(begin[i], begin[j]);
    }
  }
}

Here is a testing code:

#include <cstring>
#include <iostream>

void transform(char* begin, char* end);

int main() {

  char src[] = "a0b1c2d3e4f5g6h7i8j9k";
  const unsigned n = sizeof(src) / sizeof(char);
  char str[n];

  for (unsigned i = 1; i < n; ++i) {

    std::strcpy(str, src);
    str[i] = 0;

    transform(str, str + i);
    std::cout << str << '\n';
    
    const unsigned half = (i + 1) / 2;
    for (unsigned j = 0; j < half; ++j)
      assert(str[j] == 'a' + static_cast<int>(j) && "Failed!");
    for (unsigned j = half; j < i; ++j)
      assert(str[j] == '0' + static_cast<int>(j - half) && "Failed!");
  }
}

- cassio.neri May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are the letters and numbers relatively ordered as in the examples you gave?

- Eralp Bayraktar March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No they can be ordered in any fashion. No constraint on input.

- Anonymous March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

dude,

in-place-algorithm-for-string-transformation,
it is there in geeksforgeeks.

- rishi March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NumAlpha implements Comparator<String> {

		@Override
		public int compare(String o1, String o2) {
			
			if(o1.matches("\\d") && o2.matches("[a-zA-Z]")) {
				System.out.println("o1" + o1);
				System.out.println("o1" + o2);
				return 1;
			} else if (o2.matches("\\d") && o1.matches("[a-zA-Z]")) {
				return -1;
			}
			else 
				return o1.compareTo(o2);
				
			}
		
		
	}
Test t = new Test();
		NumAlpha na = t.new NumAlpha();
		TreeSet<String> set = new TreeSet<String>(na);
		
		set.add("a");
		set.add("1");
		set.add("b");
		set.add("2");
		set.add("c");
		set.add("3");
		set.add("d");
		set.add("4");
		System.out.println(set.toString());

- Sunny Yadav March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.google.practice;

public class SortItOut {
	public static void main(String[] arg){
		char[] mix = {'a','1','b','2','c','3','d','4'};
		
		sortItOut(mix);
		System.out.println(String.copyValueOf(mix).toString());
	}
	
	//since every alphabet is at odd position, making sure j points to odd location
	// for every swap will ensure the alphabets to be placed before digits.
	public static void sortItOut(char[] mix){
		int skip = 0;
		for(int i=1;i<mix.length;i++){
			int j = i+skip+1;
			if(j>=mix.length)
				skip = 0;
			else{
				char tmp = mix[i];
				mix[i] = mix[j];
				mix[j] = tmp;
				skip++;
			}
		}
	}
}

Need a little help here. I am able to place all alphabets before digits, before the skip is reset. When I apply the same logic again for the numeric part, it isn't working for all inputs. Trying to figure that out, but I think I am almost there.

- AlgoAlgae April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let A be the input char array and N be its size. One can easly verify that the char in position i should go to position

j = i / 2 + (i % 2) * (N / 2 + N % 2).

Using this formula makes very easy to implement a O(n) solution in time and space by copying from A[i] to B[j] where B is an auxiliary array with size N. However, we are constraint to O(1) in space.

We can workaround this limitation in a way that works for this particular problem because the ASCIIs for a-z, A-Z and 0-9 are all in [0, 127] and the range of a char is [-128, 127] (for simplicity, I'm considering a machine where char is signed but a similar argument holds for machines with unsigned char). We can mark A[i] as "dirty" if it's not in the right position by changing it's sign.

Here is the code:

bool is_dirty(char c) {
  if (std::is_signed<char>::value)
    return c < 0;
  else
    return c >= 128;
}

// Toggle c's dirtyness
char toggle(char c) {
  if (std::is_signed<char>::value)
    return -c;
  else
    return c + 128;
}

void transform(char* begin, char* end) {

  const unsigned n = end - begin;

  for (unsigned i = 0; i < n; ++i)
    begin[i] = toggle(begin[i]);

  const unsigned half = n / 2 + n % 2;

  for (unsigned i = 0; i < n; ++i) {

    unsigned j = i;
    char c = begin[j];

    while (is_dirty(c)) {
      j = j / 2 + (j % 2) * half;
      std::swap(c, begin[j]);
      begin[j] = toggle(begin[j]);
    }
  }
}

- cassio.neri April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this solution might works!
The common idea is use only even positions end replace it with index = even_position / 2
For example a1b2c3d4

1) ab12c3d4 n = 2, i = 1 (i+1 = 2, 2==2 then n += 2, i = 0)
2) abc213d4 n = 4, i = 2 (i+1 = 3, 3 < 4 then continue)
3) abc123d4 n = 4, i = 3 (i+1 = 4, 4==4 then n += 2, i = 0)
4) abcd2314 n = 6, i = 3 (i+1 = 4, 4 < 6 then continue)
5) abcd1324 n = 6, i = 4 (i+1 = 5, 5 < 6 then continue)
6) abcd1234 n = 6, i = 5 (i+1 = 6, 6 ==6 then n+=2, n >= stringArray.lengh() then it's over)

private void sort (String[] str) {
    int n = 2;
    int i = 0;
    while (true) {
        String tmpStr;
        
        if (i == 0) {
            i = n / 2;
        }
        
        tmpStr = str[i];
        str[i] = str[n];
        str[n] = tmpStr;
        
        i++;
        if (i == n) {
            n += 2;
            i = 0;
            if (n >= str.length) {
                break;
            } else 
                continue;
            }
        }
    }
}

- Rustam May 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modified my solution, now it looks a little better

private static void sort (String[] str) {
        int n = 2;
        int i = 0;
        while (n < str.length) {
            String tmpStr;

            if (i == 0) {
                i = n / 2;
            }

            tmpStr = str[i];
            str[i] = str[n];
            str[n] = tmpStr;

            i++;
            if (i == n) {
                n += 2;
                i = 0;
            }
        }
    }

- rustam.gaifullin May 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void arrangeLettersAndChars(Character[] chars) {
		int len = chars.length;
		int end = 1 - len % 2;
		for (int i = len - 2; i >= end; i -= 2, end += 2) {
			char temp = chars[i];
			chars[i] = chars[end];
			chars[end] = temp;
		}
	}

- Bhumik September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

recursion is the solution. although recursion uses its own stack but in interviews its considered to be O(1) space

1a 2b 3c 4d 5e
public static void Convert(char [] A, int i)
{
  if(i>=A.length/2) return;
  char b = A[2*i + 1];
  A[i] = A[2*i];
  Convert(A,i+1);
  A[(A.length/2)+i] = b;
}

- aditya.eagle059 February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String rearrange(String str){
        // indexes of str: 0 1 2 3 4 5 6 7
        // indexes of new: 0 2 4 6 1 3 5 7

        // indexes of str: 0 1 2 3 4 5 6 7 8 9
        // indexes of new: 0 2 4 6 8 1 3 5 7 9
        char[] arr =str.toCharArray(); // convert to array of chars
        int lastIndex = arr.length - 1; // last index
        int middle = lastIndex/2;
        int startIndex = 1;
        char startChar = arr[startIndex];
        int currIndex = startIndex;
        int nextIndex ;
        for (int i = 1 ; i < lastIndex; i++){
            if (currIndex <= middle){
                nextIndex = currIndex * 2;
            }else {
                nextIndex = 2 * currIndex - lastIndex;
            }
            if (nextIndex == startIndex){
                arr[currIndex] = startChar;
                if (i < lastIndex){
                    startIndex += 2;
                    startChar = arr[startIndex];
                    currIndex = startIndex;
                    continue;
                }else {
                    break;
                }

            }
            arr[currIndex] = arr[nextIndex];
            currIndex = nextIndex;
        }
        return new String(arr);
    }

    public static void main(String[] a){
        String str = "a1b2c3d4e5f6g7k8l9m0";
        System.out.println(rearrange(str));
        //abcdefgklm1234567890
    }

- Kemo March 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {
	
	public static void main(String args[]){
		String temp = "a1b2c3d4";
		int indexL=2;
		int indexN = 1;
		while(indexL<temp.length()){
			temp = temp.substring(0,indexN)+temp.substring(indexL,indexL+1)+temp.substring(indexN,indexL)+temp.substring(indexL+1,temp.length());
			indexN++;indexL++;indexL++;
		}
		System.out.println(temp);
	}

}

- nitesh.kedia5 March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution works without recursion, in O(n) time and O(1) memory.

It proceeds as follows, by steps

Consider the string "a1b2c3d4e5f6g7h8"
1) Handle groups of 2 -> ab12cd34ef56gh78
2) Handle groups of 4 -> abcd1234efgh5678
3) Handle groups of 8 -> abcdefgh12345678

My code works only for sizes of strings power of 2 and would require some additional code to handle any size but the main idea is there

public static void rearrange( String[] tab ){
		int l = tab.length;
		for( int i = 2 ; i <= log2( l ) ; i++){
			int kmax = (int)Math.floor( l/(Math.pow(2,i))-1/4)-1;
			for( int k = 0 ; k <= kmax ; k++ ){
				for( int j = (int) Math.pow( 2, i-2 ) ; j <  Math.pow( 2, i-1 ) ; j++ ){
					int idx1 = (int) Math.pow( 2, i ) * k + j ;
					int idx2 = (int)(Math.pow( 2, i ) * k + Math.pow( 2, i-2 ) + j);
					if( idx2 < l ){
						swap( tab , idx1 , idx2 );
					}
				}
			}
		}
	}

- antoinedematteo August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void rearange(char[] chrs, int x, int l, int y){
		if(x <= chrs.length){
			char j = chrs[x];
			if(x+1 < chrs.length){
				chrs[l] = chrs[x+1];
			}
			rearange(chrs, x+2, l+1, y+1);
			chrs[y] = j;
			System.out.println(chrs);
		}

}

- Youssef Elhafyani December 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

A Simple In-Place Algorithm for In-Shuffle

- GK March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you expand more.. I guess your technique might disturb the order..

- arsragavan March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think he meant google that phrase...

- Anonymous March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really? How did you get it? :)

- GK March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@GK: You f***ing moron. The comment was directed at the downvoter.

- Anonymous March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If then , I'am really sorry.

- GK March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 5 vote

#include <iostream>
#include <string>

using namespace std;

string str="zzzzzzzzzzzzz999999999999999999";

int main()
{
    cout << str << endl;
    int siz=str.size();
    int i, char_pos=-1, num_pos=-1;
    long long int int_val=0;
    long long int char_val=0;
    for(i=siz-1;i>=0;i--)
    {
        //cout << int(str[i]) << endl;
        if(str[i]>47&&str[i]<58)
        {
            if(num_pos==-1)
            {
                int_val=str[i]-48;
                num_pos=i;
            }
            else
                int_val=int_val*10+(str[i]-48);
            //cout << num_pos << endl;
        }
        else
        {
            if(char_pos==-1)
            {
                char_val=str[i]-97;
                char_pos=i;
            }
            else
                char_val=char_val*26+(str[i]-97);
        }
        //cout << str << endl;
    }
    cout << int_val << endl;
    cout << char_val << endl;
    i=0;
    while(char_val!=0)
    {
        str[i]=char_val%26+97;
        char_val=char_val/26;
        cout << str[i] << endl;
        i++;
    }
    while(int_val!=0)
    {
        str[i]=int_val%10+48;
        int_val=int_val/10;
        cout << str[i] << endl;
        i++;
    }
    cout << str << endl;
}

The above code will only work for maximum of 13 characters and 18 numbers in any combination.
So it would work for 31 size of minimum (of which maximum characters are 13 and maximum numbers are 18). This can be improvised.

- Kartik Reddy March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

For example say array is:
a 2 3 b c 5 d e 4 6

Start traversing from left side of array (0th index)
find the next sequence of numbers and sequence of char and exchange those in case numeric sequence is before char sequence

[Exchange the place of '2 3' to 'b c']
a b c 2 3 5 d e 4 6

apply same logic
[Exchange the place of '2 3' 5 to 'd e']
a b c d e 2 3 5 4 6

- PKT March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Solution written in C++, both recursive and iterative versions. The recursive version also allows tail-call optimization by the compiler.

Output:

x3y4z6 -> xyz346 (iterative)
x3y4z6 -> xyz346 (recursive)
x3y4z6a7 -> xyza3467 (iterative)
x3y4z6a7 -> xyza3467 (recursive)
a1b2c3d4 -> abcd1234 (iterative)
a1b2c3d4 -> abcd1234 (recursive)

Code:

#include <iostream>

static void transform_recursive(std::string& str, size_t pos = 0) {
	if (str.empty())
		return;
	if (str.size() - pos == 2) {
		return;
	}
	if (str.size() - pos == 3) {
		std::swap(str[pos], str[pos+1]);
		return;
	}
    
	size_t mid = (str.size() - pos) / 2;
	for (size_t i = pos + 1, j = 1; i+j < str.size(); ++i, ++j) {
		std::swap(str[i], str[i+j]);
	}
    
    // tail-call recursion, can be optimized by the compiler
	transform_recursive(str, pos + mid);
}

static void transform_iterative(std::string& str) {
	if (str.empty())
		return;
    
    size_t pos = 0;
    while (true) {
        if (str.size() - pos == 2) {
            break;
        }
        if (str.size() - pos == 3) {
            std::swap(str[pos], str[pos+1]);
            break;
        }
        
        size_t mid = (str.size() - pos) / 2;
        for (size_t i = pos + 1, j = 1; i+j < str.size(); ++i, ++j) {
            std::swap(str[i], str[i+j]);
        }
        
        pos += mid;
    }
}

int main() {
	std::string s1_a = "x3y4z6";
    std::cout << s1_a << " -> ";
	transform_iterative(s1_a);
    std::cout << s1_a << " (iterative)" << std::endl;
	std::string s1_b = "x3y4z6";
    std::cout << s1_b << " -> ";
	transform_recursive(s1_b);
    std::cout << s1_b << " (recursive)" << std::endl;
    
	std::string s2_a = "x3y4z6a7";
    std::cout << s2_a << " -> ";
	transform_iterative(s2_a);
    std::cout << s2_a << " (iterative)" << std::endl;
	std::string s2_b = "x3y4z6a7";
    std::cout << s2_b << " -> ";
	transform_recursive(s2_b);
    std::cout << s2_b << " (recursive)" << std::endl;

	std::string s3_a = "a1b2c3d4";
    std::cout << s3_a << " -> ";
	transform_iterative(s3_a);
    std::cout << s3_a << " (iterative)" << std::endl;
	std::string s3_b = "a1b2c3d4";
    std::cout << s3_b << " -> ";
	transform_recursive(s3_b);
    std::cout << s3_b << " (recursive)" << std::endl;
}

- Diego Giagio March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 5 vote

Since the input to be segregated is a String like "a5b6c7d8" we can use String's substring method to hand pick numbers from the string and append them at the end of the string in a single for loop.

Time complexity: O(n)
space complexity: O(1)

Example:

i here denotes the index of the character in the string

i=1 -- input: a5b6c7d8 (Append 5 to the end of string) output: ab6c7d85
i=2 -- input: ab6c7d85 (Append 6 to the end of string) output: abc7d856
i=3 -- input: abc7d856 (Append 7 to the end of string) output: abcd8567
i=4 -- input: abcd8567 (Append 8 to the end of string) output: abcd5678

package stringManipulation;

public class SegregateCharAndNumbers {

	private static String input="a1b2c3d4e5f6g7h8i9j1k2l3m4";

	public static void main(String[] args) {
		System.out.println("String before change = " + input);
		
		for(int i=1; i<input.length()/2+1;i++) {
			input = input.substring(0,i) + input.substring(i+1, input.length()) + input.charAt(i);
		}
		System.out.println("String after change = " + input);
	}
}

- Saurabh March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cool...

- PKT March 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Idiotic.

- Anonymous March 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Time complexity is not O(n) here. Because every time, you are making a new copy of the whole string (Strings are immutable in java. So, every time you use the + operator, a new copy gets created). It's an interesting solution though.

- nasseri.sara March 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I'm making use of the fact that two digits can be stored in a single character using 10*d1 + d2.

static void relocate(char[] arr) {
	int n = arr.length/2;
	char firstDigit = arr[1];

	//Replacing each digit char in 2nd half with INTEGER that combines two
	//consecutive digits as 10*(digit at pos-2) + digit
	//For example, if input is a0b1c2d3e4f5,
	//	char[11]=45,char[9]=23,char[7]=1 (integer equivalent)
	for(int i=2*n-1;i>n;i-=2) {
		arr[i] = (char)((arr[2*i-2*n+1]-'0') + 10*(arr[2*i-2*n-1]-'0'));
	}

	for(int i=1;i<n;i++) {//Move all letters to correct pos
		arr[i]=arr[2*i];
	}
	//From integers constructed above, extract the digits
	for(int i=2*n-1;i>n;i-=2) {
		arr[i-1] = (char)(arr[i]/10 + '0');
		arr[i] = (char)(arr[i]%10 + '0');
	}
	if(n%2 == 1) arr[n] = firstDigit;
}

- Ganesh Ram Sundaram March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Ganesh,
Solution is gud for single digit numbers in the array. But it will not handle numbers with double/triple digits in the series like this:
a10b11c12d13.....

- pavi.8081 March 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <string.h>

void trans(char* a, int size)
{
  if (size <= 2) return;

  for (int i = 1; i <= size - 3; i += 2)
  {
    // swap a[i] and a[i + 1]
    a[i] ^= a[i + 1];
    a[i + 1] ^= a[i];
    a[i] ^= a[i + 1];
  }

  trans(a + 1, size - 2);
}

int main(int argc, char* argv[])
{
  int length = strlen(argv[1]);

  trans(argv[1], length);

  std::cout << argv[1] << "\n";

  return 0;
}

- guest.guest March 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static String inPlaceSeparation(String str) {
		if (str == null || str.length() <= 2) {
			return str;
		}

		char[] arr = str.toCharArray();
		BitSet bs = new BitSet(arr.length);
		for (int head = 1; head < arr.length - 1; ++head) {
			if (bs.get(head)) {
				continue;
			}
			char hValue = arr[head];
			int to = head;
			while (true) {
				int from = to < arr.length / 2 ? to * 2 : 1 + 2 * (to - arr.length / 2);
				if (from == head) {
					arr[to] = hValue;
					bs.set(to);
					break;
				}
				arr[to] = arr[from];
				bs.set(to);
				to = from;
			}
		}
		return new String(arr);
	}

	public static void main(String[] args) {
		String str = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";
		System.out.println(str);
		System.out.println(inPlaceSeparation(str));
	}

- Anonymous March 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Though theoretically, it's not O(1) space complexity (n bits space cost for array of length n), but it minimizes the number of element movement with simple logic.

- Anonymous March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anon: In the word ram model, it is O(1) space.

- Anonymous March 17, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Feedback appreciated

public String fixMe (String a) {

        int l = a.length() ;

        HashMap<Integer,String> m = new HashMap<Integer,String>(1);
        for (int i=0; i < l; i++) 
            if (i%2==0) {
                char g = a.charAt(i);
                if(m.containsKey(0)) 
                    m.put(0,m.get(0)+g);
                else 
                    m.put(0,""+g);
            }

        for (int i=0;i<l;i++) 
            if(i%2 != 0)
                m.put(0, m.get(0)+a.charAt(i));

        return m.get(0);
    }

- SIDHU March 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, my apologies for HashMap, a simple String object would suffice.

public String fixMe (String a) {

        int l = a.length() ;

        String m = new String("");
        for (int i=0; i < l; i++) 
            if (i%2==0) {
                char g = a.charAt(i);
                m = m + g;
            }

        for (int i=0;i<l;i++) 
            if(i%2 != 0)
                m = m + a.charAt(i);

        return m;
    }

- SIDHU March 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isint' this solution good and simple ?

- Vishal March 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think this would be O(n) time and O(1) space. Don't get confused by the fact that it has one loop inside the other, it'd still be O(n).

void swap(string & str, int pos1, int pos2)
{
    char tmp = str[pos1];
    str[pos1] = str[pos2];
    str[pos2] = tmp;
}

void TransformString(string & str)
{
    int letterPointer = (str.size() % 2 == 0) ? str.size() - 2 : str.size() - 1;
    int count = 1;
    int numPointer = letterPointer - count;
    while (numPointer > 0)
    {
        while (numPointer < letterPointer)
        {
            swap(str, numPointer, numPointer + 1);
            numPointer++;
        }
        letterPointer--;
        count++;
        numPointer = letterPointer - count;
    }
}

- edb April 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>

void changeString(char *string1)
{

	int start;
	int end;

	// get string size

	int stringSize = 0;
	while(string1[stringSize] != '\0')
	{
		stringSize += 1;
	}

	start = 1;
	end = stringSize - 2;

	while(start < end)
	{
	
		for(int i = start; i <= end; i += 2)
		{
		
			int temp = string1[i];
			string1[i] = string1[i + 1];
			string1[i + 1] = temp;

		}

		start += 1;
		end -= 1;
	
	}

}

int main(void)
{

	char string1[100];

	printf("Enter Input: ");
	scanf("%s", string1);

	changeString(string1);

	printf("%s\n", string1);

	return 0;

}

- Alejandro Gonzalez P April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>

void changeString(char *string1)
{

	int start;
	int end;

	// get string size

	int stringSize = 0;
	while(string1[stringSize] != '\0')
	{
		stringSize += 1;
	}

	start = 1;
	end = stringSize - 2;

	while(start < end)
	{
	
		for(int i = start; i <= end; i += 2)
		{
		
			int temp = string1[i];
			string1[i] = string1[i + 1];
			string1[i + 1] = temp;

		}

		start += 1;
		end -= 1;
	
	}

}

int main(void)
{

	char string1[100];

	printf("Enter Input: ");
	scanf("%s", string1);

	changeString(string1);

	printf("%s\n", string1);

	return 0;

}

- Alejandro Gonzalez P April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

char *hopFlipSttring(char *input)
{
    int i, s1 = 0, s2 = 0;
    char *result;
    
    result = malloc(strlen(input)+1);
    s1 = 0;
    s2 = (int)strlen(input)/2;
    
    for( i = 0; i < strlen(input); i += 2 ) {
        result[s1++] = input[i];
        result[s2++] = input[i+1];
    }
    result[i] = '\n';
    
    return result;
}

- Chris March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

import java.util.Scanner;


public class Test {
Scanner x=new Scanner(System.in);
String s;
public static void main(String[] args) {
Test t=new Test();
t.get();
}
private void get()
{
StringBuilder builder1 = new StringBuilder();
StringBuilder builder2 = new StringBuilder();
s=x.next();
String tempChar[]=s.split("[0-9]");
String tempNum[]=s.split("[a-z]");
int i=0,j=0;
while(i<tempChar.length||j<tempNum.length)
{
if(i<tempChar.length)
{
builder1.append(tempChar[i++]);
}

else if(j<tempNum.length)
{
builder2.append(tempNum[j++]);
}

}

System.out.println(String.valueOf(builder1)+String.valueOf(builder2));
}
}

- Aman Raj March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is wrong with this solution?? space complexity?? can anyone explain me please?

- Aman Raj March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes exactly...the space complexity is a problem. O(1) should be the space complexity.

- nihanth March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

just use String instead of String builder ... space allocated for str='ab' and str ='abcd' is the same, in your case your space will be o(2) for the two strings which is the same as 0(1)

public class IsolateCharInt {
  String val = "";
  public IsolateCharInt(String val) {
	  this.val = val;
  }
   String printIn() {
	  
	 String nums = "";
	 String chars = "";
	 
	 for(int i=0 ; i<val.length(); i++) {
		 if((i % 2) == 0) {
			nums += val.charAt(i);
		 }else
			 chars += val.charAt(i);
	 }
	 val = nums + chars;
	 return val;
  }
 
  public static void main(String[] args) {
	IsolateCharInt i = new IsolateCharInt("1a2b3c4");
	System.out.println(i.printIn());
	
}
  
}

- estif April 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